Bevezető szó
Ezt az előadást angolul tartottam a GopherCon Russia 2019 konferencián Moszkvában, majd oroszul a nyizsnyij novgorodi meetupon. A téma a bitmap-index, amely bár kevésbé elterjedt, mint a B-fa, de nem kevésbé érdekes. Osztom meg veletek felvételét angolul és a szöveges átiratát oroszul.
Megvizsgáljuk, hogyan működik a bitmap-index, mikor jobb, mikor rosszabb más indexekhez képest, és milyen esetekben gyorsabb jelentősen náluk; megnézzük, mely népszerű DBMS-ekben találhatóak már bitmap-indexek; megpróbálunk írni egyet Go nyelven. Desszertként pedig meglévő könyvtárakat használunk, hogy létrehozzuk saját szupergyors, speciális adatbázisunkat.
Nagyon remélem, hogy a munkám hasznos és érdekes lesz számotokra. Induljunk!
Bevezetés
Helló mindenkinek! Most este hat óra van, mindannyian nagyon fáradtak vagyunk. Remek időpont beszélni az unalmas adatbázisok indexelésének elméletéről, igaz? Ne aggódjatok, itt-ott lesz egy-két sor forráskód. 🙂
Ha komolyan vesszük, az előadás tele van információval, és nem sok időnk van. Szóval kezdjünk bele.
Ma a következőkről fogok beszélni:
- mi az index;
- mi az a bitmap-index;
- hol használják és hol NEM használják, és miért;
- egyszerű implementation Go nyelven, és egy kis küzdelem a fordítóval;
- egy valamivel bonyolultabb, de sokkal teljesítménybeli kiváló Go assembly implementation;
- a bitmap-indexek "problémái";
- létező megvalósítások.
De mi is az index?
Az index egy különálló adatstruktúra, amelyet a fő adatok mellett tartunk és frissítünk. Azért használjuk, hogy felgyorsítsuk a keresést. Indexek nélkül a keresés teljes adatátjárást igényelne (ezt a folyamatot teljes átvizsgálásnak hívják), és ennek a folyamatnak lineáris algoritmikus bonyolultsága van. De az adatbázisok általában hatalmas mennyiségű adatot tartalmaznak, és a lineáris bonyolultság túl lassú. Ideális esetben logaritmikus vagy állandó bonyolultságra lenne szükségünk.
Ez egy hatalmas, komplex téma, tele finomságokkal és kompromisszummal, de néhány évtizednyi különböző adatbázisok fejlesztésének és kutatásának megtekintése után kész vagyok kijelenteni, hogy csak néhány széles körben használt megközelítés létezik az adatbázis-indexek létrehozására.
Az első megközelítés a keresési terület hierarchikus csökkentésén alapul, amely a keresési terület kisebb részekre osztását jelenti.
Jellemzően különféle fákat használunk ehhez. Például képzeljünk el egy nagy dobozt az anyagokkal a szekrényében, amelyben kisebb dobozok találhatók, különböző témák szerint elválasztva. Ha szüksége van anyagokra, valószínűleg a "Materiálok" feliratú dobozban fog keresni, nem pedig abban, amelyen "Sütemények" áll, ugye?
A második megközelítés az, hogy azonnal kiemeljük a szükséges elemet vagy elemek csoportját. Ezt hash map-ekben vagy fordított indexekben valósítjuk meg. A hash map-ek használata nagyon hasonló az előző példához, csak itt a sok kisebb doboz helyett a szekrényében végső tárgyakkal teli kis dobozok találhatók.
A harmadik megközelítés a keresés szükségességének eltüntetése. Ezt Bloom filterekkel vagy cuckoo filterekkel valósítjuk meg. Az elsőek azonnali választ adnak, megszabadítva Önt a keresés szükségességétől.
Az utolsó megközelítés pedig teljes mértékben a modern hardver adta lehetőségek kihasználására épít. Ezt valósítjuk meg bitmap indexekkel. Igen, használatukkor néha végig kell járnunk az egész indexet, de ezt szuper hatékonyan tesszük.
Ahogy már említettem, az adatbázis-indexek témája széles és tele van kompromisszumokkal. Ez azt jelenti, hogy néha több megközelítést is egyidejűleg alkalmazhatunk: ha még gyorsabb keresésre van szükségünk, vagy ha minden lehetséges keresési típusra ki kell terjednünk.
Ma a fenti megközelítések közül a legkevésbé ismerttel fogok foglalkozni — a bitmap indexekkel.
Ki vagyok én, hogy erről beszéljek?
Én a Badoo-nál dolgozom csapatvezetőként (lehet, hogy jobban ismeri másik termékünket — a Bumble-t). Már több mint 400 millió felhasználónk van világszerte, és sok funkcióval rendelkezünk, amelyek a legjobb pár keresésével foglalkoznak. Ezt egyedi szolgáltatások segítségével végezzük, amelyek között szerepelnek a bitmap indexek is.
De mi is az a bitmap index?
A bitmap index, as the name suggests, uses bitmaps or bitsets to implement a search index. From a bird's-eye view, this index consists of one or more such bitmaps representing entities (like people) and their properties or parameters (age, eye color, etc.), along with an algorithm that uses bitwise operations (AND, OR, NOT) to respond to search queries.
We are told that bitmap indexes are best suited and very efficient for cases where there is a search that combines queries across many columns with low cardinality (imagine 'eye color' or 'marital status' versus something like 'distance from the city center'). However, I will later show that they also work well with columns of high cardinality.
Let's consider a simple example of a bitmap index.
Imagine we have a list of Moscow restaurants with binary properties like these:
- near metro;
- has private parking;
- has terrace;
- accepts reservations;
- vegan friendly;
- expensive.
Let’s assign each restaurant a sequential number starting from 0 and allocate memory for 6 bitmaps (one for each characteristic). Then we will fill these bitmaps based on whether the restaurant has this property or not. If restaurant 4 has a terrace, then bit number 4 in the 'has terrace' bitmap will be set to 1 (if there is no terrace, it will be 0).
Now we have the simplest bitmap index possible, and we can use it to respond to queries like:
- "Show me restaurants that are vegan friendly";
- "Show me inexpensive restaurants with a terrace where reservations are accepted."
How? Let’s see. The first query is very simple. All we need to do is take the bitmap 'vegan friendly' and convert it into a list of restaurants whose bits are set.
A második kérdés egy kicsit bonyolultabb. Számítási NOT bitműveletet kell használnunk a "drága" bitmátrixra, hogy megkapjuk az olcsó éttermek listáját, majd ezt AND operátorral egyesíteni kell a "asztalt lehet foglalni" bitmátrix-szal, és az eredményt AND operátorral egyesíteni a "van terasz" bitmátrix-szal. A végső bitmátrix tartalmazni fogja azokat a létesítményeket, amelyek megfelelnek minden kritériumunknak. Ebben a példában ez csak a „Jugend” étterem.
Itt nagyon sok elmélet van, de ne aggódj, hamarosan látni fogjuk a kódot.
Hol használják a bitmaps indexeket?
Ha rákeresel a bitmaps indexekre, a válaszok 90%-a valamilyen módon kapcsolódik az Oracle DB-hez. De más adatbázis-kezelők is biztosan támogatják ezt a szuper dolgot, igaz?
Nézzük át a gyanúsítottak listáját.
A MySQL még nem támogatja a bitmap indexeket, de van javaslat ennek a lehetőségnek a hozzáadására ().
A PostgreSQL nem támogatja a bitmap indexeket, de egyszerű bitmátrixokat és bitműveleteket használ a többi indexen végzett keresési eredmények kombinálására.
A Tarantool bitset indexeket használ, és támogatja a rajtuk végzett egyszerű kereséseket.
A Redis egyszerű bitmezőket tartalmaz) keresési lehetőség nélkül.
A MongoDB még nem támogatja a bitmap indexeket, de szintén van javaslat ennek a lehetőségnek a hozzáadására
Az Elasticsearch bitmátrixokat használ belsőleg).
- De új szomszédunk van: Pilosa. Ez egy új nem relációs adatbázis, amely Go nyelven készült. Csak bitmap indexeket tartalmaz, és minden alapja ezek. Kicsit később beszélni fogunk róla.
Megvalósítás Go nyelven
De miért használják olyan ritkán a bitmap indexeket? Mielőtt válaszolnék erre a kérdésre, szeretném megmutatni egy nagyon egyszerű bitmap index megvalósítását Go nyelven.
A bitmátrixok lényegében egyszerű adatrészletekből állnak. A Go-ban erre használjunk bájt szeleteket.
Van egy bitmátrixunk egy étterem jellemzőre, és minden bit a bitmátrixban azt mondja meg, hogy a konkrét étterem rendelkezik-e a kívánt tulajdonsággal vagy sem.
Két segédfunkcióra lesz szükségünk. Az egyiket arra fogjuk használni, hogy a bitmátrixainkat véletlenszerű adatokkal töltsük fel. Véletlenszerűek, de van egy bizonyos valószínűség, hogy a restaurant rendelkezik minden tulajdonsággal. Például úgy gondolom, hogy Moszkvában nagyon kevés olyan étterem van, ahol nem lehet asztalt foglalni, és úgy vélem, hogy körülbelül a helyek 20%-a alkalmas vegetáriánusok számára.
A második funkció a bitmátrixot éttermek listájára fogja átkonvertálni.
Ahhoz, hogy válaszoljunk a »Mutasd meg a kedvező árú éttermeket, ahol van terasz és ahol lehet asztalt foglalni« kérdésre, két bináris műveletre lesz szükségünk: a NOT-ra és az AND-ra.
Kicsit egyszerűsíthetjük a kódunkat, ha egy bonyolultabb AND NOT műveletet használunk.
Van funkciónk minden egyes ilyen műveletre. Mindkettő szélsőségeken halad át, és a megfelelő elemeket veszi az egyes tömbökből, és kombinálja őket a bitművelettel, majd eltárolja az eredményt egy eredménytömbbe.
És most felhasználhatjuk a bitmátrixainkat és a funkcióinkat a keresési lekérdezés megválaszolására.
A teljesítmény nem olyan magas, még az egyszerű funkciók ellenére sem, és jelentős megtakarítást értünk el azzal, hogy nem hoztunk létre új eredménytömböt minden egyes funkcióhíváskor.
A pprof profilozás során észrevettem, hogy a Go fordító kihagyott egy nagyon egyszerű, de lényeges optimalizálást: a funkciók inlining-ját.
Az a helyzet, hogy a Go fordítója rettenetesen fél a tömbökön végigfutó ciklusoktól, és kategorikusan megtagadja az inlinelást a tartalmazó funkciókra.
De én nem félek, és át tudom verni a fordítót, ha goto-t használok a ciklus helyett, mint a régi szép időkben.
És ahogy látjátok, most a fordító örömmel inlineli a funkciónkat! Végül körülbelül 2 mikroszekundumot tudunk megtakarítani. Nem rossz!
A második szűk keresztmetszet nem nehezen észlelhető, ha alaposan megnézzük az assembler kimenetet. A fordító a legforróbb ciklusunkba beépített egy határ-ellenőrzést. Az a helyzet, hogy a Go biztonságos nyelv, a fordító fél a három érveimtől (három tömb) eltérő méretektől. Mert akkor elméletileg lehetőség lenne a úgynevezett puffertúláramlás (buffer overflow) bekövetkezésére.
Nyugodtan meggyőzhetjük a fordítót, hogy minden szelet ugyanolyan méretű. Ezt úgy tehetjük meg, hogy egy egyszerű ellenőrzést adunk a funkciónk elejére.
Ezt látva a fordító örömmel átugorja az ellenőrzést, és végül 500 nanosekundot takarítunk meg.
Nagyobb kötegek
Rendben, sikerült kihoznunk valami teljesítményt az egyszerű megvalósításunkból, de ez az eredmény valójában sokkal rosszabb, mint ami lehetséges a jelenlegi hardverrel.
Amit csinálunk, az alapvetően bitműveletek, és a processzoraink ezt nagyon hatékonyan hajtják végre. De sajnos a processzornak nagyon kis munkadarabokat adunk. A funkcióink bájtonként hajtják végre a műveleteket. Nagyon egyszerűen finomhangolhatjuk a kódunkat, hogy 8 bájtos darabokkal dolgozzon, a UInt64 szeletek használatával.
Ahogy látják, ez a kis változtatás nyolcszor gyorsította fel a programunkat, nyolcszoros köteg növelésével. A nyereség, mondhatni, lineáris.
Assemblerek implementálása
De ez még nem minden. A processzoraink képesek 16, 32 és még 64 bájtos darabokkal dolgozni. Az ilyen "széles" műveleteket nevezzük single instruction multiple data (SIMD; egy utasítás, sok adat), és a kód átalakítása úgy, hogy ezekkel a műveletekkel dolgozzon, a vektorizálás.
Sajnos a Go fordítója messze nem a legjobb a vektorizálásban. Jelenleg az egyetlen módja a Go kód vektorizálásának az, hogy manuálisan beszervezzük az adatokat Go assembly használatával.
A Go assembler furcsa állat. Bizonyára tudja, hogy az assembler valami, ami nagyon kötődik ahhoz a számítógép architektúrához, amelyre ír, de Go esetében nem így van. A Go assembler inkább olyan, mint egy IRL (intermediate representation language; köztes reprezentációs nyelv): gyakorlatilag platformfüggetlen. Rob Pike nagyszerű előadást tartott erről néhány évvel ezelőtt a GopherCon-on Denverben. erről néhány évvel ezelőtt a GopherCon-on Denverben.
Ezen kívül a Go egy szokatlan Plan 9 formátumot használ, amely eltér a hagyományos AT&T és Intel formátumoktól.
Bízhatunk benne, hogy a Go assembler manuális megírása nem a legszórakoztatóbb tevékenység.
De szerencsére már létezik két magas szintű eszköz, amelyek segítenek a Go assembler írásában: PeachPy és avo. Mindkét eszköz Go assembler-t generál egy magasabb szintű kódból, amelyet Pythonban és Go-ban írtunk.
Ezek az eszközök megkönnyítik olyan feladatokat, mint a regiszterek allokálása, ciklusok írása, és összességében egyszerűbbé teszik az assembly programozás világába való belépést a Go nyelvben.
Az avo-t fogjuk használni, így a programjaink szinte normális Go programok lesznek.
Így néz ki a legsimplebb avo-program példa. Van egy main() függvényünk, amely belsőleg definiál egy Add() függvényt, amelynek lényege két szám összeadása. Jelen vannak segédfüggvények a paraméterek név szerinti lekérdezésére és egy szabad, megfelelő CPU regiszter megkapására. Minden CPU műveletnek van megfelelő függvénye az avon, mint az ADDQ-n látható. Végül látunk egy segédfüggvényt az eredményérték mentésére.
A go generate futtatásával végrehajtjuk az avo programot, és két fájl fog létrejönni:
- add.s a Go assembly nyelvű eredménykóddal;
- stub.go a két világ: Go és assembly összeköttetéséhez szükséges függvényfejlécekkel.
Most, hogy láttuk, mit és hogyan csinál az avo, nézzük meg a funkcióinkat. Kiviteleztem a skaláris és a vektori (SIMD) verziókat is.
Először nézzük meg a skaláris verziókat.
Mint az előző példában, itt is kérjük egy szabad, helyes általános célú regiszter biztosítását, nem kell számolnunk az elmozdulásokkal és a méretekkel az argumentumok esetén. Mindezt az avo elvégzi helyettünk.
Korábban címkéket és goto-t (vagy ugrásokat) használtunk a teljesítmény növelésére és a Go fordító kijátszására, de most ezt az elejétől tesszük. Az a helyzet, hogy a ciklusok egy magasabb szintű fogalom. Az assembly-ben csak címkék és ugrások léteznek.
A fennmaradó kód már ismerős és érthető kell legyen. Címkékkel és ugrásokkal emuláljuk a ciklust, kis adatrészleteket veszünk a két szeletünkből, összeolvasztjuk őket egy bitművelettel (jelen esetben AND NOT), majd az eredményt a kimeneti szeletbe helyezzük. Ennyi.
Így néz ki a végső assembly kód. Nem kellett számolnunk az elmozdulásokkal és a méretekkel (zölddel kiemelve) vagy figyelni a használt regiszterekre (vörössel kiemelve).
Ha a teljesítményt összehasonlítjuk az assembly implementáció és a legjobb Go implementáció között, akkor láthatjuk, hogy az azonos. Ez várható is. Hiszen nem csináltunk semmi különöset — csupán reprodukáltuk azt, amit a Go fordító csinálna.
Sajnos nem tudjuk rávenni a fordítót, hogy in-line-ba integrálja az assembly-ben írt funkcióinkat. A Go fordítónak jelenleg nincs ilyen lehetősége, bár a kérés, hogy ezt hozzáadják, már régóta létezik.
Ezért nem lehet semmilyen előnyt szerezni a kis assembly funkciókból. Vagy nagy funkciókat kell írnunk, vagy új math/bits csomagot kell használnunk, vagy el kell kerülnünk az assembly-t.
Nézzük most meg a vektorizált változatait a funkcióinknak.
A példához az AVX2-t választottam, tehát 32 byte-os darabokkal dolgozó műveleteket fogunk használni. A kód struktúrája nagyon hasonlít a skaláris változatra: paraméterek betöltése, kérés egy szabad általános regiszterért stb.
Az egyik újdonság, hogy a szélesebb vektorizált műveletek speciális széles regisztereket használnak. A 32 byte-os darabok esetében ezek a Y előtagú regiszterek. Ezért láthatod a YMM() funkciót a kódban. Ha AVX-512-t használtam volna 64 bites darabokkal, akkor a prefix Z lett volna.
A második újdonság, hogy optimalizálást alkalmaztam, amelyet cikluskibővítésnek (loop unrolling) hívunk, azaz nyolc ciklusműveletet végeztem el manuálisan, mielőtt visszaugranék a ciklus elejére. Ez az optimalizálás csökkenti a kódban lévő ágválasztásokat, és a rendelkezésre álló szabad regiszterek száma korlátozza.
De mi a helyzet a teljesítménnyel? Kiváló! Körülbelül hétszer gyorsabbak vagyunk, mint a legjobb megoldás a Go-n. Megdöbbentő, nem?
De ezt az implementációt akár még gyorsabbá lehetne tenni AVX-512, prefetching vagy JIT (just-in-time compiler) használatával a lekérdezés ütemező számára. De ez már egy külön előadás témája.
Bitmap-indexek problémái
Most, hogy megvizsgáltuk a bitmap-index egyszerű Go implementációját és a sokkal teljesítményesebb assembly változatát, végre beszéljünk arról, hogy miért használják olyan ritkán a bitmap-indexeket.
Régi tudományos munkák említik a bitmap-indexek három problémáját, de újabb kutatások és én azt állítjuk, hogy ezek már elavultak. Nem fogunk mélyen belemenni mindegyik problémába, de felszínesen áttekintjük azokat.
A magas kardinalitás problémája
Tehát azt mondják nekünk, hogy a bitmap-indexek csak alacsony kardinalitású mezőkhöz alkalmasak, vagyis olyanokhoz, ahol kevés érték található (például nem vagy szemszín), és ennek az az oka, hogy a szokásos reprezentáció (egy bit értékenként) nagy kardinalitás esetén túl sok helyet foglalna el, és emellett ezek a bitmap-indexek alig (ritkán) lennének kitöltve.
Néha használhatunk más reprezentációt, például a hagyományosat, amit számok ábrázolására használunk. De az algoritmusok tömörítésének megjelenése mindent megváltoztatott. Az elmúlt évtizedekben tudósok és kutatók számos tömörítési algoritmust dolgoztak ki bitmapokhoz. Fő előnyük, hogy nem szükséges a bitmapokat kicsomagolni bitműveletek végrehajtásához — a bitműveleteket közvetlenül a tömörített bitmapokon is elvégezhetjük.
Az utóbbi időben hibrid megközelítések is megjelentek, mint például a roaring bitmapok. Ezek egyszerre három különböző reprezentációt használnak a bitmapokhoz — magukat a bitmapokat, tömböket és az úgynevezett bit runs-t —, és egyensúlyoznak közöttük a teljesítmény maximalizálása és a memóriafogyasztás minimalizálása érdekében.
Roaring bitmapokkal a legnépszerűbb alkalmazásokban is találkozhatunk. Már létezik hatalmas számú implementáció a legkülönbözőbb programozási nyelvekhez, több mint három implementáció például Go-hoz is.
Egy másik megközelítés, amely segíthet kezelni a nagy kardinalitást, a kategorizálás (binning) néven ismert. Képzelje el, hogy van egy mező, amely egy személy magasságát ábrázolja. A magasság egy lebegőpontos szám, de mi, emberek, nem így gondolkodunk róla. Számunkra nincs különbség a 185,2 cm és a 185,3 cm közötti magasságban.
Ezért csoportosíthatjuk a hasonló értékeket 1 cm-en belül.
Ha pedig tudjuk, hogy nagyon kevés ember van 50 cm-nél alacsonyabb vagy 250 cm-nél magasabb, akkor lényegében egy végtelen kardinalitású mezőt körülbelül 200 értékű mezővé alakíthatunk.
Természetesen, szükség esetén további szűrést is végezhetünk később.
A nagy sávszélesség problémája
A bitmap-indexek következő problémája az, hogy a frissítésük nagyon költséges lehet.
Az adatbázisoknak lehetővé kell tenniük az adatok frissítését abban a pillanatban, amikor potenciálisan száz másik kérés keres ezekben az adatokban. Zárakra van szükség, hogy elkerüljük az adatok egyidejű hozzáférésével kapcsolatos problémákat, vagy más megosztási problémákat. Ahol egy nagy zár van, ott probléma van - a lock contention, amikor ez a zár szűk keresztmetszetté válik.
Ezt a problémát shardolással vagy verziózott indexek használatával lehet megoldani vagy kikerülni.
A shardolás egyszerű és közismert dolog. A bitmap-indexet ugyanúgy shardolhatja, ahogy bármilyen más adatot. Ahelyett, hogy egy nagy zár lenne, sok kis zárat kap, így megszabadul a lock contention-től.
A probléma második megoldása a verziózott indexek használata. Lehet egy másolat az indexből, amit keresésre vagy olvasásra használ, és egy másik a írásra vagy frissítésre. És egy adott időközönként (például 100 ms vagy 500 ms-onként) megduplázzák és felcserélik őket. Nyilvánvaló, hogy ez a megközelítés csak akkor alkalmazható, ha az alkalmazásod el tud működni egy kissé elmaradó keresési indexszel.
Ezek a két megközelítés egyidejűleg is használható: lehet egy shardolt verziózott indexed.
Bonyolultabb lekérdezések
A bitmap-indexek utolsó problémája az, hogy ahogy mondják, nem igazán alkalmasak bonyolultabb kérdéstípusokhoz, például a "tartomány alapján" kérdésekhez.
Valóban, ha belegondolunk, a bitműveletek, mint AND, OR stb. nem igazán alkalmasak olyan kérdésekre, mint "Mutasd meg a szállodákat, ahol a szoba ára 200 és 300 dollár között van éjszakánként".
Naiv és nagyon ésszerűtlen megoldás lenne az, hogy minden egyes dollárértékhez veszi a találatokat, és bitművelettel, OR-jel összekapcsolja őket.
Kicsit helyesebb megoldás lenne a csoportosítás használata. Például 50 dolláros csoportokban. Ez 50-szer gyorsabbá tenné a folyamatunkat.
De a probléma könnyen megoldható egy olyan ábrázolás segítségével, amelyet kifejezetten az ilyen típusú lekérdezésekhez készítettek. Tudományos körökben ezt tartomány-kódolt bitképeknek nevezik.
Ilyen ábrázolás esetén nem csupán egy bitet állítunk be egy adott értékhez (például 200), hanem ezt az értéket és mindent, ami magasabb. 200 és annál magasabb. Ugyanez vonatkozik a 300-ra: 300 és annál magasabb. És így tovább.
Ezen ábrázolás segítségével ilyen típusú keresési kérdésre úgy tudunk válaszolni, hogy végigmegyünk az indexen mindössze kétszer. Először megkapjuk a hotelek listáját, ahol a szoba ára kevesebb, mint 300 dollár, majd eltávolítjuk belőle azokat, ahol a szoba ára kevesebb, mint 199 dollár. Kész.
Meg fog lepődni, de még a geo-lekérdezések is lehetségesek bitmap-indexek használatával. A titok abban rejlik, hogy geoábrázolást alkalmazunk, amely körülveszi az Ön koordinátáját egy geometriai formával. Például a Google S2. Az alakzatot három vagy több átfedő vonallá kell alakítani, amelyeket számozni lehet. Így a geo-lekérdezésünket több "tartomány" kérdésre tudjuk átalakítani (ezekre a számozott vonalakra).
Kész megoldások
Remélem, hogy egy kicsit érdekesnek találta, és most egy újabb hasznos eszköz került a tarsolyába. Ha valaha szüksége lenne hasonlóra, tudni fogja, hogy melyik irányba kell néznie.
Azonban nem mindenki rendelkezik idővel, türelemmel és erőforrásokkal ahhoz, hogy a bitmap-indexeket a nulláról létrehozza. Különösen a fejlettebbek, például a SIMD használatával.
Szerencsére van néhány kész megoldás, amelyek segítenek Önnek.
Roaring bitképek
Először is, itt van az a roaring bitmaps könyvtár, amiről már beszéltem. Tartalmazza az összes szükséges konténert és bitműveletet, amelyekre szüksége lesz a teljes értékű bitmap-index létrehozásához.
Sajnos jelenleg egyetlen Go-implementáció sem használ SIMD-t, ami azt jelenti, hogy a Go-implementációk teljesítménye gyengébb, mint például a C szintű implementációk.
Pilosa
A másik termék, amely segíthet Önnek, a Pilosa DB, amely lényegében csak bitmap-indexekkel rendelkezik. Ez egy viszonylag új megoldás, de rendkívül gyorsan hódítja meg a szíveket.
A Pilosa belül roaring bitképeket használ, és lehetőséget biztosít arra, hogy ezeket használja, egyszerűsíti és elmagyarázza az összes olyan dolgot, amiről korábban beszéltem: csoportosítás, tartomány-kódolt bitképek, mező fogalma stb.
Nézzük meg gyorsan a Pilosa használatának példáját a már jól ismert kérdés megválaszolására.
A példa nagyon hasonlít arra, amit korábban láttál. Létrehozunk egy Pilosa szerverhez kapcsolódó klienst, létrehozunk egy indexet és a szükséges mezőket, majd véletlenszerű adatokkal töltjük fel a mezőinket, végül pedig végrehajtjuk a jól ismert lekérdezést.
Ezt követően a «drága» mezőn NOT-ot használunk, majd a találatot (vagy AND-ot) keresztezzük a «teraszos» és a «foglalások» mezőkkel. Végül megkapjuk a végső eredményt.
Nagyon remélem, hogy a közeljövőben a MySQL és PostgreSQL adatbázisokban is megjelennek ezek az új típusú indexek — a bitmap indexek.
Zárás
Ha még nem aludtál el, köszönöm. Sokan témát érintettem a korlátozott időkeret miatt, de remélem, hogy az előadás hasznos volt, sőt talán még inspiráló is.
Jó tudni a bitmap indexekről, még akkor is, ha jelenleg nincs szükséged rájuk. Legyenek még egy eszköz az arzenálodban.
Megvizsgáltunk különböző trükköket a Go teljesítményének növelésére, és azokat a dolgokat, amelyekkel a Go fordítója még nem bánik jól. Ezt mindenképpen tudnia kell minden Go fejlesztőnek.
Ez minden, amit el akartam mondani. Köszönöm!
Forrás: habr.com
