Hash index w In-memory OLTP – tworzenie i zastosowanie

Wraz z technologią In-memory OLTP wprowadzone zostały dwa nowe indeksy tj. HASH Index oraz NONCLUSTERED Index. Każdy z nich znacznie różni się od tego co mieliśmy do dyspozycji wcześniej i ma jasno sprecyzowane scenariusze użycia. W ramach niniejszego artykułu chciałbym przedstawić Wam koncepcje pierwszego ze wspomnianych indeksów tj. HASH oraz to w jakich przypadkach może on okazać się dla Was użyteczny.

Zacznijmy od stworzenia zestawu danych na którym będziemy pracować:

--check if database exists
DROP DATABASE IF EXISTS Hekaton_Demo
GO

--create database
CREATE DATABASE [Hekaton_demo]
 ON  PRIMARY 
( 
	NAME = N'Hekaton_demo', 
	FILENAME = N'C:\Program Files\Microsoft SQL Server\MSSQL13.MSSQLSERVER\MSSQL\DATA\Hekaton_demo.mdf' , 
	SIZE = 524288KB , 
	FILEGROWTH = 65536KB 
)
 LOG ON 
( 
	NAME = N'Hekaton_demo_log', 
	FILENAME = N'C:\Program Files\Microsoft SQL Server\MSSQL13.MSSQLSERVER\MSSQL\DATA\Hekaton_demo_log.ldf' , 
	SIZE = 131072KB , 
	FILEGROWTH = 65536KB 
)
GO


--add special filegroup to database
ALTER DATABASE Hekaton_demo
ADD FILEGROUP AWMemGroup CONTAINS MEMORY_OPTIMIZED_DATA
GO

--add "file" to filegroup
ALTER DATABASE [Hekaton_demo] 
ADD FILE ( 
	NAME = N'Hekaton_demo_inmem', 
	FILENAME = N'C:\Program Files\Microsoft SQL Server\MSSQL13.MSSQLSERVER\MSSQL\DATA\Hekaton_demo_inmem' 
	) 
TO FILEGROUP [AWMemGroup]
GO

Następnie stwórzmy sobie tabelę wraz z interesującym nas indeksem i wypełnijmy ją 100 tysiącami rekordów :

CREATE TABLE dbo.HK_Indexes
(
Id1 int,
Id2 int,
CreatedDate datetime,
   CONSTRAINT PK_ID PRIMARY KEY NONCLUSTERED HASH (Id1,Id2) WITH (BUCKET_COUNT=400000) 
)  WITH (MEMORY_OPTIMIZED=ON, DURABILITY=SCHEMA_ONLY)   
 GO

DECLARE  @Counter INT=0
DECLARE  @NoOfRows INT=100000
 
WHILE @Counter<=@NoOfRows
BEGIN
	 INSERT dbo.HK_Indexes(Id1,Id2,CreatedDate)
	 VALUES (
				@Counter
				,CAST(RAND()*10000 AS INT)
				,DATEADD(DAY,-CAST(RAND()*1000 AS INT),GETDATE()))   
SET @Counter=@Counter+1
END
GO

Jak możecie zauważyć wskazaliśmy, że interesuje nas indeks hash poprzez wskazanie NONCLUSTERED HASH, następnie podaliśmy ilość tzw. wiader (BUCKET_COUNT). Jest to liczba slotów (będę używał słowa slot zamiast wiadro, które wydaje mi się bardziej intuicyjne) do której mogą trafiać wartości. Hash Index sprawdza się bardzo dobrze na wysoko selektywnych kolumnach takich jak np. klucz główny tabeli, a liczba slotów powinna być jak najbliższa liczbie unikalnych wartości w kolumnie. Dlaczego? Dowiemy się dalej.

Aby przedstawić koncepcję Hash Index posłużę się przykładem Kalen Delaney, który widziałem na jednej z jej sesji gdyż wydaje mi się, iż w doskonały sposób przedstawia on schemat działania. Na poniższym rysunku przedstawione zostały przykładowe wiersze wchodzące w skład wybranej tabeli gdzie indeks został założony na kolumnie name. Funkcja hashująca jest uzależniona od liczby slotów jakie nasz indeks posiada – dla uproszczenia powiedzmy, że funkcja ta działa analogicznie do LEN.

Dlatego też wiersz z Jane wstawiony w momencie 50 trafia do slota 4 ponieważ LEN(‘Jane’)=4, a wiersz z Susan wstawiony w momencie 70 trafia do slota nr. 5 ponieważ LEN(‘Susan’)=5.

Następnie wyobraźmy sobie sytuację, że ktoś wstawia w momencie 100 wiersz z wartością Greg dla kolumny Name. Literał poddawany jest funkcji haszującej (czyli analogicznie LEN(‘Greg’)=4) i nowy wiersz również trafia do slota nr 4, a sam nowy wiersz w odpowiednim polu nagłówka ma wskaźnik do pierwszego wiersza w łańcuchu (czyli do wiersza  Jane). Gdy wiersz trafia do slota w którym istnieje już inny wiersz to takie zdarzenie nie jest do końca pożądane i nazywa się hash collision. Jest ono niepożądane ponieważ wyszukiwanie wierszy to tak naprawdę wyszukanie slota w którym znajduje się dana wartość – jeśli w slocie jest wiele wartości to SQL Server musi je wszystkie przeskanować aby znaleźć te pożądane.

Oczywiście może również nastąpić aktualizacja wiersza np. w momencie 200 dla wiersza Greg zaktualizowane zostanie pole City z Beijing na Lisbon. Oczywiście zgodnie z koncepcją optymistycznego modelu izolacji transakcji nic nie zostaje aktualizowane, a po prostu stary wiersz zostaje oznaczony jako już nieaktywny. Jak już wiersz nieaktywny nie będzie dostępny dla żadnej transakcji to zostanie on usunięty przez Garbage Collector.

Teraz jak już wiemy mniej więcej jak działa nasz indeks to możemy użyć widoku sys.dm_db_xtp_hash_index_stats aby poznać jego wewnętrzną strukturę:

SELECT OBJECT_NAME(hkis.object_id),
	* 
FROM Sys.dm_db_xtp_hash_index_stats AS hkis
WHERE hkis.object_id=OBJECT_ID('dbo.HK_Indexes')

Istotne jest dla nas pole total_bucket_count, które oznacza ile slotów zostało stworzonych dla naszego indeksu. Liczba ta nie jest dokładnie taka jaką podaliśmy podczas tworzenia tabeli gdyż SQL Server podniósł ją do najbliższej potęgi liczby 2 (zrobił to ze względu na to, że jeżeli będzie to potęga liczby dwa to w celu lokalizacji określonego slota będzie mógł użyć operacji przesunięcia bitowego, która jest bardzo szybką operacją – w innym przypadku musiałby użyć operacji MODULO, która jest dużo kosztowniejsza). Dalej mamy empty_bucket_count czyli liczbę pustych slotów – należy pamiętać iż mimo, że są puste to zajmują miejsce w pamięci. Dalej mamy avg_chain_length czyli średnio jaka jest długość łańcucha w jednym slocie oraz max_chaing_length czyli ile wynosi najdłuższy łańcuch w naszej tabeli.

Jeśli zauważymy dużą liczbę przy avg_chain_length lub max_chain_length to albo powinniśmy zwiększyć w naszym oknie utrzymania liczbę slotów, bądź też założyliśmy indeks na zbyt mało selektywnej kolumnie. Gdy zauwazymy, że empty_bucket_count posiada wysoką liczbę możemy ograniczyć liczbę slotów w indeksie. Każda z tych operacji powinna być wnikliwie przeanalizowana tym ile dziennie może być wstawionych nowych wartości itp.

W porządku, przetestujmy zatem jak działa nasz indeks, pierwszym scenariuszem jest zapytanie z filtrowaniem wykorzystującym jeden z elementów klucza złożonego:

SELECT Id1,Id2
FROM
	dbo.HK_Indexes
WHERE Id1=4

W tradycyjnych indeksach przy dostatecznej selektywności powinniśmy otrzymać Index Seek ponieważ filtrujemy tabelę po pierwszym elemencie klucza – jak to wygląda w przypadku Hash index:

W tym wypadku mamy jednak skanowanie całej tabeli i jej późniejsza filtrację operatorem Filter. Dzieje się tak dlatego ponieważ hash z Id1 i Id2 to nie to samo co hash tylko z Id1. Spróbujmy dalej tym razem w warunku WHERE wykorzystamy oba klucze:

SELECT *
FROM
	dbo.HK_Indexes
WHERE Id1=4 AND Id2=5

Ze względu na fakt, iż wszystkie indeksy są niejako pokrywające otrzymamy Index Seek:

W kolejnym teście spróbujmy odpytać naszą tabelę wykorzystując oba elementy klucza jednakże z operatorami większy niż oraz mniejszy niż:

SELECT *
FROM
	dbo.HK_Indexes
WHERE Id1>4 AND Id2<7135

Mamy skanowanie całej tabeli – dzieje się to ze względu na fakt, iż Index Scan nie obsługuje RANGE SCANS czyli warunków opisanych operatorami innymi niż znak równości. Poniższe zapytanie również nie będą używać indeksu typu hash:

SELECT *
FROM
	dbo.HK_Indexes
WHERE Id1=4 AND Id2<>7136
GO

W dalszym przykładzie zastanówmy się czy indeks zwróci posortowane dane:

SELECT *
FROM
	dbo.HK_Indexes 
WHERE Id1=98855 AND Id2=5311
ORDER BY Id1

Można by przypuszczać, że tak w istocie jest jednakże występowanie Index Seek bez operatora Sort jest podyktowane tym, iż zwrócony zostanie maksymalnie jeden wiersz:

W przypadku gdy może wystąpić więcej niż jeden wiersz to niestety musi wystąpić dodatkowy operator Sort:

SELECT *
FROM
	dbo.HK_Indexes
WHERE (Id1=4 OR Id1=5 ) AND Id2=7135
ORDER BY Id1,Id2

Z powyższych przykładów wynika, że indeks tego typu świetnie nadaje się do operacji typu POINT LOOKUP czyli szybkich wyszukiwań po kluczu indeksu, a nie obsługuje w ogóle innych operacji. Oczywiście w In-memory OLTP mamy do dyspozycji indeks NONCLUSTERED (RANGE), który uzupełnia tą lukę – jemu poświęcimy osobny artykuł ale na ten moment utwórzmy sobie go aby porównać jego wydajność z Hash Index:

ALTER TABLE dbo.HK_Indexes 
ADD INDEX [RangeIX_HK_Indexes] NONCLUSTERED
(
	Id1,Id2
) 
  GO

SELECT *
FROM
	dbo.HK_Indexes
	WITH (INDEX(RangeIX_HK_Indexes))
WHERE Id1 = 4 AND Id2=7135
GO
SELECT *
FROM
	dbo.HK_Indexes
	WITH (INDEX(PK_ID))
WHERE Id1 = 4 AND Id2=7135

Porównując oba plany widzimy, że przeszukanie BW-Tree(struktury na której opiera się indeks RANGE)  jest dużo wolniejsze niż wyszukanie odpowiedniego slotu w Hash indeks:

Tak więc nie ma szybszego sposobu w SQL Server dla operacji POINT LOOKUP niż Hash Index! Warto pamiętać o tej własności i zakładać indeksy tego typu na bardzo mocno selektywnych kolumnach, które będą często odpytywane zapytaniami z predykatami równości. Warto również zapamiętać, że indeks ten powinien być przemyślanym wyborem i mimo, iż nie wiąże się z nim żadna fragmentacja to wymaga utrzymania odpowiedniej liczby slotów. Powinien być zawsze naszym drugim wyborem ponieważ RANGE Index o którym jeszcze będę pisał jest dużo bardziej uniwersalny i nie wymaga predefiniowania wielkości tak jak ma to miejsce w HASH.