Ten problem dotyczy podążania za linkami między elementami. To umieszcza go w dziedzinie grafów i przetwarzania grafów. W szczególności cały zestaw danych tworzy wykres i szukamy składników tego wykresu. Można to zilustrować wykresem przykładowych danych z pytania.
Pytanie mówi, że możemy śledzić GroupKey lub RecordKey, aby znaleźć inne wiersze o tej samej wartości. Możemy więc traktować oba jako wierzchołki na wykresie. Pytanie wyjaśnia, w jaki sposób GroupKeys 1–3 mają ten sam SupergroupKey. Można to postrzegać jako skupisko po lewej połączone cienkimi liniami. Zdjęcie pokazuje również dwa inne komponenty (SupergroupKey) utworzone przez oryginalne dane.
SQL Server ma wbudowane możliwości przetwarzania grafów w T-SQL. W tej chwili jest to jednak dość skąpe i nie pomaga w rozwiązaniu tego problemu. SQL Server ma również możliwość wywoływania R i Pythona oraz bogatego i solidnego pakietu dostępnych dla nich pakietów. Jednym z nich jest Igraph . Jest napisany z myślą o „szybkiej obsłudze dużych wykresów z milionami wierzchołków i krawędzi ( link )”.
Używając R i igraph byłem w stanie przetworzyć milion wierszy w ciągu 2 minut 22 sekund w testach lokalnych 1 . Oto porównanie z obecnym najlepszym rozwiązaniem:
Record Keys Paul White R
------------ ---------- --------
Per question 15ms ~220ms
100 80ms ~270ms
1,000 250ms 430ms
10,000 1.4s 1.7s
100,000 14s 14s
1M 2m29 2m22s
1M n/a 1m40 process only, no display
The first column is the number of distinct RecordKey values. The number of rows
in the table will be 8 x this number.
Podczas przetwarzania 1M wierszy zastosowano 1m40s do załadowania i przetworzenia wykresu oraz do aktualizacji tabeli. 42s były wymagane do zapełnienia tabeli wyników SSMS danymi wyjściowymi.
Obserwacja Menedżera zadań podczas przetwarzania 1M wierszy sugeruje, że wymagane było około 3 GB pamięci roboczej. To było dostępne w tym systemie bez stronicowania.
Mogę potwierdzić ocenę Ypercube dotyczącą rekurencyjnego podejścia CTE. Przy kilkuset kluczach zapisu zużywał 100% procesora i całą dostępną pamięć RAM. Ostatecznie tempdb wzrosło do ponad 80 GB i SPID się zawiesił.
Użyłem tabeli Paula z kolumną SupergroupKey, więc istnieje sprawiedliwe porównanie między rozwiązaniami.
Z jakiegoś powodu R sprzeciwił się akcentowi na Poincaré. Zmiana na zwykłe „e” pozwoliła na uruchomienie. Nie badałem, ponieważ nie ma on istotnego wpływu na omawiany problem. Jestem pewien, że istnieje rozwiązanie.
Oto kod
-- This captures the output from R so the base table can be updated.
drop table if exists #Results;
create table #Results
(
Component int not NULL,
Vertex varchar(12) not NULL primary key
);
truncate table #Results; -- facilitates re-execution
declare @Start time = sysdatetimeoffset(); -- for a 'total elapsed' calculation.
insert #Results(Component, Vertex)
exec sp_execute_external_script
@language = N'R',
@input_data_1 = N'select GroupKey, RecordKey from dbo.Example',
@script = N'
library(igraph)
df.g <- graph.data.frame(d = InputDataSet, directed = FALSE)
cpts <- components(df.g, mode = c("weak"))
OutputDataSet <- data.frame(cpts$membership)
OutputDataSet$VertexName <- V(df.g)$name
';
-- Write SuperGroupKey to the base table, as other solutions do
update e
set
SupergroupKey = r.Component
from dbo.Example as e
inner join #Results as r
on r.Vertex = e.RecordKey;
-- Return all rows, as other solutions do
select
e.SupergroupKey,
e.GroupKey,
e.RecordKey
from dbo.Example as e;
-- Calculate the elapsed
declare @End time = sysdatetimeoffset();
select Elapse_ms = DATEDIFF(MILLISECOND, @Start, @End);
Tak właśnie działa kod R.
@input_data_1 jest to, w jaki sposób SQL Server przesyła dane z tabeli do kodu R i tłumaczy je na ramkę danych R o nazwie InputDataSet.
library(igraph) importuje bibliotekę do środowiska wykonawczego R.
df.g <- graph.data.frame(d = InputDataSet, directed = FALSE)załadować dane do obiektu igraph. To jest nieukierunkowany wykres, ponieważ możemy podążać za linkami z grupy do zapisu lub zapisu do grupy. InputDataSet to domyślna nazwa programu SQL Server dla zestawu danych wysłanego do R.
cpts <- components(df.g, mode = c("weak")) przetwarza wykres, aby znaleźć dyskretne podgrupy (komponenty) i inne miary.
OutputDataSet <- data.frame(cpts$membership)SQL Server oczekuje ramki danych z powrotem od R. Jego domyślna nazwa to OutputDataSet. Komponenty są przechowywane w wektorze zwanym „członkostwem”. Ta instrukcja przekształca wektor w ramkę danych.
OutputDataSet$VertexName <- V(df.g)$nameV () to wektor wierzchołków na wykresie - lista kluczy GroupKeys i RecordKeys. Spowoduje to skopiowanie ich do ramki danych wyjściowych, tworząc nową kolumnę o nazwie VertexName. Jest to klucz używany do dopasowania do tabeli źródłowej do aktualizacji SupergroupKey.
Nie jestem ekspertem od R. Prawdopodobnie można to zoptymalizować.
Dane testowe
Dane PO zostały wykorzystane do walidacji. Do testów skali użyłem następującego skryptu.
drop table if exists Records;
drop table if exists Groups;
create table Groups(GroupKey int NOT NULL primary key);
create table Records(RecordKey varchar(12) NOT NULL primary key);
go
set nocount on;
-- Set @RecordCount to the number of distinct RecordKey values desired.
-- The number of rows in dbo.Example will be 8 * @RecordCount.
declare @RecordCount int = 1000000;
-- @Multiplier was determined by experiment.
-- It gives the OP's "8 RecordKeys per GroupKey and 4 GroupKeys per RecordKey"
-- and allows for clashes of the chosen random values.
declare @Multiplier numeric(4, 2) = 2.7;
-- The number of groups required to reproduce the OP's distribution.
declare @GroupCount int = FLOOR(@RecordCount * @Multiplier);
-- This is a poor man's numbers table.
insert Groups(GroupKey)
select top(@GroupCount)
ROW_NUMBER() over (order by (select NULL))
from sys.objects as a
cross join sys.objects as b
--cross join sys.objects as c -- include if needed
declare @c int = 0
while @c < @RecordCount
begin
-- Can't use a set-based method since RAND() gives the same value for all rows.
-- There are better ways to do this, but it works well enough.
-- RecordKeys will be 10 letters, a-z.
insert Records(RecordKey)
select
CHAR(97 + (26*RAND())) +
CHAR(97 + (26*RAND())) +
CHAR(97 + (26*RAND())) +
CHAR(97 + (26*RAND())) +
CHAR(97 + (26*RAND())) +
CHAR(97 + (26*RAND())) +
CHAR(97 + (26*RAND())) +
CHAR(97 + (26*RAND())) +
CHAR(97 + (26*RAND())) +
CHAR(97 + (26*RAND()));
set @c += 1;
end
-- Process each RecordKey in alphabetical order.
-- For each choose 8 GroupKeys to pair with it.
declare @RecordKey varchar(12) = '';
declare @Groups table (GroupKey int not null);
truncate table dbo.Example;
select top(1) @RecordKey = RecordKey
from Records
where RecordKey > @RecordKey
order by RecordKey;
while @@ROWCOUNT > 0
begin
print @Recordkey;
delete @Groups;
insert @Groups(GroupKey)
select distinct C
from
(
-- Hard-code * from OP's statistics
select FLOOR(RAND() * @GroupCount)
union all
select FLOOR(RAND() * @GroupCount)
union all
select FLOOR(RAND() * @GroupCount)
union all
select FLOOR(RAND() * @GroupCount)
union all
select FLOOR(RAND() * @GroupCount)
union all
select FLOOR(RAND() * @GroupCount)
union all
select FLOOR(RAND() * @GroupCount)
union all
select FLOOR(RAND() * @GroupCount)
) as T(C);
insert dbo.Example(GroupKey, RecordKey)
select
GroupKey, @RecordKey
from @Groups;
select top(1) @RecordKey = RecordKey
from Records
where RecordKey > @RecordKey
order by RecordKey;
end
-- Rebuild the indexes to have a consistent environment
alter index iExample on dbo.Example rebuild partition = all
WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF,
ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON);
-- Check what we ended up with:
select COUNT(*) from dbo.Example; -- Should be @RecordCount * 8
-- Often a little less due to random clashes
select
ByGroup = AVG(C)
from
(
select CONVERT(float, COUNT(1) over(partition by GroupKey))
from dbo.Example
) as T(C);
select
ByRecord = AVG(C)
from
(
select CONVERT(float, COUNT(1) over(partition by RecordKey))
from dbo.Example
) as T(C);
Właśnie zdałem sobie sprawę, że źle zrozumiałem współczynniki z definicji PO. Nie wierzę, że wpłynie to na czasy. Rekordy i grupy są symetryczne dla tego procesu. Według algorytmu wszystkie są tylko węzłami na wykresie.
Podczas testowania dane niezmiennie tworzyły pojedynczy komponent. Uważam, że jest to spowodowane jednolitym rozkładem danych. Gdyby zamiast statycznego stosunku 1: 8 zakodowanego na stałe w procedurze generowania pozwoliłbym na zmianę tego stosunku , bardziej prawdopodobne byłyby dalsze elementy.
1 Specyfikacja komputera: Microsoft SQL Server 2017 (RTM-CU12), Developer Edition (64-bit), Windows 10 Home. 16 GB pamięci RAM, dysk SSD, 4-rdzeniowy hyperthreaded i7, 2,8 GHz nominalnie. Testy były jedynymi działającymi w tym czasie elementami, innymi niż normalna aktywność systemu (około 4% procesora).
