Mowa otwarcia
Przekazałem ten raport w języku angielskim na konferencji GopherCon Russia 2019 w Moskwie oraz w języku rosyjskim na spotkaniu w Niżnym Nowogrodzie. Mówimy o indeksie bitmap - mniej powszechnym niż B-drzewo, ale nie mniej interesującym. Dzielenie się wystąpienia na konferencji w języku angielskim oraz transkrypcje tekstów 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 od nich znacznie szybszy; Zobaczmy, które popularne systemy DBMS mają już indeksy bitmap; Spróbujmy napisać własny w Go. A „na deser” skorzystamy z gotowych bibliotek, aby stworzyć własną, superszybką, specjalistyczną bazę danych.
Mam nadzieję, że moje prace okażą się dla Państwa przydatne i interesujące. Iść!
Wprowadzenie
Cześć wszystkim! Jest szósta wieczorem i wszyscy jesteśmy bardzo zmęczeni. Świetny czas, aby porozmawiać o nudnej teorii indeksów baz danych, prawda? Nie martw się, będę miał kilka linijek kodu źródłowego tu i tam. 🙂
Pomijając żarty, raport jest przepełniony informacjami, a czasu nie mamy zbyt wiele. Więc zacznijmy.
Dzisiaj opowiem o następujących kwestiach:
- czym są indeksy;
- co to jest indeks mapy bitowej;
- gdzie jest używany, a gdzie NIE i dlaczego;
- prosta implementacja w Go i mała walka z kompilatorem;
- nieco mniej prosta, ale o wiele bardziej produktywna implementacja w asemblerze Go;
- „problemy” indeksów bitmap;
- istniejące wdrożenia.
Czym zatem są indeksy?
Indeks to osobna struktura danych, którą utrzymujemy i aktualizujemy oprócz głównych danych. Służy do przyspieszenia wyszukiwania. Bez indeksów wyszukiwanie wymagałoby całkowitego przejrzenia danych (proces zwany pełnym skanowaniem), a proces ten ma liniową złożoność algorytmiczną. Jednak bazy danych zwykle zawierają ogromne ilości danych, a złożoność liniowa jest zbyt wolna. Idealnie byłoby, gdybyśmy otrzymali logarytmiczną lub stałą.
Jest to niezwykle złożony temat, pełen subtelności i kompromisów, ale po przyjrzeniu się dziesięcioleciom rozwoju i badań baz danych, jestem skłonny powiedzieć, że istnieje tylko kilka powszechnie stosowanych podejść do tworzenia indeksów baz danych.
Pierwsze podejście polega na hierarchicznym zmniejszeniu przestrzeni poszukiwań, dzieląc ją na mniejsze części.
Zwykle robimy to przy użyciu różnych gatunków drzew. Przykładem może być duże pudełko materiałów w Twojej szafie, które zawiera mniejsze pudełka materiałów podzielonych na różne tematy. Jeśli potrzebujesz materiałów, prawdopodobnie będziesz ich szukać w polu z napisem „Materiały”, a nie w polu „Pliki cookie”, prawda?
Drugie podejście polega na natychmiastowym wybraniu żądanego elementu lub grupy elementów. Robimy to w mapach skrótów lub indeksach odwrotnych. Korzystanie z map skrótów jest bardzo podobne do poprzedniego przykładu, ale zamiast pudełka z pudełkami masz w szafie kilka małych pudełek z końcowymi przedmiotami.
Trzecie podejście polega na wyeliminowaniu konieczności wyszukiwania. Robimy to za pomocą filtrów Blooma lub filtrów z kukułką. Te pierwsze dają odpowiedź natychmiast, oszczędzając Ci konieczności szukania.
Ostatnie podejście polega na pełnym wykorzystaniu całej mocy, jaką daje nam nowoczesny sprzęt. To jest dokładnie to, co robimy w indeksach bitmap. Tak, korzystając z nich, czasami musimy przejść przez cały indeks, ale robimy to super sprawnie.
Jak mówiłem, temat indeksów baz danych jest obszerny i pełen kompromisów. Oznacza to, że czasami możemy zastosować kilka podejść jednocześnie: jeśli potrzebujemy jeszcze bardziej przyspieszyć wyszukiwanie, lub jeśli musimy uwzględnić wszystkie możliwe typy wyszukiwania.
Dzisiaj opowiem o najmniej znanym podejściu z nich - indeksach bitmapowych.
Kim jestem, żeby wypowiadać się na ten temat?
Pracuję jako lider zespołu w Badoo (być może znasz bardziej nasz inny produkt, Bumble). Mamy już ponad 400 milionów użytkowników na całym świecie i wiele funkcji, które wybierają dla nich najlepsze dopasowanie. Robimy to za pomocą niestandardowych usług, w tym indeksów bitmapowych.
Czym więc jest indeks mapy bitowej?
Indeksy bitmapowe, jak sama nazwa wskazuje, wykorzystują bitmapy lub zestawy bitów do implementacji indeksu wyszukiwania. Z lotu ptaka indeks ten składa się z jednej lub większej liczby takich bitmap przedstawiających dowolne byty (takie jak ludzie) i ich właściwości lub parametry (wiek, kolor oczu itp.) oraz algorytmu wykorzystującego operacje bitowe (AND, OR, NOT ), aby odpowiedzieć na zapytanie.
Powiedziano nam, że indeksy bitmap są najlepiej dopasowane i bardzo wydajne w przypadkach, gdy wyszukiwania łączą zapytania z wielu kolumn o niskiej liczności (np. „kolor oczu” lub „stan cywilny” w porównaniu z czymś w rodzaju „odległości od centrum miasta”). Ale później pokażę, że działają one dobrze również w przypadku kolumn o dużej kardynalności.
Spójrzmy na najprostszy przykład indeksu mapy bitowej.
Wyobraź sobie, że mamy listę moskiewskich restauracji z takimi właściwościami binarnymi:
- blisko metra;
- jest prywatny parking;
- jest weranda (posiada taras);
- możesz zarezerwować stolik (przyjmuje rezerwacje);
- odpowiedni dla wegetarian (przyjazny weganom);
- drogie (drogie).
Każdej restauracji nadajmy numer kolejny zaczynając od 0 i przydzielmy pamięć na 6 bitmap (po jednej na każdą cechę). Następnie wypełnimy te mapy bitowe w zależności od tego, czy restauracja ma tę właściwość, czy nie. Jeżeli restauracja 4 ma werandę, to bit nr 4 bitmapy „ma werandę” zostanie ustawiony na 1 (jeśli nie ma werandy, to na 0).
Teraz mamy najprostszy możliwy indeks bitmapy i możemy go użyć do odpowiedzi na zapytania takie jak:
- „Pokaż mi restauracje przyjazne wegetarianom”;
- „Pokaż mi niedrogie restauracje z werandą, w których możesz zarezerwować stolik.”
Jak? Przyjrzyjmy się. Pierwsza prośba jest bardzo prosta. Wszystko, co musimy zrobić, to wziąć „przyjazną wegetarianom” bitmapę i przekształcić ją w listę restauracji, których fragmenty są wyeksponowane.
Drugie żądanie jest nieco bardziej skomplikowane. Musimy użyć bitmapy NOT na bitmapie „drogie”, aby uzyskać listę niedrogich restauracji, następnie ORAZ ją z mapą bitową „czy mogę zarezerwować stolik” i wynik ORAZ wynik bitmapą „jest weranda”. Powstała bitmapa będzie zawierać listę placówek spełniających wszystkie nasze kryteria. W tym przykładzie jest to tylko restauracja Yunost.
Jest w tym sporo teorii, ale nie martw się, kod zobaczymy wkrótce.
Gdzie używane są indeksy bitmap?
Jeśli indeksujesz mapy bitowe Google, 90% odpowiedzi będzie w taki czy inny sposób powiązanych z Oracle DB. Ale inne systemy DBMS prawdopodobnie również obsługują taką fajną rzecz, prawda? Nie bardzo.
Przejrzyjmy listę głównych podejrzanych.
MySQL nie obsługuje jeszcze indeksów bitmap, ale istnieje propozycja sugerująca dodanie tej opcji ().
PostgreSQL nie obsługuje indeksów bitmap, ale używa prostych bitmap i operacji bitowych do łączenia wyników wyszukiwania w wielu innych indeksach.
Tarantool ma indeksy bitsetowe i obsługuje proste wyszukiwanie.
Redis ma proste pola bitowe) bez możliwości ich wyszukiwania.
MongoDB nie obsługuje jeszcze indeksów bitmap, ale jest też propozycja sugerująca dodanie tej opcji
Elasticsearch używa wewnętrznie map bitowych).
- Ale w naszym domu pojawił się nowy sąsiad: Pilosa. To nowa, nierelacyjna baza danych napisana w Go. Zawiera jedynie indeksy bitmapowe i na nich wszystko opiera. Porozmawiamy o tym trochę później.
Implementacja w Go
Ale dlaczego indeksy bitmap są tak rzadko używane? Zanim odpowiem na to pytanie, chciałbym pokazać, jak zaimplementować bardzo prosty indeks bitmap w Go.
Mapy bitowe to w zasadzie tylko fragmenty danych. W Go użyjmy do tego wycinków bajtów.
Mamy jedną mapę bitową dla jednej cechy restauracji, a każdy bit mapy bitowej wskazuje, czy dana restauracja ma tę właściwość, czy nie.
Będziemy potrzebować dwóch funkcji pomocniczych. Jeden posłuży do wypełnienia naszych bitmap losowymi danymi. Losowo, ale z pewnym prawdopodobieństwem, że restauracja ma każdą właściwość. Na przykład uważam, że w Moskwie jest bardzo niewiele restauracji, w których nie można zarezerwować stolika i wydaje mi się, że około 20% lokali jest odpowiednich dla wegetarian.
Druga funkcja przekonwertuje bitmapę na listę restauracji.
Aby odpowiedzieć na pytanie „Pokaż mi niedrogie restauracje, które mają patio i mogą dokonać rezerwacji”, potrzebujemy dwóch operacji bitowych: NOT i AND.
Możemy nieco uprościć nasz kod, używając bardziej złożonego operatora AND NOT.
Mamy funkcje dla każdej z tych operacji. Obydwa przechodzą przez wycinki, pobierają z każdego odpowiednie elementy, łączą je za pomocą operacji bitowej i umieszczają wynik w powstałym wycinku.
Teraz możemy użyć naszych bitmap i funkcji, aby odpowiedzieć na zapytanie.
Wydajność nie jest zbyt wysoka, mimo że funkcje są bardzo proste i zaoszczędziliśmy dużo pieniędzy, nie zwracając nowego wynikowego wycinka za każdym razem, gdy funkcja jest wywoływana.
Po zrobieniu trochę profilowania za pomocą pprof zauważyłem, że w kompilatorze Go brakowało jednej bardzo prostej, ale bardzo ważnej optymalizacji: wstawiania funkcji.
Faktem jest, że kompilator Go strasznie boi się pętli przechodzących przez wycinki i kategorycznie odmawia wbudowanych funkcji zawierających takie pętle.
Ale ja się nie boję i mogę oszukać kompilator, używając goto zamiast pętli, jak za starych dobrych czasów.
I jak widać, teraz kompilator z radością wstawi naszą funkcję! Dzięki temu udaje nam się zaoszczędzić około 2 mikrosekund. Nie jest zły!
Drugie wąskie gardło jest łatwe do zauważenia, jeśli przyjrzysz się uważnie wynikom montażu. Kompilator dodał kontrolę granicy plasterka bezpośrednio w naszej najgorętszej pętli. Fakt jest taki, że Go jest językiem bezpiecznym, kompilator obawia się, że moje trzy argumenty (trzy wycinki) będą miały różną wielkość. Przecież wtedy będzie teoretyczna możliwość wystąpienia tzw. przepełnienia bufora.
Uspokójmy kompilator, pokazując mu, że wszystkie plasterki mają ten sam rozmiar. Możemy to zrobić dodając proste sprawdzenie na początku naszej funkcji.
Widząc to, kompilator szczęśliwie pomija sprawdzanie, a my oszczędzamy kolejne 500 nanosekund.
Duże butki
OK, udało nam się wycisnąć trochę wydajności z naszej prostej implementacji, ale w rzeczywistości jest to wynik znacznie gorszy, niż jest to możliwe przy obecnym sprzęcie.
Jedyne, co robimy, to podstawowe operacje bitowe, a nasze procesory wykonują je bardzo sprawnie. Ale niestety „karmimy” nasz procesor bardzo małymi fragmentami pracy. Nasze funkcje wykonują operacje bajt po bajcie. Możemy bardzo łatwo dostosować nasz kod do pracy z fragmentami 8-bajtowymi przy użyciu wycinków UInt64.
Jak widać, ta niewielka zmiana przyspieszyła nasz program ośmiokrotnie, zwiększając wielkość partii ośmiokrotnie. Można powiedzieć, że zysk jest liniowy.
Implementacja w asemblerze
Ale to nie koniec. Nasze procesory mogą pracować z fragmentami o wielkości 16, 32, a nawet 64 bajtów. Takie „szerokie” operacje nazywane są pojedynczą instrukcją na wielu danych (SIMD; jedna instrukcja, wiele danych), a proces przekształcania kodu w celu wykorzystania takich operacji nazywa się wektoryzacją.
Niestety, kompilator Go nie jest doskonały w wektoryzacji. Obecnie jedynym sposobem wektoryzacji kodu Go jest ręczne wykonanie i umieszczenie tych operacji przy użyciu asemblera Go.
Go assembler to dziwna bestia. Prawdopodobnie wiesz, że język asemblera jest czymś mocno powiązanym z architekturą komputera, dla którego piszesz, ale w Go tak nie jest. Asembler Go przypomina bardziej IRL (język reprezentacji pośredniej) lub język pośredni: jest praktycznie niezależny od platformy. Rob Pike dał świetny występ na ten temat kilka lat temu na GopherCon w Denver.
Ponadto Go wykorzystuje nietypowy format Plan 9, który różni się od ogólnie przyjętych formatów AT&T i Intel.
Można śmiało powiedzieć, że ręczne pisanie asemblera Go nie należy do najprzyjemniejszych.
Ale na szczęście istnieją już dwa narzędzia wysokiego poziomu, które pomagają nam napisać asembler Go: PeachPy i avo. Obydwa narzędzia generują asembler Go z kodu wyższego poziomu napisanego odpowiednio w Pythonie i Go.
Narzędzia te upraszczają takie rzeczy, jak alokacja rejestrów, pisanie pętli i ogólnie upraszczają proces wchodzenia w świat programowania w asemblerze w Go.
Użyjemy avo, więc nasze programy będą prawie zwykłymi programami Go.
Tak wygląda najprostszy przykład programu unikającego. Mamy funkcję main(), która definiuje w sobie funkcję Add(), której znaczenie polega na dodaniu dwóch liczb. Istnieją tutaj funkcje pomocnicze umożliwiające uzyskanie parametrów według nazwy i uzyskanie jednego z wolnych i odpowiednich rejestrów procesora. Każda operacja procesora ma odpowiednią funkcję na avo, jak widać w ADDQ. Na koniec widzimy funkcję pomocniczą do przechowywania wynikowej wartości.
Wywołując go generate uruchomimy program na avo i w rezultacie zostaną wygenerowane dwa pliki:
- add.s z powstałym kodem w asemblerze Go;
- stub.go z nagłówkami funkcji łączącymi dwa światy: Go i assembler.
Skoro już widzieliśmy, co i jak robi avo, przyjrzyjmy się naszym funkcjom. Zaimplementowałem zarówno wersję skalarną, jak i wektorową (SIMD).
Przyjrzyjmy się najpierw wersji skalarnej.
Podobnie jak w poprzednim przykładzie prosimy o darmowy i ważny rejestr ogólnego przeznaczenia, nie musimy obliczać przesunięć i rozmiarów argumentów. avo robi to wszystko za nas.
Kiedyś używaliśmy etykiet i goto (lub skoków), aby poprawić wydajność i oszukać kompilator Go, ale teraz robimy to od początku. Rzecz w tym, że cykle to koncepcja wyższego poziomu. W asemblerze mamy tylko etykiety i skoki.
Pozostały kod powinien być już znajomy i zrozumiały. Emulujemy pętlę z etykietami i skokami, pobieramy mały fragment danych z naszych dwóch wycinków, łączymy je operacją bitową (w tym przypadku ORAZ NIE), a następnie umieszczamy wynik w powstałym wycinku. Wszystko.
Tak wygląda końcowy kod asemblera. Nie musieliśmy obliczać przesunięć i rozmiarów (zaznaczonych na zielono) ani śledzić używanych rejestrów (zaznaczonych na czerwono).
Jeśli porównamy wydajność implementacji języka asemblera z wydajnością najlepszej implementacji w Go, zobaczymy, że jest tak samo. I tego się oczekuje. Przecież nie zrobiliśmy nic specjalnego - po prostu odtworzyliśmy to, co zrobiłby kompilator Go.
Niestety, nie możemy zmusić kompilatora do wbudowania naszych funkcji napisanych w języku asemblera. Kompilator Go nie ma obecnie takiej funkcji, chociaż od dłuższego czasu pojawiały się prośby o jej dodanie.
Dlatego właśnie niemożliwe jest uzyskanie jakichkolwiek korzyści z małych funkcji w języku asemblera. Musimy albo napisać duże funkcje, albo użyć nowego pakietu math/bits, albo ominąć język asemblera.
Przyjrzyjmy się teraz wektorowym wersjom naszych funkcji.
W tym przykładzie zdecydowałem się użyć AVX2, więc użyjemy operacji operujących na fragmentach 32-bajtowych. Struktura kodu jest bardzo podobna do wersji skalarnej: ładowanie parametrów, pytanie o darmowy rejestr współdzielony itp.
Jedną z innowacji jest to, że szersze operacje wektorowe wykorzystują specjalne szerokie rejestry. W przypadku fragmentów 32-bajtowych są to rejestry poprzedzone literą Y. Dlatego w kodzie widać funkcję YMM(). Gdybym używał AVX-512 z fragmentami 64-bitowymi, przedrostkiem byłoby Z.
Drugą innowacją jest to, że zdecydowałem się zastosować optymalizację zwaną rozwijaniem pętli, co oznacza ręczne wykonanie ośmiu operacji na pętli przed skokiem na początek pętli. Optymalizacja ta zmniejsza liczbę gałęzi w kodzie i jest ograniczona liczbą dostępnych wolnych rejestrów.
A co z wydajnością? Ona jest piękna! Osiągnęliśmy około siedmiokrotne przyspieszenie w porównaniu do najlepszego rozwiązania Go. Imponujące, prawda?
Ale nawet tę implementację można potencjalnie przyspieszyć, używając AVX-512, pobierania wstępnego lub JIT (kompilatora just-in-time) dla harmonogramu zapytań. Ale to z pewnością temat na osobny raport.
Problemy z indeksami bitmap
Teraz, gdy już przyjrzeliśmy się prostej implementacji indeksu bitmap w Go i znacznie bardziej produktywnej implementacji w języku asemblera, porozmawiajmy w końcu o tym, dlaczego indeksy bitmap są tak rzadko używane.
Starsze artykuły wspominają o trzech problemach z indeksami bitmap, ale nowsze artykuły i ja argumentuję, że nie są one już istotne. Nie będziemy zagłębiać się w każdy z tych problemów, ale przyjrzymy się im powierzchownie.
Problem dużej liczności
Powiedziano nam więc, że indeksy bitmap są odpowiednie tylko dla pól o niskiej liczności, to znaczy takich, które mają niewiele wartości (na przykład płeć lub kolor oczu), a powodem jest to, że zwykła reprezentacja takich pól (jedna bit na wartość) w przypadku dużej kardynalności zajmie to zbyt dużo miejsca, a ponadto te indeksy bitmap będą słabo (rzadko) wypełnione.
Czasami możemy użyć innej reprezentacji, na przykład standardowej, której używamy do reprezentowania liczb. Wszystko zmieniło się jednak wraz z pojawieniem się algorytmów kompresji. W ciągu ostatnich dziesięcioleci naukowcy i badacze opracowali dużą liczbę algorytmów kompresji map bitowych. Ich główną zaletą jest to, że nie ma konieczności dekompresji bitmap w celu wykonania operacji bitowych - możemy wykonywać operacje bitowe bezpośrednio na skompresowanych bitmapach.
Ostatnio zaczęły pojawiać się podejścia hybrydowe, takie jak ryczące bitmapy. Jednocześnie wykorzystują trzy różne reprezentacje map bitowych – same mapy bitowe, tablice i tak zwane ciągi bitowe – i równoważą je, aby zmaksymalizować wydajność i zminimalizować zużycie pamięci.
Ryczące bitmapy znajdziesz w najpopularniejszych aplikacjach. Istnieje już ogromna liczba implementacji dla szerokiej gamy języków programowania, w tym ponad trzy implementacje dla Go.
Inne podejście, które może pomóc nam uporać się z dużą licznością, nazywa się kategoryzacją. Wyobraź sobie, że masz pole reprezentujące wzrost osoby. Wzrost to liczba zmiennoprzecinkowa, ale my, ludzie, nie myślimy o tym w ten sposób. Dla nas nie ma różnicy pomiędzy wzrostem 185,2 cm a 185,3 cm.
Okazuje się, że podobne wartości możemy pogrupować w grupy w promieniu 1 cm.
A jeśli wiemy również, że bardzo niewiele osób ma mniej niż 50 cm i więcej niż 250 cm, wówczas możemy w zasadzie zamienić pole o nieskończonej liczności w pole o liczności około 200 wartości.
Oczywiście w razie potrzeby możemy później wykonać dodatkowe filtrowanie.
Problem z dużą przepustowością
Następnym problemem związanym z indeksami bitmap jest to, że ich aktualizacja może być bardzo kosztowna.
Bazy danych muszą być w stanie aktualizować dane, podczas gdy potencjalnie setki innych zapytań przeszukuje dane. Potrzebujemy blokad, aby uniknąć problemów z jednoczesnym dostępem do danych lub innych problemów z udostępnianiem. A tam, gdzie jest jedna duża blokada, pojawia się problem – rywalizacja o zamek, kiedy ta blokada staje się wąskim gardłem.
Ten problem można rozwiązać lub obejść, stosując sharding lub indeksy wersjonowane.
Sharding to prosta i dobrze znana rzecz. Indeks mapy bitowej można podzielić na fragmenty tak samo, jak inne dane. Zamiast jednego dużego zamka otrzymasz kilka małych zamków, a tym samym pozbędziesz się rywalizacji o zamki.
Drugim sposobem rozwiązania problemu jest użycie indeksów wersjonowanych. Możesz mieć jedną kopię indeksu, której używasz do wyszukiwania lub czytania, i jedną, której używasz do pisania lub aktualizowania. I raz na określony czas (na przykład raz na 100 ms lub 500 ms) duplikujesz je i zamieniasz. Oczywiście to podejście ma zastosowanie tylko w przypadkach, gdy Twoja aplikacja może obsłużyć nieco opóźniony indeks wyszukiwania.
Te dwa podejścia mogą być stosowane jednocześnie: możesz mieć indeks podzielony na fragmenty.
Bardziej złożone zapytania
Ostatnim problemem związanym z indeksami bitmap jest to, że powiedziano nam, że nie nadają się one dobrze do bardziej złożonych typów zapytań, takich jak zapytania dotyczące zakresu.
Rzeczywiście, jeśli się nad tym zastanowić, operacje bitowe, takie jak AND, OR itp., nie są zbyt odpowiednie w przypadku zapytań typu „Pokaż mi hotele ze stawkami za pokój od 200 do 300 dolarów za noc”.
Naiwnym i bardzo niemądrym rozwiązaniem byłoby wzięcie wyników dla każdej wartości dolara i połączenie ich bitową operacją OR.
Nieco lepszym rozwiązaniem byłoby zastosowanie grupowania. Na przykład w grupach po 50 dolarów. Przyspieszyłoby to nasz proces 50-krotnie.
Ale problem można również łatwo rozwiązać, korzystając z widoku stworzonego specjalnie dla tego typu żądań. W publikacjach naukowych nazywa się to mapami bitowymi z kodowaniem zakresu.
W tej reprezentacji nie ustawiamy tylko jednego bitu na jakąś wartość (na przykład 200), ale ustawiamy tę wartość i wszystko wyżej. 200 i więcej. To samo dla 300: 300 i więcej. I tak dalej.
Korzystając z tej reprezentacji, możemy odpowiedzieć na tego rodzaju zapytanie, przechodząc przez indeks tylko dwukrotnie. Najpierw otrzymamy listę hoteli, w których pokój kosztuje mniej lub 300 dolarów, a następnie usuniemy z niej te, w których pokój kosztuje mniej lub 199 dolarów. Gotowy.
Będziesz zaskoczony, ale nawet geokwerendy są możliwe przy użyciu indeksów bitmapowych. Sztuka polega na użyciu reprezentacji geometrycznej, która otacza współrzędne figurą geometryczną. Na przykład S2 od Google. Rysunek powinien umożliwiać przedstawienie go w postaci trzech lub większej liczby przecinających się linii, które można ponumerować. W ten sposób możemy zamienić naszą geozapytanie w kilka zapytań „wzdłuż luki” (wzdłuż ponumerowanych linii).
Gotowe rozwiązania
Mam nadzieję, że choć trochę Cię zainteresowałem i masz teraz kolejne przydatne narzędzie w swoim arsenale. Jeśli kiedykolwiek będziesz musiał zrobić coś takiego, będziesz wiedział, w którą stronę patrzeć.
Jednak nie każdy ma czas, cierpliwość lub zasoby, aby od zera tworzyć indeksy bitmap. Zwłaszcza te bardziej zaawansowane, wykorzystujące np. SIMD.
Na szczęście istnieje kilka gotowych rozwiązań, które mogą Ci w tym pomóc.
Ryczące bitmapy
Po pierwsze, istnieje ta sama biblioteka bitmap, o której już mówiłem. Zawiera wszystkie niezbędne kontenery i operacje bitowe, które będą potrzebne do stworzenia pełnoprawnego indeksu bitmap.
Niestety, w tej chwili żadna z implementacji Go nie korzysta z SIMD, co oznacza, że implementacje Go są mniej wydajne niż na przykład implementacje C.
włochaty
Innym produktem, który może Ci pomóc, jest Pilosa DBMS, który w rzeczywistości ma tylko indeksy bitmapowe. To stosunkowo nowe rozwiązanie, ale z ogromną szybkością zdobywa serca.
Pilosa używa wewnętrznie ryczących bitmap i daje możliwość ich wykorzystania, upraszcza i wyjaśnia wszystkie rzeczy, o których mówiłem powyżej: grupowanie, bitmapy z zakodowanym zakresem, koncepcja pola itp.
Rzućmy okiem na przykład użycia Pilosa do odpowiedzi na pytanie, które już znasz.
Przykład jest bardzo podobny do tego, co widziałeś wcześniej. Tworzymy klienta serwera Pilosa, tworzymy indeks i niezbędne pola, następnie wypełniamy nasze pola losowymi danymi z prawdopodobieństwami i na koniec wykonujemy znane nam zapytanie.
Następnie używamy NOT w polu „drogie”, a następnie wynik (lub ORAZ) przecinamy z polem „taras” i polem „rezerwacje”. I wreszcie otrzymujemy ostateczny wynik.
Mam wielką nadzieję, że w najbliższej przyszłości ten nowy typ indeksu pojawi się także w systemach DBMS takich jak MySQL i PostgreSQL - indeksy bitmapowe.
wniosek
Jeśli jeszcze nie zasnąłeś, dziękuję. Wiele tematów musiałem pokrótce poruszyć ze względu na ograniczony czas, ale mam nadzieję, że rozmowa była przydatna, a może nawet motywująca.
Warto wiedzieć o indeksach bitmap, nawet jeśli ich teraz nie potrzebujesz. Niech będą kolejnym narzędziem w Twoim zestawie narzędzi.
Przyjrzeliśmy się różnym sztuczkom wydajnościowym dla Go i sprawom, z którymi kompilator Go nie radzi sobie jeszcze zbyt dobrze. Ale jest to absolutnie przydatne dla każdego programisty Go.
To wszystko, co chciałem ci powiedzieć. Dziękuję!
Źródło: www.habr.com