úvod
Túto správu som podal v angličtine na konferencii GopherCon Russia 2019 v Moskve a v ruštine na stretnutí v Nižnom Novgorode. Hovoríme o bitmapovom indexe - menej bežnom ako B-strom, ale nemenej zaujímavom. Zdieľanie vystúpenia na konferencii v angličtine a prepisy textov v ruštine.
Pozrieme sa, ako funguje bitmapový index, kedy je lepší, kedy horší ako ostatné indexy a v akých prípadoch je výrazne rýchlejší ako oni; Pozrime sa, ktoré populárne DBMS už majú bitmapové indexy; Skúsme si v Go napísať vlastné. A „na dezert“ použijeme hotové knižnice na vytvorenie vlastnej superrýchlej špecializovanej databázy.
Naozaj dúfam, že moje práce budú pre vás užitočné a zaujímavé. Choď!
Úvod
Ahojte všetci! Je šesť hodín večer a všetci sme strašne unavení. Skvelý čas hovoriť o nudnej teórii indexov databázy, však? Nebojte sa, tu a tam budem mať pár riadkov zdrojového kódu. 🙂
Všetky žarty bokom, správa je preplnená informáciami a nemáme veľa času. Tak poďme na to.
Dnes budem hovoriť o nasledujúcom:
- čo sú indexy;
- čo je bitmapový index;
- kde sa používa a kde sa NEPOUŽÍVA a prečo;
- jednoduchá implementácia v Go a malý boj s kompilátorom;
- o niečo menej jednoduchá, ale oveľa produktívnejšia implementácia v Go assembleri;
- „problémy“ bitmapových indexov;
- existujúce implementácie.
Čo sú teda indexy?
Index je samostatná dátová štruktúra, ktorú udržiavame a aktualizujeme popri hlavných dátach. Používa sa na urýchlenie vyhľadávania. Bez indexov by vyhľadávanie vyžadovalo úplné prechádzanie údajov (proces nazývaný úplné skenovanie) a tento proces má lineárnu algoritmickú zložitosť. Ale databázy zvyčajne obsahujú obrovské množstvo údajov a lineárna zložitosť je príliš pomalá. V ideálnom prípade by sme dostali logaritmickú alebo konštantnú hodnotu.
Ide o mimoriadne zložitú tému, ktorá je plná jemností a kompromisov, ale po pohľade na desaťročia vývoja a výskumu databáz som ochotný povedať, že existuje len niekoľko široko používaných prístupov k vytváraniu databázových indexov.
Prvým prístupom je hierarchicky zmenšiť vyhľadávací priestor a rozdeliť ho na menšie časti.
Zvyčajne to robíme pomocou rôznych druhov stromov. Príkladom môže byť veľká krabica s materiálmi vo vašom šatníku, ktorá obsahuje menšie krabice s materiálmi rozdelené do rôznych tém. Ak potrebujete materiály, pravdepodobne ich budete hľadať v poli s nápisom „Materiály“ a nie v poli „Súbory cookie“, však?
Druhým prístupom je okamžitý výber požadovaného prvku alebo skupiny prvkov. Robíme to v hašovacích mapách alebo reverzných indexoch. Použitie hash máp je veľmi podobné predchádzajúcemu príkladu, ale namiesto škatuľky krabičiek máte v skrini kopu malých krabičiek finálnych predmetov.
Tretím prístupom je eliminácia potreby hľadania. Robíme to pomocou Bloom filtrov alebo kukučkových filtrov. Prvé dávajú odpoveď okamžite, čo vám ušetrí hľadanie.
Posledným prístupom je naplno využiť všetku silu, ktorú nám dáva moderný hardvér. To je presne to, čo robíme v bitmapových indexoch. Áno, pri ich používaní niekedy potrebujeme prejsť celý index, ale robíme to super efektívne.
Ako som povedal, téma databázových indexov je rozsiahla a plná kompromisov. To znamená, že niekedy môžeme použiť viacero prístupov súčasne: ak potrebujeme vyhľadávanie ešte zrýchliť, alebo ak potrebujeme pokryť všetky možné typy vyhľadávania.
Dnes budem hovoriť o najmenej známom prístupe z nich - bitmapových indexoch.
Kto som, aby som hovoril na túto tému?
Pracujem ako vedúci tímu v Badoo (možno vám je viac známy náš ďalší produkt, Bumble). Už máme viac ako 400 miliónov používateľov na celom svete a mnoho funkcií, ktoré im vyberú tú najlepšiu. Robíme to pomocou vlastných služieb, vrátane bitmapových indexov.
Čo je teda index bitovej mapy?
Bitmapové indexy, ako už názov napovedá, používajú bitmapy alebo bitové sady na implementáciu indexu vyhľadávania. Z vtáčej perspektívy tento index pozostáva z jednej alebo viacerých bitmapových máp reprezentujúcich ľubovoľné entity (ako sú ľudia) a ich vlastností alebo parametrov (vek, farba očí atď.) a algoritmus využívajúci bitové operácie (AND, OR, NOT ), aby ste odpovedali na vyhľadávací dopyt.
Bolo nám povedané, že bitmapové indexy sú najvhodnejšie a veľmi výkonné v prípadoch, keď existujú vyhľadávania, ktoré kombinujú dopyty v mnohých stĺpcoch s nízkou mohutnosťou (myslite si, že „farba očí“ alebo „rodinný stav“ alebo niečo ako „vzdialenosť od centra mesta“ ). Ale neskôr ukážem, že fungujú dobre aj pre stĺpce s vysokou mohutnosťou.
Pozrime sa na najjednoduchší príklad indexu bitmapy.
Predstavte si, že máme zoznam moskovských reštaurácií s binárnymi vlastnosťami, ako sú tieto:
- v blízkosti metra;
- k dispozícii je súkromné parkovisko;
- je tu veranda (má terasu);
- môžete si rezervovať stôl (prijíma rezervácie);
- vhodné pre vegetariánov (vegan friendly);
- drahé (drahé).
Dajme každej reštaurácii poradové číslo začínajúce od 0 a prideľme pamäť pre 6 bitových máp (jedna pre každú charakteristiku). Tieto bitmapy potom vyplníme podľa toho, či má reštaurácia túto vlastnosť alebo nie. Ak má reštaurácia 4 verandu, potom bit č. 4 v bitovej mape „má verandu“ bude nastavený na 1 (ak veranda nie je, potom na 0).
Teraz máme najjednoduchší možný index bitmapy a môžeme ho použiť na zodpovedanie otázok, ako sú:
- „Ukáž mi reštaurácie vhodné pre vegetariánov“;
- “Ukážte mi lacné reštaurácie s verandou, kde si môžete rezervovať stôl.”
Ako? Poďme sa pozrieť. Prvá požiadavka je veľmi jednoduchá. Všetko, čo musíme urobiť, je vziať „vegetariánsky priateľský“ bitmapu a premeniť ju na zoznam reštaurácií, ktorých kúsky sú vystavené.
Druhá požiadavka je trochu komplikovanejšia. Potrebujeme použiť bitmapu NOT na „drahej“ bitmape, aby sme získali zoznam lacných reštaurácií, potom A to s bitmapou „môžem si rezervovať stôl“ a A výsledok s bitmapou „existuje veranda“. Výsledná bitmapa bude obsahovať zoznam prevádzok, ktoré spĺňajú všetky naše kritériá. V tomto príklade ide iba o reštauráciu Yunost.
Je v tom veľa teórie, ale nebojte sa, kód uvidíme veľmi skoro.
Kde sa používajú bitmapové indexy?
Ak indexujete bitmapové mapy Google, 90 % odpovedí bude tak či onak súvisieť s Oracle DB. Ale iné DBMS pravdepodobne tiež podporujú takúto skvelú vec, však? Nie naozaj.
Poďme si prejsť zoznam hlavných podozrivých.
MySQL zatiaľ nepodporuje bitmapové indexy, ale existuje návrh, ktorý navrhuje pridať túto možnosť ().
PostgreSQL nepodporuje bitmapové indexy, ale používa jednoduché bitové mapy a bitové operácie na kombinovanie výsledkov vyhľadávania vo viacerých iných indexoch.
Tarantool má bitsetové indexy a podporuje jednoduché vyhľadávanie v nich.
Redis má jednoduché bitové polia) bez možnosti ich vyhľadať.
MongoDB zatiaľ nepodporuje bitmapové indexy, ale existuje aj návrh, ktorý navrhuje pridať túto možnosť
Elasticsearch interne používa bitmapy).
- Ale v našom dome sa objavil nový sused: Pilosa. Toto je nová nerelačná databáza napísaná v Go. Obsahuje len bitmapové indexy a na nich všetko zakladá. Povieme si o tom trochu neskôr.
Implementácia v Go
Prečo sa však bitmapové indexy tak zriedka používajú? Pred zodpovedaním tejto otázky by som vám rád ukázal, ako implementovať veľmi jednoduchý index bitmapy v Go.
Bitmapy sú v podstate len kúsky údajov. V Go na to použijeme bajtové rezy.
Máme jednu bitovú mapu pre jednu charakteristiku reštaurácie a každý bit v bitovej mape označuje, či má konkrétna reštaurácia túto vlastnosť alebo nie.
Budeme potrebovať dve pomocné funkcie. Jeden sa použije na vyplnenie našich bitových máp náhodnými údajmi. Náhodné, ale s určitou pravdepodobnosťou, že reštaurácia má každú vlastnosť. Napríklad si myslím, že v Moskve je veľmi málo reštaurácií, kde si nemôžete rezervovať stôl, a zdá sa mi, že asi 20 % podnikov je vhodných pre vegetariánov.
Druhá funkcia prevedie bitmapu na zoznam reštaurácií.
Aby sme odpovedali na otázku „Ukáž mi lacné reštaurácie, ktoré majú terasu a môžu robiť rezervácie“, potrebujeme dve bitové operácie: NOT a AND.
Náš kód môžeme trochu zjednodušiť použitím zložitejšieho operátora AND NOT.
Pre každú z týchto operácií máme funkcie. Obaja prechádzajú rezmi, z každého odoberajú zodpovedajúce prvky, kombinujú ich s trochou operácie a výsledok vložia do výsledného rezu.
A teraz môžeme použiť naše bitmapy a funkcie na zodpovedanie vyhľadávacieho dotazu.
Výkon nie je taký vysoký, aj keď funkcie sú veľmi jednoduché a ušetrili sme veľa peňazí tým, že sme pri každom volaní funkcie nevracali nový výsledný rez.
Po troche profilovania s pprof som si všimol, že kompilátoru Go chýba jedna veľmi jednoduchá, ale veľmi dôležitá optimalizácia: funkcia inlining.
Faktom je, že kompilátor Go sa strašne bojí slučiek, ktoré prechádzajú rezmi, a kategoricky odmieta vkladať funkcie, ktoré takéto slučky obsahujú.
Ale nebojím sa a kompilátor môžem oklamať použitím goto namiesto slučky, ako za starých dobrých čias.
A ako vidíte, kompilátor teraz šťastne vloží našu funkciu! Vďaka tomu sa nám podarí ušetriť približne 2 mikrosekundy. Nie zlé!
Druhé úzke miesto je ľahké zistiť, ak sa pozorne pozriete na výstup zostavy. Kompilátor pridal kontrolu hranice rezu priamo do našej najhorúcejšej slučky. Faktom je, že Go je bezpečný jazyk, kompilátor sa obáva, že moje tri argumenty (tri plátky) sú rôznej veľkosti. Koniec koncov, potom bude existovať teoretická možnosť výskytu takzvaného pretečenia vyrovnávacej pamäte.
Ubezpečme kompilátor tým, že mu ukážeme, že všetky rezy majú rovnakú veľkosť. Môžeme to urobiť pridaním jednoduchej kontroly na začiatok našej funkcie.
Keď to kompilátor vidí, šťastne preskočí kontrolu a nakoniec ušetríme ďalších 500 nanosekúnd.
Veľké buchy
Dobre, podarilo sa nám z našej jednoduchej implementácie vyžmýkať nejaký výkon, ale tento výsledok je v skutočnosti oveľa horší, ako je možné so súčasným hardvérom.
Všetko, čo robíme, sú základné bitové operácie a naše procesory ich vykonávajú veľmi efektívne. Ale, žiaľ, „kŕmime“ náš procesor veľmi malými kusmi práce. Naše funkcie vykonávajú operácie na báze bajtu po byte. Náš kód môžeme veľmi jednoducho vyladiť tak, aby pracoval s 8-bajtovými blokmi pomocou rezov UInt64.
Ako môžete vidieť, táto malá zmena zrýchlila náš program osemkrát tým, že osemkrát zvýšila veľkosť dávky. Zisk možno povedať, že je lineárny.
Implementácia v assembleri
To však nie je koniec. Naše procesory dokážu pracovať s blokmi 16, 32 a dokonca 64 bajtov. Takéto „široké“ operácie sa nazývajú single inštrukcie multiple data (SIMD; jedna inštrukcia, veľa údajov) a proces transformácie kódu tak, aby využíval takéto operácie, sa nazýva vektorizácia.
Bohužiaľ, kompilátor Go nie je ani zďaleka vynikajúci vo vektorizácii. V súčasnosti je jediným spôsobom, ako vektorizovať kód Go, vziať a zadať tieto operácie manuálne pomocou zostavy Go.
Go assembler je zvláštne zviera. Pravdepodobne viete, že jazyk symbolických inštrukcií je niečo, čo je úzko späté s architektúrou počítača, pre ktorý píšete, ale to nie je prípad Go. Go assembler je skôr IRL (jazyk strednej reprezentácie) alebo stredný jazyk: je prakticky nezávislý od platformy. Rob Pike podal výborný výkon na túto tému pred niekoľkými rokmi na GopherCon v Denveri.
Go navyše používa nezvyčajný formát Plan 9, ktorý sa líši od všeobecne akceptovaných formátov AT&T a Intel.
Dá sa povedať, že ručné písanie Go assembleru nie je práve najzábavnejšie.
Ale našťastie už existujú dva nástroje na vysokej úrovni, ktoré nám pomáhajú písať Go assembler: PeachPy a avo. Obidva nástroje generujú assembler Go z kódu vyššej úrovne napísaného v Pythone a Go.
Tieto nástroje zjednodušujú veci, ako je prideľovanie registrov, písanie slučiek a vo všeobecnosti zjednodušujú proces vstupu do sveta programovania zostavy v Go.
Budeme používať avo, takže naše programy budú takmer bežné programy Go.
Takto vyzerá najjednoduchší príklad avo programu. Máme funkciu main(), ktorá v sebe definuje funkciu Add(), ktorej významom je sčítanie dvoch čísel. Existujú pomocné funkcie na získanie parametrov podľa názvu a získanie jedného z bezplatných a vhodných registrov procesora. Každá operácia procesora má zodpovedajúcu funkciu na avo, ako je vidieť v ADDQ. Nakoniec vidíme pomocnú funkciu na uloženie výslednej hodnoty.
Volaním go generation spustíme program na avo a výsledkom budú dva súbory:
- add.s s výsledným kódom v Go assembleri;
- stub.go s hlavičkami funkcií na prepojenie dvoch svetov: Go a assembler.
Teraz, keď sme videli, čo avo robí a ako, pozrime sa na naše funkcie. Implementoval som skalárnu aj vektorovú (SIMD) verziu funkcií.
Najprv sa pozrime na skalárne verzie.
Rovnako ako v predchádzajúcom príklade, žiadame o bezplatný a platný register na všeobecné použitie, nepotrebujeme počítať posuny a veľkosti argumentov. avo to všetko robí za nás.
Používali sme štítky a goto (alebo skoky) na zlepšenie výkonu a oklamanie kompilátora Go, ale teraz to robíme od začiatku. Ide o to, že cykly sú koncepciou vyššej úrovne. V assembleri máme len štítky a skoky.
Zostávajúci kód by už mal byť známy a zrozumiteľný. Emulujeme slučku s menovkami a skokmi, vezmeme malý kúsok dát z našich dvoch rezov, skombinujeme ich s bitovou operáciou (A NIE v tomto prípade) a potom výsledok vložíme do výsledného rezu. Všetky.
Takto vyzerá konečný kód assembleru. Nemuseli sme počítať posuny a veľkosti (zvýraznené zelenou farbou) ani sledovať používané registre (zvýraznené červenou farbou).
Ak porovnáme výkon implementácie v assembleri s výkonom najlepšej implementácie v Go, uvidíme, že je rovnaký. A toto sa očakáva. Koniec koncov, neurobili sme nič špeciálne - len sme reprodukovali to, čo by urobil kompilátor Go.
Bohužiaľ, nemôžeme prinútiť kompilátor, aby vložil naše funkcie napísané v jazyku symbolických inštancií. Kompilátor Go v súčasnosti takúto funkciu nemá, aj keď už pomerne dlho existuje požiadavka na jej pridanie.
To je dôvod, prečo nie je možné získať žiadne výhody z malých funkcií v jazyku symbolických inštancií. Musíme buď napísať veľké funkcie, alebo použiť nový balík math/bits, alebo obísť jazyk assembler.
Pozrime sa teraz na vektorové verzie našich funkcií.
Pre tento príklad som sa rozhodol použiť AVX2, takže použijeme operácie, ktoré fungujú na 32-bajtových blokoch. Štruktúra kódu je veľmi podobná skalárnej verzii: načítanie parametrov, žiadosť o bezplatný zdieľaný register atď.
Jednou z inovácií je, že širšie vektorové operácie využívajú špeciálne široké registre. V prípade 32-bajtových blokov ide o registre s predponou Y. Preto v kóde vidíte funkciu YMM(). Ak by som používal AVX-512 so 64-bitovými blokmi, predpona by bola Z.
Druhou novinkou je, že som sa rozhodol použiť optimalizáciu nazývanú rozbalenie slučky, čo znamená manuálne vykonať osem operácií slučky pred skokom na začiatok slučky. Táto optimalizácia znižuje počet vetiev v kóde a je obmedzená počtom dostupných bezplatných registrov.
No a čo výkon? Je krásna! Dosiahli sme asi sedemnásobné zrýchlenie v porovnaní s najlepším riešením Go. Pôsobivé, však?
Ale aj táto implementácia by mohla byť potenciálne urýchlená použitím AVX-512, predbežného načítania alebo JIT (just-in-time kompilátor) pre plánovač dotazov. Ale to je určite téma na samostatnú správu.
Problémy s bitmapovými indexmi
Teraz, keď sme sa už pozreli na jednoduchú implementáciu bitmapového indexu v Go a oveľa produktívnejšiu implementáciu v assembleri, poďme si konečne povedať, prečo sa bitmapové indexy tak zriedka používajú.
Staršie články uvádzajú tri problémy s bitmapovými indexmi, ale novšie články a tvrdím, že už nie sú relevantné. Nebudeme sa ponoriť hlboko do každého z týchto problémov, ale pozrieme sa na ne povrchne.
Problém vysokej kardinality
Takže nám bolo povedané, že bitmapové indexy sú vhodné iba pre polia s nízkou mohutnosťou, teda tie, ktoré majú málo hodnôt (napríklad pohlavie alebo farba očí), a dôvodom je, že zvyčajná reprezentácia takýchto polí (jedna bit za hodnotu) v prípade vysokej kardinality zaberie príliš veľa miesta a navyše sa tieto bitmapové indexy budú zle (zriedka) vypĺňať.
Niekedy môžeme použiť inú reprezentáciu, napríklad štandardnú reprezentáciu, ktorú používame na reprezentáciu čísel. Všetko však zmenil príchod kompresných algoritmov. Počas posledných desaťročí vedci a výskumníci prišli s veľkým počtom kompresných algoritmov pre bitové mapy. Ich hlavnou výhodou je, že na vykonávanie bitových operácií nie je potrebné dekomprimovať bitové mapy – bitové operácie môžeme vykonávať priamo na komprimovaných bitmapách.
V poslednej dobe sa začínajú objavovať hybridné prístupy, ako napríklad burcujúce bitmapy. Súbežne používajú tri rôzne reprezentácie pre bitové mapy – samotné bitové mapy, polia a takzvané bitové behy – a balansujú medzi nimi, aby maximalizovali výkon a minimalizovali spotrebu pamäte.
V najpopulárnejších aplikáciách nájdete burácajúce bitmapy. Existuje už obrovské množstvo implementácií pre širokú škálu programovacích jazykov, vrátane viac ako troch implementácií pre Go.
Ďalší prístup, ktorý nám môže pomôcť vysporiadať sa s vysokou kardinalitou, sa nazýva binning. Predstavte si, že máte pole predstavujúce výšku osoby. Výška je číslo s pohyblivou rádovou čiarkou, no my ľudia o nej takto neuvažujeme. Pre nás nie je rozdiel medzi výškou 185,2 cm a 185,3 cm.
Ukazuje sa, že podobné hodnoty môžeme zoskupiť do skupín v rámci 1 cm.
A ak vieme, že len veľmi málo ľudí je menších ako 50 cm a vyšších ako 250 cm, potom môžeme v podstate zmeniť pole s nekonečnou mohutnosťou na pole s mohutnosťou okolo 200 hodnôt.
Samozrejme, ak je to potrebné, môžeme dodatočne filtrovať dodatočne.
Problém vysokej šírky pásma
Ďalším problémom bitmapových indexov je, že ich aktualizácia môže byť veľmi nákladná.
Databázy musia byť schopné aktualizovať údaje, zatiaľ čo potenciálne stovky ďalších dopytov vyhľadávajú údaje. Potrebujeme zámky, aby sme sa vyhli problémom so súbežným prístupom k údajom alebo iným problémom so zdieľaním. A tam, kde je jeden veľký zámok, nastáva problém – spor o zámok, keď sa tento zámok stane prekážkou.
Tento problém je možné vyriešiť alebo obísť použitím shardingu alebo použitím verziovaných indexov.
Sharding je jednoduchá a známa vec. Index bitmapy môžete roztrhať ako akékoľvek iné údaje. Namiesto jedného veľkého zámku získate kopu malých zámkov a zbavíte sa tak sporu o zámok.
Druhým spôsobom riešenia problému je použitie verziovaných indexov. Môžete mať jednu kópiu indexu, ktorú používate na vyhľadávanie alebo čítanie, a jednu kópiu, ktorú používate na písanie alebo aktualizáciu. A raz za určité časové obdobie (napríklad raz za 100 ms alebo 500 ms) ich duplikujete a vymeníte. Samozrejme, tento prístup je použiteľný iba v prípadoch, keď vaša aplikácia zvládne mierne oneskorený index vyhľadávania.
Tieto dva prístupy je možné použiť súčasne: môžete mať rozdelený index s verziou.
Zložitejšie otázky
Posledným problémom bitmapových indexov je, že nám bolo povedané, že nie sú vhodné pre zložitejšie typy dopytov, ako sú napríklad dopyty na rozpätie.
Ak sa nad tým zamyslíte, bitové operácie ako AND, OR atď. nie sú veľmi vhodné pre dopyty typu „Ukáž mi hotely s cenami od 200 do 300 dolárov za noc“.
Naivným a veľmi nerozumným riešením by bolo vziať výsledky pre každú hodnotu v dolároch a skombinovať ich s bitovou operáciou OR.
O niečo lepším riešením by bolo použiť zoskupovanie. Napríklad v skupinách po 50 dolároch. To by náš proces zrýchlilo 50-krát.
Ale problém je tiež ľahko vyriešený pomocou zobrazenia vytvoreného špeciálne pre tento typ požiadavky. Vo vedeckých prácach sa to nazýva bitmapy zakódované v rozsahu.
V tejto reprezentácii nenastavíme len jeden bit pre nejakú hodnotu (napríklad 200), ale nastavíme túto hodnotu a všetko vyššie. 200 a vyššie. To isté pre pomer 300:300 a viac. A tak ďalej.
Pomocou tejto reprezentácie môžeme odpovedať na tento druh vyhľadávacieho dopytu tak, že index prejdeme iba dvakrát. Najprv dostaneme zoznam hotelov, kde izba stojí menej alebo 300 dolárov, a potom z neho odstránime tie, kde je cena za izbu nižšia alebo 199 dolárov. Pripravený.
Budete prekvapení, ale aj geodotazy sú možné pomocou bitmapových indexov. Trik spočíva v použití geometrického znázornenia, ktoré obklopuje vašu súradnicu geometrickým obrazcom. Napríklad S2 od Google. Obrázok by malo byť možné znázorniť vo forme troch alebo viacerých pretínajúcich sa čiar, ktoré možno očíslovať. Takto môžeme náš geodotaz premeniť na niekoľko dopytov „pozdĺž medzery“ (pozdĺž týchto očíslovaných riadkov).
Pripravené riešenia
Dúfam, že som vás trochu zaujal a teraz máte vo svojom arzenáli ďalší užitočný nástroj. Ak budete niekedy potrebovať niečo také urobiť, budete vedieť, akým smerom sa máte pozerať.
Nie každý však má čas, trpezlivosť alebo zdroje na vytváranie indexov bitmap od začiatku. Najmä tie pokročilejšie, využívajúce napríklad SIMD.
Našťastie existuje niekoľko hotových riešení, ktoré vám pomôžu.
Búrlivé bitmapy
Po prvé, existuje rovnaká knižnica bitmapových máp, o ktorej som už hovoril. Obsahuje všetky potrebné kontajnery a bitové operácie, ktoré budete potrebovať na vytvorenie plnohodnotného bitmapového indexu.
Žiaľ, v súčasnosti žiadna z implementácií Go nepoužíva SIMD, čo znamená, že implementácie Go sú napríklad menej výkonné ako implementácie v jazyku C.
chlpatý
Ďalším produktom, ktorý vám môže pomôcť, je Pilosa DBMS, ktorý má v skutočnosti iba bitmapové indexy. Ide o relatívne nové riešenie, ktoré si však získava srdcia veľkou rýchlosťou.
Pilosa interne používa burcujúce bitmapy a dáva vám možnosť ich používať, zjednodušuje a vysvetľuje všetky veci, o ktorých som hovoril vyššie: zoskupovanie, rozsahovo kódované bitmapy, koncept poľa atď.
Poďme sa rýchlo pozrieť na príklad použitia Pilosa na zodpovedanie otázky, ktorú už poznáte.
Príklad je veľmi podobný tomu, čo ste videli predtým. Vytvoríme klienta pre server Pilosa, vytvoríme index a potrebné polia, potom naplníme naše polia náhodnými údajmi s pravdepodobnosťou a nakoniec vykonáme známy dotaz.
Potom použijeme NOT v poli "drahé" a potom pretíname výsledok (alebo AND) s poľom "terasa" as poľom "rezervácie". A nakoniec sa dostávame ku konečnému výsledku.
Naozaj dúfam, že v dohľadnej dobe sa tento nový typ indexu objaví aj v DBMS ako MySQL a PostgreSQL - bitmapové indexy.
Záver
Ak ste ešte nezaspali, ďakujem. Kvôli obmedzenému času som sa musel krátko dotknúť mnohých tém, ale dúfam, že prednáška bola užitočná a možno aj motivujúca.
Bitmapové indexy je dobré vedieť, aj keď ich práve nepotrebujete. Nech sú ďalším nástrojom vo vašej súprave nástrojov.
Pozreli sme sa na rôzne výkonnostné triky pre Go a veci, ktoré kompilátor Go zatiaľ príliš nezvláda. To je však absolútne užitočné pre každého programátora Go.
To je všetko, čo som vám chcel povedať. Ďakujem!
Zdroj: hab.com