Objaśnienie indeksów SQL, Pt. 2

W pierwszej lekcji SQL Indexes Explained nauczyliśmy się używać sortowania do przyspieszenia pobierania danych. Chociaż wykonanie naszego zapytania jest szybsze po posortowaniu wierszy, sortowanie polega na co najmniej jednokrotnym odczytaniu każdego wiersza i przeniesieniu go. To sprawia, że ​​metoda jest wolniejsza i mniej wydajna niż po prostu sekwencyjne czytanie całej tabeli.

Logiczny wniosek wydaje się taki, że powinniśmy utrzymywać posortowane kopie — które oficjalnie nazwiemy indeksami SQL, poprzedzonymi IX_ — danej tabeli. Wtedy miałyby zastosowanie algorytmy pobierania z pierwszego artykułu i nie musielibyśmy sortować tabeli przed rozpoczęciem.

Indeks jako posortowana kopia tabeli

Przyjrzyjmy się dosłownej realizacji tego pomysłu, ponownie przy użyciu Arkuszy Google. Nasz arkusz kalkulacyjny rezerwacji staje się zbiorem pięciu arkuszy zawierających te same dane. Każdy arkusz jest posortowany według różnych zestawów kolumn.

Ćwiczenia tutaj mają być mniej dokładne niż w poprzednim artykule samouczka dotyczącego indeksu SQL — można je wykonać bardziej na wyczucie niż za pomocą licznika czasu i liczby wierszy. Niektóre ćwiczenia będą wydawać się bardzo podobne, ale tym razem będziemy badać:

1. Jak wydajniej pobierać dane przy użyciu oddzielnych indeksów zamiast posortowanych tabel podstawowych
2. Jak zachować porządek w każdym indeksie i tabeli podczas modyfikowania danych?

Poprzedni samouczek koncentrował się na odczytach, ale w wielu typowych rzeczywistych dynamikach danych — w tym w naszych rezerwacjach hotelowych — musimy wziąć pod uwagę wpływ indeksowania na wydajność zapisu, zarówno w przypadku wstawiania nowych danych, jak i aktualizowania istniejących danych.

Ćwiczenie wstępne: Anuluj rezerwację

Aby poznać wydajność indeksu SQL przy użyciu strategii posortowanej tabeli, Twoim zadaniem jest usunięcie rezerwacji dla Klienta 12 od 22 sierpnia 2020 r. w Hotelu 4. Pamiętaj, że musisz usunąć wiersz ze wszystkich kopii tabeli i utrzymania prawidłowego sortowania.

Gotowy? Powinno być jasne, że pomysł na przechowywanie wielu posortowanych kopii tabeli nie jest tak dobry, jak się wydawało. Jeśli nadal masz jakiekolwiek wątpliwości, możesz również spróbować ponownie wstawić właśnie usuniętą rezerwację lub zmienić datę istniejącej rezerwacji.

Podczas gdy posortowane kopie tabeli pozwalają na szybsze wyszukiwanie, jak się właśnie dowiedzieliśmy, modyfikacja danych to koszmar. Ilekroć musimy dodać, usunąć lub zaktualizować istniejący wiersz, będziemy musieli pobrać wszystkie kopie tabeli, znaleźć wiersz i/lub miejsce, w którym należy go dodać lub przenieść, a na koniec przenieść bloki danych.

Indeksy SQL przy użyciu adresów wierszy

Ten arkusz kalkulacyjny zawiera indeksy, które wykorzystują inne podejście. Wiersze indeksu są nadal sortowane według określonych kryteriów, ale nie przechowujemy wszystkich innych informacji w wierszu indeksu. Zamiast tego zachowujemy tylko „adres wiersza”, adres wiersza w arkuszu Rezerwacje — reprezentujący samą tabelę — w kolumnie H.

Wszystkie implementacje RDBMS korzystają z możliwości na poziomie systemu operacyjnego, aby szybko znaleźć blok na dysku przy użyciu adresu fizycznego. Adresy wierszy zazwyczaj składają się z adresu bloku oraz pozycji wiersza w bloku.

Zróbmy kilka ćwiczeń, aby dowiedzieć się, jak działa ten projekt indeksu.

Ćwiczenie 1: Wszystkie zastrzeżenia klienta

Podobnie jak w pierwszym artykule, zasymulujesz wykonanie następującego zapytania SQL:

 SELECT * FROM Reservations WHERE ClientID = 12;

Znowu są dwa rozsądne podejścia. Pierwszym z nich jest po prostu odczytanie wszystkich wierszy z tabeli Rezerwacje i pobranie tylko wierszy spełniających kryteria:

 For each row from Reservations If Reservations.ClientID = 12 then write down Reservations.*

Drugie podejście polega na odczytaniu danych z arkusza IX_ClientID, a dla dowolnego elementu spełniającego kryteria, wyszukaniu wiersza w tabeli Reservation na podstawie wartości rowAddress:

 Get first row from IX_ClientID where ClientID = 12 While IX_ClientID.ClientID = 12 Fetch Reservations.* where rowAddress = IX_ClientID.rowAddress Write down Reservations.* Get next row from IX_ClientID

W tym przypadku wyrażenie Get first row from jest zaimplementowane przez pętlę podobną do tych, które widzieliśmy w poprzednim artykule:

 Repeat Fetch next row from IX_ClientID Until ClientID >= 12

Możesz znaleźć wiersz z podanym rowAddress, przesuwając w dół, aż znajdziesz wiersz, lub używając filtru w kolumnie rowAddress.

Gdyby do zwrotu była tylko garstka rezerwacji, lepsze byłoby podejście wykorzystujące indeks. Jednak w przypadku setek, a czasem nawet dziesiątek wierszy, które mają zostać zwrócone, samo bezpośrednie użycie tabeli Rezerwacje może być szybsze.

Ilość odczytów zależy od wartości ClientID. Dla wartości największej należy odczytać cały indeks, natomiast dla wartości najniższej jest to początek indeksu. Średnia wartość to połowa liczby wierszy.

Wrócimy do tej części później i przedstawimy skuteczne rozwiązanie. Na razie skupmy się na części po znalezieniu pierwszego wiersza odpowiadającego naszym kryteriom.

Ćwiczenie 2: Liczba rezerwacji rozpoczynających się w danym dniu

Zadanie polega na policzeniu liczby meldunków w dniu 16 sierpnia 2020 r. przy użyciu nowego projektu indeksu.

 SELECT COUNT (*) FROM Reservations WHERE DateFrom = TO_DATE('2020-08-16','YYYY-MM-DD');

Podejście polegające na użyciu odpowiedniego indeksu do liczenia jest lepsze niż skanowanie tabeli, bez względu na liczbę zaangażowanych wierszy. Powodem jest to, że w ogóle nie musimy uzyskiwać dostępu do tabeli Rezerwacje — w samym indeksie mamy wszystkie potrzebne nam informacje:

 Count := 0 Get first row from IX_DateFrom where DateFrom >= '2020-08-16' While found and DateFrom < '2020-08-17' Count := Count + 1 Get next row from IX_DateFrom Write down Count

Algorytm jest w zasadzie taki sam, jak w przypadku posortowanych tabel. Jednak wiersz indeksu jest znacznie krótszy niż wiersz tabeli, więc nasz RDBMS musiałby odczytać z dysku mniej bloków danych.

Ćwiczenie 3: Dochodzenie w sprawach karnych (lista gości z podaniem hotelu i zakresu dat)

Przygotujmy listę gości, którzy przybyli do Hotelu 3 w dniach 13-14 sierpnia 2020 r.

 SELECT ClientID FROM Reservations WHERE DateFrom BETWEEN ( TO_DATE('2020-08-13','YYYY-MM-DD') AND TO_DATE('2020-08-14','YYYY-MM-DD') ) AND HotelID = 3;

Możemy odczytać wszystkie wiersze z tabeli Rezerwacje lub skorzystać z jednego z dostępnych indeksów. Po wykonaniu tego samego ćwiczenia z tabelą posortowaną według określonych kryteriów stwierdziliśmy, że indeks IX_HotelID_DateFrom jest najbardziej wydajny.

 Get first row from IX_HotelID_DateFrom where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and DateFrom < '2020-08-15' and IX_HotelID_DateFrom.HotelID = 3 Fetch Reservations.* where rowAddress = IX_HotelID_DateFrom.rowAddress Write down Reservations.ClientID Get next row from IX_HotelID_DateFrom

Czy możemy zaprojektować jeszcze bardziej efektywny indeks?

Dostęp do tabeli uzyskujemy dzięki wartości ClientID , jedynej informacji, jakiej potrzebujemy dla zgłaszanej przez nas listy gości. Jeśli włączymy tę wartość do indeksu SQL, w ogóle nie będziemy musieli uzyskiwać dostępu do tabeli. Spróbuj przygotować listę odczytującą tylko z takiego indeksu, IX_HotelID_DateFrom_ClientID :

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Write down ClientID Get next row from IX_HotelID_DateFrom_ClientID

Gdy indeks zawiera wszystkie informacje niezbędne do wykonania zapytania, mówimy, że indeks obejmuje zapytanie.

Ćwiczenie 4: Lista nazwisk gości zamiast identyfikatorów

Lista identyfikatorów gości byłaby bezużyteczna dla policjanta prowadzącego dochodzenie w sprawie przestępstwa. Musimy podać nazwiska:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND r.HotelID = 3;

Aby podać listę, oprócz danych z tabeli Reservations potrzebujemy również tabeli Clients z informacjami o gościach, które można znaleźć w tym arkuszu Google.

To ćwiczenie jest podobne do poprzedniego, podobnie jak podejście.

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Clients.ClientName Get next row from IX_HotelID_DateFrom_ClientID

Wyrażenie Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID może być zaimplementowane przez skanowanie tabeli lub przy użyciu naszego indeksu. Jeśli użyjemy skanowania tabeli, dla każdego ClientID z pętli While musielibyśmy odczytać średnio połowę wierszy z tabeli Clients :

 -- Get row from Clients using table scan Repeat Fetch next row from Clients Until ClientID = IX_HotelID_DateFrom_ClientID.ClientID or not found If found Write down ClientName

Implementacja indeksu, którą rozważaliśmy do tej pory — nazwijmy ją „płaską” implementacją indeksu — nie byłaby zbyt pomocna. Musielibyśmy odczytać tę samą liczbę wierszy (choć mniejszych) z indeksu, a następnie przeskoczyć do wiersza w RowAddress Clients

 -- Get row from Clients using flat index Repeat Fetch next row from Clients_PK_Flat Until ClientID >= IX_HotelID_DateFrom_ClientID.ClientID If found Fetch Clients.* where rowAddress = Clients_PK_Flat.rowAddress Write down ClientName

Uwaga: tutaj PK odnosi się do „klucza podstawowego”, terminu, który omówimy w dalszej części serii.

Czy istnieje sposób, aby to osiągnąć bez konieczności czytania tylu wierszy? Tak — do tego właśnie służą indeksy B-tree.

Zrównoważone Drzewo (B-drzewo) Indeksy

Podzielmy wiersze z Clients_PK_Flat na czterowierszowe bloki i utwórzmy listę zawierającą wartość ostatniego ClientID z bloku oraz adres początku bloku (kolumna IndexRowAddress ). Wynikową strukturę danych indeksu bazy danych — można znaleźć w arkuszu Clients_PK_2Levels. Wypróbuj, jak nowa struktura pomaga znaleźć klienta o ClientID 28. Algorytm powinien wyglądać tak:

 Fetch Level2.* Loop Leaf_address := Level3Address Exit when ClientID >= 28 Fetch next row from Level2 Fetch Level3.* where Level3Address = Leaf_address -- 3-21 Loop Client_address := RowAddress Exit when ClientID >= 28 Fetch next row from Level 3 Fetch Clients.* where rowAddress = Client_address -- 42 Write down Clients.*

Prawdopodobnie zorientowałeś się, że możemy dodać kolejny poziom. Poziom 1 składa się z czterech wierszy, jak widać w zakładce IX_Clients_PK. Aby znaleźć nazwisko gościa o identyfikatorze ClientID równym 28, musisz odczytać trzy bloki (węzły) danych — jeden na poziom — ze struktury klucza podstawowego i na koniec przejść do wiersza Klienci z adresem 42.

Struktura tego indeksu SQL nazywana jest drzewem zrównoważonym. Drzewo jest zrównoważone, gdy ścieżka od węzła głównego do każdego węzła na poziomie liścia ma tę samą długość, czyli tak zwaną głębokość B-drzewa. W naszym przypadku głębokość wynosi trzy.

Od teraz będziemy uważać, że każdy indeks ma strukturę B-drzewa, mimo że nasze arkusze kalkulacyjne zawierają tylko wpisy na poziomie liścia. Najważniejsze fakty, które należy wiedzieć o B-tree to:

• Struktura indeksu B-drzewa jest najczęściej używanym indeksem przez wszystkie główne RDBMS na rynku.
• Wszystkie poziomy zbilansowanego drzewa są uporządkowane według wartości kolumn kluczowych.
• Dane odczytywane są z dysku w blokach.
• Jeden węzeł B-drzewa zawiera jeden lub więcej bloków.
• Najważniejszym czynnikiem wpływającym na wydajność zapytania jest liczba bloków odczytanych z dysku.
• Liczba elementów na każdym nowym poziomie B-drzewa, zaczynając od korzenia, kończąc na poziomie liścia, rośnie wykładniczo.

Ćwiczenie 5: Dochodzenie karne, część II

Teraz inspektor policji szuka listy odpowiadających im nazwisk gości, dat przyjazdu i nazw hoteli ze wszystkich hoteli w mieście A.

 SELECT h.HotelName, r.DateFrom as CheckInDate, c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID JOIN Hotels h ON r.HotelID = h.HotelID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND h.City = 'A';

Podejście 1

Jeśli użyjemy indeksu IX_DateFrom_HotelID_ClientID , to dla każdego wiersza z zakresu dat musielibyśmy uzyskać dostęp do tabeli Hotele i sprawdzić, czy hotel jest z miasta A. Gdyby tak było, musielibyśmy również uzyskać dostęp do tabeli Klienci, aby przeczytaj nazwę klienta.

 For each row from IX_DateFrom_HotelID_ClientID where DateFrom between '2020-08-13' and '2020-08-14' For each row from Hotels where HotelID = IX_DateFrom_HotelID_ClientID.HotelID If Hotels.City = 'A' then Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Podejście 2

Użycie IX_HotelID_DateFrom_ClientID daje nam bardziej efektywny plan wykonania.

 For each row from Hotels where City = 'A' For each row from IX_HotelID_DateFrom_ClientID where HotelID = Hotels.HotelID and DateFrom between '2020-08-13' and '2020-08-14' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Z tabeli Hotels odnajdujemy wszystkie hotele z miasta A. Znając identyfikatory tych hoteli, możemy odczytać kolejne pozycje z indeksu IX_HotelID_DateFrom_ClientID . W ten sposób, po znalezieniu pierwszego wiersza na poziomie liścia B dla każdego hotelu i daty, nie odczytujemy rezerwacji z hoteli poza miastem A.

Tutaj widzimy, że gdy mamy indeks bazy danych, który jest odpowiedni dla naszych celów, dodatkowe sprzężenie może faktycznie przyspieszyć zapytanie.

Struktura B-drzewa i sposób, w jaki jest ona aktualizowana za każdym razem, gdy wiersz jest wstawiany, aktualizowany lub usuwany, zostanie omówiony bardziej szczegółowo, gdy wyjaśnię motywację partycjonowania i jego wpływ. Chodzi o to, że za każdym razem, gdy używamy indeksu, możemy rozważyć tę operację szybko.

Zapytanie indeksujące w SQL: szczegóły robią różnicę

W przypadku indeksów i baz danych praca na poziomie języka SQL w pewnym stopniu ukrywa szczegóły implementacyjne. Ćwiczenia te mają na celu pomóc Ci zrozumieć, jak działają plany wykonania przy użyciu różnych indeksów SQL. Mam nadzieję, że po przeczytaniu artykułu będziesz w stanie odgadnąć najlepszy plan wykonania biorąc pod uwagę dostępne indeksy i indeksy projektowe, które sprawią, że zapytanie będzie tak szybkie i wydajne, jak to tylko możliwe.

W kolejnej części tej serii wykorzystamy i poszerzymy nowo nabyte umiejętności, aby zbadać i zrozumieć najczęstsze najlepsze praktyki i antywzorce w korzystaniu z indeksów w SQL. Mam listę dobrych i najlepszych praktyk, które chcę omówić w następnej części, ale aby następny artykuł był bardziej adekwatny do twoich potrzeb i doświadczenia, możesz zadawać własne pytania, na które chciałbyś otrzymać odpowiedź .

W końcowej części SQL Indexes Explained dowiemy się również o partycjonowaniu tabel i indeksów, właściwych i niewłaściwych motywacjach korzystania z niego oraz jego wpływie na wydajność zapytań i utrzymanie bazy danych.