sissejuhatus
Esitasin selle ettekande inglise keeles Moskvas GopherCon Russia 2019 konverentsil ja vene keeles Nižni Novgorodis toimunud kohtumisel. Me räägime bitmap indeksist - vähem levinud kui B-puu, kuid mitte vähem huvitav. Jagamine kõned konverentsil inglise keeles ja tekstide stenogrammid vene keeles.
Vaatame, kuidas bitmap-indeks töötab, millal on see parem, millal kehvem kui teised indeksid ja millistel juhtudel on see neist oluliselt kiirem; Vaatame, millistel populaarsetel DBMS-idel on juba bitmap-indeksid; Proovime Go-sse kirjutada. Ja "magustoiduks" kasutame valmis teeke, et luua oma ülikiire spetsialiseeritud andmebaas.
Loodan väga, et minu tööd on teile kasulikud ja huvitavad. Mine!
Sissejuhatus
Tere kõigile! Kell on kuus õhtul ja me kõik oleme üliväsinud. Hea aeg rääkida igavast andmebaasiindeksi teooriast, eks? Ärge muretsege, mul on siin-seal paar rida lähtekoodi. 🙂
Kui nali kõrvale jätta, on aruanne infot täis ja meil pole palju aega. Nii et alustame.
Täna räägin järgmistest asjadest:
- mis on indeksid;
- mis on bitmap-indeks;
- kus seda kasutatakse ja kus EI KASUTATA ning miks;
- lihtne rakendamine Go-s ja väike võitlus kompilaatoriga;
- veidi vähem lihtne, kuid palju produktiivsem teostus Go assembleris;
- bitmap-indeksite "probleemid";
- olemasolevaid rakendusi.
Mis on siis indeksid?
Indeks on eraldiseisev andmestruktuur, mida lisaks põhiandmetele hooldame ja uuendame. Seda kasutatakse otsingu kiirendamiseks. Ilma indeksiteta nõuaks otsimine andmete täielikku läbimist (seda nimetatakse täielikuks skannimiseks) ja sellel protsessil on lineaarne algoritmiline keerukus. Kuid andmebaasid sisaldavad tavaliselt tohutul hulgal andmeid ja lineaarne keerukus on liiga aeglane. Ideaalis saaksime logaritmilise või konstantse.
See on tohutult keeruline teema, mis on täis nüansse ja kompromisse, kuid pärast aastakümnete pikkust andmebaasi arendust ja uurimistööd olen nõus ütlema, et andmebaasiindeksite loomisel on laialdaselt kasutatud vaid mõned lähenemisviisid.
Esimene lähenemine on otsinguruumi hierarhiline vähendamine, jagades otsinguruumi väiksemateks osadeks.
Tavaliselt teeme seda erinevat tüüpi puid kasutades. Näiteks võib tuua teie kapis oleva suure materjalikasti, mis sisaldab väiksemaid kaste erinevate teemade kaupa. Kui vajate materjale, otsite neid tõenäoliselt kastist, millel on kirjas "Materjalid", mitte "Küpsised", eks?
Teine lähenemisviis on soovitud elemendi või elementide rühma kohene valimine. Teeme seda räsikaartides või pöördindeksites. Räsikaartide kasutamine on väga sarnane eelmisele näitele, kuid kastide asemel on teie kapis hunnik väikeseid kaste lõplike esemetega.
Kolmas lähenemisviis on otsinguvajaduse kaotamine. Teeme seda Bloomi või kägufiltrite abil. Esimesed annavad vastuse koheselt, säästes teid otsimast.
Viimane lähenemisviis on kasutada täielikult ära kogu võimsus, mille kaasaegne riistvara meile annab. See on täpselt see, mida me bitmap-indeksites teeme. Jah, nende kasutamisel peame mõnikord läbima kogu indeksi, kuid me teeme seda ülitõhusalt.
Nagu ma ütlesin, on andmebaasiindeksite teema ulatuslik ja täis kompromisse. See tähendab, et mõnikord saame kasutada mitut lähenemist korraga: kui peame otsingut veelgi kiirendama või kui peame katma kõik võimalikud otsingutüübid.
Täna räägin nende kõige vähem tuntud lähenemisviisist - bitmap indeksid.
Kes ma olen, et sel teemal rääkida?
Töötan Badoos meeskonnajuhina (võib-olla olete meie teise tootega Bumble rohkem tuttav). Meil on juba üle 400 miljoni kasutaja üle maailma ja palju funktsioone, mis valivad neile sobivaima. Teeme seda kohandatud teenuste, sealhulgas bitmap-indeksite abil.
Mis on bitmap-indeks?
Bitmap-indeksid, nagu nimigi ütleb, kasutavad otsinguindeksi rakendamiseks bitimape või bitikomplekte. Linnulennult vaadatuna koosneb see indeks ühest või mitmest sellisest bitikaardist, mis esindab mis tahes oleme (nt inimesi) ja nende omadusi või parameetreid (vanus, silmade värv jne), ning bitioperatsioone (AND, OR, NOT) kasutavast algoritmist. ), et otsingupäringule vastata.
Meile öeldakse, et bitmap-indeksid sobivad kõige paremini ja toimivad väga hästi juhtudel, kui on otsinguid, mis kombineerivad päringuid paljudes madala kardinaalsusega veergudes (mõelge "silmade värvile" või "perekonnaseisule" versus "kaugusele kesklinnast"). Kuid ma näitan hiljem, et need töötavad suurepäraselt ka suure kardinaalsusega veergude jaoks.
Vaatame bitmap-indeksi lihtsaimat näidet.
Kujutage ette, et meil on nimekiri Moskva restoranidest, millel on sellised binaarsed omadused:
- metroo lähedal;
- on privaatne parkla;
- on veranda (on terrass);
- saate reserveerida laua (aktsepteerib broneeringuid);
- sobib taimetoitlastele (veganisõbralik);
- kallis (kallis).
Anname igale restoranile järjekorranumbri, mis algab 0-st ja eraldame mälu 6 bitmapi jaoks (üks iga tunnuse jaoks). Seejärel täidame need bitmapid sõltuvalt sellest, kas restoranil on see omadus või mitte. Kui restoranis 4 on veranda, seatakse bitikaardil "on veranda" biti nr 4 väärtuseks 1 (kui verandat pole, siis 0).
Nüüd on meil võimalikult lihtne bitmap-indeks ja saame seda kasutada sellistele päringutele vastamiseks nagu:
- "Näita mulle taimetoitlastele sobivaid restorane";
- "Näidake mulle odavaid verandaga restorane, kus saate laua reserveerida."
Kuidas? Vaatame. Esimene taotlus on väga lihtne. Kõik, mida peame tegema, on võtta "taimetoitlastele sõbralik" bitmap ja muuta see restoranide loendiks, mille bitid on paljastatud.
Teine taotlus on veidi keerulisem. Odavate restoranide loendi saamiseks peame kasutama "kallil" bitmapil EI bitmapi, seejärel JA seda bitmapiga "Kas ma saan laua broneerida" ja tulemust "veranda on" bitmapiga. Saadud bitmap sisaldab loendit ettevõtetest, mis vastavad kõigile meie kriteeriumidele. Selles näites on see ainult Yunost restoran.
Sellega on seotud palju teooriat, kuid ärge muretsege, koodi näeme varsti.
Kus kasutatakse bitmap indekseid?
Kui guugeldada bitmap indekseid, on 90% vastustest ühel või teisel viisil seotud Oracle DB-ga. Kuid ilmselt toetavad ka teised DBMS-id sellist lahedat asja, eks? Mitte päris.
Vaatame läbi peamiste kahtlusaluste nimekirja.
MySQL ei toeta veel bitmap indekseid, kuid on olemas ettepanek selle valiku lisamiseks ().
PostgreSQL ei toeta bitmap-indekseid, kuid kasutab lihtsaid bitikaarte ja bitioperatsioone, et kombineerida otsingutulemusi mitme teise indeksi vahel.
Tarantoolil on bitikomplekti indeksid ja see toetab nendes lihtsaid otsinguid.
Redis on lihtsad bitiväljad) ilma võimaluseta neid otsida.
MongoDB ei toeta veel bitmap indekseid, kuid on ka ettepanek selle võimaluse lisamiseks
Elasticsearch kasutab sisemiselt bittraate).
- Aga meie majja on ilmunud uus naaber: Pilosa. See on Go keeles kirjutatud uus mitterelatsiooniline andmebaas. See sisaldab ainult bitmap indekseid ja põhineb kõik nendel. Räägime sellest veidi hiljem.
Rakendamine Go-s
Aga miks bitmap-indekseid nii harva kasutatakse? Enne sellele küsimusele vastamist tahaksin teile näidata, kuidas Go-s rakendada väga lihtsat bitmap-indeksit.
Bitkaardid on sisuliselt vaid andmed. Go-s kasutame selleks baitlõike.
Meil on üks bitmap ühe restorani karakteristiku kohta ja iga bitikaart näitab, kas konkreetsel restoranil on see omadus või mitte.
Vajame kahte abifunktsiooni. Ühte kasutatakse meie bitikaartide täitmiseks juhuslike andmetega. Juhuslik, kuid teatud tõenäosusega, et restoranis on iga vara. Näiteks usun, et Moskvas on väga vähe restorane, kus ei saa lauda reserveerida, ja mulle tundub, et umbes 20% asutustest sobivad taimetoitlastele.
Teine funktsioon teisendab bitmapi restoranide loendiks.
Päringule „Näita odavaid restorane, millel on siseõu ja kus saab broneerida” vastamiseks vajame kahte bititoimingut: NOT ja AND.
Saame oma koodi pisut lihtsustada, kasutades keerukamat AND NOT operaatorit.
Meil on iga toimingu jaoks funktsioonid. Mõlemad läbivad viilud, võtavad kummaltki vastavad elemendid, kombineerivad need bitioperatsiooniga ja panevad tulemuse saadud viilu sisse.
Ja nüüd saame otsingupäringule vastamiseks kasutada oma bitikaarte ja funktsioone.
Jõudlus pole nii kõrge, kuigi funktsioonid on väga lihtsad ja säästsime palju raha, kuna ei tagastanud iga kord, kui funktsiooni kutsuti, uut saadud lõiku.
Pärast pprofiga pisut profileerimist märkasin, et Go kompilaatoril oli puudu üks väga lihtne, kuid väga oluline optimeerimine: funktsioonide sisestamine.
Fakt on see, et Go kompilaator kardab kohutavalt ahelaid, mis läbivad lõike, ja keeldub kategooriliselt selliseid silmuseid sisaldavate funktsioonide kaasamisest.
Aga ma ei karda ja võin kompilaatorit petta, kasutades tsükli asemel goto, nagu vanadel headel aegadel.
Ja nagu näete, lisab kompilaator nüüd rõõmsalt meie funktsiooni! Selle tulemusel õnnestub meil säästa umbes 2 mikrosekundit. Pole paha!
Teist kitsaskohta on lihtne näha, kui vaatate tähelepanelikult koostu väljundit. Kompilaator lisas lõigu piirikontrolli otse meie kuumimasse tsüklisse. Fakt on see, et Go on turvaline keel, koostaja kardab, et minu kolm argumenti (kolm viilu) on erineva suurusega. Siis on ju teoreetiline võimalus nn puhvri ülevooluks.
Rahustagem koostajat, näidates talle, et kõik lõigud on ühesuurused. Seda saame teha, lisades funktsiooni algusesse lihtsa kontrolli.
Seda nähes jätab koostaja rõõmsalt kontrolli vahele ja lõpuks säästame veel 500 nanosekundit.
Suured punnid
Olgu, meil õnnestus oma lihtsast teostusest jõudlust välja pigistada, kuid see tulemus on tegelikult palju hullem kui praeguse riistvaraga võimalik.
Kõik, mida me teeme, on põhilised bititoimingud ja meie protsessorid täidavad neid väga tõhusalt. Kuid kahjuks "toidame" oma protsessorit väga väikeste töödega. Meie funktsioonid teostavad toiminguid bait-baidipõhiselt. Saame oma koodi väga lihtsalt kohandada nii, et see töötaks 8-baidiste tükkidega, kasutades UInt64 lõike.
Nagu näete, kiirendab see väike muudatus meie programmi kaheksa korda, suurendades partii suurust kaheksa korda. Kasu võib öelda, et see on lineaarne.
Rakendamine assembleris
Kuid see pole veel lõpp. Meie protsessorid saavad töötada 16-, 32- ja isegi 64-baidiste tükkidega. Selliseid laiaulatuslikke operatsioone nimetatakse ühe käsuga mitmeks andmeks (SIMD; üks käsk, palju andmeid) ja koodi teisendamist nii, et see selliseid toiminguid kasutaks, nimetatakse vektoriseerimiseks.
Kahjuks pole Go kompilaator vektoriseerimise osas kaugeltki suurepärane. Praegu on ainus viis Go koodi vektoriseerimiseks võtta ja panna need toimingud Go assembleri abil käsitsi.
Go assembler on kummaline loom. Tõenäoliselt teate, et montaažikeel on miski, mis on tugevalt seotud selle arvuti arhitektuuriga, millele kirjutate, kuid Go puhul see nii ei ole. Go assembler on rohkem nagu IRL (intermediate representation language) või vahekeel: see on praktiliselt platvormist sõltumatu. Rob Pike tegi suurepärase esituse sellel teemal mitu aastat tagasi Denveris GopherConil.
Lisaks kasutab Go ebatavalist Plan 9 vormingut, mis erineb üldtunnustatud AT&T ja Inteli formaatidest.
Võib kindlalt öelda, et Go assembleri käsitsi kirjutamine pole just kõige lõbusam.
Kuid õnneks on juba kaks kõrgetasemelist tööriista, mis aitavad meil Go assemblerit kirjutada: PeachPy ja avo. Mõlemad utiliidid genereerivad Go assembleri kõrgema taseme koodist, mis on kirjutatud vastavalt Pythonis ja Go-s.
Need utiliidid lihtsustavad selliseid asju nagu registri eraldamine, kirjutamistsüklid ja üldiselt lihtsustavad Go koosteprogrammeerimise maailma sisenemise protsessi.
Me kasutame avo-d, seega on meie programmid peaaegu tavalised Go programmid.
Selline näeb välja avoprogrammi lihtsaim näide. Meil on funktsioon main(), mis defineerib enda sees funktsiooni Add(), mille tähendus on kahe numbri liitmine. Siin on abifunktsioonid parameetrite nime järgi hankimiseks ja ühe tasuta ja sobiva protsessoriregistri hankimiseks. Igal protsessori toimingul on avo vastav funktsioon, nagu on näha ADDQ-st. Lõpuks näeme abifunktsiooni saadud väärtuse salvestamiseks.
Kutsudes go generate, käivitame programmi avo-s ja selle tulemusena genereeritakse kaks faili:
- add.s koos saadud koodiga Go assembleris;
- stub.go funktsioonipäistega, et ühendada kaks maailma: Go ja assembler.
Nüüd, kui oleme näinud, mida ja kuidas avo teeb, vaatame oma funktsioone. Realiseerisin funktsioonide nii skalaar- kui ka vektorversioonid (SIMD).
Vaatame kõigepealt skalaarversioone.
Nagu eelmises näites, küsime tasuta ja kehtivat üldotstarbelist registrit, argumentide nihkeid ja suurusi pole vaja arvutada. avo teeb seda kõike meie eest.
Varem kasutasime silte ja goto (või hüppeid) jõudluse parandamiseks ja Go kompilaatori trikitamiseks, kuid nüüd teeme seda algusest peale. Asi on selles, et tsüklid on kõrgema taseme mõiste. Assembleris on meil ainult sildid ja hüpped.
Ülejäänud kood peaks olema juba tuttav ja arusaadav. Emuleerime siltide ja hüpetega tsüklit, võtame kahest lõigust väikese andmetüki, ühendame need bitioperatsiooniga (JA antud juhul MITTE) ja seejärel paneme tulemuse saadud lõiku. Kõik.
Selline näeb välja lõplik komplekteerija kood. Me ei pidanud arvutama nihkeid ja suurusi (rohelisega esile tõstetud) ega jälgima kasutatud registreid (punasega esile tõstetud).
Kui võrdleme montaažikeele teostuse jõudlust Go parima teostuse jõudlusega, näeme, et see on sama. Ja seda oodatakse. Lõppude lõpuks ei teinud me midagi erilist – me lihtsalt reprodutseerisime seda, mida Go kompilaator teeks.
Kahjuks ei saa me sundida kompilaatorit meie assemblerkeeles kirjutatud funktsioone lisama. Go kompilaatoril praegu sellist võimalust pole, kuigi soovi selle lisamiseks on olnud juba tükk aega.
Seetõttu on väikestest funktsioonidest assambleekeeles võimatu kasu saada. Peame kas kirjutama suured funktsioonid või kasutama uut matemaatika/bittide paketti või mööduma assemblerkeelest.
Vaatame nüüd oma funktsioonide vektorversioone.
Selle näite puhul otsustasin kasutada AVX2, seega kasutame toiminguid, mis töötavad 32-baidiste tükkidega. Koodi struktuur on väga sarnane skalaarversiooniga: parameetrite laadimine, tasuta jagatud registri küsimine jne.
Üks uuendus on see, et laiemate vektoroperatsioonide puhul kasutatakse spetsiaalseid lairegistreid. 32-baidiste tükkide puhul on need registrid, mille eesliide on Y. Seetõttu näete koodis funktsiooni YMM(). Kui ma kasutaksin AVX-512 64-bitiste tükkidega, oleks eesliide Z.
Teine uuendus on see, et otsustasin kasutada optimeerimist, mida nimetatakse silmuse lahtirullimiseks, mis tähendab kaheksa tsüklioperatsiooni käsitsi tegemist enne tsükli algusesse hüppamist. See optimeerimine vähendab koodi harude arvu ja seda piirab saadaolevate tasuta registrite arv.
Aga jõudlus? Ta on ilus! Võrreldes parima Go lahendusega saavutasime umbes seitsmekordse kiiruse. Muljetavaldav, eks?
Kuid isegi seda rakendamist saab potentsiaalselt kiirendada, kasutades päringu ajakava jaoks AVX-512, eellaadimist või JIT-i (just-in-time kompilaator). Kuid see on kindlasti eraldi raporti teema.
Probleemid bitmap-indeksitega
Nüüd, kui oleme juba vaadanud lihtsat bitmap-indeksi rakendust Go-s ja palju produktiivsemat montaažikeeles, räägime lõpuks sellest, miks bitmap-indekseid nii harva kasutatakse.
Vanemad artiklid mainivad kolme bitmap-indeksitega seotud probleemi, kuid uuemates paberites väidan, et need pole enam asjakohased. Me ei sukeldu igasse neist probleemidest sügavalt, vaid vaatame neid pealiskaudselt.
Kõrge kardinaalsuse probleem
Niisiis, meile öeldakse, et bitmap-indeksid sobivad ainult madala kardinaalsusega väljadele, st neile, millel on vähe väärtusi (näiteks sugu või silmade värv), ja põhjus on selles, et selliste väljade tavapärane esitus (üks bit per value) suure kardinaalsuse korral võtab see liiga palju ruumi ja pealegi on need bitmap indeksid halvasti (harva) täidetud.
Mõnikord võime kasutada teistsugust esitust, näiteks tavalist, mida kasutame numbrite esitamiseks. Kuid just tihendusalgoritmide tulek muutis kõike. Viimastel aastakümnetel on teadlased ja uurijad välja pakkunud suure hulga bitikaartide tihendusalgoritme. Nende peamine eelis on see, et bitioperatsioonide teostamiseks pole vaja bitikaarte lahti pakkida – saame bitioperatsioone teha otse tihendatud bitikaartidel.
Viimasel ajal on hakanud ilmuma hübriidsed lähenemisviisid, näiteks möirgavad bitmaps. Nad kasutavad üheaegselt kolme erinevat bitikaartide esitust – bitmapid ise, massiive ja nn bitijooksud – ning tasakaalustavad nende vahel, et maksimeerida jõudlust ja minimeerida mälutarbimist.
Möirgavaid bitmaate leiate kõige populaarsematest rakendustest. Paljude programmeerimiskeelte jaoks on juba olemas tohutul hulgal rakendusi, sealhulgas rohkem kui kolm rakendust Go jaoks.
Teine lähenemisviis, mis aitab meil toime tulla suure kardinaalsusega, on binning. Kujutage ette, et teil on väli, mis tähistab inimese pikkust. Kõrgus on ujukomaarv, kuid meie, inimesed, ei mõtle sellele nii. Meie jaoks ei ole pikkusel 185,2 cm ja 185,3 cm vahet.
Selgub, et saame sarnased väärtused rühmitada rühmadesse 1 cm piires.
Ja kui me veel teame, et väga vähesed inimesed on lühemad kui 50 cm ja pikemad kui 250 cm, siis saame sisuliselt muuta lõpmatu kardinaalsusega välja umbes 200 väärtusega väljaks.
Vajadusel saame muidugi ka tagantjärele täiendava filtreerimise teha.
Suure ribalaiusega probleem
Järgmine probleem bitmap-indeksitega on see, et nende värskendamine võib olla väga kulukas.
Andmebaasid peavad suutma andmeid värskendada, samal ajal kui andmeid otsivad potentsiaalselt sajad muud päringud. Vajame lukke, et vältida probleeme samaaegse juurdepääsuga andmetele või muid jagamisprobleeme. Ja kus on üks suur lukk, seal on probleem - lukuvaidlus, kui see lukk muutub kitsaskohaks.
Seda probleemi saab lahendada või sellest mööda hiilida, kasutades shardingut või versioonide indekseid.
Jagamine on lihtne ja tuntud asi. Saate bitmap-indeksit killustada nagu mis tahes muid andmeid. Ühe suure luku asemel saad hunniku väikseid lukke ja saad seeläbi lahti lukutüli.
Teine viis probleemi lahendamiseks on kasutada versioonidega indekseid. Teil võib olla üks koopia registrist, mida kasutate otsimiseks või lugemiseks, ja üks, mida kasutate kirjutamiseks või värskendamiseks. Ja kord teatud aja jooksul (näiteks iga 100 ms või 500 ms järel) dubleerite need ja vahetate need. Loomulikult on see lähenemisviis rakendatav ainult juhtudel, kui teie rakendus saab hakkama veidi mahajäänud otsinguindeksiga.
Neid kahte lähenemisviisi saab kasutada samaaegselt: teil võib olla killustatud versiooniindeks.
Keerulisemad päringud
Viimane probleem bitmap-indeksitega on see, et meile öeldakse, et need ei sobi hästi keerukamate päringute tüüpide jaoks, nagu näiteks ulatuspäringud.
Tõepoolest, kui järele mõelda, siis sellised bitioperatsioonid nagu JA, VÕI jne ei sobi eriti päringute jaoks a la “Näita mulle hotelle, mille toahinnad on 200–300 dollarit öö kohta”.
Naiivne ja väga ebamõistlik lahendus oleks võtta iga dollari väärtuse tulemused ja kombineerida need bitipõhise VÕI-tehtega.
Veidi parem lahendus oleks kasutada rühmitamist. Näiteks 50-dollarilistes rühmades. See kiirendaks meie protsessi 50 korda.
Kuid probleemi saab hõlpsasti lahendada ka spetsiaalselt seda tüüpi päringu jaoks loodud vaate abil. Teadustöödes nimetatakse seda vahemiku kodeeringuga bitmapiks.
Selles esituses ei määra me mõne väärtuse jaoks ainult ühte bitti (näiteks 200), vaid seame selle väärtuse ja kõik suuremaks. 200 ja rohkem. Sama 300: 300 ja üle selle. Ja nii edasi.
Seda esitust kasutades saame seda tüüpi otsingupäringule vastata, läbides indeksi vaid kaks korda. Kõigepealt saame nimekirja hotellidest, kus tuba maksab vähem ehk $300 ja seejärel eemaldame sealt need, kus tuba maksab vähem ehk $199. Valmis.
Teid üllatab, kuid isegi geopäringud on bitmap-indeksite abil võimalikud. Trikk on kasutada geomeetrilist esitust, mis ümbritseb teie koordinaati geomeetrilise kujundiga. Näiteks S2 Google'ilt. Figuuri peab olema võimalik esitada kolme või enama ristuva joonena, mida saab nummerdada. Nii saame oma geopäringu muuta mitmeks päringuks “piki vahet” (mööda neid nummerdatud ridu).
Valmis lahendused
Loodan, et huvitasin teid pisut ja nüüd on teie arsenalis veel üks kasulik tööriist. Kui teil on kunagi vaja midagi sellist teha, siis teate, kuidas vaadata.
Kõigil pole aga aega, kannatlikkust ega ressursse bitmap-indeksite nullist loomiseks. Eriti arenenumad, kasutades näiteks SIMD-d.
Õnneks on teile abiks mitu valmislahendust.
Möirgavad bitmapid
Esiteks on see sama mürisev bitmaps-teek, millest ma juba rääkisin. See sisaldab kõiki vajalikke konteinereid ja bititoiminguid, mida vajate täisväärtusliku bitmap-indeksi loomiseks.
Kahjuks ei kasuta hetkel ükski Go juurutus SIMD-d, mis tähendab, et Go teostused on vähem jõudsad kui näiteks C juurutused.
Pilosa
Teine toode, mis teid aidata võib, on Pilosa DBMS, millel on tegelikult ainult bitmap indeksid. See on suhteliselt uus lahendus, kuid võidab südameid suurel kiirusel.
Pilosa kasutab sisemiselt möirgavaid bittraate ja annab teile võimaluse neid kasutada, lihtsustab ja selgitab kõiki asju, millest ma eespool rääkisin: rühmitamine, vahemiku kodeeringuga bitikaardid, välja mõiste jne.
Vaatame lühidalt näidet Pilosa kasutamisest, et vastata juba tuttavale küsimusele.
Näide on väga sarnane sellele, mida varem nägite. Loome Pilosa serverile kliendi, loome indeksi ja vajalikud väljad, seejärel täidame oma väljad tõenäosustega juhuslike andmetega ja lõpuks täidame tuttava päringu.
Pärast seda kasutame väljal "kallis" EI, seejärel lõigame tulemuse (või JA selle) väljaga "terrass" ja väljaga "reserveeringud". Ja lõpuks saame lõpptulemuse.
Loodan väga, et lähitulevikus ilmub see uut tüüpi indeks ka sellistesse andmebaasisüsteemidesse nagu MySQL ja PostgreSQL – bitmap indeksid.
Järeldus
Kui sa pole veel magama jäänud, siis tänan. Pidin ajapiirangu tõttu põgusalt paljusid teemasid puudutama, kuid loodan, et jutt oli kasulik ja ehk isegi motiveeriv.
Bitmap-indeksite kohta on hea teada, isegi kui te neid praegu ei vaja. Olgu need teie tööriistakastis veel üks tööriist.
Vaatasime Go jaoks erinevaid jõudlusnippe ja asju, millega Go kompilaator veel eriti hästi hakkama ei saa. Kuid see on igale Go programmeerijale kasulik teada.
See on kõik, mida ma teile öelda tahtsin. Aitäh!
Allikas: www.habr.com