Optymalizacja przeszukiwania zakresu liczbowego (interwału) w SQL Server

To pytanie jest podobne do optymalizacji wyszukiwania zakresu adresów IP? ale ten jest ograniczony do SQL Server 2000.

Załóżmy, że mam 10 milionów zakresów tymczasowo zapisanych w tabeli o strukturze i wypełnionej jak poniżej.

CREATE TABLE MyTable
(
Id        INT IDENTITY PRIMARY KEY,
RangeFrom INT NOT NULL,
RangeTo   INT NOT NULL,
CHECK (RangeTo > RangeFrom),
INDEX IX1 (RangeFrom,RangeTo),
INDEX IX2 (RangeTo,RangeFrom)
);

WITH RandomNumbers
     AS (SELECT TOP 10000000 ABS(CRYPT_GEN_RANDOM(4)%100000000) AS Num
         FROM   sys.all_objects o1,
                sys.all_objects o2,
                sys.all_objects o3,
                sys.all_objects o4)
INSERT INTO MyTable
            (RangeFrom,
             RangeTo)
SELECT Num,
       Num + 1 + CRYPT_GEN_RANDOM(1)
FROM   RandomNumbers 

Muszę znać wszystkie zakresy zawierające wartość 50,000,000. Próbuję następujące zapytanie

SELECT *
FROM MyTable
WHERE 50000000 BETWEEN RangeFrom AND RangeTo

SQL Server pokazuje, że było 10 951 odczytów logicznych i odczytano prawie 5 milionów wierszy, aby zwrócić 12 pasujących.

Czy mogę poprawić tę wydajność? Każda restrukturyzacja tabeli lub dodatkowych indeksów jest w porządku.

Columnstore jest tutaj bardzo pomocny w porównaniu do nieklastrowanego indeksu, który skanuje połowę tabeli. Niesklastrowany indeks magazynu kolumn zapewnia większość korzyści, ale wstawianie uporządkowanych danych do klastrowego indeksu magazynu kolumn jest jeszcze lepsze.

DROP TABLE IF EXISTS dbo.MyTableCCI;

CREATE TABLE dbo.MyTableCCI
(
Id        INT PRIMARY KEY,
RangeFrom INT NOT NULL,
RangeTo   INT NOT NULL,
CHECK (RangeTo > RangeFrom),
INDEX CCI CLUSTERED COLUMNSTORE
);

INSERT INTO dbo.MyTableCCI
SELECT TOP (987654321) *
FROM dbo.MyTable
ORDER BY RangeFrom ASC
OPTION (MAXDOP 1);

Z założenia mogę uzyskać eliminację grupy wierszy w RangeFromkolumnie, co wyeliminuje połowę moich grup wierszy. Ale ze względu na charakter danych również eliminuję grupę wierszy w RangeTokolumnie:

Table 'MyTableCCI'. Segment reads 1, segment skipped 9.

W przypadku większych tabel z większą liczbą zmiennych danych istnieją różne sposoby ładowania danych, aby zagwarantować najlepszą możliwą eliminację grup wierszy w obu kolumnach. W szczególności dla danych zapytanie zajmuje 1 ms.

Paul White wskazał odpowiedź na podobne pytanie zawierające link do interesującego artykułu Itzika Bena Gana . Opisuje to model „statycznego drzewa relacji relacyjnych”, który pozwala to zrobić skutecznie.

Podsumowując, podejście to polega na przechowywaniu wartości obliczonej („forknode”) na podstawie wartości przedziału w wierszu. Podczas wyszukiwania zakresów, które przecinają inny zakres, można wstępnie obliczyć możliwe wartości forknode, które muszą mieć pasujące wiersze, i użyć tego do znalezienia wyników z maksymalnie 31 operacjami wyszukiwania (poniżej obsługuje liczby całkowite z zakresu od 0 do maksimum ze znakiem 32 bit int)

Na tej podstawie zrestrukturyzowałem tabelę jak poniżej.

CREATE TABLE dbo.MyTable3
(
  Id        INT IDENTITY PRIMARY KEY,
  RangeFrom INT NOT NULL,
  RangeTo   INT NOT NULL,   
  node  AS RangeTo - RangeTo % POWER(2, FLOOR(LOG((RangeFrom - 1) ^ RangeTo, 2))) PERSISTED NOT NULL,
  CHECK (RangeTo > RangeFrom)
);

CREATE INDEX ix1 ON dbo.MyTable3 (node, RangeFrom) INCLUDE (RangeTo);
CREATE INDEX ix2 ON dbo.MyTable3 (node, RangeTo) INCLUDE (RangeFrom);

SET IDENTITY_INSERT MyTable3 ON

INSERT INTO MyTable3
            (Id,
             RangeFrom,
             RangeTo)
SELECT Id,
       RangeFrom,
       RangeTo
FROM   MyTable

SET IDENTITY_INSERT MyTable3 OFF 

A potem użyłem następującego zapytania (artykuł szuka przecinających się przedziałów, więc znalezienie przedziału zawierającego punkt jest zdegenerowanym przypadkiem)

DECLARE @value INT = 50000000;

;WITH N AS
(
SELECT 30 AS Level, 
       CASE WHEN @value > POWER(2,30) THEN POWER(2,30) END AS selected_left_node, 
       CASE WHEN @value < POWER(2,30) THEN POWER(2,30) END AS selected_right_node, 
       (SIGN(@value - POWER(2,30)) * POWER(2,29)) + POWER(2,30)  AS node
UNION ALL
SELECT N.Level-1,   
       CASE WHEN @value > node THEN node END AS selected_left_node,  
       CASE WHEN @value < node THEN node END AS selected_right_node,
       (SIGN(@value - node) * POWER(2,N.Level-2)) + node  AS node
FROM N 
WHERE N.Level > 0
)
SELECT I.id, I.RangeFrom, I.RangeTo
FROM dbo.MyTable3 AS I
  JOIN N AS L
    ON I.node = L.selected_left_node
    AND I.RangeTo >= @value
    AND L.selected_left_node IS NOT NULL
UNION ALL
SELECT I.id, I.RangeFrom, I.RangeTo
FROM dbo.MyTable3 AS I
  JOIN N AS R
    ON I.node = R.selected_right_node
    AND I.RangeFrom <= @value
    AND R.selected_right_node IS NOT NULL
UNION ALL
SELECT I.id, I.RangeFrom, I.RangeTo
FROM dbo.MyTable3 AS I
WHERE node = @value;

Zwykle wykonuje się to 1msna moim komputerze, gdy wszystkie strony są w pamięci podręcznej - ze statystykami IO.

Table 'MyTable3'. Scan count 24, logical reads 72, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 4, logical reads 374, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

i plan

NB: Źródło używa wielopłaszczyznowych TVF zamiast rekurencyjnych CTE, aby zachęcić węzły do ​​przyłączenia się, ale w interesie uczynienia mojej odpowiedzi samodzielną zdecydowałem się na to drugie. Do użytku produkcyjnego prawdopodobnie użyłbym TVF.

Udało mi się znaleźć podejście w trybie wiersza, które jest konkurencyjne w stosunku do podejścia N / CCI, ale musisz wiedzieć coś o swoich danych. Załóżmy, że masz kolumnę, która zawierała różnicę RangeFromi RangeToi indeksowane go razem z RangeFrom:

ALTER TABLE dbo.MyTableWithDiff ADD DiffOfColumns AS RangeTo-RangeFrom;

CREATE INDEX IXDIFF ON dbo.MyTableWithDiff (DiffOfColumns,RangeFrom) INCLUDE (RangeTo);

Jeśli znasz wszystkie odrębne wartości, DiffOfColumnsmożesz wykonać wyszukiwanie każdej wartości DiffOfColumnsz włączonym filtrem zakresu, RangeToaby uzyskać wszystkie odpowiednie dane. Na przykład, jeśli wiemy, że DiffOfColumns= 2, wówczas jedynymi dozwolonymi wartościami RangeFromsą 49999998, 49999999 i 50000000. Rekurencja może być użyta do uzyskania wszystkich odrębnych wartości DiffOfColumnsi działa dobrze dla twojego zestawu danych, ponieważ jest ich tylko 256. Poniższe zapytanie zajmuje około 6 ms na moim komputerze:

WITH RecursiveCTE
AS
(
    -- Anchor
    SELECT TOP (1)
        DiffOfColumns
    FROM dbo.MyTableWithDiff AS T
    ORDER BY
        T.DiffOfColumns

    UNION ALL

    -- Recursive
    SELECT R.DiffOfColumns
    FROM
    (
        -- Number the rows
        SELECT 
            T.DiffOfColumns,
            rn = ROW_NUMBER() OVER (
                ORDER BY T.DiffOfColumns)
        FROM dbo.MyTableWithDiff AS T
        JOIN RecursiveCTE AS R
            ON R.DiffOfColumns < T.DiffOfColumns
    ) AS R
    WHERE
        -- Only the row that sorts lowest
        R.rn = 1
)
SELECT ca.*
FROM RecursiveCTE rcte
CROSS APPLY (
    SELECT mt.Id, mt.RangeFrom, mt.RangeTo
    FROM dbo.MyTableWithDiff mt
    WHERE mt.DiffOfColumns = rcte.DiffOfColumns
    AND mt.RangeFrom >= 50000000 - rcte.DiffOfColumns AND mt.RangeFrom <= 50000000
) ca
OPTION (MAXRECURSION 0);

Możesz zobaczyć zwykłą część rekurencyjną wraz z wyszukiwaniem indeksu dla każdej odrębnej wartości:

Wadą tego podejścia jest to, że zaczyna zwalniać, gdy jest zbyt wiele różnych wartości dla DiffOfColumns. Zróbmy ten sam test, ale użyj CRYPT_GEN_RANDOM(2)zamiast CRYPT_GEN_RANDOM(1).

DROP TABLE IF EXISTS dbo.MyTableBigDiff;

CREATE TABLE dbo.MyTableBigDiff
(
Id        INT IDENTITY PRIMARY KEY,
RangeFrom INT NOT NULL,
RangeTo   INT NOT NULL,
CHECK (RangeTo > RangeFrom)
);

WITH RandomNumbers
     AS (SELECT TOP 10000000 ABS(CRYPT_GEN_RANDOM(4)%100000000) AS Num
         FROM   sys.all_objects o1,
                sys.all_objects o2,
                sys.all_objects o3,
                sys.all_objects o4)
INSERT INTO dbo.MyTableBigDiff
            (RangeFrom,
             RangeTo)
SELECT Num,
       Num + 1 + CRYPT_GEN_RANDOM(2) -- note the 2
FROM   RandomNumbers;


ALTER TABLE dbo.MyTableBigDiff ADD DiffOfColumns AS RangeTo-RangeFrom;

CREATE INDEX IXDIFF ON dbo.MyTableBigDiff (DiffOfColumns,RangeFrom) INCLUDE (RangeTo);

To samo zapytanie znajduje teraz 65536 wierszy z części rekurencyjnej i zajmuje 823 ms procesora na moim komputerze. PAGELATCH_SH czeka i dzieje się coś złego. Mogę poprawić wydajność, grupując wartości różnic, aby utrzymać liczbę unikatowych wartości pod kontrolą i dostosowując się do segmentu w CROSS APPLY. Dla tego zestawu danych wypróbuję 256 segmentów:

ALTER TABLE dbo.MyTableBigDiff ADD DiffOfColumns_bucket256 AS CAST(CEILING((RangeTo-RangeFrom) / 256.) AS INT);

CREATE INDEX [IXDIFF😎] ON dbo.MyTableBigDiff (DiffOfColumns_bucket256, RangeFrom) INCLUDE (RangeTo);

Jednym ze sposobów uniknięcia uzyskania dodatkowych wierszy (teraz porównuję do zaokrąglonej wartości zamiast wartości rzeczywistej) jest filtrowanie na RangeTo:

CROSS APPLY (
    SELECT mt.Id, mt.RangeFrom, mt.RangeTo
    FROM dbo.MyTableBigDiff mt
    WHERE mt.DiffOfColumns_bucket256 = rcte.DiffOfColumns_bucket256
    AND mt.RangeFrom >= 50000000 - (256 * rcte.DiffOfColumns_bucket256)
    AND mt.RangeFrom <= 50000000
    AND mt.RangeTo >= 50000000
) ca

Pełne zapytanie zajmuje teraz 6 ms na moim komputerze.

Jednym z alternatywnych sposobów przedstawiania zakresu są punkty na linii.

Poniżej migruje wszystkie dane do nowej tabeli z zakresem reprezentowanym jako geometrytyp danych.

CREATE TABLE MyTable2
(
Id INT IDENTITY PRIMARY KEY,
Range GEOMETRY NOT NULL,
RangeFrom AS Range.STPointN(1).STX,
RangeTo   AS Range.STPointN(2).STX,
CHECK (Range.STNumPoints() = 2 AND Range.STPointN(1).STY = 0 AND Range.STPointN(2).STY = 0)
);

SET IDENTITY_INSERT MyTable2 ON

INSERT INTO MyTable2
            (Id,
             Range)
SELECT ID,
       geometry::STLineFromText(CONCAT('LINESTRING(', RangeFrom, ' 0, ', RangeTo, ' 0)'), 0)
FROM   MyTable

SET IDENTITY_INSERT MyTable2 OFF 


CREATE SPATIAL INDEX index_name   
ON MyTable2 ( Range )  
USING GEOMETRY_GRID  
WITH (  
BOUNDING_BOX = ( xmin=0, ymin=0, xmax=110000000, ymax=1 ),  
GRIDS = (HIGH, HIGH, HIGH, HIGH),  
CELLS_PER_OBJECT = 16); 

Równoważne zapytanie umożliwiające znalezienie zakresów zawierających wartość 50,000,000znajduje się poniżej.

SELECT Id,
       RangeFrom,
       RangeTo
FROM   MyTable2
WHERE  Range.STContains(geometry::STPointFromText ('POINT (50000000 0)', 0)) = 1 

Odczyty tego pokazują ulepszenie w 10,951stosunku do pierwotnego zapytania.

Table 'MyTable2'. Scan count 0, logical reads 505, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Workfile'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'extended_index_1797581442_384000'. Scan count 4, logical reads 17, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Jednak nie ma znaczącej poprawy w stosunku do oryginału pod względem upływu czasu . Typowe wyniki wykonania to 250 ms wobec 252 ms.

Plan wykonania jest bardziej złożony, jak poniżej

Jedynym przypadkiem, w którym przepisywanie działa niezawodnie dla mnie, jest zimna pamięć podręczna.

Rozczarowujące w tym przypadku i trudno polecić to przepisanie, ale publikacja negatywnych wyników może być również przydatna.

W hołdzie naszym nowym panom-robotom postanowiłem sprawdzić, czy któraś z nowych funkcji R i Python może nam w tym pomóc. Odpowiedź brzmi nie, przynajmniej w przypadku skryptów, które mogłem uruchomić i zwracać prawidłowe wyniki. Jeśli pojawi się ktoś z lepszą wiedzą, cóż, nie krępuj się, żeby mnie liczyć. Moje stawki są rozsądne.

Aby to zrobić, skonfigurowałem maszynę wirtualną z 4 rdzeniami i 16 GB pamięci RAM, myśląc, że to wystarczy, aby poradzić sobie z ~ 200 MB zestawem danych.

Zacznijmy od języka, który nie istnieje w Bostonie!

R

EXEC sp_execute_external_script 
@language = N'R', 
@script = N'
tweener = 50000000
MO = data.frame(MartinIn)
MartinOut <- subset(MO, RangeFrom <= tweener & RangeTo >= tweener, select = c("Id","RangeFrom","RangeTo"))
', 
@input_data_1_name = N'MartinIn',
@input_data_1 = N'SELECT Id, RangeFrom, RangeTo FROM dbo.MyTable',
@output_data_1_name = N'MartinOut',
@parallel = 1
WITH RESULT SETS ((ID INT, RangeFrom INT, RangeTo INT));

To był zły czas.

Table 'MyTable'. Scan count 1, logical reads 22400

 SQL Server Execution Times:
   CPU time = 3219 ms,  elapsed time = 5349 ms.

Plan wykonania jest dość nieciekawy, chociaż nie wiem, dlaczego środkowy operator musi nazywać nas nazwiskami.

Następnie kodujemy kredkami!

Pyton

EXEC sp_execute_external_script 
@language = N'Python', 
@script = N'
import pandas as pd
MO = pd.DataFrame(MartinIn)
tweener = 50000000
MartinOut = MO[(MO.RangeFrom <= tweener) & (MO.RangeTo >= tweener)]
', 
@input_data_1_name = N'MartinIn',
@input_data_1 = N'SELECT Id, RangeFrom, RangeTo FROM dbo.MyTable',
@output_data_1_name = N'MartinOut',
@parallel = 1
WITH RESULT SETS ((ID INT, RangeFrom INT, RangeTo INT));

Właśnie wtedy, gdy myślałeś, że nie może być gorzej niż R:

Table 'MyTable'. Scan count 1, logical reads 22400

 SQL Server Execution Times:
   CPU time = 3797 ms,  elapsed time = 10146 ms.

Kolejny zepsuty plan egzekucyjny :

Hmm i Hmmer

Jak dotąd nie jestem pod wrażeniem. Nie mogę się doczekać, aby usunąć tę maszynę wirtualną.

Znalazłem całkiem dobre rozwiązanie przy użyciu kolumny obliczeniowej, jednak jest dobre tylko dla pojedynczej wartości. Biorąc to pod uwagę, jeśli masz magiczną wartość, może to wystarczy.

Zaczynając od podanej próbki, a następnie modyfikując tabelę:

ALTER TABLE dbo.MyTable
    ADD curtis_jackson 
        AS CONVERT(BIT, CASE 
                            WHEN RangeTo >= 50000000
                            AND RangeFrom < 50000000
                            THEN 1 
                            ELSE 0 
                        END);

CREATE INDEX IX1_redo 
    ON dbo.MyTable (curtis_jackson) 
        INCLUDE (RangeFrom, RangeTo);

Zapytanie staje się po prostu:

SELECT *
FROM MyTable
WHERE curtis_jackson = 1;

Który zwraca takie same wyniki jak zapytanie początkowe. Gdy plany wykonania są wyłączone, oto statystyki (obcięte dla zwięzłości):

Table 'MyTable'. Scan count 1, logical reads 3...

SQL Server Execution Times:
  CPU time = 0 ms,  elapsed time = 0 ms.

A oto plan zapytań :

Moje rozwiązanie opiera się na obserwacji, że przedział ma znanego maksymalna szerokość W . Dla przykładowych danych jest to jeden bajt lub 256 liczb całkowitych. Stąd dla danego wyszukiwania wartości parametru P wiemy najmniejszą RangeFrom, które mogą być w zbiorze wynikowym jest P - szer . Dodanie tego do predykatu daje

declare @P int = 50000000;
declare @W int = 256;

select
    *
from MyTable
where @P between RangeFrom and RangeTo
and RangeFrom >= (@P - @W);

Biorąc pod uwagę oryginalną konfigurację i zapytanie mojego komputera (64-bitowy Windows 10, 4-rdzeniowy hyperthreaded i7, 2.8GHz, 16GB RAM) zwraca 13 wierszy. To zapytanie wykorzystuje równoległe wyszukiwanie indeksu indeksu (RangeFrom, RangeTo). Zmienione zapytanie wykonuje również równoległe wyszukiwanie indeksu na tym samym indeksie.

Pomiary dla oryginalnych i poprawionych zapytań to

                          Original  Revised
                          --------  -------
Stats IO Scan count              9        6
Stats IO logical reads       11547        6

Estimated number of rows   1643170  1216080
Number of rows read        5109666       29
QueryTimeStats CPU             344        2
QueryTimeStats Elapsed          53        0

W pierwotnym zapytaniu liczba odczytanych wierszy jest równa liczbie wierszy mniejszych lub równych @P. Optymalizator zapytań (QO) nie ma alternatywy, ale odczytuje je wszystkie, ponieważ nie może z góry ustalić, które z tych wierszy spełnią predykat. Indeks wielokolumnowy na (RangeFrom, RangeTo) nie jest przydatny w eliminowaniu wierszy, które nie pasują do RangeTo, ponieważ nie ma korelacji między pierwszym kluczem indeksu a drugim, który można zastosować. Na przykład pierwszy rząd może mieć mały odstęp i zostać wyeliminowany, podczas gdy drugi rząd ma duży odstęp i jest zwracany lub odwrotnie.

Podczas jednej nieudanej próby próbowałem zapewnić tę pewność poprzez ograniczenie sprawdzania:

alter table MyTable with check
add constraint CK_MyTable_Interval
check
(
    RangeTo <= RangeFrom + 256
);

To nie miało znaczenia.

Uwzględniając moją wiedzę zewnętrzną na temat dystrybucji danych w predykacie, mogę sprawić, że QO pominie wiersze RangeFrom o niskiej wartości, które nigdy nie mogą być częścią zestawu wyników, i przejdę wiodącą kolumnę indeksu do dopuszczalnych wierszy. Pokazuje to w różnych predykatach wyszukiwania dla każdego zapytania.

W argumentu lustra górna granica RangeTo jest P + W . Nie jest to jednak użyteczne, ponieważ nie ma korelacji między RangeFrom i RangeTo, która pozwoliłaby, aby końcowa kolumna indeksu wielokolumnowego wyeliminowała wiersze. Dlatego dodanie tej klauzuli do zapytania nie przynosi korzyści.

Podejście to czerpie najwięcej korzyści z małego rozmiaru interwału. W miarę wzrostu możliwego rozmiaru interwału liczba pomijanych wierszy o niskiej wartości maleje, chociaż niektóre nadal będą pomijane. W ograniczającym przypadku, gdy przedział jest tak duży, jak zakres danych, takie podejście nie jest gorsze niż oryginalne zapytanie (co jest przyzwoitym zimnym komfortem).

Przepraszam za wszelkie błędy popełniane w tej odpowiedzi.