Wstępne słowo
Wygłosiłem tę prezentację w języku angielskim na konferencji GopherCon Rosja 2019 w Moskwie, a w języku rosyjskim podczas meetupu w Niżnym Nowogrodzie. Mówi ona o indeksie bitmapowym — mniej rozpowszechnionym niż B-drzewo, ale nie mniej interesującym. Dzielę się wystąpienia na konferencji w języku angielskim oraz transkrypcją tekstową w języku rosyjskim.
Przyjrzymy się, jak działa indeks bitmapowy, kiedy jest lepszy, kiedy gorszy od innych indeksów i w jakich przypadkach jest znacznie szybszy; zobaczymy, w jakich popularnych systemach baz danych już istnieją indeksy bitmapowe; spróbujemy napisać własny w Go. A na "deser" skorzystamy z gotowych bibliotek, aby stworzyć naszą super szybką specjalistyczną bazę danych.
Bardzo mam nadzieję, że moje prace okażą się dla was pomocne i interesujące. Zaczynajmy!
Wprowadzenie
Cześć wszystkim! Jest szósta wieczorem, wszyscy jesteśmy bardzo zmęczeni. Doskonały czas, aby porozmawiać o nudnej teorii indeksów baz danych, prawda? Nie martwcie się, będę miał kilka linijek kodu źródłowego tu i tam. 🙂
Bez żartów, ten referat jest przepełniony informacjami, a mamy mało czasu. Dlatego zaczynajmy.
Dziś będę mówił o następujących kwestiach:
- czym są indeksy;
- czym jest indeks bitmapowy;
- gdzie jest używany, a gdzie NIE jest używany i dlaczego;
- prosta implementacja w Go i trochę walki z kompilatorem;
- nieco mniej prosta, ale znacznie bardziej wydajna implementacja w assemblerze Go;
- "problemy" indeksów bitmapowych;
- istniejące realizacje.
Czym są więc indeksy?
Indeks to oddzielna struktura danych, którą przechowujemy i aktualizujemy w uzupełnieniu do danych podstawowych. Służy do przyspieszania wyszukiwania. Bez indeksów wyszukiwanie wymagałoby pełnego przeszukiwania danych (proces ten nazywany jest pełnym skanowaniem) i ten proces ma liniową złożoność algorytmiczną. Ale bazy danych zwykle zawierają ogromne ilości danych, a liniowa złożoność — to zbyt wolno. Idealnie chcielibyśmy uzyskać złożoność logarytmiczną lub stałą.
To ogromny skomplikowany temat, przepełniony niuansami i kompromisami, ale po obejrzeniu dziesiątek lat rozwoju i badań różnych baz danych, mogę z przekonaniem stwierdzić, że istnieje tylko kilka szeroko stosowanych podejść do tworzenia indeksów baz danych.
Pierwsze podejście polega na hierarchicznym zmniejszeniu obszaru wyszukiwania, podzieleniu go na mniejsze części.
Zazwyczaj robimy to, używając różnego rodzaju drzew. Przykładem może być duża skrzynka z materiałami w twojej szafie, w której znajdują się mniejsze skrzynki z materiałami, podzielonymi według różnych tematów. Jeśli potrzebujesz materiałów, to na pewno będziesz ich szukać w skrzynce z napisem „Materiały”, a nie w tej oznaczonej jako „Ciastka”, prawda?
Drugie podejście polega na od razu zidentyfikowaniu potrzebnego elementu lub grupy elementów. Robimy to za pomocą map hash lub indeksów odwrotnych. Użycie map hash jest bardzo podobne do poprzedniego przykładu, tylko zamiast skrzynki z skrzynkami masz w szafie stos małych skrzynek z gotowymi przedmiotami.
Trzecie podejście to pozbycie się potrzeby wyszukiwania. Robimy to za pomocą filtrów Bloom lub filtrów cuckoo. Te pierwsze dają odpowiedź natychmiast, uwalniając cię od konieczności wyszukiwania.
Ostatnie podejście polega na pełnym wykorzystaniu wszystkich możliwości, które daje nam nowoczesny sprzęt. Dokładnie to robimy w indeksach bitmapowych. Tak, korzystając z nich, czasami musimy przeszukać cały indeks, ale robimy to super efektywnie.
Jak już powiedziałem, temat indeksów baz danych jest obszerny i pełen kompromisów. To oznacza, że czasami możemy stosować kilka podejść jednocześnie: jeśli musimy jeszcze bardziej przyspieszyć wyszukiwanie lub jeśli konieczne jest objęcie wszystkich możliwych typów wyszukiwania.
Dziś opowiem o najmniej znanym podejściu spośród wymienionych — o indeksach bitmapowych.
Kim jestem, żeby mówić na ten temat?
Pracuję jako lider zespołu w Badoo (może znasz nasz inny produkt — Bumble). Mamy już ponad 400 milionów użytkowników na całym świecie i wiele funkcji, które pomagają im znaleźć najlepsza parę. Robimy to za pomocą własnych usług, które wykorzystują również indeksy bitmapowe.
Czym zatem jest indeks bitmapowy?
Indeksy bitmap, jak sugeruje nazwa, wykorzystują bitmapy lub zestawy bitów do zaimplementowania indeksu wyszukiwania. Z lotu ptaka ten indeks składa się z jednego lub kilku takich bitmap, reprezentujących różne encje (takie jak ludzie) oraz ich cechy lub parametry (wiek, kolor oczu itd.), a także z algorytmu wykorzystującego operacje bitowe (AND, OR, NOT) do odpowiadania na zapytania wyszukiwania.
Mówi się, że indeksy bitmap są najlepiej dopasowane i bardzo wydajne w przypadkach, gdy wyszukiwanie łączy zapytania dotyczące wielu kolumn o niskiej kardynalności (wyobraź sobie «kolor oczu» lub «stan cywilny» w porównaniu do czegoś takiego jak «odległość od centrum miasta»). Ale później pokażę, że doskonale działają również w przypadku kolumn o wysokiej kardynalności.
Rozważmy najprostszy przykład indeksu bitmap.
Wyobraź sobie, że mamy listę restauracji w Moskwie z binarnymi właściwościami jak te:
- blisko metra (near metro);
- ma prywatny parking (has private parking);
- ma taras (has terrace);
- przyjmuje rezerwacje (accepts reservations);
- przyjazne dla wegetarian (vegan friendly);
- droga (expensive).
Nadajmy każdej restauracji numer porządkowy zaczynając od 0 i zarezerwujmy pamięć na 6 bitmap (po jednej dla każdej cechy). Następnie wypełnimy te bitmapy w zależności od tego, czy restauracja posiada daną cechę, czy nie. Jeśli restauracja 4 ma taras, to bit nr 4 w bitmapie «ma taras» zostanie ustawiony na 1 (jeśli tarasu nie ma, to na 0).
Teraz mamy najprostszy możliwy indeks bitmap, który możemy wykorzystać do odpowiadania na zapytania takie jak:
- «Pokaż mi restauracje przyjazne dla wegetarian»;
- «Pokaż mi niedrogie restauracje z tarasem, które przyjmują rezerwacje».
Jak? Przejdźmy do tego. Pierwsze zapytanie jest bardzo proste. Wszystko, co musimy zrobić, to wziąć bitmapę «przyjazne dla wegetarian» i przekształcić ją w listę restauracji, których bity są ustawione.
Drugi zapytanie jest nieco bardziej skomplikowane. Musimy użyć operacji bitowej NOT na bitmapie „drogi”, aby uzyskać listę niedrogich restauracji, a następnie połączyć ją z bitmapą „można zarezerwować stolik” i ponownie połączyć wynik z bitmapą „jest weranda”. Powstała bitmapa będzie zawierać listę miejsc, które spełniają wszystkie nasze kryteria. W tym przykładzie jest to tylko restauracja „Młodość”.
Jest tu dużo teorii, ale nie martwcie się, niebawem zobaczymy kod.
Gdzie są używane indeksy bitmapowe?
Jeśli „zguglujecie” indeksy bitmapowe, 90% odpowiedzi będzie w jakiś sposób związanych z Oracle DB. Ale inne systemy baz danych także z pewnością wspierają tak świetną funkcję, prawda? Nie do końca.
Przejdźmy do listy głównych podejrzanych.
MySQL jeszcze nie wspiera indeksów bitmapowych, ale jest propozycja dodania tej opcji ().
PostgreSQL nie wspiera indeksów bitmapowych, ale wykorzystuje proste bitmapy i operacje bitowe do łączenia wyników wyszukiwania z wieloma innymi indeksami.
Tarantool ma indeksy bitset, wspiera prostą wyszukiwarkę po nich.
Redis ma proste pola bitowe) bez możliwości ich wyszukiwania.
MongoDB jeszcze nie wspiera indeksów bitmapowych, ale także jest propozycja dodania tej opcji
Elasticsearch używa bitmap w środku).
- Ale w naszym domu pojawił się nowy sąsiad: Pilosa. To nowa nierelacyjna baza danych, napisana w Go. Zawiera tylko indeksy bitmapowe i wszystko na nich opiera. Porozmawiamy o niej nieco później.
Implementacja w Go
Ale dlaczego indeksy bitmapowe są tak rzadko używane? Zanim odpowiem na to pytanie, chciałbym zaprezentować Wam implementację bardzo prostego indeksu bitmapowego na Go.
Bitmapy zasadniczo przedstawione są jako kawałki danych. W Go użyjmy w tym celu tablic bajtów.
Mamy jeden bitmap na jedną cechę restauracji, a każdy bit w bitmapie mówi o tym, czy dana restauracja ma tę cechę, czy nie.
Potrzebujemy dwóch funkcji pomocniczych. Jedna z nich będzie używana do wypełnienia naszych bitmap losowymi danymi. Losowymi, ale z określoną prawdopodobieństwem, że restauracja ma każdą z cech. Na przykład uważam, że w Moskwie jest bardzo mało restauracji, w których nie można zarezerwować stolika, a wydaje mi się, że około 20% lokali nadaje się dla wegetarian.
Druga funkcja przekształci bitmapę w listę restauracji.
Aby odpowiedzieć na zapytanie „Pokaż mi niedrogie restauracje, które mają taras i w których można zarezerwować stolik”, potrzebujemy dwóch operacji bitowych: NOT i AND.
Możemy nieco uprościć nasz kod, korzystając z bardziej złożonej operacji AND NOT.
Mamy funkcje dla każdej z tych operacji. Obie przechodzą przez slice'y, pobierają odpowiednie elementy z każdego, łączą je operacją bitową i umieszczają wynik w wynikowym slice'ie.
A teraz możemy skorzystać z naszych bitmap i funkcji, aby odpowiedzieć na zapytanie wyszukiwania.
Wydajność nie jest zbyt wysoka, nawet pomimo tego, że funkcje są bardzo proste i znacznie zaoszczędziliśmy, nie zwracając nowego wynikowego slice'a przy każdym wywołaniu funkcji.
Po przeprofilowaniu z pprof zauważyłem, że kompilator Go pominął jedną bardzo prostą, ale bardzo ważną optymalizację: zagnieżdżanie funkcji.
Chodzi o to, że kompilator Go okropnie boi się pętli, które działają na slice'ach, i kategorycznie odmawia zagnieżdżania funkcji, które zawierają takie pętle.
Ale ja się nie boję i mogę oszukać kompilator, korzystając z goto zamiast pętli, jak w dawnych dobrych czasach.
I jak widzicie, teraz kompilator z przyjemnością zagnieżdża naszą funkcję! W efekcie udaje nam się zaoszczędzić około 2 mikrosekundy. Niezły wynik!
Drugie wąskie gardło można łatwo dostrzec, jeśli uważnie przyjrzeć się wynikowi asemblera. Kompilator dodał sprawdzanie granic slice'a bezpośrednio wewnątrz naszej najgorętszej pętli. Chodzi o to, że Go to język bezpieczny, kompilator obawia się, że moje trzy argumenty (trzy slice'y) mają różne rozmiary. Wówczas istnieje teoretyczna możliwość wystąpienia tak zwanego przepełnienia bufora (buffer overflow).
Uspokójmy kompilator, pokazując mu, że wszystkie slajdy mają ten sam rozmiar. Możemy to osiągnąć, dodając prostą kontrolę na początku naszej funkcji.
Widząc to, kompilator chętnie pomija kontrolę, a my oszczędzamy dodatkowe 500 nanosekund.
Duże partie
Ok, udało nam się wydobyć pewną wydajność z naszej prostej implementacji, ale ten wynik jest zdecydowanie gorszy, niż można by osiągnąć z obecnym sprzętem.
Wszystko, co robimy, to podstawowe operacje bitowe, a nasze procesory wykonują je bardzo efektywnie. Niestety, "karmimy" nasz procesor bardzo małymi kawałkami pracy. Nasze funkcje wykonują operacje bajt po bajcie. Możemy bardzo łatwo dostroić nasz kod, aby pracował z 8-bajtowymi kawałkami, używając slajdów UInt64.
Jak widać, ta mała zmiana przyspieszyła nasz program ośmiokrotnie dzięki zwiększeniu partii ośmiokrotnie. Zysk, można powiedzieć, jest liniowy.
Implementacja w asemblerze
Ale to jeszcze nie koniec. Nasze procesory mogą pracować z kawałkami o rozmiarze 16, 32, a nawet 64 bajtów. Takie "szerokie" operacje nazywane są single instruction multiple data (SIMD; jedna instrukcja, wiele danych), a proces przekształcania kodu w taki sposób, by używał takich operacji, nazywa się wektoryzacją.
Niestety, kompilator Go nie jest najlepszy w wektoryzacji. Na chwilę obecną jedynym sposobem wektoryzacji kodu w Go jest zrobienie tego ręcznie, używając asemblera Go.
Asembler Go to dziwna bestia. Z pewnością wiesz, że asembler to coś, co jest mocno związane z architekturą komputera, dla którego piszesz, ale w Go tak nie jest. Asembler Go jest bardziej podobny do IRL (intermediate representation language) lub języka pośredniego: jest praktycznie niezależny od platformy. Rob Pike zaprezentował świetną prezentację na ten temat kilka lat temu na GopherCon w Denver.
Dodatkowo Go używa niezwykłego formatu Plan 9, różniącego się od uznawanych formatów AT&T i Intel.
Można śmiało powiedzieć, że pisanie asemblera Go ręcznie to nie jest zbyt przyjemne zajęcie.
Ale na szczęście już istnieją dwie zaawansowane narzędzia, które pomagają nam w pisaniu asemblera Go: PeachPy i avo. Obie narzędzia generują asembler Go z bardziej zaawansowanego kodu napisanego odpowiednio w Pythonie i Go.
Te narzędzia ułatwiają takie rzeczy, jak przydział rejestrów (wybór rejestru procesora), pisanie pętli i ogólnie ułatwiają proces wejścia w świat programowania w assemblerze w Go.
Będziemy używać avo, dzięki czemu nasze programy będą niemal zwykłymi programami w Go.
Oto jak wygląda najprostszy przykład programu avo. Mamy funkcję main(), która definiuje wewnątrz siebie funkcję Add(), której celem jest dodanie dwóch liczb. Istnieją tutaj funkcje pomocnicze do uzyskiwania parametrów po nazwie i do uzyskania jednego z dostępnych odpowiednich rejestrów procesora. Dla każdej operacji procesora istnieje odpowiadająca funkcja w avo, jak widać po ADDQ. Na koniec widzimy funkcję pomocniczą do przechowywania wyniku.
Wywołując go generate, uruchomimy program w avo i w efekcie zostaną wygenerowane dwa pliki:
- add.s z rezultatem kodu w assemblerze Go;
- stub.go z nagłówkami funkcji do połączenia dwóch światów: Go i assemblera.
Teraz, gdy widzieliśmy, co i jak robi avo, przyjrzyjmy się naszym funkcjom. Zaimplementowałem zarówno wersje skalarne, jak i wektorowe (SIMD) funkcji.
Najpierw spójrzmy na wersje skalarne.
Jak w poprzednim przykładzie, prosimy o dostępny i odpowiedni rejestr ogólnego przeznaczenia, nie musimy obliczać przesunięć i rozmiarów dla argumentów. Wszystko to avo robi za nas.
Wcześniej używaliśmy etykiet i goto (lub skoków) w celu zwiększenia wydajności i oszukania kompilatora Go, ale teraz robimy to od samego początku. Chodzi o to, że pętle to pojęcie wyższego poziomu. W assemblerze mamy tylko etykiety i skoki.
Pozostały kod powinien być już znany i zrozumiały. Emulujemy pętlę etykietami i skokami, bierzemy małą część danych z naszych dwóch slajdów, łączymy je operacją bitową (AND NOT w tym przypadku) i następnie umieszczamy wynik w rezultacie. I to wszystko.
Oto jak wygląda ostateczny kod w assemblerze. Nie musieliśmy obliczać przesunięć i rozmiarów (podświetlone na zielono) ani monitorować używanych rejestrów (podświetlone na czerwono).
Jeśli porównamy wydajność implementacji w assemblerze z wydajnością najlepszej implementacji w Go, zobaczymy, że są one równe. I jest to oczekiwane. W końcu nie zrobiliśmy nic specjalnego — tylko powtórzyliśmy to, co robiłby kompilator Go.
Niestety, nie możemy zmusić kompilatora do zainline’owania naszych funkcji napisanych w assemblerze. Kompilator Go nie ma obecnie takiej opcji, chociaż prośba o jej dodanie trwa już dość długo.
Właśnie dlatego nie możemy uzyskać żadnych korzyści z małych funkcji w assemblerze. Musimy pisać albo duże funkcje, albo używać nowego pakietu math/bits, albo całkowicie unikać assemblera.
Teraz przyjrzyjmy się wersjom wektorowym naszych funkcji.
W tym przykładzie zdecydowałem się zastosować AVX2, dlatego będziemy korzystać z operacji działających na 32-bajtowych kawałkach. Struktura kodu jest bardzo podobna do wersji skalarnych: ładowanie parametrów, prośba o udostępnienie wolnego ogólnego rejestru itd.
Jednym z nowości jest to, że szersze operacje wektorowe wykorzystują specjalne szerokie rejestry. W przypadku 32-bajtowych kawałków są to rejestry z prefiksem Y. Dlatego w kodzie widzisz funkcję YMM(). Gdybym wykorzystał AVX-512 z 64-bitowymi kawałkami, prefiks byłby Z.
Drugą nowością jest to, że zdecydowałem się na optymalizację zwaną rozpakowywaniem pętli (loop unrolling), czyli wykonanie ośmiu operacji pętli ręcznie, zanim wrócimy na początek pętli. Ta optymalizacja zmniejsza liczbę rozgałęzień w kodzie i jest ograniczona liczbą dostępnych wolnych rejestrów.
A co z wydajnością? Jest doskonała! Osiągnęliśmy przyspieszenie o około siedem razy w porównaniu do najlepszego rozwiązania w Go. Imponujące, prawda?
Ale nawet tę implementację potencjalnie można by przyspieszyć, korzystając z AVX-512, prefetchingu lub JIT (just-in-time compiler) dla planisty zapytań. Ale to już na pewno temat na osobny referat.
Problemy indeksów bitmapowych
Teraz, kiedy już omówiliśmy prostą implementację indeksu bitmapowego w Go oraz znacznie bardziej wydajną w assemblerze, porozmawiajmy wreszcie o tym, dlaczego indeksy bitmapowe są tak rzadko stosowane.
W starszych pracach naukowych wymienia się trzy problemy indeksów bitmapowych, ale nowsze badania, w tym moje, twierdzą, że są one już nieaktualne. Nie będziemy zgłębiać każdego z tych problemów, ale przeanalizujemy je pobieżnie.
Problem wysokiej kardynalności
Mówi się, że indeksy bitmapowe nadają się tylko do pól o niskiej kardynalności, czyli takich, które mają mało wartości (jak na przykład płeć czy kolor oczu), ponieważ tradycyjne przedstawienie takich pól (jeden bit na wartość) w przypadku wysokiej kardynalności zajmie zbyt dużo miejsca, a ponadto te indeksy bitmapowe będą słabo (rzadko) wypełnione.
Czasami możemy użyć innego przedstawienia, na przykład standardowego, które stosujemy do reprezentacji liczb. Ale to właśnie pojawienie się algorytmów kompresji wszystko zmieniło. Przez ostatnie dziesięciolecia naukowcy i badacze wymyślili wiele algorytmów kompresji dla bitmap. Ich główną zaletą jest to, że nie trzeba dekompresować bitmap do wykonywania operacji bitowych—możemy przeprowadzać operacje bitowe bezpośrednio na skompresowanych bitmapach.
Ostatnio zaczęły się również pojawiać hybrydowe podejścia, takie jak na przykład roaring bitmapy. Wykorzystują one jednocześnie trzy różne reprezentacje bitmap—same bitmapy, tablice i tzw. bit runs—i równoważą się między nimi, aby zmaksymalizować wydajność i zminimalizować zużycie pamięci.
Można spotkać roaring bitmapy w najpopularniejszych aplikacjach. Istnieje już wiele implementacji w różnych językach programowania, w tym ponad trzy implementacje dla Go.
Inne podejście, które może pomóc w radzeniu sobie z wysoką kardynalnością, to grupowanie (binning). Wyobraźmy sobie, że mamy pole reprezentujące wzrost człowieka. Wzrost to liczba zmiennoprzecinkowa, ale nie myślimy o nim w ten sposób. Dla nas nie ma różnicy między wzrostem 185,2 cm a 185,3 cm.
Możemy więc pogrupować podobne wartości w grupy w granicach 1 cm.
A jeśli dodatkowo wiemy, że bardzo mało ludzi ma wzrost poniżej 50 cm i powyżej 250 cm, to zasadniczo możemy przekształcić pole o nieskończonej kardynalności w pole o kardynalności wynoszącej około 200 wartości.
Oczywiście, w razie potrzeby możemy dokonać dodatkowej filtracji później.
Problem z dużą przepustowością
Kolejny problem związany z indeksami bitmapowymi polega na tym, że ich aktualizacja może być bardzo kosztowna.
Bazy danych muszą umożliwiać aktualizację danych w momencie, gdy setki innych zapytań przeszukują te dane. Potrzebujemy blokad, aby uniknąć problemów z równoczesnym dostępem do danych lub innych problemów związanych z współdzielonym dostępem. A tam, gdzie jest jedna duża blokada, występuje problem – contention lock, kiedy ta blokada staje się wąskim gardłem.
Problem ten można rozwiązać lub obejść poprzez sharding lub użycie wersjonowanych indeksów.
Sharding to prosta i powszechnie znana metoda. Możesz shardować indeks bitmapowy tak, jak shardujesz każde inne dane. Zamiast jednej dużej blokady otrzymujesz wiele małych blokad i w ten sposób unikasz contention lock.
Drugim sposobem rozwiązania problemu jest użycie wersjonowanych indeksów. Możesz mieć jedną kopię indeksu, której używasz do wyszukiwania lub odczytu, i jedną – do zapisywania lub aktualizacji. Co pewien czas (np. co 100 ms lub 500 ms) duplikujesz je i zamieniasz miejscami. Oczywiście, podejście to ma zastosowanie tylko w przypadkach, gdy Twoja aplikacja może działać z nieco opóźnionym indeksem wyszukiwania.
Te dwa podejścia można stosować jednocześnie: możesz mieć shardowany wersjonowany indeks.
Bardziej złożone zapytania
Ostatnim problemem indeksów bitmapowych jest to, że, jak mówią, nie nadają się one dobrze do bardziej złożonych typów zapytań, na przykład zapytań "w przedziale".
Rzeczywiście, jeśli się zastanowić, operacje bitowe typu AND, OR itd. nie nadają się do zapytań typu "Pokaż mi hotele z ceną pokoju od 200 do 300 dolarów za noc".
Naivnym i bardzo nierozsądnym rozwiązaniem byłoby wzięcie wyników dla każdej wartości dolara i połączenie ich operacją bitową OR.
Nieco lepszym rozwiązaniem byłoby zastosowanie grupowania. Na przykład w grupy po 50 dolarów. Przyspieszyłoby to nasz proces pięćdziesięciokrotnie.
Jednak problem ten można łatwo rozwiązać, korzystając z reprezentacji stworzonej specjalnie dla tego typu zapytań. W pracach naukowych nazywa się to bitmapami kodowanymi na podstawie zakresu.
W takiej reprezentacji nie ustawiamy jednego bitu dla jakiejś wartości (na przykład 200), ale ustawiamy tę wartość oraz wszystko, co jest powyżej. 200 i wyżej. To samo dotyczy 300: 300 i wyżej. I tak dalej.
Korzystając z tej reprezentacji, możemy odpowiedzieć na takie wyszukiwanie, przeszukując indeks tylko dwa razy. Najpierw uzyskujemy listę hoteli, w których cena pokoju wynosi mniej niż 300 dolarów, a następnie eliminujemy te, w których cena pokoju wynosi mniej niż 199 dolarów. Gotowe.
Możesz być zaskoczony, ale nawet zapytania geograficzne są możliwe przy użyciu indeksów bitmapowych. Sztuczka polega na wykorzystaniu reprezentacji geograficznej, która otacza twoje współrzędne kształtem geometrycznym. Na przykład S2 od Google. Kształt powinien być możliwy do przedstawienia w postaci trzech lub więcej przecinających się linii, które można ponumerować. Dzięki temu możemy przekształcić nasze zapytanie geograficzne w kilka zapytań „po przedziale” (po tych ponumerowanych liniach).
Gotowe rozwiązania
Mam nadzieję, że trochę cię zainteresowałem i masz w swoim arsenale jeszcze jedno przydatne narzędzie. Jeśli kiedykolwiek będziesz musiał zrobić coś podobnego, będziesz wiedział, w którą stronę patrzeć.
Niemniej jednak nie wszyscy mają czas, cierpliwość i zasoby, aby stworzyć bitmapowe indeksy od podstaw. Szczególnie bardziej zaawansowane, z wykorzystaniem SIMD, na przykład.
Na szczęście istnieje kilka gotowych rozwiązań, które mogą ci pomóc.
Roaring bitmaps
Po pierwsze, istnieje ta sama biblioteka roaring bitmaps, o której już wspomniałem. Zawiera wszystkie niezbędne kontenery i operacje bitowe, które będą potrzebne do stworzenia pełnoprawnego indeksu bitmapowego.
Niestety, jak na razie żadna z realizacji w Go nie korzysta z SIMD, co oznacza, że realizacje w Go są mniej wydajne niż realizacje w C, na przykład.
Pilosa
Inny produkt, który może ci pomóc, to baza danych Pilosa, która w zasadzie opiera się tylko na indeksach bitmapowych. To stosunkowo nowe rozwiązanie, ale zdobywa serca z niesamowitą szybkością.
Pilosa wykorzystuje wewnętrznie roaring bitmaps i daje ci możliwość ich wykorzystania, upraszcza i objaśnia wszystkie te rzeczy, o których mówiłem wcześniej: grupowanie, bitmapy kodowane na podstawie zakresu, pojęcie pola itd.
Zobaczmy szybko przykład użycia Pilosa w odpowiedzi na już znane pytanie.
Przykład jest bardzo podobny do tego, co widziałeś wcześniej. Tworzymy klienta dla serwera Pilosa, tworzymy indeks oraz niezbędne pola, a następnie wypełniamy nasze pola losowymi danymi z prawdopodobieństwami i w końcu wykonujemy znane zapytanie.
Następnie używamy NOT na polu «expensive», a następnie przecinamy wynik (czyli robimy AND) z polem «terrace» oraz z polem «reservations». A na końcu uzyskujemy ostateczny wynik.
Bardzo mam nadzieję, że w nieodległej przyszłości w systemach baz danych takich jak MySQL i PostgreSQL pojawi się ten nowy typ indeksów — indeksy bitmapowe.
Podsumowanie
Jeśli jeszcze nie zasnąłeś, dziękuję. Musiałem poruszyć wiele tematów w związku z ograniczonym czasem, ale mam nadzieję, że prezentacja była użyteczna, a może nawet motywująca.
Warto znać indeksy bitmapowe, nawet jeśli nie są ci teraz potrzebne. Niech będą jednym z narzędzi w twoim zestawie.
Rozeznaliśmy się w różnych sztuczkach poprawiających wydajność dla Go oraz w rzeczach, z którymi kompilator Go nadal sobie nie radzi. To naprawdę coś, co każdy programista Go powinien wiedzieć.
To wszystko, co chciałem powiedzieć. Dziękuję!
Źródło: habr.com
