Bitmapové indexy v Go: vyhledávání divokou rychlostí

Bitmapové indexy v Go: vyhledávání divokou rychlostí

úvod

Tuto zprávu jsem podal v angličtině na konferenci GopherCon Russia 2019 v Moskvě a v ruštině na setkání v Nižním Novgorodu. Mluvíme o bitmapovém indexu – méně běžném než B-strom, ale neméně zajímavém. Sdílení záznam vystoupení na konferenci v angličtině a přepisy textů v ruštině.

Podíváme se, jak bitmapový index funguje, kdy je lepší, kdy horší než jiné indexy a v jakých případech je výrazně rychlejší než oni; Podívejme se, které populární DBMS již mají bitmapové indexy; Zkusme si napsat vlastní v Go. A „na dezert“ použijeme hotové knihovny k vytvoření vlastní superrychlé specializované databáze.

Opravdu doufám, že moje práce budou pro vás užitečné a zajímavé. Jít!

úvod


http://bit.ly/bitmapindexes
https://github.com/mkevac/gopherconrussia2019

Ahoj všichni! Je šest večer a všichni jsme strašně unavení. Skvělý čas mluvit o nudné teorii indexu databáze, že? Nebojte se, sem tam budu mít pár řádků zdrojového kódu. 🙂

Všechny vtipy stranou, zpráva je přecpaná informacemi a my nemáme moc času. Pojďme tedy začít.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Dnes budu mluvit o následujícím:

  • co jsou indexy;
  • co je bitmapový index;
  • kde se používá a kde se NEPOUŽÍVÁ a proč;
  • jednoduchá implementace v Go a malý boj s kompilátorem;
  • o něco méně jednoduchá, ale mnohem produktivnější implementace v Go assembleru;
  • „problémy“ bitmapových indexů;
  • stávající implementace.

Co jsou tedy indexy?

Bitmapové indexy v Go: vyhledávání divokou rychlostí

Index je samostatná datová struktura, kterou udržujeme a aktualizujeme vedle hlavních dat. Slouží ke zrychlení vyhledávání. Bez indexů by vyhledávání vyžadovalo úplné procházení dat (proces zvaný úplné skenování) a tento proces má lineární algoritmickou složitost. Databáze ale obvykle obsahují obrovské množství dat a lineární složitost je příliš pomalá. V ideálním případě bychom dostali logaritmický nebo konstantní.

Toto je nesmírně složité téma plné jemností a kompromisů, ale po desetiletích vývoje a výzkumu databází jsem ochoten říci, že existuje jen několik široce používaných přístupů k vytváření databázových indexů.

Bitmapové indexy v Go: vyhledávání divokou rychlostí

Prvním přístupem je hierarchicky redukovat vyhledávací prostor, rozdělovat vyhledávací prostor na menší části.

Obvykle to děláme pomocí různých druhů stromů. Příkladem může být velká krabice s materiály ve vaší skříni, která obsahuje menší krabice s materiály rozdělenými do různých témat. Pokud potřebujete materiály, pravděpodobně je budete hledat v krabici s nápisem „Materiály“ spíše než v krabici s nápisem „Cookies“, že?

Bitmapové indexy v Go: vyhledávání divokou rychlostí

Druhým přístupem je okamžitý výběr požadovaného prvku nebo skupiny prvků. Děláme to v hash mapách nebo reverzních indexech. Použití hash map je velmi podobné předchozímu příkladu, ale místo krabice krabic máte ve skříni spoustu malých krabic s konečnými předměty.

Bitmapové indexy v Go: vyhledávání divokou rychlostí

Třetím přístupem je eliminace potřeby hledání. Děláme to pomocí Bloom filtrů nebo kukačkových filtrů. První z nich dají odpověď okamžitě, takže nemusíte hledat.

Bitmapové indexy v Go: vyhledávání divokou rychlostí

Posledním přístupem je plné využití veškeré síly, kterou nám moderní hardware dává. To je přesně to, co děláme v bitmapových indexech. Ano, při jejich používání občas potřebujeme projít celý index, ale děláme to super efektivně.

Jak jsem řekl, téma databázových indexů je rozsáhlé a plné kompromisů. To znamená, že někdy můžeme použít více přístupů současně: pokud potřebujeme vyhledávání ještě urychlit, nebo pokud potřebujeme pokrýt všechny možné typy vyhledávání.

Dnes budu hovořit o nejméně známém přístupu z nich - bitmapových indexech.

Kdo jsem, abych na toto téma mluvil?

Bitmapové indexy v Go: vyhledávání divokou rychlostí

Pracuji jako vedoucí týmu ve společnosti Badoo (možná jste více obeznámeni s naším dalším produktem, Bumble). Máme již více než 400 milionů uživatelů po celém světě a mnoho funkcí, které pro ně vybírají to nejlepší. Děláme to pomocí vlastních služeb, včetně bitmapových indexů.

Co je tedy bitmapový index?

Bitmapové indexy v Go: vyhledávání divokou rychlostí
Bitmapové indexy, jak název napovídá, používají bitmapy nebo bitové sady k implementaci vyhledávacího indexu. Z ptačí perspektivy se tento index skládá z jedné nebo více bitmap reprezentujících jakékoli entity (jako jsou lidé) a jejich vlastností nebo parametrů (věk, barva očí atd.) a algoritmu využívajícího bitové operace (AND, OR, NOT ), abyste odpověděli na vyhledávací dotaz.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Bylo nám řečeno, že bitmapové indexy jsou nejvhodnější a velmi výkonné pro případy, kdy existují vyhledávání, která kombinují dotazy v mnoha sloupcích s nízkou mohutností (předpokládejme „barva očí“ nebo „rodinný stav“ versus něco jako „vzdálenost od centra města“ ). Ale později ukážu, že fungují dobře i pro sloupce s vysokou mohutností.

Podívejme se na nejjednodušší příklad indexu bitmapy.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Představte si, že máme seznam moskevských restaurací s binárními vlastnostmi, jako jsou tyto:

  • blízko metra;
  • k dispozici je soukromé parkoviště;
  • je zde veranda (má terasu);
  • můžete si rezervovat stůl (přijímá rezervace);
  • vhodné pro vegetariány (vegan friendly);
  • drahé (drahé).

Bitmapové indexy v Go: vyhledávání divokou rychlostí
Přidělme každé restauraci pořadové číslo začínající od 0 a přidělme paměť pro 6 bitmap (jedna pro každou charakteristiku). Tyto bitmapy pak naplníme podle toho, zda má restaurace tuto vlastnost nebo ne. Pokud má restaurace 4 verandu, bude bit č. 4 v bitmapě „má verandu“ nastaven na 1 (pokud veranda není, pak na 0).
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Nyní máme nejjednodušší bitmapový index a můžeme jej použít k zodpovězení dotazů jako:

  • „Ukaž mi vegetariánské restaurace“;
  • "Ukažte mi levné restaurace s verandou, kde si můžete rezervovat stůl."

Bitmapové indexy v Go: vyhledávání divokou rychlostí
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Jak? Pojďme se podívat. První požadavek je velmi jednoduchý. Vše, co musíme udělat, je vzít „vegetarian friendly“ bitmapu a přeměnit ji na seznam restaurací, jejichž kousky jsou vystaveny.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Druhý požadavek je trochu složitější. Potřebujeme použít bitmapu NOT na bitmapě „drahé“, abychom získali seznam levných restaurací, pak A to s bitmapou „mohu si rezervovat stůl“ a výsledek s bitmapou „existuje veranda“. Výsledná bitmapa bude obsahovat seznam provozoven, které splňují všechna naše kritéria. V tomto příkladu se jedná pouze o restauraci Yunost.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Je v tom spousta teorie, ale nebojte se, kód uvidíme velmi brzy.

Kde se používají bitmapové indexy?

Bitmapové indexy v Go: vyhledávání divokou rychlostí
Pokud Google indexujete bitmapy, 90 % odpovědí bude tak či onak souviset s Oracle DB. Ale ostatní DBMS pravděpodobně také podporují takovou skvělou věc, že? Spíš ne.

Pojďme si projít seznam hlavních podezřelých.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
MySQL zatím nepodporuje bitmapové indexy, ale existuje návrh doporučující přidat tuto možnost (https://dev.mysql.com/worklog/task/?id=1524).

PostgreSQL nepodporuje bitmapové indexy, ale používá jednoduché bitmapy a bitové operace ke zkombinování výsledků vyhledávání napříč více jinými indexy.

Tarantool má bitsetové indexy a podporuje v nich jednoduché vyhledávání.

Redis má jednoduchá bitová pole (https://redis.io/commands/bitfield) bez možnosti je vyhledávat.

MongoDB zatím nepodporuje bitmapové indexy, ale existuje také návrh, který navrhuje tuto možnost přidat https://jira.mongodb.org/browse/SERVER-1723

Elasticsearch interně používá bitmapy (https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps).

Bitmapové indexy v Go: vyhledávání divokou rychlostí

  • Ale v našem domě se objevil nový soused: Pilosa. Toto je nová nerelační databáze napsaná v Go. Obsahuje pouze bitmapové indexy a na nich vše zakládá. Promluvíme si o tom trochu později.

Implementace v Go

Proč se ale bitmapové indexy tak zřídka používají? Než odpovím na tuto otázku, rád bych vám ukázal, jak implementovat velmi jednoduchý bitmapový index v Go.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Bitmapy jsou v podstatě jen kousky dat. V Go k tomu použijeme bajtové řezy.

Máme jednu bitmapu pro jednu charakteristiku restaurace a každý bit v bitmapě označuje, zda konkrétní restaurace tuto vlastnost má nebo ne.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Budeme potřebovat dvě pomocné funkce. Jeden bude použit k vyplnění našich bitmap náhodnými daty. Náhodné, ale s určitou pravděpodobností, že restaurace má každou vlastnost. Například se domnívám, že v Moskvě je velmi málo restaurací, kde si nemůžete rezervovat stůl, a zdá se mi, že asi 20 % podniků je vhodných pro vegetariány.

Druhá funkce převede bitmapu na seznam restaurací.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Abychom odpověděli na dotaz „Ukažte mi levné restaurace, které mají terasu a mohou provádět rezervace“, potřebujeme dvě bitové operace: NOT a AND.

Náš kód můžeme trochu zjednodušit použitím složitějšího operátoru AND NOT.

Pro každou z těchto operací máme funkce. Oba projdou řezy, z každého vezmou odpovídající prvky, zkombinují je pomocí bitové operace a výsledek vloží do výsledného řezu.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
A nyní můžeme použít naše bitmapy a funkce k zodpovězení vyhledávacího dotazu.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Výkon není tak vysoký, i když funkce jsou velmi jednoduché a ušetřili jsme spoustu peněz tím, že jsme při každém volání funkce nevraceli nový výsledný řez.

Po trochu profilování s pprof jsem si všiml, že kompilátoru Go chybí jedna velmi jednoduchá, ale velmi důležitá optimalizace: funkce inlining.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Faktem je, že kompilátor Go se strašně bojí smyček, které procházejí řezy, a kategoricky odmítá vkládat funkce, které takové smyčky obsahují.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Ale nebojím se a mohu kompilátor oklamat použitím goto místo smyčky, jako za starých dobrých časů.

Bitmapové indexy v Go: vyhledávání divokou rychlostí
Bitmapové indexy v Go: vyhledávání divokou rychlostí

A jak vidíte, kompilátor nyní šťastně vloží naši funkci! Ve výsledku se nám podaří ušetřit asi 2 mikrosekundy. Není špatné!

Bitmapové indexy v Go: vyhledávání divokou rychlostí

Druhé úzké hrdlo lze snadno zjistit, když se pozorně podíváte na výstup sestavy. Kompilátor přidal kontrolu hranice řezu přímo do naší nejžhavější smyčky. Faktem je, že Go je bezpečný jazyk, kompilátor se obává, že mé tři argumenty (tři řezy) jsou různé velikosti. Ostatně pak bude teoretická možnost vzniku tzv. buffer overflow.

Ujistíme kompilátor tím, že mu ukážeme, že všechny řezy mají stejnou velikost. Můžeme to udělat přidáním jednoduché kontroly na začátek naší funkce.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Když to kompilátor vidí, šťastně přeskočí kontrolu a my nakonec ušetříme dalších 500 nanosekund.

Velcí řezníci

Dobře, podařilo se nám z naší jednoduché implementace vymáčknout nějaký výkon, ale tento výsledek je ve skutečnosti mnohem horší, než je možné se současným hardwarem.

Vše, co děláme, jsou základní bitové operace a naše procesory je provádějí velmi efektivně. Ale bohužel „krmíme“ náš procesor velmi malými kousky práce. Naše funkce provádějí operace na bázi bajtu po bajtu. Náš kód můžeme velmi snadno vyladit tak, aby pracoval s 8bajtovými bloky pomocí řezů UInt64.

Bitmapové indexy v Go: vyhledávání divokou rychlostí

Jak můžete vidět, tato malá změna zrychlila náš program osmkrát zvýšením velikosti dávky osmkrát. Zisk lze říci, že je lineární.

Bitmapové indexy v Go: vyhledávání divokou rychlostí

Implementace v assembleru

Bitmapové indexy v Go: vyhledávání divokou rychlostí
Ale to není konec. Naše procesory mohou pracovat s bloky o velikosti 16, 32 a dokonce 64 bajtů. Takové „široké“ operace se nazývají jedna instrukce více dat (SIMD; jedna instrukce, mnoho dat) a proces transformace kódu tak, aby takové operace používal, se nazývá vektorizace.

Kompilátor Go bohužel není zdaleka excelentní ve vektorizaci. V současnosti je jediným způsobem, jak vektorizovat kód Go, vzít a vložit tyto operace ručně pomocí assembleru Go.

Bitmapové indexy v Go: vyhledávání divokou rychlostí

Go assembler je zvláštní zvíře. Pravděpodobně víte, že jazyk symbolických instrukcí je něco, co je silně svázáno s architekturou počítače, pro který píšete, ale to není případ Go. Go assembler je spíše IRL (intermediate representation language) nebo intermediární jazyk: je prakticky nezávislý na platformě. Rob Pike podal výborný výkon zpráva na toto téma před několika lety na GopherCon v Denveru.

Go navíc používá neobvyklý formát Plan 9, který se liší od obecně přijímaných formátů AT&T a Intel.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Dá se s jistotou říci, že ruční psaní Go assembleru není nejzábavnější.

Ale naštěstí již existují dva nástroje na vysoké úrovni, které nám pomáhají psát Go assembler: PeachPy a avo. Oba nástroje generují assembler Go z kódu vyšší úrovně napsaného v Pythonu a Go.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Tyto nástroje zjednodušují věci, jako je alokace registrů, psaní smyček, a obecně zjednodušují proces vstupu do světa programování sestavení v Go.

Budeme používat avo, takže naše programy budou téměř běžné programy Go.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Takto vypadá nejjednodušší příklad avo programu. Máme funkci main(), která v sobě definuje funkci Add(), jejímž smyslem je sečíst dvě čísla. Jsou zde pomocné funkce pro získání parametrů podle názvu a získání jednoho z volných a vhodných registrů procesoru. Každá operace procesoru má odpovídající funkci na avo, jak je vidět v ADDQ. Nakonec vidíme pomocnou funkci pro uložení výsledné hodnoty.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Zavoláním go generation spustíme program na avo a v důsledku toho se vygenerují dva soubory:

  • add.s s výsledným kódem v Go assembleru;
  • stub.go s hlavičkami funkcí pro propojení dvou světů: Go a assembler.

Bitmapové indexy v Go: vyhledávání divokou rychlostí
Nyní, když jsme viděli, co avo dělá a jak, pojďme se podívat na naše funkce. Implementoval jsem jak skalární, tak vektorovou (SIMD) verzi funkcí.

Nejprve se podívejme na skalární verze.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Stejně jako v předchozím příkladu žádáme o bezplatný a platný obecný registr, nepotřebujeme počítat offsety a velikosti argumentů. avo to vše dělá za nás.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Dříve jsme používali štítky a goto (neboli skoky) ke zlepšení výkonu a triku kompilátoru Go, ale teď to děláme od začátku. Jde o to, že cykly jsou konceptem vyšší úrovně. V assembleru máme pouze štítky a skoky.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Zbývající kód by již měl být známý a srozumitelný. Emulujeme smyčku s popisky a skoky, vezmeme malý kousek dat z našich dvou řezů, spojíme je s bitovou operací (A v tomto případě NE) a výsledek pak vložíme do výsledného řezu. Všechno.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Takto vypadá finální kód assembleru. Nemuseli jsme počítat offsety a velikosti (zvýrazněno zeleně) ani sledovat použité registry (zvýrazněno červeně).
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Pokud porovnáme výkon implementace v assembleru s výkonem nejlepší implementace v Go, uvidíme, že je stejný. A to se očekává. Koneckonců jsme nedělali nic zvláštního - jen jsme reprodukovali to, co by udělal kompilátor Go.

Bohužel nemůžeme přinutit kompilátor, aby vložil naše funkce napsané v jazyce symbolických instrukcí. Kompilátor Go v současné době takovou funkci nemá, i když již delší dobu existuje požadavek na její přidání.

To je důvod, proč je nemožné získat jakýkoli užitek z malých funkcí v jazyce symbolických instrukcí. Musíme buď napsat velké funkce, nebo použít nový balíček math/bits, nebo obejít jazyk assembleru.

Podívejme se nyní na vektorové verze našich funkcí.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Pro tento příklad jsem se rozhodl použít AVX2, takže použijeme operace, které fungují na 32bajtových blocích. Struktura kódu je velmi podobná skalární verzi: načítání parametrů, žádost o bezplatný sdílený registr atd.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Jednou z novinek je, že širší vektorové operace používají speciální široké registry. V případě 32bajtových bloků se jedná o registry s předponou Y. Proto v kódu vidíte funkci YMM(). Pokud bych používal AVX-512 s 64bitovými bloky, předpona by byla Z.

Druhou novinkou je, že jsem se rozhodl použít optimalizaci zvanou rozvinování smyčky, což znamená ruční provedení osmi operací smyčky před skokem na začátek smyčky. Tato optimalizace snižuje počet větví v kódu a je omezena počtem dostupných bezplatných registrů.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
No a co výkon? Ona je krásná! Dosáhli jsme zhruba sedminásobného zrychlení ve srovnání s nejlepším řešením Go. Působivé, že?
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Ale i tato implementace by mohla být potenciálně urychlena použitím AVX-512, prefetchingu nebo JIT (just-in-time kompilátor) pro plánovač dotazů. Ale to je jistě téma na samostatnou reportáž.

Problémy s bitmapovými indexy

Nyní, když jsme se již podívali na jednoduchou implementaci bitmapového indexu v Go a mnohem produktivnější implementaci v assembleru, pojďme si konečně promluvit o tom, proč se bitmapové indexy tak zřídka používají.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Starší články zmiňují tři problémy s bitmapovými indexy, ale novější články a já tvrdím, že už nejsou relevantní. Nebudeme se ponořit do hloubky každého z těchto problémů, ale budeme se na ně dívat povrchně.

Problém vysoké kardinality

Bylo nám tedy řečeno, že bitmapové indexy jsou vhodné pouze pro pole s nízkou mohutností, tedy ta, která mají málo hodnot (například pohlaví nebo barva očí), a důvodem je, že obvyklá reprezentace takových polí (jedna bit na hodnotu) v případě vysoké kardinality zabere příliš mnoho místa a navíc se tyto bitmapové indexy budou špatně (zřídka) plnit.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Někdy můžeme použít jinou reprezentaci, například standardní reprezentaci, kterou používáme k reprezentaci čísel. Vše ale změnil příchod kompresních algoritmů. Během posledních desetiletí přišli vědci a výzkumníci s velkým množstvím kompresních algoritmů pro bitmapy. Jejich hlavní výhodou je, že pro provádění bitových operací není potřeba bitmapy dekomprimovat – bitové operace můžeme provádět přímo na komprimovaných bitmapách.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
V poslední době se začínají objevovat hybridní přístupy, jako jsou burcující bitmapy. Používají současně tři různé reprezentace bitmap – bitmapy samotné, pole a takzvané bitové běhy – a balancují mezi nimi, aby maximalizovaly výkon a minimalizovaly spotřebu paměti.

Řvoucí bitmapy najdete v nejoblíbenějších aplikacích. Již existuje obrovské množství implementací pro širokou škálu programovacích jazyků, včetně více než tří implementací pro Go.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Další přístup, který nám může pomoci vypořádat se s vysokou mohutností, se nazývá binning. Představte si, že máte pole představující výšku osoby. Výška je číslo s pohyblivou řádovou čárkou, ale my lidé o ní takto nepřemýšlíme. Pro nás není rozdíl mezi výškou 185,2 cm a 185,3 cm.

Ukazuje se, že podobné hodnoty můžeme seskupit do skupin v rámci 1 cm.

A pokud také víme, že jen velmi málo lidí je menších než 50 cm a vyšších než 250 cm, pak můžeme v podstatě pole s nekonečnou mohutností proměnit na pole s mohutností asi 200 hodnot.

V případě potřeby můžeme samozřejmě dodatečnou filtraci provést dodatečně.

Problém s velkou šířkou pásma

Dalším problémem bitmapových indexů je, že jejich aktualizace může být velmi nákladná.

Databáze musí být schopny aktualizovat data, zatímco potenciálně stovky dalších dotazů prohledávají data. Zámky potřebujeme, abychom se vyhnuli problémům se souběžným přístupem k datům nebo jiným problémům se sdílením. A kde je jeden velký zámek, nastává problém – spor o zámek, kdy se tento zámek stává úzkým hrdlem.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Tento problém lze vyřešit nebo obejít pomocí shardingu nebo pomocí verzovaných indexů.

Sharding je jednoduchá a známá věc. Index bitmapy můžete rozdělit jako jakákoli jiná data. Místo jednoho velkého zámku získáte hromadu malých zámků a zbavíte se tak sporů o zámek.

Druhým způsobem řešení problému je použití verzovaných indexů. Můžete mít jednu kopii rejstříku, kterou používáte pro vyhledávání nebo čtení, a jednu, kterou používáte pro zápis nebo aktualizaci. A jednou za určité časové období (například jednou za 100 ms nebo 500 ms) je duplikujete a prohodíte. Tento přístup je samozřejmě použitelný pouze v případech, kdy vaše aplikace zvládne mírně zaostávající index vyhledávání.

Tyto dva přístupy lze použít současně: můžete mít index s rozdělenou verzí.

Složitější dotazy

Posledním problémem bitmapových indexů je, že nám bylo řečeno, že nejsou příliš vhodné pro složitější typy dotazů, jako jsou dotazy na rozpětí.

Pokud se nad tím zamyslíte, bitové operace jako AND, OR atd. nejsou příliš vhodné pro dotazy typu „Ukaž mi hotely s cenami pokojů od 200 do 300 dolarů za noc“.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Naivním a velmi nemoudrým řešením by bylo vzít výsledky pro každou dolarovou hodnotu a zkombinovat je s bitovou operací OR.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
O něco lepším řešením by bylo použití seskupování. Například ve skupinách po 50 dolarech. To by náš proces urychlilo 50krát.

Ale problém lze také snadno vyřešit pomocí pohledu vytvořeného speciálně pro tento typ požadavku. Ve vědeckých pracích se tomu říká bitmapy zakódované v rozsahu.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
V této reprezentaci nenastavujeme jen jeden bit pro nějakou hodnotu (například 200), ale nastavujeme tuto hodnotu a vše vyšší. 200 a výše. Totéž pro 300:300 a více. A tak dále.

Pomocí této reprezentace můžeme odpovědět na tento druh vyhledávacího dotazu tím, že projdeme index pouze dvakrát. Nejprve získáme seznam hotelů, kde pokoj stojí méně nebo 300 $, a poté z něj odstraníme ty, kde je pokoj nižší nebo 199 $. Připraven.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Budete se divit, ale i geodotazy jsou možné pomocí bitmapových indexů. Trik spočívá v použití geometrického zobrazení, které obklopí vaši souřadnici geometrickým obrazcem. Například S2 od Googlu. Obrázek by mělo být možné znázornit ve formě tří nebo více protínajících se čar, které lze očíslovat. Tímto způsobem můžeme náš geodotaz převést na několik dotazů „podél mezery“ (podle těchto očíslovaných čar).

Připravené řešení

Doufám, že jsem vás trochu zaujal a nyní máte ve svém arzenálu další užitečný nástroj. Pokud budete někdy potřebovat něco takového udělat, budete vědět, jakým směrem se dívat.

Ne každý však má čas, trpělivost nebo prostředky na vytváření bitmapových indexů od začátku. Zejména pokročilejší, využívající například SIMD.

Naštěstí existuje několik hotových řešení, která vám pomohou.
Bitmapové indexy v Go: vyhledávání divokou rychlostí

Řvoucí bitmapy

Za prvé, existuje stejná knihovna bitmap, o které jsem již mluvil. Obsahuje všechny potřebné kontejnery a bitové operace, které budete potřebovat k vytvoření plnohodnotného bitmapového indexu.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Bohužel v tuto chvíli žádná z implementací Go nepoužívá SIMD, což znamená, že implementace Go jsou méně výkonné než například implementace C.

chlupatý

Dalším produktem, který vám může pomoci, je Pilosa DBMS, který má ve skutečnosti pouze bitmapové indexy. Jedná se o relativně nové řešení, které si však získává srdce obrovskou rychlostí.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Pilosa interně používá burcující bitmapy a dává vám možnost je používat, zjednodušuje a vysvětluje všechny věci, o kterých jsem mluvil výše: seskupování, bitmapy s rozsahem kódování, koncept pole atd.

Pojďme se rychle podívat na příklad použití Pilosa k zodpovězení otázky, kterou již znáte.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Příklad je velmi podobný tomu, co jste viděli dříve. Vytvoříme klienta pro server Pilosa, vytvoříme index a potřebná pole, poté naplníme naše pole náhodnými údaji s pravděpodobnostmi a nakonec provedeme známý dotaz.

Poté použijeme NOT v poli "drahé" a pak protneme výsledek (nebo AND) s polem "terasa" a polem "rezervace". A konečně se dostáváme ke konečnému výsledku.
Bitmapové indexy v Go: vyhledávání divokou rychlostí
Pevně ​​doufám, že se tento nový typ indexu v dohledné době objeví i v DBMS jako MySQL a PostgreSQL - bitmapové indexy.
Bitmapové indexy v Go: vyhledávání divokou rychlostí

Závěr

Bitmapové indexy v Go: vyhledávání divokou rychlostí
Pokud jste ještě neusnuli, děkuji. Kvůli omezenému času jsem se musel krátce dotknout mnoha témat, ale doufám, že přednáška byla užitečná a možná i motivující.

Bitmapové indexy je dobré vědět, i když je zrovna nepotřebujete. Nechte je být dalším nástrojem ve vaší sadě nástrojů.

Podívali jsme se na různé výkonnostní triky pro Go a věci, které kompilátor Go zatím příliš nezvládá. Ale to je naprosto užitečné pro každého programátora Go vědět.

To je vše, co jsem vám chtěl říct. Děkuji!

Zdroj: www.habr.com

Přidat komentář