nyitóbeszéd
Ezt a beszámolót angolul a moszkvai GopherCon Russia 2019 konferencián, oroszul pedig egy Nyizsnyij Novgorodban tartott találkozón tartottam. Bittérképes indexről beszélünk - kevésbé gyakori, mint a B-fa, de nem kevésbé érdekes. Megosztás a konferencián elhangzott beszédek angol nyelven és szöveges átiratok orosz nyelven.
Megnézzük, hogyan működik a bitmap index, mikor jobb, mikor rosszabb, mint más indexek, és milyen esetekben lényegesen gyorsabb náluk; Nézzük meg, mely népszerű DBMS-ek rendelkeznek már bittérképes indexekkel; Próbáljuk meg megírni a sajátunkat a Go-ban. Desszertként pedig kész könyvtárakat fogunk használni saját szupergyors speciális adatbázisunk létrehozásához.
Nagyon remélem, hogy munkáim hasznosak és érdekesek lesznek számodra. Megy!
Bevezetés
Sziasztok! Este hat óra, és mindannyian nagyon fáradtak vagyunk. Jó alkalom beszélni az unalmas adatbázis-index elméletről, igaz? Ne aggódjon, itt-ott lesz pár soros forráskódom. 🙂
Minden viccet félretéve, a jelentés tele van információval, és nincs sok időnk. Tehát kezdjük.
Ma a következőkről fogok beszélni:
- mik az indexek;
- mi az a bitmap index;
- hol használják és hol NEM, és miért;
- egyszerű megvalósítás a Go-ban és egy kis küzdelem a fordítóval;
- valamivel kevésbé egyszerű, de sokkal produktívabb megvalósítás a Go assemblerben;
- bitmap indexek „problémái”;
- meglévő megvalósítások.
Tehát mik azok az indexek?
Az index egy különálló adatstruktúra, amelyet a fő adatok mellett karbantartunk és frissítünk. A keresés felgyorsítására szolgál. Indexek nélkül a kereséshez teljesen át kellene menni az adatokon (a teljes vizsgálatnak nevezett folyamat), és ez a folyamat lineáris algoritmussal rendelkezik. Az adatbázisok azonban általában hatalmas mennyiségű adatot tartalmaznak, és a lineáris bonyolultság túl lassú. Ideális esetben logaritmikust vagy konstanst kapunk.
Ez egy rendkívül összetett téma, tele van finomságokkal és kompromisszumokkal, de több évtizedes adatbázisfejlesztés és kutatás után hajlandó 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ése, a keresési terület kisebb részekre osztása.
Ezt általában különböző típusú fákkal tesszük. Példa erre egy nagy doboz anyag a szekrényében, amely kisebb dobozokat tartalmaz különböző témákra osztva. Ha anyagokra van szüksége, valószínűleg az "Anyagok" feliratú dobozban keresi őket, nem pedig a "Cookie-k" feliratú dobozban, igaz?
A második megközelítés a kívánt elem vagy elemcsoport azonnali kiválasztása. Ezt hash térképekben vagy fordított indexekben tesszük. A hash-térképek használata nagyon hasonlít az előző példához, de egy doboz helyett egy csomó kis doboz utolsó cikk van a szekrényében.
A harmadik megközelítés a keresés szükségességének megszüntetése. Ezt Bloom szűrőkkel vagy kakukkszűrőkkel tesszük. Az elsők azonnal választ adnak, megkímélve Önt a kereséstől.
Az utolsó megközelítés az, hogy teljes mértékben kihasználjuk a modern hardver által biztosított erőt. Pontosan ezt tesszük a bittérképes indexekben. Igen, használatukkor néha át kell mennünk a teljes indexen, de ezt rendkívül hatékonyan tesszük.
Mint mondtam, az adatbázis-indexek témája hatalmas és tele van kompromisszumokkal. Ez azt jelenti, hogy néha több megközelítést is alkalmazhatunk egyszerre: ha még jobban fel kell gyorsítanunk a keresést, vagy ha minden lehetséges keresési típust le kell fednünk.
Ma ezek közül a legkevésbé ismert megközelítésről – a bittérképes indexekről – fogok beszélni.
Ki vagyok én, hogy beszéljek erről a témáról?
Csapatvezetőként dolgozom a Badoo-nál (talán Ön jobban ismeri másik termékünket, a Bumble-t). Már több mint 400 millió felhasználónk van szerte a világon, és számos funkciónk választja ki a számukra legmegfelelőbbet. Ezt egyedi szolgáltatásokkal tesszük, beleértve a bittérképes indexeket is.
Tehát mi az a bittérképes index?
A bittérképes indexek, ahogy a neve is sugallja, bittérképeket vagy bitkészleteket használnak a keresési index megvalósításához. Madártávlatból ez az index egy vagy több ilyen bittérképből áll, amelyek bármilyen entitást (például embereket) és azok tulajdonságait vagy paramétereit (életkor, szemszín stb.) reprezentálják, valamint egy bitműveleteket használó algoritmust (ÉS, VAGY, NEM). ) a keresési lekérdezés megválaszolásához.
Azt mondták nekünk, hogy a bittérképes indexek a legalkalmasabbak és nagyon hatékonyak azokban az esetekben, amikor vannak olyan keresések, amelyek sok alacsony kardinalitású oszlopban egyesítik a lekérdezéseket (gondoljunk a „szemszínre” vagy „családi állapotra” szemben a „városközponttól való távolság”-ra). De később megmutatom, hogy jól működnek a nagy számosságú oszlopoknál is.
Nézzük a bittérképes index legegyszerűbb példáját.
Képzelje el, hogy van egy listánk a moszkvai éttermekről, amelyek bináris tulajdonságokkal rendelkeznek, mint például:
- metró közelében;
- van saját parkoló;
- van veranda (terasszal);
- asztalt foglalhat (foglalásokat elfogad);
- alkalmas vegetáriánusok számára (vegánbarát);
- drága (drága).
Adjunk minden étteremnek egy 0-tól kezdődő sorszámot, és foglaljunk le memóriát 6 bittérképhez (minden jellemzőhöz egy). Ezután feltöltjük ezeket a bitképeket attól függően, hogy az étterem rendelkezik-e ezzel a tulajdonsággal vagy sem. Ha a 4. étteremnek van veranda, akkor a „Van veranda” bitkép 4. bitje 1-re lesz állítva (ha nincs veranda, akkor 0-ra).
Most megvan a lehető legegyszerűbb bittérképes index, és használhatjuk olyan kérdések megválaszolására, mint például:
- „Mutass vegetáriánusbarát éttermeket”;
- "Mutasson olcsó éttermeket verandával, ahol asztalt foglalhat."
Hogyan? Nézzük meg. Az első kérés nagyon egyszerű. Nem kell mást tennünk, mint elővenni a „vegetáriánusbarát” bittérképet, és át kell alakítanunk azon éttermek listáját, amelyeknek a részei láthatók.
A második kérés egy kicsit bonyolultabb. A NOT bitmap-et kell használnunk a „drága” bittérképen, hogy megkapjuk az olcsó éttermek listáját, majd az ÉS a „Foglalhatok asztalt” bittérképpel, az ÉS az eredmény a „Van egy veranda” bittérképpel. Az eredményül kapott bittérkép azon létesítmények listáját fogja tartalmazni, amelyek minden kritériumunknak megfelelnek. Ebben a példában ez csak a Yunost étterem.
Sok elmélet van benne, de ne aggódjon, hamarosan látni fogjuk a kódot.
Hol használják a bittérképes indexeket?
Ha a Google bittérképes indexeket használja, a válaszok 90%-a ilyen vagy olyan módon kapcsolódik az Oracle DB-hez. De valószínűleg más DBMS-ek is támogatnak egy ilyen klassz dolgot, igaz? Nem igazán.
Nézzük át a fő gyanúsítottak listáját.
A MySQL még nem támogatja a bittérképes indexeket, de van egy javaslat, amely javasolja ennek az opciónak a hozzáadását ().
A PostgreSQL nem támogatja a bittérképes indexeket, de egyszerű bittérképeket és bitműveleteket használ a keresési eredmények több más indexben történő kombinálására.
A Tarantool bitkészlet indexekkel rendelkezik, és támogatja az egyszerű kereséseket.
A Redisnek egyszerű bitmezői vannak) anélkül, hogy képes lenne rájuk keresni.
A MongoDB még nem támogatja a bittérképes indexeket, de van egy javaslat is, amely javasolja ennek a lehetőségnek a hozzáadását
Az Elasticsearch belsőleg bittérképeket használ).
- De egy új szomszéd jelent meg a házunkban: Pilosa. Ez egy új, nem relációs adatbázis Go nyelven írva. Csak bittérképes indexeket tartalmaz, és azokra alapoz mindent. Kicsit később beszélünk róla.
Megvalósítás a Go-ban
De miért olyan ritkán használják a bitmap indexeket? Mielőtt válaszolnék erre a kérdésre, szeretném megmutatni, hogyan valósíthat meg egy nagyon egyszerű bitmap indexet a Go-ban.
A bittérképek lényegében csak adatdarabok. A Go-ban használjunk bájtszeleteket erre.
Egy étterem jellemzőre egy bittérképünk van, és a bittérkép minden egyes bitje jelzi, hogy egy adott étterem rendelkezik-e ezzel a tulajdonsággal vagy sem.
Két segédfunkcióra lesz szükségünk. Az egyiket arra használjuk, hogy a bittérképeinket véletlenszerű adatokkal töltsük meg. Véletlenszerű, de bizonyos valószínűséggel az étterem minden tulajdonsággal rendelkezik. Például úgy gondolom, hogy Moszkvában nagyon kevés olyan étterem van, ahol nem lehet asztalt foglalni, és számomra úgy tűnik, hogy az éttermek körülbelül 20%-a vegetáriánusok számára alkalmas.
A második funkció a bittérképet éttermek listájává alakítja.
A „Mutasson olcsó éttermeket, amelyek terasszal rendelkeznek és le tudnak foglalni” kérdés megválaszolásához két bites műveletre van szükség: NOT és AND.
A bonyolultabb AND NOT operátor használatával kicsit leegyszerűsíthetjük a kódunkat.
Mindegyik művelethez megvannak a függvényeink. Mindkettő átmegy a szeleteken, mindegyikből kiveszi a megfelelő elemeket, egy bitművelettel kombinálja és az eredményt belerakja a kapott szeletbe.
És most már használhatjuk bittérképeinket és függvényeinket a keresési lekérdezések megválaszolásához.
A teljesítmény nem olyan magas, annak ellenére, hogy a függvények nagyon egyszerűek, és sok pénzt spóroltunk meg azzal, hogy nem adtunk vissza új eredményt a függvény minden egyes meghívásakor.
Miután elvégeztem egy kis profilozást a pprof-fel, észrevettem, hogy a Go fordítóból hiányzik egy nagyon egyszerű, de nagyon fontos optimalizálás: a függvénybeillesztés.
A helyzet az, hogy a Go fordító rettenetesen fél a szeleteken átmenő ciklusoktól, és kategorikusan elutasítja az ilyen ciklusokat tartalmazó függvények beágyazását.
De nem félek, és be tudom csapni a fordítót, ha ciklus helyett goto-t használok, mint a régi szép időkben.
És amint látja, most a fordító boldogan beépíti funkciónkat! Ennek eredményeként körülbelül 2 mikroszekundumot sikerül megtakarítanunk. Nem rossz!
A második szűk keresztmetszet könnyen belátható, ha alaposan megnézzük az összeállítás kimenetét. A fordító hozzáadott egy szelethatár-ellenőrzést a legforróbb ciklusunkhoz. Az tény, hogy a Go biztonságos nyelv, a fordító attól tart, hogy a három argumentum (három szelet) különböző méretű. Hiszen ekkor elméletileg fennáll az úgynevezett puffertúlcsordulás előfordulásának lehetősége.
Nyugtassuk meg a fordítót azzal, hogy megmutatjuk, hogy minden szelet egyforma méretű. Ezt úgy tehetjük meg, hogy a függvényünk elején egy egyszerű ellenőrzést adunk hozzá.
Ezt látva a fordító boldogan kihagyja az ellenőrzést, és a végén még 500 nanoszekundumot spórolunk meg.
Nagy csapások
Oké, sikerült némi teljesítményt kicsikarnunk az egyszerű megvalósításunkból, de ez az eredmény valójában sokkal rosszabb, mint a jelenlegi hardverrel lehetséges.
Csupán alapvető bitműveleteket végzünk, és processzoraink nagyon hatékonyan hajtják végre azokat. De sajnos nagyon kis munkával „etetjük” a processzorunkat. Funkcióink byte-byte alapon hajtják végre a műveleteket. Az UInt8 szeletekkel nagyon egyszerűen módosíthatjuk a kódunkat, hogy működjön a 64 bájtos darabokkal.
Amint látja, ez a kis változtatás nyolcszorosára gyorsította fel programunkat azáltal, hogy nyolcszorosára növelte a kötegméretet. A nyereség lineárisnak mondható.
Megvalósítás assemblerben
De ez még nem a vége. Processzoraink 16, 32 és akár 64 bájtos darabokkal is tudnak dolgozni. Az ilyen „tág” műveleteket egyetlen utasítás többszörös adatnak (SIMD; egy utasítás, sok adat) nevezik, és a kód átalakításának folyamatát, hogy az ilyen műveleteket használjon, vektorizálásnak nevezzük.
Sajnos a Go fordító távolról sem kiváló a vektorizálásban. Jelenleg a Go kód vektorizálásának egyetlen módja az, hogy ezeket a műveleteket manuálisan, a Go assembler segítségével végezzük el.
A Go assembler egy furcsa vadállat. Valószínűleg tudja, hogy az assembly nyelv olyan dolog, amely erősen kötődik annak a számítógépnek az architektúrájához, amelyre ír, de ez nem így van a Go esetében. A Go assembler inkább egy IRL-hez (intermediate representation language) vagy intermediate nyelvhez hasonlít: gyakorlatilag platformfüggetlen. Rob Pike kiváló teljesítményt nyújtott erről a témáról néhány évvel ezelőtt a denveri GopherConon.
Ezenkívül a Go egy szokatlan Plan 9 formátumot használ, amely eltér az általánosan elfogadott AT&T és Intel formátumoktól.
Nyugodtan kijelenthetjük, hogy a Go assemblert kézzel írni nem a legszórakoztatóbb.
De szerencsére már van két magas szintű eszköz, amely segít a Go assembler megírásában: PeachPy és avo. Mindkét segédprogram Go assemblert állít elő a Pythonban, illetve a Goban írt magasabb szintű kódból.
Ezek a segédprogramok leegyszerűsítik az olyan dolgokat, mint a regiszterek kiosztása, az írási hurkok, és általában leegyszerűsítik az összeállítási programozás világába való belépést a Go-ban.
Az avo-t fogjuk használni, így a programjaink szinte szokásos Go programok lesznek.
Így néz ki egy avo program legegyszerűbb példája. Van egy main() függvényünk, ami magában definiálja az Add() függvényt, aminek a jelentése két szám összeadása. Itt vannak segédfunkciók, amelyek segítségével név szerint kaphatunk paramétereket, és megkaphatjuk az ingyenes és megfelelő processzorregiszterek valamelyikét. Minden processzorműveletnek megfelelő funkciója van az avo-n, amint az az ADDQ-ban látható. Végül egy segítő függvényt látunk a kapott érték tárolására.
A go generate meghívásával végrehajtjuk a programot az avo-n, és ennek eredményeként két fájl generálódik:
- add.s a kapott kóddal a Go assemblerben;
- A stub.go funkciófejlécekkel összekapcsolja a két világot: Go és assembler.
Most, hogy láttuk, mit csinál az avo és hogyan, nézzük meg a funkcióinkat. A függvények skaláris és vektoros (SIMD) változatát is megvalósítottam.
Nézzük először a skaláris változatokat.
Az előző példához hasonlóan ingyenes és érvényes általános célú regisztert kérünk, nem kell eltolásokat és méreteket számolnunk az argumentumokhoz. avo mindezt értünk teszi.
Korábban címkéket és goto-t (vagy ugrásokat) használtunk a teljesítmény javítására és a Go fordító átverésére, de most már az elejétől fogva ezt tesszük. A lényeg az, hogy a ciklusok magasabb szintű fogalom. Az assemblerben csak címkéink és ugrások vannak.
A fennmaradó kódnak már ismerősnek és érthetőnek kell lennie. Emulálunk egy ciklust címkékkel és ugrásokkal, kiveszünk egy kis adatot a két szeletünkből, kombináljuk egy bitművelettel (ÉS ebben az esetben NEM), majd az eredményt beletesszük a kapott szeletbe. Minden.
Így néz ki a végső assembler kód. Nem kellett eltolásokat és méreteket számolnunk (zöld színnel kiemelve), vagy nyomon követni a használt regisztereket (pirossal kiemelve).
Ha összehasonlítjuk az assembly nyelvi megvalósítás teljesítményét a Go legjobb megvalósításának teljesítményével, látni fogjuk, hogy ez ugyanaz. És ez várható is. Végül is nem csináltunk semmi különöset – csak reprodukáltuk azt, amit egy Go fordító csinálna.
Sajnos nem tudjuk rákényszeríteni a fordítót, hogy beépítse assembly nyelven írt függvényeinket. A Go fordító jelenleg nem rendelkezik ilyen funkcióval, bár már jó ideje kérték a hozzáadását.
Ez az oka annak, hogy az assembly nyelven nem lehet hasznot húzni a kis függvényekből. Vagy nagy függvényeket kell írnunk, vagy az új math/bits csomagot kell használnunk, vagy megkerülnünk az assembler nyelvet.
Nézzük most függvényeink vektoros változatait.
Ebben a példában az AVX2 használata mellett döntöttem, ezért olyan műveleteket fogunk használni, amelyek 32 bájtos darabokon működnek. A kód felépítése nagyon hasonlít a skaláris verzióhoz: paraméterek betöltése, ingyenes megosztott regiszter kérése stb.
Az egyik újítás az, hogy a szélesebb vektorműveletek speciális széles regisztereket használnak. A 32 bájtos darabok esetében ezek Y előtagú regiszterek. Emiatt látható az YMM() függvény a kódban. Ha AVX-512-t használnék 64 bites darabokkal, akkor az előtag Z lenne.
A második újítás az, hogy úgy döntöttem, hogy a loop unrolling nevű optimalizálást használom, ami azt jelenti, hogy nyolc ciklus műveletet kell manuálisan elvégezni, mielőtt a ciklus elejére ugornék. Ez az optimalizálás csökkenti a kódban lévő fiókok számát, és korlátozza a rendelkezésre álló ingyenes regiszterek száma.
Nos, mi a helyzet a teljesítménnyel? Ő szép! Körülbelül hétszeres gyorsulást értünk el a legjobb Go megoldáshoz képest. Lenyűgöző, igaz?
De még ez a megvalósítás is felgyorsítható az AVX-512, az előzetes letöltés vagy a JIT (just-in-time fordító) használatával a lekérdezésütemezőhöz. De ez minden bizonnyal egy külön jelentés témája.
Problémák a bittérképes indexekkel
Most, hogy már megvizsgáltuk a bittérképes index egyszerű megvalósítását a Go-ban, és egy sokkal produktívabbat assembly nyelven, beszéljünk végre arról, hogy miért használnak olyan ritkán bitmap indexeket.
A régebbi cikkek három problémát említenek a bittérképes indexekkel, de az újabb dolgozatok, és én azt állítom, hogy ezek már nem relevánsak. Nem merülünk el mélyen ezekben a problémákban, hanem felületesen vizsgáljuk meg őket.
A magas kardinalitás problémája
Tehát azt mondják nekünk, hogy a bittérképes indexek csak az alacsony kardinalitású mezőkhöz alkalmasak, vagyis azokhoz, amelyeknek kevés értéke van (például nem vagy szemszín), és ennek az az oka, hogy az ilyen mezők szokásos megjelenítése (egy bit per érték) nagy számosság esetén túl sok helyet foglal el, ráadásul ezek a bittérképes indexek rosszul (ritkán) lesznek kitöltve.
Néha másfajta ábrázolást is használhatunk, például a számok ábrázolására használt standardot. De a tömörítési algoritmusok megjelenése mindent megváltoztatott. Az elmúlt évtizedekben a tudósok és kutatók számos tömörítési algoritmust dolgoztak ki bittérképekhez. Fő előnyük, hogy a bitműveletek végrehajtásához nincs szükség a bitképek kitömörítésére – a tömörített bittérképeken közvetlenül is végezhetünk bitműveleteket.
Az utóbbi időben megjelentek a hibrid megközelítések, például az ordító bittérképek. Egyszerre három különböző reprezentációt használnak a bitképekhez – maguk a bitképek, a tömbök és az úgynevezett bitfutások –, és egyensúlyt teremtenek közöttük a teljesítmény maximalizálása és a memóriafelhasználás minimalizálása érdekében.
A legnépszerűbb alkalmazásokban üvöltő bittérképeket találhat. Már most is rengeteg implementáció létezik a legkülönfélébb programozási nyelvekhez, köztük több mint három implementáció a Go számára.
Egy másik megközelítés, amely segíthet megbirkózni a nagy számossággal, az úgynevezett binning. Képzelje el, hogy van egy mezője, amely egy személy magasságát jelzi. A magasság egy lebegőpontos szám, de mi, emberek nem így gondoljuk. Nálunk nincs különbség 185,2 cm és 185,3 cm magasság között.
Kiderült, hogy a hasonló értékeket 1 cm-en belül csoportokba csoportosíthatjuk.
És ha azt is tudjuk, hogy nagyon kevesen vannak 50 cm-nél alacsonyabbak és 250 cm-nél magasabbak, akkor egy végtelen számú mezőt lényegében egy körülbelül 200 értékű kardinalitású mezővé alakíthatunk.
Természetesen szükség esetén utólag további szűrést is végezhetünk.
Nagy sávszélesség probléma
A következő probléma a bittérképes indexekkel az, hogy frissítésük nagyon költséges lehet.
Az adatbázisoknak képesnek kell lenniük az adatok frissítésére, miközben potenciálisan több száz egyéb lekérdezés keresi az adatokat. Zárakra van szükségünk, hogy elkerüljük az egyidejű adathozzáféréssel vagy más megosztási problémákkal kapcsolatos problémákat. És ahol egy nagy zár van, ott van egy probléma - zárverseny, amikor ez a zár szűk keresztmetszetté válik.
Ez a probléma megoldható vagy megkerülhető felosztással vagy verziószámú indexek használatával.
A megosztás egyszerű és jól ismert dolog. A bittérképes indexeket ugyanúgy feldarabolhatja, mint bármely más adatot. Egy nagy zár helyett egy csomó kis zárat kap, és így megszabadul a zárral kapcsolatos vitáktól.
A probléma megoldásának második módja a verziószámú indexek használata. Rendelkezhet egy példányával az indexből, amelyet keresésre vagy olvasásra használ, és egyet, amelyet íráshoz vagy frissítéshez használ. És bizonyos időközönként (például 100 ms-onként vagy 500 ms-onként egyszer) lemásolja és felcseréli őket. Természetesen ez a megközelítés csak olyan esetekben alkalmazható, amikor az alkalmazás képes kezelni egy kissé lemaradt keresési indexet.
Ez a két megközelítés egyszerre is használható: rendelkezhet szilánkos verziójú indexszel.
Bonyolultabb lekérdezések
A bittérképes indexekkel kapcsolatos végső probléma az, hogy azt mondják, hogy nem alkalmasak bonyolultabb típusú lekérdezésekre, például a span lekérdezésekre.
Valóban, ha jobban belegondolunk, az olyan bitműveletek, mint az ÉS, VAGY stb., nem nagyon alkalmasak az olyan lekérdezésekre, mint a „Mutasd a szállodákat éjszakánként 200 és 300 dollár közötti szobaárakkal”.
Naiv és nagyon oktalan megoldás az lenne, ha az eredményeket minden egyes dollárértékre vesszük, és egy bitenkénti VAGY művelettel kombináljuk.
Valamivel jobb megoldás lenne a csoportosítás használata. Például 50 dolláros csoportokban. Ez 50-szeresére gyorsítaná fel a folyamatot.
De a probléma is könnyen megoldható egy kifejezetten az ilyen típusú kérésekhez készített nézet használatával. A tudományos közleményekben tartománykódolt bittérképeknek nevezik.
Ebben az ábrázolásban nem csak egy bitet állítunk be valamilyen értékhez (például 200), hanem ezt az értéket és mindent magasabbra állítunk. 200 és felette. Ugyanez vonatkozik a 300:300-ra és afelettire is. Stb.
Ezzel a reprezentációval megválaszolhatjuk az ilyen típusú keresési lekérdezéseket, ha kétszer bejárjuk az indexet. Először egy listát kapunk azokról a szállodákról, ahol kevesebb vagy 300 dollár a szoba, majd eltávolítjuk belőle azokat, ahol a szoba ára kevesebb vagy 199 dollár. Kész.
Meg fog lepődni, de még a geolekérdezések is lehetségesek bittérképes indexek használatával. A trükk az, hogy olyan geometriai ábrázolást használunk, amely körülveszi a koordinátát egy geometriai ábrával. Például az S2 a Google-tól. Az ábrát három vagy több egymást metsző, számozható vonal formájában kell ábrázolni. Így a geolekérdezésünket több lekérdezéssé alakíthatjuk „a rés mentén” (e számozott sorok mentén).
Kész megoldások
Remélem, egy kicsit érdekelt, és most egy másik hasznos eszköz is van az arzenáljában. Ha valami ilyesmit kell tennie, tudni fogja, hogyan nézzen ki.
Azonban nem mindenkinek van ideje, türelme vagy erőforrása bitmap indexek létrehozására a semmiből. Főleg a fejlettebbek, például SIMD használatával.
Szerencsére több kész megoldás is segíthet.
Ordító bitképek
Először is, ott van ugyanaz az ordító bittérképes könyvtár, amelyről már beszéltem. Tartalmazza az összes szükséges konténert és bitműveletet, amelyekre egy teljes bitmap index elkészítéséhez szüksége lesz.
Sajnos jelenleg egyik Go implementáció sem használ SIMD-t, ami azt jelenti, hogy a Go implementációk kevésbé teljesítenek, mint például a C implementációk.
szőrös
Egy másik termék, amely segíthet, a Pilosa DBMS, amely valójában csak bittérképes indexekkel rendelkezik. Ez egy viszonylag új megoldás, de nagy sebességgel hódítja meg a szíveket.
A Pilosa belsőleg zúgó bittérképeket használ, és lehetőséget ad ezek használatára, leegyszerűsíti és elmagyarázza mindazt, amiről fentebb beszéltem: csoportosítás, tartománykódolt bittérképek, mező fogalma stb.
Vessünk egy rövid pillantást a Pilosa használatára egy olyan kérdés megválaszolására, amelyet már ismer.
A példa nagyon hasonló ahhoz, amit korábban láttál. Létrehozunk egy klienst a Pilosa szerverhez, elkészítjük az indexet és a szükséges mezőket, majd kitöltjük a mezőinket véletlenszerű adatokkal valószínűségekkel és végül végrehajtjuk az ismerős lekérdezést.
Ezt követően a "drága" mezőben használjuk a NEM-et, majd az eredményt (vagy ÉS azt) metsszük a "terasz" mezővel és a "foglalások" mezővel. És végül megkapjuk a végeredményt.
Nagyon remélem, hogy a belátható jövőben ez az új típusú index az olyan adatbázis-kezelő rendszerekben is megjelenik, mint a MySQL és a PostgreSQL - bitmap indexek.
Következtetés
Ha még nem aludtál el, köszönöm. Az idő szűkössége miatt sok témát kellett röviden érintenem, de remélem, hasznos volt a beszélgetés, sőt talán motiváló is volt.
A bitmap indexeket akkor is jó tudni, ha jelenleg nincs rájuk szüksége. Legyenek egy másik eszköz az eszköztáradban.
Megvizsgáltunk különféle teljesítmény-trükköket a Go-hoz, és olyan dolgokat, amelyeket a Go fordító még nem kezel túl jól. De ezt minden Go programozónak feltétlenül tudnia kell.
Ez minden, amit el akartam mondani. Köszönöm!
Forrás: will.com