Bitmap-indeksid Go-s: metsik kiirus

Sissejuhatus

Esitasin selle ettekande inglise keeles GopherCon Russia 2019 konverentsil Moskvas ja vene keeles mitmal korral Nizhni Novgorodis. Räägin bitmap-indeksist — vähem levinud kui B-puu, kuid mitte vähem huvitav. Jagame salvestust konverentsiettekandest inglise keeles ja skripti vene keeles.

Külastame, kuidas bitmap-indeks töötab, millal see on parem ja millal halvem kui teised indeksid ning millal on see neist märkimisväärselt kiirem; näeme, millistes populaarsetes DBMS-ides on juba bitmap-indeksid; proovime kirjutada enda oma Go-s. Ja "magustoiduks" kasutame valmis teeke, et luua oma superkiire spetsialiseeritud andmebaas.

Loodan väga, et minu töötooted on teile kasulikud ja huvitavad. Olgu alustame!

Sissejuhatus

Tere kõigile! Praegu on kell kuus õhtul, me kõik oleme väsinud. Suurepärane aeg rääkida igavast andmebaasi indeksite teooriast, eks? Ärge muretsege, mul on siin ja seal paar rida lähtekoodi. 🙂

Kui tõsiselt rääkida, siis ettekand praktiliselt uputab meid informatsiooniga, ja meil ei ole palju aega. Seega, alustame.

Täna räägin järgmistest teemadest:

• mis on indeksid;
• mis on bitmap-indeks;
• kus seda kasutatakse ja kus seda EI KASUTATA ja miks;
• lihtne teostus Go keeles ja veidi võitlust kompilaatoriga;
• veidi vähem lihtne, kuid palju tõhusam teostus Go-assembleris;
• bitmap-indeksite 'probleemid';
• olemasolevad rakendused.

Mis on siis indeksid?

Indeks on eraldi andmestruktuur, mida hoiame ja uuendame koos peamistest andmetest. Seda kasutatakse otsingu kiirendamiseks. Ilma indeksiteta nõuaks otsing täielikku andmete läbivaatamist (protsess, mida nimetatakse täisakaane skaneerimiseks), ja selle protsessi keerukus on lineaarne. Kuid andmebaasid sisaldavad tavaliselt tohutult palju andmeid ja lineaarne keerukus on liiga aeglane. Ideaalis sooviksime logaritmilist või konstantset keerukust.

See on tohutu keeruline teema, mis on täis nüansse ja kompromisse, kuid vaadates mitme aastakümne arendust ja uurimist erinevates andmebaasides, olen valmis väitma, et on vaid paar laialdaselt kasutatavat lähenemist andmebaasi indeksite loomisele.

Esimene lähenemine seisneb otsinguala hierarhilises vähendamises, jagades otsinguala väiksemateks osadeks.

Tavaliselt teeme seda erinevat tüüpi puude abil. Näiteks võib see olla suur kast materjalidega teie kapis, kus on väiksemad kastid, mis on jagatud erinevateks teemadeks. Kui teil on materjale vaja, otsite neid kindlasti kastist, mille peal on kiri „Materjalid“, mitte sellest, mille peal on kirjutatud „Küpsised“, eks?

Teine lähenemine on kohe vajalik elemendi või elementide rühma tuvastamine. Me teeme seda hash-kaartide või pöördkataloogide abil. Hash-kaartide kasutamine on väga sarnane eelnevale näitele, ainult et teie kapis on hunnik väikseid karpe lõppartiklitega, mitte kastid karpidega.

Kolmas lähenemine on eemaldada vajadus otsimise järele. Seda teeme Bloom-filterite või cuckoo-filterite abil. Esimesed annavad vastuse viivitamatult, vabastades teid otsimise vajadusest.

Viimane lähenemine seisneb kõikide kaasaegse riistvara pakkumiste täielikus kasutamises. Just seda teeme bitmap-indeksite abil. Jah, nende kasutamise puhul peab meil mõnikord kogu indeks läbi käima, kuid teeme seda superefektiivselt.

Nagu ma juba ütlesin, on andmebaasi indeksite teema ulatuslik ja täis kompromisse. See tähendab, et mõnikord saame kasutada mitut lähenemist koos: kui peame otsingu veelgi kiiremaks muutma või kui on vaja katta kõikvõimalikud otsingutüübid.

Täna räägin ma kõige vähem tuntud lähenemisviisist — bitmap-indeksite kohta.

Kes ma olen, et sellest rääkida?

Olen Badoo tiimijuht (võib-olla tunnete te paremini meie teist toodet — Bumble). Meie hulgas on juba üle 400 miljoni kasutaja üle kogu maailma ning palju funktsioone, mis aitavad neil leida parima paari. Teeme seda kohandatud teenuste abil, mis kasutavad sealhulgas ka bitmap-indekseid.

Mis siis ikkagi on bitmap-indeks?

Bitmap-indeksid, nagu nimi viitab, kasutavad bitmap'e ehk bitisette, et ellu viia otsinguindeks. Lindude kõrguselt näeb see indeks välja nagu üks või mitu sellist bitmap'i, mis kujutavad erinevaid entiteete (nt inimesi) ja nende omadusi või parameetreid (vanus, silmade värv jms), ning algoritm, mis kasutab bititehteid (AND, OR, NOT) otsingu päringute vastamiseks.

Meile öeldakse, et bitmap-indeksid sobivad kõige paremini ja on väga tõhusad juhtudel, kui otsing ühendab päringuid paljude vähe arvu saavutavate veergude kaudu (kujuta ette "silmade värv" või "peresituatsioon" võrreldes millegagi nagu "kaugus kesklinnast"). Kuid hiljem näitan, et need töötavad suure arvnäitajaga veergude puhul samuti suurepäraselt.

Vaadakem kõige lihtsamat bitmap-indeksi näidet.

Kujutage ette, et meil on nimekiri Moskvast restoranidest, millel on binaarsed omadused nagu:

• lähedal metroo (near metro);
• privaatne parkimine (has private parking);
• terrass (has terrace);
• on võimalik broneerida laud (accepts reservations);
• sobib taimetoitlastele (vegan friendly);
• kallis (expensive).

Anname igale restoranile järjestusnumber, alates 0, ja eraldame mälu 6 bitmapi jaoks (üks iga omaduse jaoks). Siis täidame need bitmapi sõltuvalt sellest, kas restoran omab antud omadust või mitte. Kui restoranil 4 on terrass, siis bit №4 bitmapi «on terrass» asetatakse väärtuseks 1 (kui terrassi pole, siis 0).

Nüüd on meil kõige lihtsam bitmap-indeks, mida saab kasutada vastamiseks päringutele nagu:

• „Näita mulle restorane, mis sobivad taimetoitlastele”;
• „Näita mulle soodsaid restorane terrassiga, kus saab laudadele broneerida”.

Kuidas? Vaatame. Esimene päring on väga lihtne. Kõik, mida meil vaja on, on võtta bitmap «sobib taimetoitlastele» ja muuta see restoranide nimekirjaks, mille bitid on aktiivsed.


Teine päring on natuke keerulisem. Peame rakendama bititehet NOT bitmapi "kallis" kasutamiseks, et saada nimekiri soodsamate restoranide kohta, seejärel ANDime selle "broneeritava kaupluse" bitmapiga ja ANDime tulemuse "on terrass" bitmapiga. Saadud bitmap sisaldab kõiki meie kriteeriume vastavaid asutusi. Antud näites on see ainult restoran "Noorus".


Siin on palju teooriat, kuid ärge muretsege, peagi näeme koodi.

Kus kasutatakse bitmap-indekseid?

Kui otsite "bitmap-indekseid", on 90% vastustest seotud Oracle DB-ga. Kuid teised andmebaasi haldustarkvarad toetavad kindlasti ka selliseid ägedaid asju, eks? Mitte päris.

Vaatame peamiste kahtlusaluste nimekirja.

MySQL ei toeta veel bitmap-indekseid, kuid on olemas ettepanek selle valiku lisamiseks (https://dev.mysql.com/worklog/task/?id=1524).

PostgreSQL ei toeta bitmap-indekseid, kuid kasutab lihtsaid bitmape ja bititehteid, et ühendada otsingu tulemusi mitme teise indeksi kaudu.

Tarantoolil on bitset-indeksid, see toetab nendega lihtsat otsingut.

Redisel on lihtsad bitiväljad (https://redis.io/commands/bitfield) ilma nende otsimisvõimaluseta.

MongoDB ei toeta veel bitmap-indekseid, kuid on olemas ettepanek selle võimaluse lisamiseks. https://jira.mongodb.org/browse/SERVER-1723

Elasticsearch kasutab bitmap'e sees. (https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps).

• Kuid meie majas on uus naaber: Pilosa. See on uus mitte-relineeriv andmebaas, kirjutatud Go keeles. See sisaldab ainult bitmap-indekseid ja põhineb täielikult nende peal. Räägime sellest hiljem.

Rakendus Go-s

Aga miks on bitmap-indeksid nii harva kasutusel? Enne kui vastan sellele küsimusele, tahaksin näidata teile väga lihtsa bitmap-indeksi rakendust Go-s.

Bitmap'id on põhimõtteliselt lihtsalt andmeosad. Go-s kasutame selleks baitide arvutustükke.

Meil on üks bitmap iga restorani omaduse kohta, ja iga bit bitmap'is näitab, kas konkreetses restoranis on see omadus või mitte.

Me vajame kahte abifunktsiooni. Üks neist kasutatakse meie bitikaartide täitmiseks juhuslike andmetega. Juhuslike, kuid teatud tõenäosusega, et restoranil on iga omadus. Näiteks arvan, et Moskvas on väga vähe restorane, kus ei saa broneerida lauda, ja mulle tundub, et umbes 20% kohtadest sobib taimetoitlastele.

Teine funktsioon muudab bitikaardi restoranide nimekirjaks.


Küsimusele «Näita mulle odavaid restorane, kus on terrass ja kus saab broneerida lauda» vastamiseks vajame kahte bititehnikat: NOT ja AND.

Me saame oma koodi veidi lihtsustada, kasutades keerukamat AND NOT operatsiooni.

Meil on igaüks neist operatsioonidest kohta funktsioonid. Mõlemad läbivad viisil põhjalikult, võtavad igaühe vastavad elemendid ja ühendavad need bititehnikaga ning paneb tulemuse tulemuste viisi.

Nüüd saame kasutada oma bitikaarte ja funktsioone, et vastata otsingupäringule.

Jõudlus ei ole kuigi kõrge, kuigi funktsioonid on väga lihtsad ja me säästsime kenasti, kuna me ei tagastanud uut tulemuste massi igal funktsiooni kutsumisel.

Tehes natuke profiliseerimist pprof'iga, märkasin, et Go kompilaator jättis ühe väga lihtsa, kuid väga olulise optimeerimise vahele: funktsiooni sisenemine.

Asi on selles, et Go kompilaator kardab kohutavalt silmusid, mis käivad massiivide kaudu, ja keelab resoluutselt funktsioonide sisenemise, mis sisaldavad selliseid silmuseid.

Aga mina ei karda ja saan petta kompilaatorit, kasutades goto tsükli asemel, nagu vanad head ajad.

Ja nagu näete, kompilaator rõõmuga siseneb meie funktsiooni! Lõpuks õnnestub meil kokku hoida umbes 2 mikrosekundit. Mitte paha!

Teise kitsaskoha võib kergesti märgata, kui vaadata assembleri väljundit hoolikalt. Kompilaator lisas piiride kontrolli otse meie kõige kuumemasse tsüklisse. Asi on selles, et Go on turvaline keel; kompilaator kardab, et minu kolm argumenti (kolm slicet) võivad olla erineva suurusega. Sel juhul oleks teoreetiliselt võimalik nii-öelda puhverdusülekoormus.

Rahu nimel, näitame kompilaatorile, et kõigil slicetel on sama suurus. Saame selle saavutada, lisades meie funktsiooni algusesse lihtsa kontrolli.

Seda nähes laseb kompilaator kontrolli rõõmuga mööda ning me säästame lõpuks veel 500 nanosekundit.

Suured partiid

Okei, me suutsime okkar midagi meie lihtsast rakendusest välja pigistada, kuid see tulemus on tegelikult palju hullem, kui praeguse rauaga võimalik oleks.

Kõik, mida me teeme, on põhilised bititehingud, ja meie protsessorid täidavad neid väga efektiivselt. Kahjuks "toidame" meie protsessorit väga väikeste tööosadega. Meie funktsioonid töötlevad tehinguid byte kaupa. Saame oma koodi väga lihtsalt häälestada, et see töötaks 8-baidiste tükkidega, kasutades UInt64 lõike.

Nagu näete, kiirendas see väike muudatus meie programmi kaheksa korda, suurendades partii suurust kaheksa korda. Kasu on ütleme, lineaarne.

Rakendamine assembleris

Aga see ei ole veel lõpp. Meie protsessorid saavad töötada tükkidega, mis on 16, 32 ja isegi 64 baiti. Selliseid „laiade“ tehingute nimetatakse single instruction multiple data (SIMD; üks käsk, palju andmeid), ja protsessi, mille käigus kood muudetakse nii, et see kasutab selliseid tehinguid, nimetatakse vektoreerimiseks.

Kahjuks ei ole Go kompilaator kaugeltki vektoreerimise meister. Praegu on ainus viis Go koodi vektoreerida, võttes ja asetades andmed tehingud käsitsi, kasutades Go assemblerit.

Go assembler on kummaline loom. Te tõenäoliselt teadsite, et assembler on midagi, mis on tugevalt seotud arvuti arhitektuuriga, mille jaoks te kirjutate, kuid Go puhul ei ole see nii. Go assembler sarnaneb pigem IRL (vahe-representatsioonikeel) või vahekeelele: see on praktiliselt platvormist sõltumatu. Rob Pike esitas sellel teemal suurepärase ettekanne kõne paar aastat tagasi GopherCon'il Denvers.

Lisaks sellele kasutab Go ebatavalist Plan 9 formaati, mis erineb tunnustatud AT&T ja Intel formaatidest.

Võib julgelt öelda, et Go assembleri käsitsi kirjutamine ei ole kõige lõbusam tegevus.

Kuid õnneks on juba olemas kaks kõrgema taseme tööriista, mis aitavad meil Go assemblerit kirjutada: PeachPy ja avo. Mõlemad utiliidid genereerivad Go-assemblerit kõrgema taseme koodist, mis on kirjutatud vastavalt Pythonis ja Go's.

Need utiliidid lihtsustavad selliseid asju nagu register allocation (protsessoriregistri valimine), tsüklite kirjutamine ja muudavad üldiselt Go assembleri maailma sisenemise protsessi lihtsamaks.

Kasutame avo't, nii et meie programmid on peaaegu tavalised Go programmid.

Nii näeb välja kõige lihtsam näide avo-programmist. Meil on funktsioon main(), mille sees on defineeritud funktsioon Add(), mille eesmärk on kahe numbri liitmine. Siin on ka abifunktsioonid parameetride saamiseks nime järgi ja ühte vaba ning sobivat protsessori registrit saamiseks. Igal protsessoritegevusel on vastav funktsioon avo keeles, nagu näha ADDQ-st. Ja lõpuks näeme abifunktsiooni tulemuse väärtuse salvestamiseks.

Käivitades go generate, täidame programmi avo ja genereerime lõpuks kaks faili:

• add.s, mis sisaldab Go-montaažikoodi;
• stub.go, mis sisaldab funktsioonide pealkirju kahe maailma ühendamiseks: Go ja montaaž.

Nüüd, kui oleme näinud, mida ja kuidas avo teeb, vaatame meie funktsioone. Olen rakendanud nii skalaarset kui ka vektorkujulist (SIMD) versiooni funktsioonidest.

Esmalt vaatame skalaarseid versioone.

Nagu eelnevas näites, palume anda meile vaba ja õige üldotstarbeline register, me ei pea argumentide nihkeid ja mõõtmeid arvutama. Kõike seda teeb avo meie eest.

Varem kasutasime silte ja hüppeid (või hüppeid), et parandada jõudlust ja petta Go kompilaatorit, kuid nüüd teeme seda algusest peale. Tõde on see, et tsüklid on kõrgema taseme mõisted. Assembleris on meil ainult sildid ja hüpped.

Ülejäänud kood peaks olema juba tuttav ja arusaadav. Me emuleerime tsüklit siltide ja hüpetega, võtame väikese osa andmeid kahest meie slice'ist, ühendame need bititehte (AND NOT sel juhul) ja paneme tulemuse tulemuslikku slice'i. Kõik.

Nii näeb välja lõplik kood assembleris. Me ei pidanud arvutama nihkeid ja suurusi (marked green) ega jälgima kasutatavaid registreid (marked red).

Kui võrrelda assembleri rakenduse jõudlust parima Go rakenduse jõudlusega, näeme, et need on võrdväärsed. Ja see on ootuspärane. Me ei teinud midagi erilist — me lihtsalt kopeerisime, mida teeks Go kompilaator.

Kahjuks ei saa me kompilaatorit sundida meie assembleris kirjutatud funktsioone inlinesema. Go kompilaatoril puudub tänase päevani selline võimalus, kuigi selle lisamise soov on juba pikka aega olemas.

Just sellepärast ei saa me mingit kasu väikestest assembleri funktsioonidest. Peame kas kirjutama suuri funktsioone või kasutama uut math/bits paketti, või vältima assemblerit üldse.

Vaadakem nüüd meie funktsioonide vektorkoopiaid.

Selle näite jaoks otsustasin kasutada AVX2, seega kasutame 32-baidiste tükkidega töötavaid operatsioone. Koodi struktuur on väga sarnane skalaarversiooniga: parameetrite laadimine, palve meie jaoks vaba üldregistredi saamiseks jne.

Üks uuendus on see, et laiemad vektori operatsioonid kasutavad spetsiaalseid laiu registreid. 32-baidiste tükkide puhul on need Y-prefiksiga registrid. Seetõttu näete koodis funktsiooni YMM(). Kui ma oleksin kasutanud AVX-512 koos 64-bitiste tükkidega, oleks prefiks olnud Z.

Teine uuendus seisneb selles, et otsustasin kasutada optimeerimist, mida nimetatakse tsükli avamiseks (loop unrolling), s.t. teha kaheksa tsüklioperatsiooni käsitsi, enne kui hüppame tsükli algusesse. See optimeerimine vähendab koodis harude arvu ja on piiratud olemasolevate vabade registeride hulgaga.

Aga kuidas siis jõudlus? See on suurepärane! Saime kiirusetaotluse umbes seitse korda kiiremini võrreldes parima lahendusega Go-s. Muljetavaldav, eks?

Kuid isegi seda rakendust oleks potentsiaalselt võimalik kiirendada, kasutades AVX-512, eelprefetchingut või JIT (just-in-time compiler) päringute planeerijale. Kuid see on kindlasti eraldi ettekande teema.

Bitmap-indekside probleemid

Nüüd, kui oleme juba uurinud lihtsat bitmap-indeksi rakendust Go-s ja palju tootlikumat assembleris, räägime lõpuks sellest, miks bitmap-indekseid kasutatakse nii harva.

Vanades teadusartiklites mainitakse kolme bitmap-indeksi problema, kuid uuemad teadustööd ja mina väidame, et need on juba aegunud. Ei lasku sügavale igasse neist problemidest, vaid käsitleme neid pinnapealselt.

Suur kardinaalsuse probleem

Nii et meile öeldakse, et bitmap-indeksid sobivad ainult vähe väärtustega välja jaoks, see tähendab, et neil on vähe väärtusi (näiteks sugu või silmade värv), ja põhjus on see, et tavaline kujutamine selliste välja (üks bitt väärtuse kohta) suure kardinaalsuse puhul võtaks liiga palju ruumi ja peale selle oleksid need bitmap-indeksid halvasti (harva) täidetud.


Mõnikord saame kasutada muud kujutamist, näiteks standardset, mida kasutame numbrite kujutamiseks. Aga just kokkusurumismeetodite ilmumine muutis kõike. Viimase paarikümne aasta jooksul on teadlased ja uurijad välja mõelnud rohkelt algorytme bitmapide kokkusurutamiseks. Nende peamine eelis on see, et bitmapide avamiseks pole vaja — me saame bitoperatsioone teha otse kokkusurutud bitmapide peal.

Viimase ajal on hakanud ilmnema ka hübriidlahendused, nagu näiteks roaring bitmaps. Need kasutavad samaaegselt kolme erinevat esitlemisviisi bitmappide jaoks — nimelt bitmaps, massiivid ja nn bit runs — ning tasakaalustavad nende vahel, et maksimeerida jõudlust ja minimeerida mälutarvet.

Roaring bitmaps'e võib leida paljudes populaarsetes rakendustes. Juba on olemas tohutult palju teostusi erinevates programmeerimiskeeltes, sealhulgas üle kolme teostuse Go jaoks.

Veel üks lähenemine, mis võib aidata meil toime tulla suure kardinaalsusega, on rühmitamine (binning). Kujutage ette, et teil on väli, mis esindab inimese pikkust. Pikkus on ujuvnumber, kuid meie, inimesed, ei mõtle sellele nii. Meie jaoks pole vahet 185,2 cm ja 185,3 cm vahel.

Seega saame sarnased väärtused grupeerida rühmadesse, mille suurus on 1 cm ulatuses.

Ja kui me veel teame, et väga vähestel inimestel on pikkus alla 50 cm või üle 250 cm, siis saame põhimõtteliselt muuta lõpmatu kardinaalsusega välja umbes 200 väärtusega väljaks.

Muidugi, vajadusel saame teha täiendava filtreerimise ka hiljem.

Suure läbilaskevõime probleem

Järgmine bitmap-indeksite probleem on see, et nende uuendamine võib olla väga kulukas.

Andmebaasid peavad võimaldama andmete uuendamist hetkel, kui potentsiaalselt sajad muud päringud otsivad neid andmeid. Me vajame lukke, et vältida andmete samasuguseid probleeme või muid juurdepääsulubade probleeme. Kui on olemas üks suur lukk, siis tekib probleem — lock contention, kui see lukk muutub kitsaskohaks.

Seda probleemi saab lahendada või ümber minna andmete jagamise või versioneeritud indeksite kasutamise kaudu.

Andmete jagamine on lihtne ja üldtuntud asi. Saate jagada bitmap-indeksi nii, nagu jagaksite kõiki teisi andmeid. Ühe suure luku asemel saate hulga väikeseid lukke ja seeläbi vabanete lock contention'ist.

Teine võimalus probleemi lahendamiseks on versioonitud indeksite kasutamine. Teil võib olla üks indeksikoor, mida te otsimiseks või lugemiseks kasutate, ja teine - kirjutamiseks või uuendamiseks. Ja iga teatud aja järel (nt iga 100 ms või 500 ms) teete neist koopiad ja vahetate neid. Loomulikult on see lähenemine rakendatav ainult juhtudel, kui teie rakendus suudab töötada veidi aeglasema otsinguindeksi abil.

Neid kahte lähenemist saab kasutada samaaegselt: teil võib olla jaotatud versioonitud indeks.

Komplekssemad päringud

Bitmap-indeksite viimane probleem on see, et nagu öeldakse, ei sobi nad hästi keerukamate päringute, näiteks „vahemiku” päringute jaoks.

Ja tõepoolest, kui sellele mõelda, ei sobi bititehteid nagu AND, OR jms päringuteks, mis ütlevad „Näita mulle hotelle, mille toade maksumus on 200 kuni 300 dollarit öö kohta”.

Naiv ja väga mõistlik lahendus oleks võtta tulemused iga dollari väärtuse jaoks ja ühendada need bititehte OR abil.

Veidi parema lahendusena oleks kasutada rühmitamist. Näiteks 50 dollari kaupa. See kiirendaks meie protsessi 50 korda.

Kuid probleem lahendatakse samuti kergesti, kasutades ettevalmistatud esitust, mis on loodud spetsiaalselt selliste päringute jaoks. Teadusartiklites nimetatakse seda vahemikku kodeeritud bitmapideks.

Sellises esituses me ei pane lihtsalt ühte bitti mingi väärtuse (näiteks 200) jaoks, vaid esitame selle väärtuse ja kõik, mis on kõrgem. 200 ja rohkem. Sama kehtib 300 kohta: 300 ja rohkem. Nii edasi.

Kasutades seda esitust, saame sellistele otsingupäringutele vastata, läbides indeksi vaid kaks korda. Esiteks saame nimekirja hotelle, kus toa hind on alla 300 dollari, ja seejärel eemaldame neist need, kus toa hind on alla 199 dollari. Valmis.

Te üllatute, kuid isegi geoküsimused on võimalikud bitmap-indeksite abil. Trikk on kasutada geoesitust, mis ümbritseb teie koordinaati geomeetrilise kujundi abil. Näiteks Google'i S2. Kujundit tuleks olla võimalik esitada kolme või enama üksteisega ristuva joonega, mida saab nummerdada. Nii saame muuta meie geoküsimuse mitmeks «vahe» päringuks ( nende nummerdatud joonte järgi).

Valmis lahendused

Loodan, et see huvi tekitas ja Teie arsenali lisandusid veel üks kasulik tööriist. Kui teil kunagi tuleb teha midagi sarnast, teate, kuhu vaadata.

Kahjuks ei ole kõigil aega, kannatust ja ressursse, et luua bitmap-indekseid nullist. Eriti keerukamaid, kasutades näiteks SIMD-tehnoloogiat.

Õnneks on mitmeid valmis lahendusi, mis võivad teid aidata.

Roaring bitmaps

Esiteks on olemas see tuntud roaring bitmaps raamatukogu, millest ma juba rääkisin. See sisaldab kõiki vajalikke konteinerite ja bititegevusi, mida vajate täiusliku bitmap-indeksi loomiseks.

Kahjuks ei kasuta hetkel ükski Go teostus SIMD-d, mis tähendab, et Go teostused on vähem tootlikud kui C keeltes teostused.

Pilosa

Teine toode, mis võib aidata, on andmebaas Pilosa, millel on põhimõtteliselt ainult bitmap-indeksid. See on suhteliselt uus lahendus, kuid vallutab südameid tohutu kiirus.

Pilosa kasutab enda sees roaring bitmaps'i, andes teile võimaluse neid kasutada, lihtsustades ja selgitades kõiki eelnevalt mainitud aspekte: gruppeerimine, range-encoded bitmaps, välja mõisted jne.

Vaatame kiirelt Pilosa kasutamise näidet, et vastata juba tuttavale küsimusele.

Näide on väga sarnane sellele, mida olete varem näinud. Loome Pilosa serveri kliendi, loome indeksi ja vajalikud väljad, seejärel täidame meie väljad juhuslike andmetega tõenäosustega ning lõpuks sooritan tuttava päringu.

Peale seda kasutame NOT välja «expensive» peale, seejärel ristsime tulemuse (või AND-ime) välja «terrace» ja välja «reservations». Ja lõpuks saame lõpliku tulemuse.

Loodan tõeliselt, et peagi ilmuvad sellised uued indeksitüübid nagu bitmap-indeksid ka andmebaasidesse nagu MySQL ja PostgreSQL.

Kokkuvõte

Kui te pole veel uinunud, siis aitäh. Mul tuli puudutada paljusid teemasid ajapiirangu tõttu, kuid loodan, et ettekandest oli kasu ja see oli võib-olla isegi inspireeriv.

Bitmap-indeksite kohta on hea teada, isegi kui need ei ole teile hetkel vajalikud. Las nad jäävad teie tööriistakasti veel üheks tööriistaks.

Me oleme arutanud erinevaid nippe Go jõudluse suurendamiseks ja asju, millega Go kompilaator veel liiga hästi toime ei tule. Seda on tõeliselt kasulik teada igale Go programmeerijale.

See on kõik, mida tahtsin jagada. Aitäh!

Allikas: habr.com