Introducere
Am susținut această prezentare în limba engleză la conferința GopherCon Rusia 2019 din Moscova și în limba rusă la meet-up-ul din Nizhni Novgorod. Este vorba despre bitmap-index — mai puțin răspândit decât B-tree, dar nu mai puțin interesant. Împărtășesc prezentării de la conferință în limba engleză și transcrierea textului în limba rusă.
Vom analiza cum funcționează bitmap-index, când este mai bun, când este mai puțin eficient decât celelalte indici și în ce cazuri este semnificativ mai rapid decât ele; vom vedea în ce SGBD populare există deja bitmap-indici; vom încerca să scriem unul pe Go. Iar "la desert", ne vom folosi de biblioteci existente pentru a crea propria noastră bază de date super rapidă și specializată.
Sper cu mare tărie că eforturile mele se vor dovedi utile și interesante pentru voi. Să începem!
Introducere
Salut tuturor! Acum este ora șase seara, suntem cu toții foarte obosiți. Un moment minunat pentru a discuta despre teoria plictisitoare a indecșilor de baze de date, nu-i așa? Nu vă faceți griji, voi avea câteva linii de cod pe aici și pe acolo. 🙂
Serios vorbind, prezentarea este plină de informații, iar noi nu avem foarte mult timp. Așa că să începem.
Astăzi voi vorbi despre următoarele:
- ce sunt indecșii;
- ce este bitmap-index;
- unde este folosit și unde NU este folosit și de ce;
- o implementare simplă pe Go și puțină luptă cu compilatorul;
- o implementare puțin mai complexă, dar mult mai performantă pe asamblarea Go;
- "problemele" bitmap-indicilor;
- implementări existente.
Ce sunt indecșii?
Un index este o structură de date separată pe care o păstrăm și o actualizăm pe lângă datele principale. Este utilizată pentru a accelera căutarea. Fără indecși, căutarea ar necesita o trecere completă prin date (proces numit full scan), iar acest proces are o complexitate algoritmică liniară. Dar bazele de date conțin de obicei o cantitate uriașă de date și complexitatea liniară este prea lentă. În mod ideal, am dori să obținem complexitate logaritmică sau constantă.
Aceasta este o temă uriașă și complexă, plină de subtilități și compromisuri, dar, având în vedere zeci de ani de dezvoltare și cercetare a diferitelor baze de date, sunt pregătit să afirm că există doar câteva abordări utilizate pe scară largă pentru crearea indecșilor de baze de date.
Prima abordare constă în reducerea ierarhică a domeniului de căutare, împărțind domeniul de căutare în părți mai mici.
De obicei, facem asta folosind diverse tipuri de arbori. Un exemplu poate fi o cutie mare cu materiale în dulapul tău, în care se află cutii mai mici cu materiale împărțite pe diverse teme. Dacă ai nevoie de materiale, cu siguranță le vei căuta în cutia cu eticheta „Materiale”, nu în cea cu eticheta „Biscuiți”, nu-i așa?
A doua abordare constă în a evidenția imediat elementul sau grupul dorit de elemente. Facem asta în hash maps sau în indici inversați. Utilizarea hash maps este foarte asemănătoare cu exemplul anterior, doar că în dulapul tău ai o mulțime de cutii mici cu obiecte finale.
A treia abordare este de a scăpa de necesitatea căutării. Facem asta cu ajutorul filtrelor Bloom sau filtrelor cuckoo. Primele oferă un răspuns instantaneu, eliberându-te de necesitatea de a efectua o căutare.
Ultima abordare constă în a utiliza pe deplin toate capacitățile pe care ni le oferă hardware-ul modern. Asta facem cu indici bitmap. Da, în utilizarea lor, uneori trebuie să parcurgem întregul indice, dar o facem super eficient.
Așa cum am spus, tema indicilor de baze de date este vastă și plină de compromisuri. Acest lucru înseamnă că uneori putem folosi mai multe abordări simultan: dacă trebuie să accelerăm și mai mult căutarea sau dacă este necesar să acoperim toate tipurile posibile de căutare.
Astăzi voi vorbi despre cea mai puțin cunoscută abordare menționată — despre indicii bitmap.
Cine sunt eu să vorbesc despre acest subiect?
Lucrez ca team lead la Badoo (poate că știi mai bine un alt produs al nostru — Bumble). Avem deja peste 400 de milioane de utilizatori în întreaga lume și multe funcționalități care se ocupă de a le oferi cea mai bună pereche. Facem asta cu ajutorul serviciilor personalizate, care folosesc inclusiv indicii bitmap.
Așadar, ce este un indice bitmap?
Indexurile bitmap, așa cum sugerează și numele, folosesc bitmapuri sau bitseturi pentru a implementa un index de căutare. Dintr-o perspectivă de ansamblu, acest index constă din unul sau mai multe astfel de bitmapuri, care reprezintă entități (de exemplu, oameni) și proprietățile sau parametrii acestora (vârstă, culoare a ochilor etc.), precum și dintr-un algoritm care folosește operații pe biți (AND, OR, NOT) pentru a răspunde la interogările de căutare.
Se spune că indexurile bitmap sunt cele mai potrivite și foarte eficiente în cazurile în care există o căutare care combină interogările pe multe coloane cu cardinalitate mică (imaginează-ți „culoare a ochilor” sau „stare civilă” în contrast cu ceva de tip „distanță față de centrul orașului”). Dar mai târziu voi arăta că acestea funcționează foarte bine și în cazul coloanelor cu cardinalitate mare.
Să luăm un exemplu simplu de index bitmap.
Imaginați-vă că avem o listă de restaurante din Moscova cu proprietăți binare precum acestea:
- lângă metrou (near metro);
- are parcare privată (has private parking);
- are terasă (has terrace);
- acceptă rezervări (accepts reservations);
- potrivit pentru vegetarieni (vegan friendly);
- scump (expensive).
Să atribuim fiecărui restaurant un număr secvențial începând de la 0 și să alocăm memorie pentru 6 bitmapuri (câte unul pentru fiecare caracteristică). Apoi, vom completa aceste bitmapuri în funcție de faptul dacă restaurantul are sau nu această proprietate. Dacă restaurantul 4 are terasă, atunci bitul nr. 4 din bitmapul „are terasă” va fi setat la 1 (dacă nu are terasă, va fi 0).
Acum avem cel mai simplu index bitmap posibil, iar acesta poate fi folosit pentru a răspunde la interogări precum:
- „Arată-mi restaurantele potrivite pentru vegetarieni”;
- „Arată-mi restaurantele ieftine cu terasă, unde pot face rezervări”.
Cum? Hai să vedem. Prima interogare este foarte simplă. Tot ce trebuie să facem este să luăm bitmapul „potrivit pentru vegetarieni” și să-l transformăm într-o listă de restaurante, al căror biți sunt setați.
A doua interogare este puțin mai complexă. Trebuie să folosim operația bitwise NOT pe bitmap-ul „costisitor” pentru a obține o listă de restaurante ieftine, apoi să-l AND-ăm cu bitmap-ul „se poate rezerva o masă” și să AND-ăm rezultatul cu bitmap-ul „are terasă”. Bitmap-ul rezultat va conține o listă de unități care îndeplinesc toate criteriile noastre. În acest exemplu, este doar restaurantul „Juventus”.
Aici este foarte multă teorie, dar nu vă faceți griji, vom vedea codul foarte curând.
Unde se folosesc indecșii bitmap?
Dacă „găsiți pe Google” indecșii bitmap, 90% din răspunsuri vor fi, într-un fel sau altul, legate de Oracle DB. Dar celelalte SGBD-uri cu siguranță suportă și această caracteristică tare, nu-i așa? Nu chiar.
Să trecem în revistă lista principalelor suspecți.
MySQL încă nu suportă indecșii bitmap, dar există o propunere pentru a adăuga această opțiune ().
PostgreSQL nu suportă indecșii bitmap, dar folosește bitmap-uri simple și operații bitwise pentru a combina rezultatele căutării pe mai mulți alți indecși.
Tarantool are indecși bitset, permite căutarea simplă pe acestea.
Redis are câmpuri bit simple) fără posibilitatea de căutare pe acestea.
MongoDB încă nu suportă indecșii bitmap, dar există de asemenea o propunere pentru a adăuga această opțiune
Elasticsearch utilizează bitmap-uri intern).
- Dar în casa noastră a apărut un nou vecin: Pilosa. Aceasta este o nouă bază de date nerelațională, scrisă în Go. Conține doar indecși bitmap și se bazează pe aceștia. Vom discuta despre ea puțin mai târziu.
Implementare în Go
Dar de ce indecșii bitmap sunt atât de rar folosiți? Înainte de a răspunde la această întrebare, aș dori să vă demonstrez o implementare foarte simplă a unui indecș bitmap în Go.
Bitmap-urile, în esență, sunt reprezentate doar ca bucăți de date. În Go, să folosim pentru asta slice-uri de bytes.
Avem un bitmap pentru o caracteristică a restaurantului, iar fiecare bit din bitmap arată dacă un anumit restaurant are această proprietate sau nu.
Avem nevoie de două funcții auxiliare. Una va fi utilizată pentru a umple bitmapurile noastre cu date aleatorii. Aleatorii, dar cu o probabilitate definită că restaurantul are fiecare proprietate. De exemplu, cred că în Moscova sunt foarte puține restaurante în care nu se poate rezerva o masă și mi se pare că aproximativ 20% dintre locații sunt potrivite pentru vegetarieni.
A doua funcție va transforma bitmapul într-o listă de restaurante.
Pentru a răspunde la cererea „Arată-mi restaurantele ieftine care au terasă și în care se poate rezerva o masă”, avem nevoie de două operații bitwise: NOT și AND.
Putem simplifica un pic codul nostru, folosind o operație AND NOT mai complexă.
Avem funcții pentru fiecare dintre aceste operații. Ambele parcurg slice-urile, iau elementele corespunzătoare din fiecare, le combină prin operația bitwise și plasează rezultatul într-un slice de rezultate.
Și acum putem folosi bitmapurile și funcțiile noastre pentru a răspunde la cererea de căutare.
Performanța nu este atât de bună, chiar dacă funcțiile sunt foarte simple și am economisit destul de bine pe faptul că nu returnam un nou slice de rezultate la fiecare apel al funcției.
După câteva profilări cu pprof, am observat că compilatorul Go a ratat o optimizare foarte simplă, dar extrem de importantă: inlining-ul funcției.
Problema este că compilatorul Go se teme teribil de buclele care parcurg slice-urile și refuză categoric să facă inlining la funcțiile care conțin astfel de bucle.
Dar eu nu mă tem și pot să păcălesc compilatorul, folosind goto în loc de bucle, ca în vremurile bune.
Și, după cum vedeți, acum compilatorul face cu bucurie inlining la funcția noastră! În cele din urmă, reușim să economisim aproximativ 2 microsecunde. Nu e rău!
Al doilea loc restricționat nu este greu de observat dacă te uiți cu atenție la output-ul assemblerului. Compilatorul a adăugat o verificare de limite pentru slice direct în cel mai fierbinte ciclu al nostru. Problema este că Go este un limbaj sigur, compilatorul se teme că cei trei argumenti ai mei (cele trei slice-uri) au dimensiuni diferite. Aceasta ar putea crea o posibilitate teoretică de apariție a așa-zisei depășiri de buffer (buffer overflow).
Haideți să-l liniștim pe compilator, arătându-i că toate slice-urile au aceeași dimensiune. Putem face acest lucru adăugând o verificare simplă la începutul funcției noastre.
Văzând aceasta, compilatorul trece cu bucurie peste verificare, iar noi economisim încă 500 de nanosecunde.
Loturi mari
Ok, am reușit să extragem o anumită performanță din implementarea noastră simplă, dar acest rezultat este, de fapt, mult mai slab decât ar putea fi cu hardware-ul actual.
Tot ce facem sunt operații de bază cu biți, iar procesoarele noastre le execută foarte eficient. Dar, din păcate, "hrănim" procesorul nostru cu foarte mici bucăți de lucru. Funcțiile noastre efectuează operații pe byte. Putem ajusta cu ușurință codul nostru pentru a lucra cu bucăți de 8 byte, folosind slice-uri UInt64.
După cum vedeți, această mică modificare a accelerat programul nostru de opt ori prin creșterea lotului de opt ori. Câștigul este, să spunem, liniar.
Implementare în assembler
Dar acesta nu este sfârșitul. Procesoarele noastre pot lucra cu bucăți de 16, 32 și chiar 64 de byte. Astfel de operații "late" sunt numite single instruction multiple data (SIMD; o instrucțiune, multe date), iar procesul de transformare a codului astfel încât să utilizeze aceste operații se numește vectorizare.
Din păcate, compilatorul Go nu este cel mai bun în ceea ce privește vectorizarea. În prezent, singurul mod de a vectoriza codul în Go este să iei și să așezi manual operațiile datelor folosind assembler Go.
Assemblerul Go este o ființă ciudată. Probabil știți că assemblerul este ceva ce este foarte legat de arhitectura computerului pentru care scrieți, dar în Go nu este așa. Assemblerul Go este mai asemănător cu IRL (intermediate representation language) sau limbaj de reprezentare intermediară: este practic independent de platformă. Rob Pike a avut o prezentare excelentă pe această temă acum câțiva ani la GopherCon în Denver.
În plus, Go folosește un format neobișnuit, Plan 9, diferit de formatele bine cunoscute AT&T și Intel.
Se poate spune cu siguranță că scrierea manuală a assemblerului Go nu este cea mai distractivă activitate.
Dar, din fericire, există deja două unelte de nivel înalt care ne ajută în scrierea assemblerului Go: PeachPy și avo. Ambele utilitare generează assembler Go dintr-un cod de nivel mai înalt, scris în Python și Go, respectiv.
Aceste utilitare simplifică activități precum alocarea registrelor (selectarea unui registru CPU), scrierea buclelor și, în general, facilitează procesul de intrare în lumea programării înasmblere în Go.
Vom folosi avo, astfel încât programele noastre vor fi aproape programe obișnuite în Go.
Iată cum arată cel mai simplu exemplu de program avo. Avem o funcție main() care definește în interiorul ei funcția Add(), a cărei semnificație constă în adunarea a două numere. Există funcții auxiliare pentru obținerea parametrilor după nume și pentru obținerea unuia dintre registreele potrivite și disponibile. Fiecare operație procesorare are o funcție corespunzătoare în avo, așa cum se poate observa la ADDQ. Și în final, vedem o funcție auxiliară pentru salvarea valorii rezultate.
Apelez go generate, vom rula programul pe avo și, în final, vor fi generate două fișiere:
- add.s cu codul rezultat înasmblere pentru Go;
- stub.go cu antetele funcțiilor pentru a lega cele două lumi: Go și asamblatorul.
Acum, că am văzut ce și cum face avo, haideți să ne uităm la funcțiile noastre. Am implementat atât versiuni scalare, cât și vectoriale (SIMD) ale funcțiilor.
Începem prin a privi versiunile scalare.
Așa cum am făcut în exemplul anterior, cerem să ni se ofere un registru general corespunzător și liber, nu trebuie să calculăm deplasările și dimensiunile pentru argumente. Totul acesta îl face avo pentru noi.
Anterior, am folosit etichete și goto (sau sărituri) pentru a îmbunătăți performanța și pentru a păcăli compilatorul Go, dar acum facem asta de la bun început. Ideea este că buclele sunt un concept de nivel mai înalt. În asamblare, avem doar etichete și sărituri.
Codul rămas ar trebui să fie deja familiar și ușor de înțeles. Emulăm bucla cu etichete și sărituri, luăm o mică parte de date din cele două slice-uri ale noastre, le combinăm printr-o operație pe biți (AND NOT în acest caz) și apoi plasăm rezultatul în slice-ul rezultat. Totul.
Iată cum arată codul final în asamblare. Nu a trebuit să calculăm deplasările și dimensiunile (evidentiate în verde) sau să urmărim registrele utilizate (evidențiate în roșu).
Dacă comparăm performanța implementării în assembler cu performanța celei mai bune implementări în Go, vom observa că este identică. Și acest lucru era de așteptat. Nu am făcut nimic special — doar am reprodus ceea ce ar face compilatorul Go.
Din păcate, nu putem forța compilatorul să înlinieze funcțiile noastre scrise în assembler. Compilatorul Go nu are în prezent această capacitate, deși cererea de a o adăuga există de ceva timp.
De aceea, nu putem obține avantaje de la funcțiile mici în assembler. Trebuie să scriem fie funcții mari, fie să utilizăm noul pachet math/bits, fie să evităm assemblerul complet.
Acum să ne uităm la versiunile vectoriale ale funcțiilor noastre.
Pentru acest exemplu am decis să aplic AVX2, așa că vom folosi operațiuni care lucrează cu bucăți de 32 de biți. Structura codului este foarte asemănătoare cu varianta scalară: încărcarea parametrilor, cererea unui registru general liber și așa mai departe.
Una dintre noutăți este că operațiunile vectoriale mai largi folosesc registre speciale largi. În cazul bucăților de 32 de biți, acestea sunt registre cu prefix Y. De aceea vedeți funcția YMM() în cod. Dacă aș fi folosit AVX-512 cu bucăți de 64 de biți, prefixul ar fi fost Z.
A doua noutate se referă la faptul că am decis să folosesc o optimizare numită desfășurarea buclei (loop unrolling), adică să efectuez manual opt operațiuni de ciclu înainte de a sări înapoi la începutul buclei. Această optimizare reduce numărul de ramificări (branching) din cod, iar aceasta este limitată de numărul de registre libere disponibile.
Dar ce putem spune despre performanță? Este fantastică! Am obținut o accelerare de aproximativ șapte ori comparativ cu cea mai bună soluție din Go. Impresionant, nu?
Dar chiar și această implementare ar putea fi potențial accelerată, folosind AVX-512, prefetching sau JIT (compilator just-in-time) pentru planificatorul de cereri. Dar aceasta este cu siguranță o temă pentru o prezentare separată.
Problemele indicilor bitmap
Acum, când am examinat deja implementarea simplă a unui index bitmap în Go și mult mai performantă în assembler, să discutăm în sfârșit despre motivul pentru care indicii bitmap sunt atât de rar utilizați.
În lucrările științifice vechi se menționează trei probleme ale indexurilor bitmap, dar lucrări științifice mai recente și eu susținem că acestea nu mai sunt relevante. Nu ne vom adânci în fiecare dintre aceste probleme, dar le vom analiza superficial.
Problema cardinalității mari
Așadar, ni se spune că indexurile bitmap sunt potrivite doar pentru câmpuri cu cardinalitate mică, adică acelea care au puține valori (de exemplu, genul sau culoarea ochilor), iar motivul este că reprezentarea obișnuită a acestor câmpuri (un bit pe valoare) în cazul cardinalității mari va ocupa prea mult spațiu și, mai mult, aceste indexuri bitmap vor fi slab (rar) umplute.
Uneori putem folosi o altă reprezentare, de exemplu, reprezentarea standard pe care o folosim pentru a reprezenta numere. Dar fix apariția algoritmilor de compresie a schimbat totul. În ultimele decenii, oamenii de știință și cercetătorii au invenționat o mulțime de algoritmi de compresie pentru bitmap-uri. Principalul lor avantaj este că nu trebuie să decomprimăm bitmap-urile pentru a efectua operații pe biți — putem efectua operații pe biți direct asupra bitmap-urilor comprimate.
În ultima vreme au apărut și abordări hibride, cum ar fi bitmap-urile roaring. Acestea folosesc simultan trei reprezentări diferite pentru bitmap-uri — propriu-zis bitmap-uri, aranjamente și așa-numitele bit runs — și echilibrează între ele pentru a maximiza performanța și a minimiza consumul de memorie.
Puteți întâlni bitmap-uri roaring în cele mai populare aplicații. Deja există o mulțime de implementări pentru cele mai diverse limbaje de programare, inclusiv mai mult de trei implementări pentru Go.
O altă abordare care ne poate ajuta să facem față cardinalității mari se numește grupare (binning). Imaginează-ți că ai un câmp care reprezintă înălțimea unei persoane. Înălțimea este un număr cu virgulă mobilă, dar noi, oamenii, nu ne gândim la ea în acest mod. Pentru noi nu există o diferență între înălțimea de 185,2 cm și cea de 185,3 cm.
Așadar, putem grupa valori asemănătoare în grupuri în intervalul de 1 cm.
Și dacă mai știm că foarte puțini oameni au o înălțime mai mică de 50 cm și mai mare de 250 cm, atunci, practic, putem transforma un câmp cu cardinalitate infinită într-un câmp cu o cardinalitate de aproximativ 200 de valori.
Desigur, dacă este necesar, putem efectua o filtrare suplimentară ulterior.
Problema lățimii de bandă mari
Următoarea problemă a indexurilor bitmap este că actualizarea lor poate fi foarte costisitoare.
Bazele de date trebuie să permită actualizarea datelor în momentul în care pot exista sute de alte solicitări care caută aceste date. Avem nevoie de blocări pentru a evita problemele de acces concurent la date sau alte probleme de partajare. Iar acolo unde există o mare blocare, apare problema — contentia de blocare, când acel blocaj devine un punct critic.
Această problemă poate fi rezolvată sau ocolită prin sharding sau utilizarea indexurilor versionate.
Shardingul este un concept simplu și bine cunoscut. Puteți să sharduiți un index bitmap așa cum ați shardui orice alte date. În loc de o mare blocare, veți obține o mulțime de blocări mici și astfel veți scăpa de contentia de blocare.
O altă metodă de a rezolva problema este utilizarea indexurilor versionate. Puteți avea o copie a indexului pe care o folosiți pentru căutare sau citire și una pentru scriere sau actualizare. Și la un anumit interval de timp (de exemplu, la fiecare 100 ms sau 500 ms) le duplicati și schimbați între ele. Evident, această abordare se aplică doar în cazurile în care aplicația dvs. poate funcționa cu un index de căutare ușor întârziat.
Aceste două abordări pot fi utilizate simultan: puteți avea un index versionat sharduit.
Interogări mai complexe
Ultima problemă a indexurilor bitmap este că, după cum ni se spune, acestea nu se potrivesc bine pentru tipuri mai complexe de interogări, cum ar fi interogările "pe interval".
Și adevărat, dacă ne gândim, operațiile bitare de tip AND, OR etc. nu se potrivesc bine pentru interogări de tip "Arată-mi hotelurile cu prețul camerei între 200 și 300 de dolari pe noapte".
O soluție naivă și foarte nechibzuită ar fi fost să obținem rezultatele pentru fiecare valoare în dolari și să le combinăm folosind operația de tip OR.
O soluție puțin mai corectă ar fi fost utilizarea grupării. De exemplu, în grupuri de 50 de dolari. Acest lucru ar accelera procesul nostru de 50 de ori.
Dar problema este, de asemenea, ușor de rezolvat prin utilizarea unei reprezentări create special pentru acest tip de interogări. În lucrările științifice, se numește bitmap-uri codificate pe intervale.
Într-o astfel de reprezentare, nu simplu setăm un bit pentru o anumită valoare (de exemplu, 200), ci setăm acea valoare și tot ce este mai mare. 200 și mai sus. La fel și pentru 300: 300 și mai sus. Și așa mai departe.
Folosind această reprezentare, putem răspunde la astfel de interogări de căutare parcurgând indexul doar de două ori. Mai întâi, vom obține lista hotelurilor, unde prețul este mai mic de 300 de dolari, apoi vom elimina din această listă cele cu prețul mai mic de 199 dolari. Gata.
Vei fi surprins, dar chiar și interogările geo sunt posibile utilizând indexuri bitmap. Trucul constă în a folosi o reprezentare geografică care înconjoară coordonata ta cu o figură geometrică. De exemplu, S2 de la Google. Figura trebuie să poată fi reprezentată prin trei sau mai multe linii intersectate care pot fi numerotate. Astfel, vom putea transforma interogarea noastră geo în mai multe interogări „pe interval” (pe aceste linii numerotate).
Soluții gata făcute
Sper că te-am interesat puțin și ai acum un instrument util în arsenalul tău. Dacă vreodată vei avea nevoie să faci ceva similar, vei ști în ce direcție să cauți.
Cu toate acestea, nu toată lumea are timp, răbdare și resurse pentru a crea indexuri bitmap de la zero. În special cele mai avansate, utilizând SIMD, de exemplu.
Din fericire, există câteva soluții gata făcute care te pot ajuta.
Bitmap-uri Roaring
Mai întâi, există biblioteca de bitmap-uri roaring despre care am menționat deja. Aceasta conține toate containele și operațiile bit necesare pentru a crea un index bitmap complet.
Din păcate, în prezent, niciuna dintre implementările Go nu folosește SIMD, ceea ce înseamnă că implementările Go sunt mai puțin eficiente decât cele în C, de exemplu.
Pilosa
Un alt produs care te poate ajuta este SGBD-ul Pilosa, care, în esență, are doar indexuri bitmap. Este o soluție relativ nouă, dar câștigă popularitate cu o viteză incredibilă.
Pilosa utilizează bitmap-uri roaring în interiorul său și vă oferă posibilitatea de a le folosi, simplificând și explicând toate acele lucruri despre care am vorbit mai sus: grupare, bitmap-uri codificate pe interval, noțiunea de câmp etc.
Să aruncăm o privire rapidă asupra unui exemplu de utilizare a Pilosa pentru a răspunde la o întrebare pe care o cunoașteți deja.
Exemplul este foarte similar cu ceea ce ați văzut înainte. Creăm un client pentru serverul Pilosa, creăm un index și câmpurile necesare, apoi umplem câmpurile noastre cu date aleatorii cu probabilități și, în final, efectuam interogarea cunoscută.
După aceasta, folosim NOT pe câmpul „expensive”, apoi intersecționăm rezultatul (sau facem AND) cu câmpul „terrace” și cu câmpul „reservations”. Și, în final, obținem rezultatul final.
Sper foarte mult că, în viitorul apropiat, tipuri noi de indici — bitmap-indici — vor apărea și în SGBD-uri precum MySQL și PostgreSQL.
Concluzie
Dacă nu ați adormit încă, vă mulțumesc. A trebuit să ating pe scurt multe subiecte din cauza timpului limitat, dar sper că prezentarea a fost utilă și, poate, chiar motivantă.
Este bine să cunoașteți bitmap-îndici, chiar dacă acum nu vă sunt necesari. Să fie un alt instrument în trusa dumneavoastră.
Am discutat diferite trucuri pentru îmbunătățirea performanței în Go și acele lucruri cu care compilatorul Go încă nu se descurcă foarte bine. Aceasta este absolut ceva ce fiecare programator Go ar trebui să know.
Asta este tot ce am vrut să împărtășesc. Vă mulțumesc!
Sursa: habr.com
