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.
sql-server
optimization
Martin Smith
źródło
źródło
contains
zapytania i chociaż działają dobrze w zmniejszaniu ilości odczytanych danych, wydaje się, że dodają inne koszty ogólne, które to przeciwdziałają.Odpowiedzi:
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.
Z założenia mogę uzyskać eliminację grupy wierszy w
RangeFrom
kolumnie, co wyeliminuje połowę moich grup wierszy. Ale ze względu na charakter danych również eliminuję grupę wierszy wRangeTo
kolumnie: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.
źródło
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.
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)
Zwykle wykonuje się to
1ms
na moim komputerze, gdy wszystkie strony są w pamięci podręcznej - ze statystykami IO.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.
źródło
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ę
RangeFrom
iRangeTo
i indeksowane go razem zRangeFrom
:Jeśli znasz wszystkie odrębne wartości,
DiffOfColumns
możesz wykonać wyszukiwanie każdej wartościDiffOfColumns
z włączonym filtrem zakresu,RangeTo
aby uzyskać wszystkie odpowiednie dane. Na przykład, jeśli wiemy, żeDiffOfColumns
= 2, wówczas jedynymi dozwolonymi wartościamiRangeFrom
są 49999998, 49999999 i 50000000. Rekurencja może być użyta do uzyskania wszystkich odrębnych wartościDiffOfColumns
i działa dobrze dla twojego zestawu danych, ponieważ jest ich tylko 256. Poniższe zapytanie zajmuje około 6 ms na moim komputerze: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żyjCRYPT_GEN_RANDOM(2)
zamiastCRYPT_GEN_RANDOM(1)
.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: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
:Pełne zapytanie zajmuje teraz 6 ms na moim komputerze.
źródło
Jednym z alternatywnych sposobów przedstawiania zakresu są punkty na linii.
Poniżej migruje wszystkie dane do nowej tabeli z zakresem reprezentowanym jako
geometry
typ danych.Równoważne zapytanie umożliwiające znalezienie zakresów zawierających wartość
50,000,000
znajduje się poniżej.Odczyty tego pokazują ulepszenie w
10,951
stosunku do pierwotnego zapytania.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.
źródło
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
To był zły czas.
Plan wykonania jest dość nieciekawy, chociaż nie wiem, dlaczego środkowy operator musi nazywać nas nazwiskami.
Następnie kodujemy kredkami!
Pyton
Właśnie wtedy, gdy myślałeś, że nie może być gorzej niż R:
Kolejny zepsuty plan egzekucyjny :
Hmm i Hmmer
Jak dotąd nie jestem pod wrażeniem. Nie mogę się doczekać, aby usunąć tę maszynę wirtualną.
źródło
DECLARE @input INT = 50000001; EXEC dbo.sp_execute_external_script @language = N'R', @script = N'OutputDataSet <- InputDataSet[which(x >= InputDataSet$RangeFrom & x <= InputDataSet$RangeTo) , ]', @parallel = 1, @input_data_1 = N'SELECT Id, RangeFrom, RangeTo FROM dbo.MyTable;', @params = N'@x INT', @x = 50000001 WITH RESULT SETS ( ( Id INT NOT NULL, RangeFrom INT NOT NULL, RangeTo INT NOT NULL ));
Tak, wydajność nie jest świetna. Używam R do rzeczy, których nie możesz zrobić w SQL, powiedzmy, jeśli chcesz coś przewidzieć.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ę:
Zapytanie staje się po prostu:
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):
A oto plan zapytań :
źródło
WHERE (50000000 BETWEEN RangeFrom AND RangeTo) INCLUDE (..)
?CREATE INDEX IX1_redo ON dbo.MyTable (curtis_jackson) INCLUDE (RangeFrom, RangeTo) WHERE RangeTo >= 50000000 AND RangeFrom <= 50000000
pracowałbym. I zapytanieSELECT * FROM MyTable WHERE RangeTo >= 50000000 AND RangeFrom <= 50000000;
to wykorzystuje - więc nie ma potrzeby, aby biedny CurtisMoje 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
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
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:
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.
źródło