TSQL-Tasks: января 2015

Данная статья является заключительной частью цикла работ, посвященных изучению понятия индекса графа. Для ее понимания требуются знания из двух предыдущих работ (Индекс графа. Часть 1. Логическая архитектура (гипердеревья, фундаментальная группа)., Индекс графа. Часть 2. Физическая архитектура.).

Протестируем алгоритм поиска маршрутов на больших объемах. Создадим такое же дерево как и при тестировании традиционного способа поиска маршрутов. То есть построим тернарное дерево, состоящее из 18 уровней. Для решения задачи выполним такой скрипт:

declare @maxLevel int = 18, @curLevel int = 1, @num int

while @curLevel <= @maxLevel

begin

if @curLevel = 0

begin

insert into dbo.HyperTrees ( LevelId, VerParId, IsRoot, VerRootId, EdgeId, VerStartEdgeId, VerEndEdgeId )

values ( 1, null, 1, null, null, null, null )

end

set @num = power ( 3, @curLevel )

insert into dbo.HyperTrees with ( tablock ) ( LevelId, VerParId, IsRoot, VerRootId, EdgeId, VerStartEdgeId, VerEndEdgeId )

select 1,

(

( data.num + ( @num - 3 ) / 2 ) - 1

) / 3,

0, null, null, null, null

from

(

select top ( power ( 3, @curLevel ) ) row_number () over ( order by ( select 1 ) ) as num

from

master.dbo.spt_values val1

cross join

master.dbo.spt_values val2

cross join

master.dbo.spt_values val3

) data

set @curLevel += 1

end

Код работал около 12 часов, объем данных в таблице составил 52 Гб. Запустим такой запрос:

declare @dt1 datetime2 = sysdatetime ()

exec dbo.FindPath 200000000, 400000000

declare @dt2 datetime2 = sysdatetime ()

select datediff ( [ms], @dt1, @dt2 )

Код работает 40 миллисекунд, возвращая маршрут из 37 вершин! Проверим теперь как работает процедура в ситуации, когда есть несколько соединений, выполняющие поиск маршрутов в большом графе. Запустим следующий код одновременно в 10 соединениях:

waitfor time '21:40:00'

declare @dt1 datetime2 = sysdatetime ()

exec dbo.FindPath 200000000, 400000000

declare @dt2 datetime2 = sysdatetime ()

select datediff ( [ms], @dt1, @dt2 )

Время работы кода в миллисекундах во всех этих соединениях:

1) 561; 2) 550; 3) 600; 4) 86; 5) 415; 6) 451; 7) 559; 8) 430; 9) 402; 10) 584.

Проверим удаление ребер. Попробуем удалить ребро, которое находится близко к листовому уровню дерева:

begin tran

declare @dt1 datetime2 = sysdatetime ()

exec dbo.DeleteEdge 400000000, 134666666

declare @dt2 datetime2 = sysdatetime ()

select datediff ( [ms], @dt1, @dt2 )

rollback tran

Такой код работает на горячем кэше всего 6 миллисекунд ()на холодном кэше время выполнения 0.9 секунды. Если предпринять попытку удаления ребра на уровне, близком к корню, то время выполнения может увеличиться, так как процедуре потребуется проверять наличие ребер соединяющих вершины их двух больших поддеревьев. Чтобы этого избежать, можно в процедуре удаления ребра по другому искать внешнее ребро, соединяющее два дерева. Вместо соединения вершин на таблицу с внешними ребрами, можно найти корни для концов внешних ребер и сравнить их с корнями тех деревьев, для которых мы ищем ребро.

Посмотрим как можно построить индекс графа. Допустим имеется таблица dbo.Edges, которая рассматривалась в первой части. Требуется наполнить таблицы dbo.HyperTrees, dbo.ExtEdges, dbo.EdgesRel данными, которые бы составляли индекс графа, который хранится в dbo.Edges. Мы напишем хранимую процедуру, которая построит индекс графа. Идея алгоритма процедуры состоит в том, чтобы организовать цикл по компонентам связности графа. На каждой итерации необходимо выбрать произвольную вершину и рассматривать ее как корень. Построить дерево и добавить в таблицу внешних ребер все ребра, не входящие в построенное дерево. Данная процедура является одновременно и процедурой создания и процедурой перестройки индекса графа.

if object_id ( N'dbo.IndexGraphsRebuild', N'P' ) is null

exec ( N'create proc dbo.IndexGraphsRebuild as return' )

alter proc dbo.IndexGraphsRebuild

begin

set nocount, xact_abort on

declare @VerId int, @LevCount int, @Component int = 0, @LevelTree int, @ErrMsg varchar ( max ), @NewVerId int

set identity_insert Graphs.dbo.HyperTrees on

begin try

dbcc traceon ( 610 )

if objecT_id ( N'tempdb..#EdgesRel', N'U' ) is not null

drop table #EdgesRel

create table #EdgesRel

(

LevelTree int not null,

Component int not null,

VerIniId int not null,

VerId int not null,

primary key clustered ( Component asc, LevelTree asc, VerIniId asc, VerId asc ) on [PRIMARY]

) on [PRIMARY]

if object_id ( N'tempdb..#HyperTrees_Tmp', N'U' ) is not null

drop table #HyperTrees_Tmp

create table #HyperTrees_Tmp

(

LevelTree int not null,

Component int not null,

LevelId int not null,

VerId int identity ( 1, 1 ) not null,

VerParId int not null,

IsRoot int not null,

constraint PK_Tmp primary key clustered ( Component asc, LevelTree asc, VerId asc ) on [PRIMARY],

constraint AK_Tmp_Component unique nonclustered ( Component asc, VerId asc ) on [PRIMARY],

constraint AK_Tmp_VerId unique nonclustered ( VerId, VerParId asc ) on [PRIMARY],

constraint AK_Tmp_VerParId unique nonclustered ( VerParId, VerId asc ) on [PRIMARY]

) on [PRIMARY]

select top 1 @VerId = StartId

from dbo.Edges

while @VerId is not null

begin

set @VerId = (

select top 1 edge.StartId

from dbo.Edges edge

where not exists

(

select VerId

from #HyperTrees_Tmp tr

where tr.VerId = edge.StartId

)

if @VerId is null

begin

break

end

else

begin

set @LevelTree = 1

set @Component += 1

insert into #HyperTrees_Tmp

(

LevelTree,

Component,

LevelId,

VerParId,

IsRoot

)

values

(

@LevelTree,

@Component,

null,

)

set @NewVerId = scope_identity ()

insert into #EdgesRel

(

LevelTree,

Component,

VerIniId,

VerId

)

values

(

@LevelTree,

@Component,

@NewVerId,

@VerId

)

end

set @LevCount = 1

while @LevCount <> 0

begin

set @LevelTree += 1

merge #HyperTrees_Tmp with ( tablock ) as trg

using

(

select @LevelTree LevelTree, @Component Component, 1 LevelId, max ( tr.VerId ) VerParId, 0 IsRoot, edge.EndId

from

#HyperTrees_Tmp tr

inner join

#EdgesRel rel on

tr.Component = rel.Component and

tr.LevelTree = rel.LevelTree and

tr.VerId = rel.VerIniId

inner join

dbo.Edges edge on rel.VerId = edge.StartId

where

tr.LevelTree = @LevelTree and

tr.Component = @Component and

not exists

(

select *

from #HyperTrees_Tmp trIn

where

trIn.Component = @Component and

trIn.VerId = edge.EndId

)

group by edge.EndId

) as src on 1 = 0

when not matched then insert

(

LevelTree,

Component,

LevelId,

VerParId,

IsRoot

)

values

(

src.LevelTree,

src.Component,

src.LevelId,

src.VerParId,

src.IsRoot

)

output

src.LevelTree,

src.Component,

src.EndId,

inserted.VerId

into #EdgesRel

(

LevelTree,

Component,

VerIniId,

VerId

)

;

set @LevCount = @@rowcount

merge #HyperTrees_Tmp with ( tablock ) as trg

using

(

select @LevelTree LevelTree, @Component Component, 1 LevelId, max ( tr.VerId ) VerParId, 0 IsRoot, edge.StartId

from

#HyperTrees_Tmp tr

inner join

#EdgesRel rel on

tr.Component = rel.Component and

tr.LevelTree = rel.LevelTree and

tr.VerId = rel.VerIniId

inner join

dbo.Edges edge on rel.VerId = edge.EndId

where

tr.LevelTree = @LevelTree and

tr.Component = @Component and

not exists

(

select *

from #HyperTrees_Tmp trIn

where

trIn.Component = @Component and

trIn.VerId = edge.StartId

)

group by edge.EndId

) as src on 1 = 0

when not matched then insert

(

LevelTree,

Component,

LevelId,

VerParId,

IsRoot

)

values

(

src.LevelTree,

src.Component,

src.LevelId,

src.VerParId,

src.IsRoot

)

output

src.LevelTree,

src.Component,

src.StartId,

inserted.VerId

into #EdgesRel

(

LevelTree,

Component,

VerIniId,

VerId

)

;

set @LevCount += @@rowcount

end

begin tran

truncate table Graphs.dbo.HyperTrees

truncate table Graphs.dbo.ExtEdge

truncate table Graphs.dbo.EdgesRel

insert into Graphs.dbo.EdgesRel with ( tablock )

(

VerIniId,

VerId

)

select

VerIniId,

VerId

from #EdgesRel

insert into Graphs.dbo.HyperTrees with ( tablock )

(

LevelId,

VerId,

VerParId,

IsRoot

)

select

LevelId,

VerId,

VerParId,

IsRoot

from #HyperTrees_Tmp

insert into Graphs.dbo.ExtEdges with ( tablock ) ( StartId, EndId )

select edge.StartId, edge.EndId

from

dbo.Edges edge

inner join

Graphs.dbo.EdgesRel relst on edge.StartId = relst.VerIniId

inner join

Graphs.dbo.EdgesRel relen on edge.EndId = relen.VerIniId

left outer join

Graphs.dbo.HyperTrees st on

relst.VerId = st.VerId and

relen.VerId = st.VerParId

left outer join

Graphs.dbo.HyperTrees en on

relst.VerId = en.VerParId and

relst.VerId = en.VerId

where st.VerId is null and en.VerId is null

commit tran

end try

begin catch

set @ErrMsg = 'Ошибка. Строка: ' + isnull ( cast ( error_line () as varchar ( 100 ) ), 'неизвестно' ) +

'. Номер: ' + isnull ( cast ( error_number () as varchar ( 100 ) ), 'неизвестно' ) +

'. Описание: ' + isnull ( error_message (), 'неизвестно' )

end catch

set identity_insert Graphs.dbo.HyperTrees off

if isnull ( @ErrMsg, '' ) <> ''

begin

; throw 50000, @ErrMsg, 1

end

Процедура реализует описанный выше алгоритм. При вставке данных в промежуточную таблицу необходимо делать группировку по добавляемым вершинам, поскольку несколько маршрутов из выбранного корня могут вести к одной вершине. При наполнении временной таблицы #HyperTrees_Tmp делается merge для того, чтобы в предложении output была возможность запомнить и новое идентификационное значение и идентификатор вершины из таблицы dbo.Edges. Подробнее об это можно прочитать в статье этого блога: Интересное применение оператора merge и функции output.

В самом начале процедуры включается 610-ый флаг трассировки, который появился в MS SQL 2008. Он задает минимальное протоколирование при вставке. То есть при аллокации новой страницы, в журнале транзакций записывается только ее параметры, но не сами строки. Поскольку в конце делается вставка в таблицу dbo.HyperTrees, которая предварительно очищается, и модель восстановления для базы данных Graphs является простой, то включение этого флага значительно повысит производительность на больших объемах.
Последняя вставка добавляет в таблицу dbo.ExtEdges внешние ребра, которые не входят в связное поддерево. Как я упоминал в первой части, вместе с таблицей dbo.Edges можно хранить таблицу для изолированных вершин. Тогда в процедуре необходимо IndexGraphsRebuild необходимо в конце делать дополнительную вставку этих вершин в dbo.HyperTress. Поле VerParId инициализировалось бы для них пустым значением.

При работе данной процедуры, необходимо чтобы никто не добавлял и не удалял вершин и ребер, то есть чтобы не было обновлений в таблице dbo.Edges.

TSQL-Tasks

Страницы

Страницы

вторник, 27 января 2015 г.

Индекс графа. Часть 3. Тесты на производительность, дефрагментация индекса графа.

Страницы

Страницы

вторник, 27 января 2015 г.

Индекс графа. Часть 3. Тесты на производительность, дефрагментация индекса графа.

вторник, 27 января 2015 г.