Uvod
Održao sam ovo izvješće na engleskom na konferenciji GopherCon Russia 2019 u Moskvi i na ruskom na sastanku u Nižnjem Novgorodu. Govorimo o bitmap indeksu - manje uobičajenom od B-stabla, ali ne manje zanimljivom. Dijeljenje govori na konferenciji na engleskom jeziku i transkripti teksta na ruskom.
Pogledat ćemo kako bitmap indeks radi, kada je bolji, kada lošiji od ostalih indeksa, au kojim slučajevima je značajno brži od njih; Pogledajmo koji popularni DBMS-ovi već imaju bitmap indekse; Pokušajmo napisati svoje u Go-u. A "za desert" ćemo koristiti gotove biblioteke za stvaranje vlastite super-brze specijalizirane baze podataka.
Zaista se nadam da će vam moji radovi biti korisni i zanimljivi. Ići!
Uvod
Bok svima! Šest je navečer i svi smo super umorni. Odlično vrijeme za razgovor o dosadnoj teoriji indeksa baze podataka, zar ne? Ne brinite, tu i tamo ću imati nekoliko redaka izvornog koda. 🙂
Šalu na stranu, izvješće je krcato informacijama, a nemamo puno vremena. Pa krenimo.
Danas ću govoriti o sljedećem:
- što su indeksi;
- što je bitmap indeks;
- gdje se koristi, a gdje se NE koristi i zašto;
- jednostavna implementacija u Go i malo borbe s kompajlerom;
- malo manje jednostavna, ali mnogo produktivnija implementacija u Go asembleru;
- “problemi” bitmap indeksa;
- postojeće implementacije.
Dakle, što su indeksi?
Indeks je zasebna podatkovna struktura koju održavamo i ažuriramo uz glavne podatke. Koristi se za ubrzanje pretrage. Bez indeksa, pretraživanje bi zahtijevalo potpuno prolaženje podataka (proces koji se zove potpuno skeniranje), a ovaj proces ima linearnu algoritamsku složenost. Ali baze podataka obično sadrže ogromne količine podataka, a linearna složenost je prespora. Idealno bi bilo da dobijemo logaritamsku ili konstantnu.
Ovo je iznimno složena tema, puna suptilnosti i kompromisa, ali nakon što sam pogledao desetljeća razvoja i istraživanja baze podataka, spreman sam reći da postoji samo nekoliko široko korištenih pristupa stvaranju indeksa baze podataka.
Prvi pristup je hijerarhijsko smanjenje prostora pretraživanja, dijeljenje prostora pretraživanja na manje dijelove.
Obično to radimo koristeći različite vrste drveća. Primjer bi bila velika kutija materijala u vašem ormaru koja sadrži manje kutije materijala podijeljenih u različite teme. Ako trebate materijale, vjerojatno ćete ih potražiti u kutiji s natpisom "Materijali", a ne u kutiji s natpisom "Kolačići", zar ne?
Drugi pristup je odmah odabrati željeni element ili grupu elemenata. To radimo u hash mapama ili obrnutim indeksima. Korištenje hash mapa vrlo je slično prethodnom primjeru, ali umjesto kutije s kutijama, imate hrpu malih kutija s konačnim predmetima u svom ormaru.
Treći pristup je uklanjanje potrebe za traženjem. To radimo pomoću Bloom filtera ili kukavičastih filtera. Prvi daju odgovor trenutno, štedeći vas traženja.
Posljednji pristup je u potpunosti iskoristiti svu moć koju nam moderni hardver daje. To je upravo ono što radimo u bitmap indeksima. Da, kada ih koristimo ponekad trebamo proći kroz cijeli indeks, ali mi to radimo super učinkovito.
Kao što sam rekao, tema indeksa baze podataka je ogromna i puna kompromisa. To znači da ponekad možemo koristiti više pristupa istovremeno: ako trebamo još više ubrzati pretragu ili ako trebamo pokriti sve moguće vrste pretrage.
Danas ću govoriti o najmanje poznatom pristupu - bitmap indeksima.
Tko sam ja da govorim o ovoj temi?
Radim kao voditelj tima na Badoou (možda ste više upoznati s našim drugim proizvodom, Bumble). Već imamo više od 400 milijuna korisnika diljem svijeta i mnoge značajke koje biraju ono što im najbolje odgovara. To radimo pomoću prilagođenih usluga, uključujući bitmap indekse.
Dakle, što je bitmap indeks?
Bitmap indeksi, kao što ime sugerira, koriste bitmape ili bitsetove za implementaciju indeksa pretraživanja. Iz ptičje perspektive, ovaj se indeks sastoji od jedne ili više takvih bitmapa koje predstavljaju bilo koje entitete (kao što su ljudi) i njihova svojstva ili parametre (dob, boja očiju, itd.) i algoritam koji koristi bitne operacije (AND, OR, NOT ) za odgovor na upit za pretraživanje.
Rečeno nam je da su bitmap indeksi najprikladniji i vrlo učinkoviti za slučajeve kada postoje pretraživanja koja kombiniraju upite u mnogim stupcima niske kardinalnosti (razmislite o "boji očiju" ili "bračnom statusu" nasuprot nečemu poput "udaljenosti od centra grada"). Ali kasnije ću pokazati da dobro funkcioniraju i za stupce visoke kardinalnosti.
Pogledajmo najjednostavniji primjer bitmap indeksa.
Zamislite da imamo popis moskovskih restorana s binarnim svojstvima poput ovih:
- u blizini metroa;
- postoji privatni parking;
- postoji veranda (ima terasu);
- možete rezervirati stol (prima rezervacije);
- pogodno za vegetarijance (vegan friendly);
- skupo (skupo).
Dodijelimo svakom restoranu redni broj počevši od 0 i dodijelimo memoriju za 6 bitmapa (jednu za svaku karakteristiku). Zatim ćemo popuniti te bitmape ovisno o tome ima li restoran to svojstvo ili ne. Ako restoran 4 ima verandu, tada će bit br. 4 u bitmapi "ima verandu" biti postavljen na 1 (ako nema verande, onda na 0).
Sada imamo najjednostavniji mogući bitmap indeks i možemo ga koristiti za odgovaranje na upite poput:
- “Pokaži mi vegetarijanske restorane”;
- "Pokažite mi jeftine restorane s verandom na kojoj možete rezervirati stol."
Kako? Idemo pogledati. Prvi zahtjev je vrlo jednostavan. Sve što trebamo učiniti je uzeti bitmapu "prilagođeno vegetarijancima" i pretvoriti je u popis restorana čiji su dijelovi izloženi.
Drugi zahtjev je malo kompliciraniji. Trebamo upotrijebiti bitmapu NOT na bitmapi "skupo" da bismo dobili popis jeftinih restorana, zatim ga I s bitmapom "mogu li rezervirati stol" i I rezultat s bitmapom "postoji veranda". Dobivena bitmapa sadržavat će popis ustanova koje zadovoljavaju sve naše kriterije. U ovom primjeru radi se samo o restoranu Yunost.
Puno je teorije uključeno, ali ne brinite, vrlo brzo ćemo vidjeti kôd.
Gdje se koriste bitmap indeksi?
Ako guglate bitmap indekse, 90% odgovora bit će na ovaj ili onaj način povezano s Oracle DB-om. Ali drugi DBMS-ovi vjerojatno također podržavaju tako cool stvar, zar ne? Ne baš.
Prođimo kroz popis glavnih osumnjičenih.
MySQL još ne podržava bitmap indekse, ali postoji prijedlog koji predlaže dodavanje ove opcije ().
PostgreSQL ne podržava bitmap indekse, ali koristi jednostavne bitmape i bit operacije za kombiniranje rezultata pretraživanja u više drugih indeksa.
Tarantool ima bitset indekse i podržava jednostavna pretraživanja na njima.
Redis ima jednostavna bitna polja) bez mogućnosti da ih tražite.
MongoDB još ne podržava bitmap indekse, ali također postoji prijedlog koji predlaže da se ova opcija doda
Elasticsearch interno koristi bitmape).
- Ali u našoj kući se pojavio novi susjed: Pilosa. Ovo je nova nerelacijska baza podataka napisana u Go. Sadrži samo bitmap indekse i sve se temelji na njima. O tome ćemo malo kasnije.
Implementacija u Go
Ali zašto se bitmap indeksi tako rijetko koriste? Prije nego odgovorim na ovo pitanje, želio bih vam pokazati kako implementirati vrlo jednostavan bitmap indeks u Go.
Bitmape su u biti samo dijelovi podataka. U Go-u koristimo odsječke bajtova za ovo.
Imamo jednu bitmapu za jednu karakteristiku restorana, a svaki bit u bitmapi označava ima li određeni restoran to svojstvo ili ne.
Trebat će nam dvije pomoćne funkcije. Jedan će se koristiti za ispunjavanje naših bitmapa nasumičnim podacima. Slučajno, ali s određenom vjerojatnošću da restoran ima svaki svojstvo. Na primjer, vjerujem da u Moskvi postoji vrlo malo restorana u kojima ne možete rezervirati stol, a čini mi se da je oko 20% objekata prikladno za vegetarijance.
Druga funkcija pretvorit će bitmapu u popis restorana.
Da bismo odgovorili na upit "Pokaži mi jeftine restorane koji imaju terasu i mogu napraviti rezervacije", potrebne su nam dvije bitne operacije: NOT i AND.
Naš kôd možemo malo pojednostaviti korištenjem složenijeg operatora AND NOT.
Imamo funkcije za svaku od ovih operacija. Obojica prolaze kroz kriške, uzimaju odgovarajuće elemente iz svake, kombiniraju ih malom operacijom i stavljaju rezultat u dobivenu krišku.
I sada možemo koristiti naše bitmape i funkcije da odgovorimo na upit za pretraživanje.
Performanse nisu tako visoke, iako su funkcije vrlo jednostavne i uštedjeli smo mnogo novca jer nismo vraćali novi rezultirajući isječak svaki put kada je funkcija pozvana.
Nakon što sam napravio malo profiliranja s pprofom, primijetio sam da prevoditelju Go nedostaje jedna vrlo jednostavna, ali vrlo važna optimizacija: inlining funkcija.
Činjenica je da se Go prevodilac užasno boji petlji koje prolaze kroz odsječke i kategorički odbija ugraditi funkcije koje sadrže takve petlje.
Ali ne bojim se i mogu prevariti kompajler koristeći goto umjesto petlje, kao u dobra stara vremena.
I, kao što vidite, sada će prevodilac rado ugraditi našu funkciju! Kao rezultat toga, uspijevamo uštedjeti oko 2 mikrosekunde. Nije loše!
Drugo usko grlo je lako vidjeti ako pažljivo pogledate izlaz sklopa. Kompajler je dodao provjeru granice odsječka unutar naše najtoplije petlje. Činjenica je da je Go siguran jezik, prevodilac se boji da su moja tri argumenta (tri kriške) različite veličine. Uostalom, tada će postojati teoretska mogućnost pojave tzv. buffer overflow-a.
Uvjerimo kompilator pokazujući mu da su svi dijelovi iste veličine. To možemo učiniti dodavanjem jednostavne provjere na početku naše funkcije.
Vidjevši to, prevodilac sretno preskače provjeru, a mi na kraju štedimo još 500 nanosekundi.
Veliki butches
U redu, uspjeli smo izvući neke performanse iz naše jednostavne implementacije, ali ovaj rezultat je zapravo puno lošiji nego što je moguće s trenutnim hardverom.
Sve što radimo su osnovne bitne operacije, a naši ih procesori izvode vrlo učinkovito. Ali, nažalost, mi svoj procesor “hranimo” vrlo malim dijelovima rada. Naše funkcije izvode operacije na bazi bajt po bajt. Možemo vrlo lako prilagoditi naš kod da radi s 8-bajtnim komadima koristeći UInt64 odsječke.
Kao što vidite, ova mala promjena ubrzala je naš program osam puta povećanjem veličine serije za osam puta. Može se reći da je dobitak linearan.
Implementacija u asembleru
Ali ovo nije kraj. Naši procesori mogu raditi s komadima od 16, 32 pa čak i 64 bajta. Takve "široke" operacije nazivaju se single instruction multiple data (SIMD; jedna instrukcija, mnogo podataka), a proces transformacije koda tako da koristi takve operacije naziva se vektorizacija.
Nažalost, Go kompajler je daleko od izvrsnog u vektorizaciji. Trenutačno, jedini način za vektorizaciju Go koda je preuzimanje i postavljanje ovih operacija ručno pomoću Go asemblera.
Go asembler je čudna zvijer. Vjerojatno znate da je asemblerski jezik nešto što je usko povezano s arhitekturom računala za koje pišete, ali to nije slučaj u Gou. Go asembler je više poput IRL-a (intermediate representation language) ili srednjeg jezika: praktički je neovisan o platformi. Rob Pike odigrao je izvrsnu igru na ovu temu prije nekoliko godina na GopherConu u Denveru.
Osim toga, Go koristi neobičan format Plan 9, koji se razlikuje od općeprihvaćenih formata AT&T i Intel.
Sa sigurnošću se može reći da ručno pisanje Go asemblera nije najzabavnije.
Ali, na sreću, već postoje dva alata visoke razine koji nam pomažu u pisanju Go asemblera: PeachPy i avo. Oba pomoćna programa generiraju Go asembler iz koda više razine napisanog u Pythonu i Gou.
Ovi uslužni programi pojednostavljuju stvari poput dodjele registara, pisanja petlji i općenito pojednostavljuju proces ulaska u svijet asemblerskog programiranja u Gou.
Koristit ćemo avo, tako da će naši programi biti gotovo obični Go programi.
Ovako izgleda najjednostavniji primjer avo programa. Imamo funkciju main(), koja unutar sebe definira funkciju Add() čije je značenje zbrajanje dva broja. Ovdje postoje pomoćne funkcije za dobivanje parametara po imenu i dobivanje jednog od besplatnih i prikladnih registara procesora. Svaka operacija procesora ima odgovarajuću funkciju na avo, kao što se vidi u ADDQ. Na kraju, vidimo pomoćnu funkciju za pohranjivanje dobivene vrijednosti.
Pozivom gogenerirati, izvršit ćemo program na avo i kao rezultat će se generirati dvije datoteke:
- add.s s rezultirajućim kodom u Go asembleru;
- stub.go sa zaglavljima funkcija za povezivanje dva svijeta: Go i asembler.
Sada kada smo vidjeli što avo radi i kako, pogledajmo naše funkcije. Implementirao sam i skalarnu i vektorsku (SIMD) verziju funkcija.
Pogledajmo najprije skalarne verzije.
Kao u prethodnom primjeru, tražimo besplatan i važeći registar opće namjene, ne moramo izračunati pomake i veličine za argumente. avo radi sve ovo za nas.
Prije smo koristili oznake i goto (ili skokove) kako bismo poboljšali performanse i prevarili Go kompajler, ali sada to radimo od početka. Poanta je da su ciklusi koncept više razine. U asembleru imamo samo oznake i skokove.
Preostali kod već bi trebao biti poznat i razumljiv. Emuliramo petlju s oznakama i skokovima, uzimamo mali dio podataka iz naša dva odsječka, kombiniramo ih s malom operacijom (I NE u ovom slučaju) i zatim stavljamo rezultat u rezultirajući odsječak. Svi.
Ovako izgleda konačni asemblerski kod. Nismo morali izračunavati pomake i veličine (označeno zelenom bojom) niti pratiti korištene registre (označeno crvenom bojom).
Ako usporedimo izvedbu implementacije asemblerskog jezika s izvedbom najbolje implementacije u Gou, vidjet ćemo da je ista. I to je očekivano. Uostalom, nismo učinili ništa posebno - samo smo reproducirali ono što bi Go prevodilac učinio.
Nažalost, ne možemo prisiliti prevoditelj da ugradi naše funkcije napisane u asemblerskom jeziku. Go kompajler trenutno nema takvu značajku, iako već duže vrijeme postoji zahtjev da se doda.
Zbog toga je nemoguće izvući bilo kakvu korist od malih funkcija u asemblerskom jeziku. Moramo ili napisati velike funkcije, ili koristiti novi math/bits paket, ili zaobići asemblerski jezik.
Pogledajmo sada vektorske verzije naših funkcija.
Za ovaj primjer odlučio sam koristiti AVX2, tako da ćemo koristiti operacije koje rade na 32-bajtnim komadima. Struktura koda vrlo je slična skalarnoj verziji: učitavanje parametara, traženje besplatnog zajedničkog registra itd.
Jedna od inovacija je da šire vektorske operacije koriste posebne široke registre. U slučaju 32-bajtnih dijelova, to su registri s prefiksom Y. Zbog toga u kodu vidite funkciju YMM(). Da sam koristio AVX-512 sa 64-bitnim komadima, prefiks bi bio Z.
Druga je inovacija ta da sam odlučio upotrijebiti optimizaciju koja se zove odmotavanje petlje, što znači ručno obavljanje osam operacija petlje prije skoka na početak petlje. Ova optimizacija smanjuje broj grana u kodu i ograničena je brojem dostupnih besplatnih registara.
Pa, što je s izvedbom? Ona je prekrasna! Postigli smo ubrzanje od oko sedam puta u usporedbi s najboljim Go rješenjem. Impresivno, zar ne?
Ali čak bi se i ova implementacija potencijalno mogla ubrzati korištenjem AVX-512, prethodnog dohvaćanja ili JIT-a (just-in-time compiler) za planer upita. Ali ovo je svakako tema za poseban izvještaj.
Problemi s bitmap indeksima
Sad kad smo već pogledali jednostavnu implementaciju bitmap indeksa u Go i mnogo produktivniju onu u asemblerskom jeziku, razgovarajmo konačno o tome zašto se bitmap indeksi tako rijetko koriste.
Stariji radovi spominju tri problema s bitmap indeksima, ali noviji radovi i ja tvrdim da oni više nisu relevantni. Nećemo duboko ulaziti u svaki od ovih problema, već ćemo ih sagledati površno.
Problem visoke kardinalnosti
Dakle, rečeno nam je da su bitmap indeksi prikladni samo za polja niske kardinalnosti, to jest ona koja imaju nekoliko vrijednosti (na primjer, spol ili boja očiju), a razlog je to što je uobičajeni prikaz takvih polja (jedan bit po vrijednosti) u slučaju visoke kardinalnosti, zauzet će previše prostora i, štoviše, ovi bitmap indeksi bit će slabo (rijetko) popunjeni.
Ponekad možemo upotrijebiti drugačiji prikaz, poput standardnog koji koristimo za predstavljanje brojeva. Ali sve je promijenila pojava algoritama za kompresiju. Tijekom proteklih desetljeća znanstvenici i istraživači osmislili su velik broj algoritama za kompresiju bitmapa. Njihova glavna prednost je u tome što nema potrebe za dekompresijom bitmapa za izvođenje bitnih operacija - bitne operacije možemo izvoditi izravno na komprimiranim bitmapama.
Nedavno su se počeli pojavljivati hibridni pristupi, poput roaring bitmapa. Oni istovremeno koriste tri različita prikaza za bitmape - same bitmape, nizove i takozvane nizove bitova - i balansiraju između njih kako bi maksimizirali performanse i smanjili potrošnju memorije.
Možete pronaći bučne bitmape u najpopularnijim aplikacijama. Već postoji ogroman broj implementacija za širok izbor programskih jezika, uključujući više od tri implementacije za Go.
Drugi pristup koji nam može pomoći da se nosimo s visokom kardinalnošću zove se binning. Zamislite da imate polje koje predstavlja visinu osobe. Visina je broj s pomičnim zarezom, ali mi ljudi ne razmišljamo o tome na taj način. Za nas nema razlike između visine 185,2 cm i 185,3 cm.
Ispada da slične vrijednosti možemo grupirati u grupe unutar 1 cm.
A ako također znamo da je vrlo malo ljudi nižih od 50 cm i viših od 250 cm, tada u biti možemo pretvoriti polje s beskonačnom kardinalnošću u polje s kardinalnošću od oko 200 vrijednosti.
Naravno, po potrebi možemo dodatno filtrirati naknadno.
Problem visoke propusnosti
Sljedeći problem s bitmap indeksima je da njihovo ažuriranje može biti vrlo skupo.
Baze podataka moraju biti u mogućnosti ažurirati podatke dok potencijalno stotine drugih upita pretražuju podatke. Potrebne su nam brave kako bismo izbjegli probleme s istodobnim pristupom podacima ili druge probleme s dijeljenjem. A gdje postoji jedna velika brava, postoji problem - prepirka oko brave, kada ova brava postane usko grlo.
Ovaj se problem može riješiti ili zaobići korištenjem dijeljenja ili korištenjem verzioniranih indeksa.
Sharding je jednostavna i dobro poznata stvar. Indeks bitmape možete podijeliti kao što biste to učinili s bilo kojim drugim podacima. Umjesto jedne velike brave, dobit ćete hrpu malih brava i tako se riješiti sukoba oko brava.
Drugi način rješavanja problema je korištenje verzioniranih indeksa. Možete imati jednu kopiju indeksa koju koristite za pretraživanje ili čitanje i jednu koju koristite za pisanje ili ažuriranje. I jednom u određenom vremenskom razdoblju (na primjer, jednom svakih 100 ms ili 500 ms) duplicirate ih i zamijenite. Naravno, ovaj je pristup primjenjiv samo u slučajevima kada vaša aplikacija može podnijeti indeks pretraživanja koji malo zaostaje.
Ova dva pristupa mogu se koristiti istovremeno: možete imati indeks s razdijeljenim verzijama.
Složeniji upiti
Posljednji problem s bitmap indeksima je taj što nam je rečeno da nisu prikladni za složenije tipove upita, kao što su span upiti.
Doista, ako razmislite o tome, bitne operacije poput AND, OR, itd. nisu baš prikladne za upite tipa "Pokaži mi hotele s cijenama soba od 200 do 300 dolara po noćenju."
Naivno i vrlo nerazborito rješenje bilo bi uzeti rezultate za svaku vrijednost u dolarima i kombinirati ih s bit-wise OR operacijom.
Malo bolje rješenje bilo bi korištenje grupiranja. Na primjer, u grupama od 50 dolara. To bi ubrzalo naš proces 50 puta.
Ali problem se također lako rješava upotrebom prikaza kreiranog posebno za ovu vrstu zahtjeva. U znanstvenim se radovima naziva bitmapama kodiranim rasponom.
U ovom prikazu ne postavljamo samo jedan bit za neku vrijednost (na primjer, 200), već postavljamo ovu vrijednost i sve više. 200 i više. Isto za 300: 300 i više. I tako dalje.
Koristeći ovaj prikaz, možemo odgovoriti na ovu vrstu upita za pretraživanje tako što ćemo samo dvaput proći kroz indeks. Prvo ćemo dobiti popis hotela u kojima soba košta manje ili 300 dolara, a zatim ćemo s njega ukloniti one u kojima je cijena sobe niža ili 199 dolara. Spreman.
Iznenadit ćete se, ali čak su i geoupiti mogući korištenjem bitmap indeksa. Trik je u korištenju geometrijskog prikaza koji okružuje vašu koordinatu geometrijskim likom. Na primjer, S2 od Googlea. Sliku treba moći prikazati u obliku tri ili više linija koje se sijeku i koje je moguće numerirati. Na ovaj način možemo pretvoriti naš geoupit u nekoliko upita "duž praznine" (duž ovih numeriranih linija).
Spremna rješenja
Nadam se da sam vas malo zainteresirao i da sada imate još jedan koristan alat u svom arsenalu. Ako ikad trebate učiniti nešto poput ovoga, znat ćete s koje strane tražiti.
Međutim, nema svatko vremena, strpljenja ili resursa za stvaranje bitmap indeksa od nule. Pogotovo oni napredniji, koji koriste SIMD, na primjer.
Srećom, postoji nekoliko gotovih rješenja koja će vam pomoći.
Urlajuće bitmape
Prvo, tu je ista velika biblioteka bitmapa o kojoj sam već govorio. Sadrži sve potrebne spremnike i bitne operacije koje ćete trebati za izradu potpunog bitmap indeksa.
Nažalost, u ovom trenutku niti jedna Go implementacija ne koristi SIMD, što znači da su Go implementacije manje učinkovite od C implementacija, na primjer.
dlakav
Drugi proizvod koji vam može pomoći je Pilosa DBMS, koji zapravo ima samo bitmap indekse. Ovo je relativno novo rješenje, ali velikom brzinom osvaja srca.
Pilosa interno koristi rastuće bitmape i daje vam mogućnost da ih koristite, pojednostavljuje i objašnjava sve stvari o kojima sam govorio gore: grupiranje, bitmape kodirane rasponom, koncept polja itd.
Pogledajmo na brzinu primjer korištenja Pilosa za odgovor na pitanje s kojim ste već upoznati.
Primjer je vrlo sličan onome što ste vidjeli prije. Kreiramo klijenta Pilosa poslužitelju, kreiramo indeks i potrebna polja, zatim ispunjavamo naša polja nasumičnim podacima s vjerojatnostima i na kraju izvršavamo poznati upit.
Nakon toga koristimo NOT na polju "skupo", zatim siječemo rezultat (ili ga AND) s poljem "terasa" i poljem "rezervacije". I na kraju, dobivamo konačni rezultat.
Stvarno se nadam da će se u dogledno vrijeme ovaj novi tip indeksa pojaviti iu DBMS-ovima kao što su MySQL i PostgreSQL - bitmap indeksi.
Zaključak
Ako još niste zaspali, hvala. Morao sam se ukratko dotaknuti mnogih tema zbog ograničenog vremena, ali se nadam da je razgovor bio koristan i možda čak motivirajući.
Bitmap indekse je dobro znati, čak i ako vam trenutno nisu potrebni. Neka budu još jedan alat u vašoj kutiji s alatima.
Pogledali smo razne trikove performansi za Go i stvari s kojima Go kompajler još ne rukuje dobro. Ali ovo je apsolutno korisno da zna svaki Go programer.
To je sve što sam ti htio reći. Hvala vam!
Izvor: www.habr.com