Bitmap-indeksid Go-s: otsimine metsiku kiirusel

Sissejuhatav sõna

Esitasin selle ettekande inglise keeles konverentsil GopherCon Venemaa 2019 Moskvas ja vene keeles kohtumisel Nizhni Novgorodis. Räägin bitmap-indeksist — vähem levinud, kui B-puu, kuid mitte vähem huvitav. Jagatud salvestus ettekandest konverentsil inglise keeles ja tekstiline tõlge vene keeles.

Käsitleme, kuidas bitmap-indeks töötab, millal on see parem, millal halvem kui teised indeksid ja millal on see neist oluliselt kiirem; näeme, millistes populaarsetes andmebaasisüsteemides juba on bitmap-indekseid; proovime kirjutada oma Go-s. Ja „magustoiduks“ kasutame valmis raamatukogusid, et luua oma superkiire spetsialiseeritud andmebaas.

Loodan tõeliselt, et mu töö leidub teile kasulik ja huvitav. Lähme!

Sissejuhatus

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

Tõsiselt rääkides, ettekande on informatsiooni täis, kuid meie aega pole palju. Seega alustame.

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

• mis on indeksid;
• mis on bitmap-indeks;
• kus seda kasutatakse ja kus ei kasutata ning miks;
• lihtne rakendus Go-s ja natuke võitlust kompilaatoriga;
• veidi vähem lihtne, kuid palju tõhusam rakendus Go-assembleril;
• "probleemid" bitmap-indeksitega;
• olemasolevad rakendused.

Mis siis on indeksid?

Indeks on eraldiseisev andmestruktuur, mida hoiame ja uuendame peamise andmekogumi lisana. Seda kasutatakse otsingu kiirendamiseks. Ilma indeksiteta nõuaks otsing andmete täielikku läbimist (protsess, mida nimetatakse full scaniks), ja selle protsessi algoritmiline keerukus on lineaarne. Kuid andmebaasid sisaldavad tavaliselt tohutul hulgal andmeid, ning lineaarne keerukus — see on liiga aeglane. Ideaalis tahaksime saavutada logaritmilise või konstantse.

See on tohutu keeruline teema, täis nüansse ja kompromisse, kuid vaadates aastate jooksul eri andmebaaside arengut ja uurimist, olen valmis väitma, et andmebaasi indeksite loomiseks on vaid mõned laialdaselt kasutatavad lähenemisviisid.

Esimene lähenemine hõlmab otsingupiirkonna hierarhilist vähendamist, jagades otsingupiirkonna väiksemateks osadeks.

Tavaliselt teeme seda erinevat tüüpi puude abil. Näiteks võib tuua suure kasti materjalidega teie riidekapis, mis sisaldab väiksemaid kaste, mis on jaotatud erinevate teemade järgi. Kui vajate materjale, siis otsite kindlasti materjalide sildiga kastist, mitte küpsiste sildiga kastist, eks?

Teine lähenemine on kohe vajaliku elemendi või elementide rühma eristamine. Teeme seda hash-map'ide või pöördindeksite abil. Hash-map'ide kasutamine sarnaneb eelnevale näitele, ainult et teie kapis on hulk väikseid kaste lõplike esemete kogumitega.

Kolmas lähenemine on vabaneda otsingu vajadusest. Selle teeme Bloom-filtrite või cuckoo-filtrite abil. Esimesed annavad vastuse kohe, vabastades teid otsimise kohustusest.

Viimane lähenemine on täielikult kasutada kõiki võimeid, mida tänapäevane riistvara meile pakub. Just seda teeme bitmap-indeхite abil. Jah, nende kasutamisel tuleb meil mõnikord kogu indeks läbi käia, kuid teeme seda ülimalt efektiivselt.

Kuidas ma juba ütlesin, on andmebaasi indeksite teema ulatuslik ja täis kompromisse. See tähendab, et mõnikord saame kasutada mitut lähenemist korraga: kui peame otsingut veelgi kiiremaks muutma või kui on vaja katab kõiki võimalikke otsingutüüpe.

Täna räägin ma kõige vähem tuntud lähenemisest - bitmap-indeхitest.

Kes ma olen, et sellest teemast rääkida?

Töötan meeskonnajuhina Badoos (võib-olla tunnete paremini meie teist toodet - Bumble). Meil on üle 400 miljoni kasutaja üle kogu maailma ja palju funktsioone, mis aitavad leida neile parima kaaslase. Teeme seda kohandatud teenuste abil, mis kasutavad sealhulgas ka bitmap-indeхite.

Mis siis on bitmap-indeks?

Bitmap-indeksid, nagu nimigi ütleb, kasutavad bitmape või bitsüste, et rakendada otsinguindeksit. Kõrgselt vaadatuna koosneb see indeks ühest või mitmest sellisest bitmapist, mis esindavad teatud entiteete (nt inimesi) ja nende omadusi või parameetreid (vanus, silmade värv jne), ning algoritmist, mis kasutab bititehteid (AND, OR, NOT) otsingu päringule vastamiseks.

Meile öeldakse, et bitmap-indeksid sobivad kõige paremini ja on väga tõhusad olukordades, kus otsingu käigus ühendatakse päringud paljude vähekaariliste veergudega (kujuta ette „silmade värv” või „pereliikmeid” võrreldes millegagi nagu „kaugus linna keskpunktist”). Kuid hiljem näitan ma, et need toimivad suure kaardinaalsusega veergude puhul samuti suurepäraselt.

Vaatame lihtsaimat bitmap-indeksi näidet.

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

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

Andke igale restoranile järjekorranumber alates 0 ja reserveerime mälu 6 bitmapi jaoks (üks igas omaduses). Seejärel täidame need bitmaps sõltuvalt sellest, kas restoran omab antud omadust või mitte. Kui restoranil 4 on terrass, siis bit nr 4 bitmapsis „on terrass” seatakse 1 (kui terrassi pole, siis 0).

Nüüd on meil kõige lihtsam võimalik bitmap-indeks, ja me saame seda kasutada küsimustele vastamiseks, nagu:

• „Näita mulle restorane, mis sobivad taimetoitlastele”;
• „Näita mulle odavaid restorane terrassiga, kus on võimalik broneerida laud”.

Kuidas? Vaatame. Esimene päring on väga lihtne. Kõik, mida me vajame, on võtta bitmap „sobib taimetoitlastele” ja muuta see restoranide nimekirjaks, kelle bitid on seatud.


Teine päring on veidi keerulisem. Peame kasutama BIT operatsiooni NOT bitimapis "kallis", et saada odavate restoranide nimekiri, seejärel AND-ime selle "saab broneerida" bitimapiga ja AND-ime tulemuse "on terrass" bitimapiga. Tulemuseks olev bitimap sisaldab nimekirja asutustest, mis vastavad kõigile meie kriteeriumidele. Sel juhul on see ainult restoran "Noorus".


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

Kus kasutatakse bitmap-indekseid?

Kui te "googeldaksite" bitmap-indekseid, siis 90% vastustest oleksid vahetult seotud Oracle DB-ga. Kuid teised andmebaasid toetavad kindlasti ka sellist ägedat funktsiooni, eks?

Vaatame üle peamised kahtlusalused.

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

PostgreSQL ei toeta bitmap-indekseid, kuid kasutab lihtsaid bitimappe ja bitoperatsioone mitmete teiste indeksite otsingutulemuste ühendamiseks.

Tarantoolil on bitset-indeksid, mis toetavad lihtsat otsingut nende kaudu.

Redis'il on lihtsad bitiväljad (https://redis.io/commands/bitfield) ilma võimaluseta nende kaudu otsida.

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

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

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

Täitmine Go keeles

Aga miks bitmap-indekseid nii harva kasutatakse? Enne sellele küsimusele vastamist tahaksin näidata teile väga lihtsa bitmap-indeksi rakendust Go keeles.

Bitimapid koosnevad tegelikult lihtsalt andmeplokkidest. Go-s kasutame selleks baitide slice'e.

Meil on üks bitimap ühe restorani omaduse jaoks, ja iga bit bitimapis näitab, kas konkreetses restoranis on see omadus või mitte.

Me vajame kahte abifunktsiooni. Üks neist kasutatakse meie bitmapside 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 lauda broneerida, ja mulle tundub, et umbes 20% asutustest sobivad taimetoitlastele.

Teine funktsioon muundab bitmapi restoranide nimekirjaks.


Et vastata päringule "Näita mulle odavaid restorane, kus on terrass ja kus saab lauda broneerida", vajame kahte bititegevust: NOT ja AND.

Saame meie koodi veidi lihtsustada, kasutades keerukamat operaatori AND NOT.

Meil on igasuguste nende tegevuste jaoks funktsioonid. Mõlemad läbivad viipeid, võtavad vastavad elemendid igaühes ning ühendavad need bititegevuse abil ja panevad tulemuse tulemuslikku viipesse.

Ja nüüd saame kasutada meie bitmapsid ja funktsioone, et vastata otsingupäringule.

Jõudlus ei ole nii kõrge, isegi hoolimata sellest, et funktsioonid on väga lihtsad ja me oleme oluliselt kokku hoidnud, kuna ei tagastanud igal funktsiooni kutsumisel uut tulemuslikku viipi.

Pärast mõningast profilimist pprof-iga märkasin, et Go kompilaator jättis ühe väga lihtsa, kuid äärmiselt olulise optimeerimise vahele: funktsiooni inlining.

Fakt on selles, et Go kompilaator kardab kohutavalt viipeid, mis läbivad viipeid, ja keelab kategooriliselt inlining funktsioonide jaoks, mis sisaldavad selliseid silke.

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

Ja nagu näete, kompilaator on nüüd rõõmuga inlining meie funktsiooni! Lõpuks õnnestub meil kokku hoida umbes 2 mikrosekundit. Pole paha!

Teine kitsaskoht on lihtne näha, kui vaatate assembleri väljundit hoolikalt. Kompilaator lisas meie kõige kuumema silmuse sisse viipi piiride kontrolli. Fakt on selles, et Go on turvaline keel, kompilaator kardab, et minu kolm argumenti (kolm viipi) on erineva suurusega. Siis võib teoreetiliselt tekkida niinimetatud puhveri ülevool (buffer overflow).

Lähme rahustame kompilatsiooniprogrammi, näidates talle, et kõikide lõikude suurused on samad. Saame seda teha, lisades meie funktsiooni algusesse lihtsa kontrolli.

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

Suured partiid

Olgu, oleme suutnud meie lihtsast rakendusest mingitki jõudlust välja pigistada, kuid see tulemus on tegelikult palju halvem, kui praeguse riistvara puhul võimalik oleks.

Kõik, mida me teeme, on põhised bititegevused ning meie protsessorid täidavad neid väga tõhusalt. Kuid kahjuks „toidame” oma protsessorit väga väikeste tööosadega. Meie funktsioonid teostavad toimingud baitide kaupa. Saame koodi väga lihtsalt timmida, 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 partiid kaheksa korda. Kasutame, võib öelda, lineaarset kasu.

Assemblerskeemide rakendamine

Aga see pole veel lõpp. Meie protsessorid saavad töötada 16, 32 ja isegi 64 baitiste tükkidega. Selliseid „laiade” toimingute nimetatakse single instruction multiple data (SIMD; üks käsk, palju andmeid), ja protsessi, millega kodeerimist selliselt muudetakse, et see kasutaks selliseid toiminguid, nimetatakse vektoriseerimiseks.

Kahjuks ei ole Go kompilaator vektoriseerimises just kiitust väärt. Praeguseks on ainus viis Go koodi vektoriseerimiseks luua ja sisestada andmed käsitsi Go assembleriga.

Go assembler on kummaline olend. Teate kindlasti, et assembler on midagi, mis on tugevalt seotud arvuti arhitektuuriga, mille jaoks te kirjutate, kuid Go puhul pole see nii. Go assembler sarnaneb rohkem IRL (intermediate representation language) või vahekeelele: see on praktiliselt platvormidevaheline. Rob Pike tegi sellel teemal suurepärase ettekanne esituse mõned aastat tagasi GopherConil Denveris.

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

Saab kindlalt öelda, et Go assembleri käsitsi kirjutamine ei ole just kõige lõbusam tegevus.

Aga õnneks on olemas juba kaks kõrgema taseme tööriista, mis aitavad meid Go assembleri kirjutamisel: PeachPy ja avo. Mõlemad tööriistad genereerivad Go assemblerit kõrgema taseme koodist, mis on kirjutatud vastavalt Pythonis ja Go-s.

Need this utilities simplifies tasks like register allocation, writing loops, and overall simplifies the entry into the world of assembly programming in Go.

We'll be using avo, so our programs will be almost typical Go programs.

Here's what the simplest example of an avo program looks like. We have a main() function that defines an Add() function inside it, which is responsible for adding two numbers. There are helper functions to get parameters by name and to acquire one of the free and suitable CPU registers. Each CPU operation has a corresponding function in avo, as seen with ADDQ. Finally, we see a helper function to store the resulting value.

By calling go generate, we will execute the program on avo and ultimately two files will be generated:

• add.s with the resulting code in Go assembly;
• stub.go with function headers to link the two worlds: Go and assembly.

Now that we've seen what avo does and how it works, let's take a look at our functions. I have implemented both scalar and vector (SIMD) versions of the functions.

First, let's look at the scalar versions.

As in the previous example, we request a free and appropriate general-purpose register, and we don’t need to compute offsets and sizes for the arguments. All of that is handled by avo for us.

Previously we used labels and goto (or jumps) to boost performance and trick the Go compiler, but now we do it from the get-go. The thing is, loops are a higher-level concept. In assembly, we only have labels and jumps.

The remaining code should already be familiar and clear. We emulate a loop with labels and jumps, take a small part of data from our two slices, combine them using a bitwise operation (AND NOT in this case) and then place the result in the resulting slice. That's it.

Here’s what the final code in assembly looks like. We didn't need to calculate offsets and sizes (highlighted in green) or track the used registers (highlighted in red).

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

Kahjuks ei saa me sundida kompilaatorit inline'ima meie assembleris kirjutatud funktsioone. Go kompilaatoril puudub praegu see võimalus, kuigi palve selle lisamiseks on eksisteerinud juba üsna kaua.

Seetõttu ei suuda me saada mingit kasu väikestest funktsioonidest assembleris. Peame kas kirjutama suuri funktsioone, kasutama uut math/bits paketti või vältima assemblerit.

Vaadakem nüüd meie funktsioonide vektorkoopiaid.

Käesolevas näites otsustasin rakendada AVX2, seega kasutame 32-bitiste tükkidega töötavaid operatsioone. Koodistruktuur on väga sarnane skalaari variandile: parameetrite laadimine, palve anda meile tasuta üldregister jne.

Üks uuendus on seotud sellega, et laiemad vektorioperatsioonid kasutavad spetsiaalseid laiu registreid. 32-bitiste tükkide puhul on need registrid, mille eelotsik on Y. Just seetõttu näete koodis funktsiooni YMM(). Kui oleksin kasutanud AVX-512 64-bitiste tükkidega, siis oleks eelotsik Z.

Teine uuendus tuleneb sellest, et otsustasin kasutada optimeerimist, mida nimetatakse tsükli lahtimurdmiseks (loop unrolling), see tähendab, et tegin kaheksa tsükli operatsiooni käsitsi, enne kui hüppasin tsükli algusesse. See optimeerimine vähendab koodis harude (branch) arvu ning on piiratud vaba registreid, mis on saadaval.

Aga kuidas on jõudlusega? See on suurepärane! Saime kiiruskasvu ligikaudu seitsme võrra võrreldes parima lahendusega Go-s. Muljetavaldav, kas pole?

Aga isegi seda rakendust oleks potentsiaalselt võimalik kiirendada, kasutades AVX-512, prefetšimist või JIT (just-in-time compiler) päringute planeerimise jaoks. Kuid see on juba täiesti eraldi ettekande teema.

Bitmap-indeksite probleemid

Nüüd, kui oleme vaadanud Go lihtsat bitmap-indeksi rakendust ja palju efektiivsemat assembleris, räägime lõpuks sellest, miks bitmap-indeksid on nii harva kasutusel.

Vanades teadusartiklites mainitakse bitmap-indeksite kolme probleemi, kuid uuemad teadusartiklid ja mina väidame, et need on juba aegunud. Ärme süvene sügavale igasse neist probleemidest, vaid käsitleme neid pinnapealselt.

Suure kardinaalsuse probleem

Nii ütlevad meile, et bitmap-indeksid sobivad ainult väikese kardinaalsusega väljadele, st väljadele, millel on vähe väärtusi (nt sugu või silmade värv), ja põhjus on see, et tavaline esitus nende väljade puhul (üks bitt väärtuse kohta) suurte kardinaalsuste korral koosneb liiga suurest mahust ning pealegi on need bitmap-indeksid halvasti (harva) täidetud.


Mõnikord võime kasutada teistsugust esitust, näiteks standardset, mida me kasutame arvude esitlemiseks. Kuid alles tihendamisalgoritmide ilmumine muutis kõike. Viimase paarikümne aasta jooksul on teadlased ja uurijad välja mõelnud palju tihendamisalgoritme bitmapide jaoks. Nende peamine eelis on see, et bitmapide dekopeerimine pole bititegevuste läbiviimiseks vajalik – me saame teostada bititegevusi otse tihendatud bitmapide peal.

Viimasel ajal on hakanud ilmuma ka hübriidmeetodeid, nagu näiteks roaring bitmapid. Need kasutavad samaaegselt kolme erinevat esitusviisi bitmapide jaoks – otseselt bitmapid, massiivid ja nn bitituksid – ja tasakaalustavad nende vahel, et maksimeerida jõudlust ja minimeerida mälutarvet.

Saate kohtuda roaring bitmapidega kõige populaarsemates rakendustes. Juba on olemas tohutult palju teostusi erinevates programmeerimiskeeltes, sealhulgas rohkem kui kolm teostust Go jaoks.

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

Sellega saame sarnased väärtused rühmitada rühmadesse, mille vahemik on 1 cm.

Ja kui me teame, et väga vähesel inimesel on pikkus alla 50 cm või üle 250 cm, siis saame põhimõtteliselt muuta väljad, millel on lõpmatu kardinaalsus, väljadeks, mille kardinaalsus on umbes 200 väärtust.

Muidugi, vajadusel saame teha täiendavat filtreerimist ka hiljem.

Suur läbilaskevõime probleem

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

Andmebaasid peavad võimaldama andmete värskendamist hetkel, kui potentsiaalselt sada muud päringut otsivad neid andmeid. Me vajame lukke, et vältida andmete üheaegse juurdepääsu probleeme või muid jagatud juurdepääsu probleeme. Ja seal, kus on üks suur lukustus, tekib probleem — lukustuskonkurents, kui see lukustus muutub kitsaskohaks.

Seda probleemi saab lahendada või vältida andmete šardimise või versiooniindeksite kasutamise kaudu.

Šardimine on lihtne ja teadaolev mõisted. Saate šardida bitmap-indeksi nii, nagu šardite kõiki teisigi andmeid. Ühe suure lukustuse asemel saate hulga väikeseid lukustusi ja seega vältida lukustuskonkurentsi.

Teine viis probleemi lahendamiseks on versiooniga indeksite kasutamine. Te võite omada ühte indeksikoorust, mida kasutate otsimiseks või lugemiseks, ja ühte – kirjutamiseks või uuendamiseks. Ja igal teatud ajavahemikul (näiteks iga 100 ms või 500 ms) teete nende koopiad ja vahetate neid. Loomulikult on see lähenemine rakendatav ainult siis, kui teie rakendus suudab töötada pisut hilinenud otsingute indeksiga.

Nende kahte lähenemist saab kasutada samaaegselt: teil võib olla šarditud versiooniga indeks.

Täpsemad päringud

Viimane probleem bitmap-indeksite puhul on see, et nagu meile öeldakse, sobivad need halvasti keerukamate päringutüüpide jaoks, näiteks „vahemiku” päringud.

Tõepoolest, kui sellele mõelda, ei sobi bitilised operatsioonid nagu AND, OR jne väga hästi päringute jaoks, nagu „Näita mulle hotelle, mille toa hind on vahemikus 200 kuni 300 dollarit öö kohta.”

Naive ja väga mõttetu lahendus oleks võtta tulemused iga dollari väärtuse jaoks ja liita need bitiliselt operatsiooniga OR.

Veidi paremini lahenduseks oleks rühmitamine. Näiteks 50 dollari kaupa. See kiirendaks meie protsessi 50 korda.

Aga probleem lahendatakse lihtsalt esitusviisi kasutamisega, mis on loodud spetsiaalselt selliste päringute jaoks. Teadustöös nimetatakse seda vahemiku kodeeritud bitmapideks.

Sellises esitusviisis me ei tähista lihtsalt ühte bitti mõne väärtuse jaoks (näiteks 200), vaid tähistame seda väärtust ja kõike, mis on kõrgem. 200 ja kõrgem. Sama kehtib 300 kohta: 300 ja kõrgem. Ja nii edasi.

Seda esitusviisi kasutades saame vastata sellisele otsingupäringule, läbides indeksi vaid kaks korda. Esiteks saame hotellide nimekirja, kus hind on alla 300 dollari, ja seejärel eemaldame need, kus hind on alla 199 dollari. Valmis.

Te üllatute, kuid isegi geopäringud on võimalikud bitmap-indeksite kasutamisega. Nipp on kasutada geoesitust, mis ümbritseb teie koordinaati geomeetrilise kujundiga. Näiteks Google'i S2. Kujund tuleb olla võimalik esitada kolmest või enamast üksteisega ristuvatest joonest, mida saab nummerdada. Nii saame meie geopäringu muuta mitmeks „vahepealseks“ päringuks (leitud numeeritud joonte järgi).

Valmis lahendused

Loodan, et ma pakkusin teile veidi huvi ja teil on nüüd uus kasulik tööriist oma arsenalis. Kui kunagi tekib vajadus midagi sellist teha, teate, millise suuna poole vaadata.

Kuid mitte kõigil ei ole aega, kannatlikkust ja ressursse bitmap-indeksite loomiseks nullist. Eriti edasijõudnud, mis kasutavad näiteks SIMD-d.

Õnneks on olemas mitmeid valmislahendusi, mis aitavad teid.

Roaring bitmaapid

Esiteks on see roaring bitmaps teek, millest olen juba rääkinud. See sisaldab kõiki vajalikke konteinerite ja bititegevuste komplekse, mida vajate täieliku bitmap-indeksi loomiseks.

Kahjuks ei kasuta praegu ükski Go teostus SIMD-d, mistõttu on Go teostused vähem jõudlikud, võrreldes näiteks C-teostustega.

Pilosa

Teine toode, mis võib teid aidata, on andmebaas Pilosa, millel on sisuliselt ainult bitmap-indeksid. See on suhteliselt uus lahendus, kuid see võidab südameid tohutu kiirus.

Pilosa kasutab endas roaring bitmaapeid ja annab teile võimaluse neid kasutada, lihtsustades ja seletades kõiki neid asju, millest ma eespool rääkisin: rühmitamine, vahemiku kodeeritud bitmaps, välja mõisted jne.

Vaadake kiire üle Pilosa kasutamise näide, et vastata küsimusele, mis on teile juba tuttav.

Näide sarnaneb väga sellele, mida olete varem näinud. Loome kliendi Pilosa serverisse, loome indeksit ja vajalikud väljad, seejärel täidame oma väljad juhuslike andmetega tõenäosustega ja lõpuks teeme tuttava päringu.

Pärast seda kasutame NOT väljal "expensive", seejärel ristame tulemuse (või AND-ime) välja "terrace" ja välja "reservations". Ja lõpuks saame lõpptulemuse.

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

Kokkuvõte

Kui te pole veel magama jäänud, siis aitäh. Peasin käsitlema paljusid teemasid lühidalt piiratud aja tõttu, kuid loodan, et ettekande sisu oli kasulik ja võib-olla isegi motiveeriv.

Bitmap-indeksite olemasolust tasub teada isegi siis, kui need ei ole praegu teile vajalikud. Las need olla veel üks tööriist teie tööriistakastis.

Vaatasime erinevaid nippe Go jõudluse parandamiseks ja neid asju, millega Go kompilaator praegu eriti hästi toime ei tule. See on tõeliselt kasulik teadmine iga Go programmeerija jaoks.

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

Allikas: habr.com