Fjalët e hapjes
Unë e mbajta këtë prezantim në anglisht në konferencën GopherCon Rusia 2019 në Moskë dhe në rusisht në meet-up në Nizhny Novgorod. Tema është mbi indeksin bitmap — më pak i zakonshëm se B-tree, por aspak më pak interesant. Po ndajem e prezantimit në konferencë në anglisht dhe përkthimin tekstual në rusisht.
Ne do të shikojmë se si funksionon indeksi bitmap, kur ai është më i mirë, kur është më i keq se indekset e tjera dhe në cilat rastet ai është ndjeshëm më i shpejtë; do të shohim në cilat sisteme të njohura DBMS tashmë ekzistojnë indekse bitmap; do të përpiqemi të shkruajmë të tonin në Go. Dhe për "dessert", do të përdorim biblioteka të gatshme për të krijuar një bazë të dhënash të specializuar super të shpejtë.
Shpresoj shumë që punët e mia do të jenë të dobishme dhe interesante për ju. Le të fillojmë!
Hyrje
Përshëndetje të gjithëve! Tani është gjashtë pasdite, ne jemi të gjithë të lodhur. Koha e shkëlqyer për të folur për teorinë e mërzitshme të indekseve të bazave të të dhënave, apo jo? Mos u shqetësoni, do të kem disa rreshta kod këtu e atje. 🙂
Nëse flasim seriozisht, prezantimi është i mbushur me informacion, dhe nuk kemi shumë kohë. Pra, le të fillojmë.
Sot do të flas për:
- çfarë janë indekset;
- çfarë është indeksi bitmap;
- ku përdoret dhe ku NUK përdoret ai dhe pse;
- një implementim i thjeshtë në Go dhe pak përpjekje me kompilatorin;
- një implementim pak më pak të thjeshtë, por shumë më të efikas në Go-assembler;
- "problemet" e indekseve bitmap;
- implementime ekzistuese.
Pra, çfarë janë indekset?
Indeksi është një strukturë të dhënash e veçantë që e mbahet dhe e përditësohet përveç të dhënave kryesore. Përdoret për të përshpejtuar kërkimin. Pa indekse, kërkimi do të kërkonte një kalim të plotë përmes të dhënave (procesi i quajtur skanim i plotë), dhe ky proces ka një kompleksitet algoritmik linear. Por bazat e të dhënave zakonisht përmbajnë një sasi të madhe të dhënash dhe kompleksiteti linear është shumë i ngadalshëm. Në mënyrë ideale, do të donim të merrnim një kompleksitet logjaritmik ose konstant.
Kjo është një temë e madhe e komplikuar, e mbushur me nuanca dhe kompromise, por, duke parë mbi dhjetë vite zhvillimi dhe kërkimi të bazave të të dhënave të ndryshme, jam i gatshëm të pretendoj se ekzistojnë vetëm disa qasje të njohura për krijimin e indekseve të DB.
Qasja e parë përfshin reduktimin hierarkik të zonës së kërkimit, duke ndarë zonën e kërkimit në pjesë më të vogla.
Në përgjithësi, ne e bëjmë këtë duke përdorur lloje të ndryshme pemësh. Një shembull mund të jetë një kuti e madhe me materiale në dollapin tuaj, në të cilën ndodhen kutia më të vogla me materiale, të ndara sipas temave të ndryshme. Nëse ju nevojiten materiale, me siguri do të kërkoni ato në kutinë e etiketuar "Materiale", dhe jo në atë me etiketë "Biskota", apo jo?
Qasja e dytë është që të nxjerrim menjëherë elementin e nevojshëm ose grupin e elementeve. Ne e bëjmë këtë në harta hash ose në indekse të kundërta. Përdorimi i harta hash është shumë i ngjashëm me shembullin e mëparshëm, vetëm se në dollapin tuaj keni shumë kutia të vogla me objekte përfundimtare.
Qasja e tretë është të hiqni nevojën për kërkim. Kjo e bëjmë me ndihmën e filtreve Bloom ose filtreve cuckoo. E para jep përgjigjen menjëherë, duke ju shpëtuar nga nevoja për të kryer kërkimin.
Qasja e fundit është të përdorim plotësisht të gjitha kapacitetet që na ofron hardueri modern. Këtë e bëjmë në indekset bitmap. Po, kur i përdorim, ndonjëherë na nevojitet të kalojmë nëpër të gjithë indeksin, por e bëjmë këtë super efikas.
Siç thashë, tema e indekseve të DB është e gjerë dhe e mbushur me kompromise. Kjo do të thotë që ndonjëherë ne mund të përdorim disa qasje njëkohësisht: nëse na nevojitet të përshpejtojmë më tej kërkimin ose nëse është e nevojshme të mbulojmë të gjitha llojet e mundshme të kërkimit.
Sot do të flas për qasjen më pak të njohur nga ato — për indekset bitmap.
Kush jam unë për të folur rreth kësaj teme?
Unë punoj si lider ekipi në Badoo (ndoshta e njihni më mirë produktin tonë tjetër — Bumble). Ne kemi më shumë se 400 milion përdorues në të gjithë botën dhe shumë karakteristika që merren me atë që gjejnë çiftin më të mirë për ta. Kjo e bëjmë përmes shërbimeve të personalizuara, duke përdorur gjithashtu indekset bitmap.
Pra, çfarë është indeksi bitmap?
Indeksat bitmap, siç sugjerohet nga emri, përdorin bitmap ose bitset për të implementuar një indeks kërkimi. Nga një perspektivë e lartë, ky indeks përbëhet nga një ose disa prej këtyre bitmap-eve, që përfaqësojnë entitete të tilla si njerëz dhe pronat ose parametrat e tyre (mosha, ngjyra e syve, etj.), dhe nga një algoritëm që përdor operacione bitore (AND, OR, NOT) për të përgjigjur në kërkesat e kërkimit.
Na thuhet se indeksat bitmap janë më të përshtatshëm dhe shumë efikas për raste kur ka kërkesa që bashkojnë kërkesa mbi shumë kolona me cardinalitet të ulët (imagjinoni "ngjyrën e syve" ose "statusin familjar" kundër diçkaje si "distanca nga qendra e qytetit"). Por më vonë do t'ju tregoj se ata funksionojnë edhe në rastin e kolonave me cardinalitet të lartë.
Le të shqyrtojmë një shembull të thjeshtë të një indeksi bitmap.
Imagjinoni se kemi një listë restoranesh në Moskë me prona binare si këto:
- pranë metrosë (near metro);
- ka parkim privat (has private parking);
- ka verande (has terrace);
- pranon rezervime (accepts reservations);
- është vegetarian-friendly (vegan friendly);
- eshte i shtrenjtë (expensive).
Le të japim çdo restoranti një numër rendor duke filluar nga 0 dhe t'i rezervojmë hapësirë për 6 bitmap-e (një për çdo karakteristikë). Pastaj ne do t’i mbushim këto bitmap-e në varësi të faktit nëse restoranti ka këtë pronë apo jo. Nëse restoranti 4 ka verande, atëherë biti nr. 4 në bitmapin "ka verande" do të vendoset në 1 (nëse nuk ka verande, atëherë në 0).
Tani kemi indeksin bitmap më të thjeshtë të mundshëm, dhe mund ta përdorim atë për të përgjigjur në kërkesa si:
- "Më trego restoranet që janë vegetarian-friendly";
- "Më trego restorantet e lira me verande, ku mund të rezervoj një tavolinë".
Si? Le të shohim. Kërkesa e parë është shumë e thjeshtë. E gjithë ciò që na nevojitet është të marrim bitmapin "është vegetarian-friendly" dhe ta shndërrojmë atë në një listë restorantesh, të cilët kanë bitet e vendosura.
Kërkesa e dytë është pak më e komplikuar. Na nevojitet të përdorim operacionin bitor NOT në bitmapin "i shtrenjtë" për të marrë listën e restoranteve të lira, pastaj ta AND-me me bitmapin "pranon rezervime" dhe të AND-me rezultatin me bitmapin "ka verande". Bitmapi rezultues do të përmbajë një listë të shërbimeve që përfshijnë të gjitha kriteret tona. Në këtë shembull, kjo është vetëm restoranti "Junost".
Këtu ka shumë teori, por mos u shqetësoni, do të shohim kodin shumë shpejt.
Ku përdoren indeksat bitmap?
Nëse e "Google-oni" indeksat bitmap, 90% e përgjigjeve do të jenë në një farë mënyre të lidhura me Oracle DB. Por sistemet e tjera DB gjithashtu sigurisht që mbështesin një gjë kaq të mahnitshme, apo jo? Jo saktësisht.
Le të shkojmë përmes listës së dyshuarve kryesorë.
MySQL nuk mbështet ende indeksat bitmap, por ka një propozim për të shtuar këtë opsion ().
PostgreSQL nuk mbështet indeksat bitmap, por përdor bitmap të thjeshtë dhe operacione bitore për të bashkuar rezultatet e kërkimit mbi shumë indekse të tjera.
Tarantool ka indekse bitset, ai mbështet kërkimin e thjeshtë mbi to.
Redis ka fushat e thjeshta bitore) pa mundësi për kërkim mbi to.
MongoDB ende nuk mbështet indeksat bitmap, por gjithashtu ka një propozim për të shtuar këtë opsion.
Elasticsearch përdor bitmap brenda).
- Por në shtëpinë tonë ka një fqinj të ri: Pilosa. Kjo është një bazë të dhënash jo-relacionale e shkruar në Go. Ajo vetëm përmban indekse bitmap dhe bazohet krejtësisht në to. Do të flasim për të më vonë.
Implementimi në Go
Por pse indekset bitmap përdorenaq më rrallë? Para se të përgjigjem në këtë pyetje, do të doja t'ju demonstroja implementimin e një indeksi bitmap shumë të thjeshtë në Go.
Bitmap janë, në thelb, bërë thjesht nga copa të të dhënave. Në Go, le t'i përdorim për këtë slice e byte.
Kemi një bitmap për një karakteristikë restoranti, dhe çdo bit në bitmap tregon nëse një restorant konkret ka këtë pronë apo jo.
Na duhen dy funksione ndihmëse. Njëra do të përdoret për të mbushur bitmapet tona me të dhëna rastësore. Rastësore, por me një probabilitet të caktuar për secilin pronë që restoranti ka. Për shembull, unë besoj se në Moskë ka shumë pak restorante ku nuk mund të rezervosh një tavolinë, dhe mendoj se rreth 20% e shërbimeve janë vegetarian-friendly.
Funksioni i dytë do të shndërrojë bitmapin në një listë restorantesh.
Për të përgjigjur në kërkesën "Më trego restoranet e lira, që kanë verande dhe ku mund të rezervosh një tavolinë", na nevojiten dy operacione bitore: NOT dhe AND.
Mund të thjeshtojmë pak kodin tonë duke përdorur një operacion më të avancuar AND NOT.
Kemi funksione për secilin prej këtyre operacioneve. Të dyja kalojnë përmes slice-ve, marrin elementet përkatëse nga secili, i bashkojnë ata me operacionin bitor dhe e vendosin rezultatin në slice-n përfundimtar.
Dhe tani mund t’i shfrytëzojmë bit-mapet dhe funksionet tona për të përgjigjur në kërkesën e kërkimit.
Performanca nuk është kaq e lartë, edhe pse funksionet janë shumë të thjeshta dhe ne kemi kursyer shumë duke mos kthyer një slice përfundimtar të ri me çdo thirrje funksioni.
Pasi profilioj pak me pprof, vura re se kompajleri Go kaloi një optimizim shumë të thjeshtë, por shumë të rëndësishëm: inlining i funksioneve.
E vërteta është se kompajleri Go ka frikë nga ciklet që kalojnë përmes slice-ve dhe kurrë nuk pranon të inline funksione që përmbajnë këto cikle.
Por unë nuk kam frikë dhe mund ta gënjej kompajlerin duke përdorur goto në vend të ciklit, si në ditët e mira të vjetra.
Dhe, siç e shihni, tani kompajleri me kënaqësi inline-ona funksionin tonë! Në fund, arrijmë të kursejmë rreth 2 mikrosekonda. Jo keq!
Ngushtica e dytë nuk është e vështirë të shihet, nëse shikoni me kujdes daljen e assembler-it. Kompajleri shtoi një kontroll në kufijtë e slice-it brenda ciklit tonë më të nxehtë. E vërteta është se Go është një gjuhë e sigurt, kompajleri është i shqetësuar që tre argumentet e mia (tre slice) kanë përmasa të ndryshme. Sepse atëherë do të kishte mundësi teorike për të ndodhur ajo që quhet mbushja e tamponit (buffer overflow).
Le të qetësojmë kompajlerin, duke i treguar atij se të gjithë slice-t kanë të njëjtën madhësi. Mund ta bëjmë këtë duke shtuar një kontroll të thjeshtë në fillim të funksionit tonë.
Duke e parë këtë, kompajleri me kënaqësi kalon kontrollin, dhe ne përfundojmë me kursim të tjera 500 nanosekonda.
Batches të mëdha
OK, arritëm të nxjerrim ndonjë performancë nga implementimi ynë i thjeshtë, por rezultati në të vërtetë është shumë më i dobët se sa mund të jetë me harduerin aktual.
E gjitha që po bëjmë është operacione të baza bitore, dhe procesorët tanë i kryejnë këto operacione shumë efikas. Por, fatkeqësisht, ne 'ushqejmë' procesorin tonë me copëza shumë të vogla pune. Funksionet tona kryejnë operacione në bajta. Mund ta përmirësojmë shumë lehtë kodin tonë që të punojë me copëza 8-bajtëshe, duke përdorur slice UInt64.
Siç e shihni, kjo ndryshim e vogël e përshpejton programin tonë në tetë herë duke rritur batch-in në tetë herë. Fitimi, mund të thuhet, është linear.
Implementimi në assembler
Por kjo nuk është fundi. Procesorët tanë mund të punojnë me copëza 16, 32 dhe madje edhe 64 bajt. Këto operacione 'të gjera' quhen single instruction multiple data (SIMD; një instruktion, shumë të dhëna), dhe procesi për të transformuar kodin në mënyrë që të përdorë këto operacione quhet vektorizim.
Fatkeqësisht, kompajleri Go nuk është një student i shkëlqyer në vektorizim. Aktualisht, mënyra e vetme për të vektorizuar kodin në Go është të marrësh të dhënat e operacionit manualisht duke përdorur assembler-in Go.
Assembler-i Go është një krijesë e çuditshme. Ju me siguri e dini se assembler-i është diçka shumë e lidhur me arkitekturën e kompjuterit për të cilin shkruani, por në Go nuk është kështu. Assembler-i Go është më shumë si IRL (intermediate representation language) ose një gjuhë përfaqësimi të mesëm: është praktikisht platformë e pavarur. Rob Pike mbajti një prezantim të shkëlqyer në këtë temë disa vjet më parë në GopherCon në Denver.
Përveç kësaj, Go përdor një format të pazakontë Plan 9, që ndryshon nga formatet e njohura AT&T dhe Intel.
Mund të thuhet me besim se të shkruash assembler Go me dorë nuk është aktiviteti më argëtues.
Por, fatmirësisht, tashmë ka dy mjete të nivelit të lartë që na ndihmojnë në shkruarjen e assembler-it Go: PeachPy dhe avo. Të dyja mjetet gjenerojnë assembler Go nga kod më të lartë të shkruar në Python dhe Go përkatësisht.
Këto mjete thjeshtojnë gjërat si alokimi i regjistrit (zgjedhja e regjistrit të procesorit), shkruarja e cikleve, dhe në përgjithësi e thjeshtojnë procesin e hyrjes në botën e programimit assembler në Go.
Ne do të përdorim avo, kështu që programet tona do të jenë pothuajse si programet normale në Go.
Kjo është një shembull shumë i thjeshtë i një programi avo. Ne kemi një funksion main() që përcakton brenda vetes një funksion Add(), ku synimi është të mbledhë dy numra. Këtu ka funksione ndihmëse për të marrë parametrat sipas emrit dhe për të marrë një nga regjistrat e procesorit të lirë dhe të përshtatshëm. Çdo operacion të procesorit ka një funksion përkatës në avo, siç tregohet nga ADDQ. Dhe në fund, shohim funksionin ndihmës për të ruajtur vlerën e rezultatit.
Duke thirrur go generate, ne do të ekzekutojmë programin në avo dhe përfundimisht do të gjenerohen dy skedarë:
- add.s me kodin e rezultuar në Go-assembly;
- stub.go me tituj funksionesh për lidhjen e dy botëve: Go dhe assembly.
Tani, kur kemi parë se çfarë bën dhe si funksionon avo, le të shohim funksionet tona. Kam realizuar si versionet skalar, ashtu edhe ato vektoriale (SIMD).
Më parë, le të shohim versionet skalar.
Ashtu si në shembullin e mëparshëm, ne kërkojmë të na sigurohet një regjistrë të lirë dhe të duhur të përgjithshëm, ne nuk kemi nevojë të llogarisim zhvendosjet dhe madhësitë për argumentet. Të gjitha këto i bën avo për ne.
Më parë kemi përdorur etiketat dhe goto (ose skenarë) për të përmirësuar performancën dhe për të mashtruar kompajlerin Go, por tani po e bëjmë këtë qysh në fillim. Arsyeja është se ciklet janë një koncept më i avancuar. Në assembly kemi vetëm etiketat dhe skenarët.
Kodi i mbetur duhet të jetë tashmë i njohur dhe i qartë. Ne po imitojmë ciklin me etiketa dhe skenarë, marrim një pjesë të vogël të të dhënave nga dy sllajsat tona, i bashkojmë ato me një operacion bitësh (AND NOT në këtë rast) dhe më pas vendosim rezultatin në sllajsin rezultues. Kaq.
Kjo është si duket kodi përfundimtar në assembly. Ne nuk keni pasur nevojë të llogarisim zhvendosjet dhe madhësitë (gjë që është theksuar me të gjelbër) ose të monitorojmë regjistrat e përdorur (theksuar me të kuqe).
Nëse krahasojmë performancën e implementimit në assembly me performancën e implementimit më të mirë në Go, ne do të shohim se ato janë të njëjta. Dhe kjo është e parashikueshme. Sepse ne nuk bëmë asgjë të veçantë - thjesht riprodhuam atë që do të bënte kompajleri Go.
Për fat të keq, ne nuk mund të detyrojmë kompajlerin të bëjë inlinin e funksioneve tona të shkruara në assembly. Kompajleri Go aktualisht nuk ka këtë mundësi, megjithatë kërkesa për ta shtuar atë ekziston prej një kohe të gjatë.
Pikërisht për këtë arsye është e pamundur të fitojmë ndonjë përfitim nga funksionet e vogla në assembly. Duhet të shkruajmë ose funksione të mëdha, ose të përdorim paketën e re math/bits, ose të anashkalojmë assembly-n.
Tani le të shohim versionet vektoriale të funksioneve tona.
Për këtë shembull kam vendosur të përdorë AVX2, kështu që ne do të përdorim operacionet që punojnë me copëza 32-byte. Struktura e kodit është shumë e ngjashme me versionin skalar: ngarkimi i parametrave, kërkesa për një regjistër të përgjithshëm të lirë, etj.
Një nga risitë ka të bëjë me faktin se operacionet më të gjera vektoriale përdorin regjistra të veçantë të gjërë. Në rastin e copëzave 32-byte, këta janë regjistrat me prefix Y. Kjo është arsyeja pse ju shihni funksionin YMM() në kod. Nëse do të përdorja AVX-512 me copëza 64-bit, atëherë prefixi do të ishte Z.
Risia e dytë ka të bëjë me faktin se kam vendosur të përdor optimizimin që quhet zhvillimi i ciklit (loop unrolling), domethënë të bëj tetë operacione cikli manualisht, para se të hidhem në fillimin e ciklit. Ky optimizim zvogëlon numrin e degëzimeve (branching) në kod, dhe ai është i kufizuar nga numri i regjistrave të lirë që kemi në dispozicion.
Ndërsa, çfarë është për performancën? Ajo është e shkëlqyer! Kemi arritur një përshpejtim rreth shtatë herë krahasuar me zgjidhjen më të mirë në Go. Impressive, apo jo?
Por edhe kjo implementim potencialisht mund të optimizohet duke përdorur AVX-512, prë-fetching ose JIT (just-in-time compiler) për planifikuesin e kërkesave. Por kjo është sigurisht një temë për një prezantim të veçantë.
Problemet e indekseve bitmap
Tani që kemi shqyrtuar implementimin e thjeshtë të indekseve bitmap në Go dhe shumë më të performueshëm në assembly, le të flasim përse indekset bitmap përdoren kaq rrallë.
Në studimet e vjetra shkencore përmenden tre probleme të indekseve bitmap, por studimet e reja shkencore dhe unë pretendojmë se ato tashmë nuk janë të vlefshme. Nuk do të thellohemi shumë në secilën nga këto probleme, por do t'i shqyrtojmë ato nga sipër.
Problemi i kardinalitetit të lartë
Pra, na thuhet se indeksët bitmap funksionojnë vetëm për fushat me kardinalitet të ulët, pra ato që kanë pak vlera (p.sh., gjinia ose ngjyra e syve), dhe arsyeja është se paraqitja e zakonshme e këtyre fushave (një bit për vlerë) do të merrte shumë hapësirë në rastin e kardinalitetit të lartë, dhe madje, këta indekse bitmap do të ishin të mbushur dobët (rrallë).
Ndonjëherë mund të përdorim një paraqitje tjetër, p.sh., atë standard që përdorim për të paraqitur numrat. Por është pikërisht shfaqja e algoritmeve të kompresimit që ndryshoi gjithçka. Gjatë dy dekadave të fundit, shkencëtarët dhe hulumtuesit kanë krijuar shumë algoritme kompresimi për bitmap-et. Avantazhi kryesor i tyre është se nuk është e nevojshme të dekompresojmë bitmap-et për të kryer operacione bitore — mund të kryejmë operacione bitore direkt mbi bitmap-et e kompresuar.
Së fundmi, kanë filluar të shfaqen edhe qasje hibride, siç janë bitmap-et roaring. Ato përdorin në të njëjtën kohë tre përfaqësime të ndryshme për bitmap-et — në thelb bitmap-et, masa dhe të ashtuquajturat bit runs — dhe balancojnë midis tyre për të maksimizuar performancën dhe minimizuar konsumimin e memories.
Mund të takoni bitmap-et roaring në aplikacionet më të njohura. Tani ekziston një numër i madh implementimesh për gjuhë të ndryshme programimi, duke përfshirë më shumë se tre implementime për Go.
Një tjetër qasje që mund të na ndihmojë të përballojmë kardinalitetin e lartë quhet grupimi (binning). Imagjinoni se keni një fushë që përfaqëson rritjen e një personi. Rritja është një numër me pikë të lëvizshme, por ne, njerëzit, nuk mendojmë kështu. Për ne, nuk ka ndonjë ndryshim midis rritjes 185.2 cm dhe 185.3 cm.
Kështu, mund të grupojmë vlerat e ngjashme në grupe brenda 1 cm.
Dhe nëse dimë se shumë pak njerëz kanë rritje më të vogël se 50 cm dhe më të madhe se 250 cm, atëherë ne mund të kthejmë një fushë me kardinalitet të pafund në një fushë me kardinalitet rreth 200 vlerash.
Sigurisht, nëse nevojitet, mund të bëjmë filtrimin shtesë pas kësaj.
Problemi i kapacitetit të lartë
Problemi tjetër me indeksët bitmap është se përditësimi i tyre mund të jetë shumë i shtrenjtë.
Bashkët e dhënave duhet të lejojnë përditësimin e të dhënave në momentin kur potencialisht qindra kërkesa të tjera po kërkojnë mbi këto të dhëna. Na duhen bllokime për të shmangur problemet me qasjen e përbashkët mbi të dhënat ose probleme të tjera të qasjes. Dhe atje ku ka një bllok të madh, aty ka një problem — kontestimi i bllokut, kur ky bllok bëhet ngushticë.
Ky problem mund të zgjidhet ose të shmanget përmes shardingut ose përdorimit të indeksëve me versióne.
Shardingu është diçka e thjeshtë dhe e njohur. Mund të bëni sharding të indeksit bitmap ashtu siç do të sharding-ronit të dhëna të tjera. Në vend të një blloku të madh, do të merrni shumë blloqe të vogla, duke eliminuar kështu kontestimin e bllokut.
Mënyra e dytë për të zgjidhur problemin është përdorimi i indeksëve me version. Mund të keni një kopje të indeksit që përdorni për kërkimin ose leximin, dhe një tjetër për shkruajtur ose përditësuar. Dhe çdo herë pas një intervali të caktuar (p.sh., çdo 100 ms ose 500 ms) i kopjoni ato dhe i ndërrojnë vendet. Sigurisht, ky qasje është e aplikueshme vetëm në ato raste kur aplikacioni juaj mund të punojë me një indeks kërkimi paksa pas.
Këto dy qasje mund të përdoren njëkohësisht: mund të keni një indeks të ndarë dhe me versione.
Kërkesat më të ndërlikuara
Problemi i fundit me indeksët bitmap është se, siç na thuhet, ata nuk funksionojnë mirë me tipe më të ndërlikuara kërkesash, si p.sh. kërkesat "në interval".
Në të vërtetë, nëse mendoni, operacionet bitore si AND, OR, etj., nuk janë shumë të përshtatshme për kërkesat si "Më trego hotelet me çmimin e dhomës nga 200 deri në 300 dollarë për natë".
Një zgjidhje naive dhe shumë e pamenduar do të ishte të merrni rezultatet për çdo vlerë dollarësh dhe t'i bashkoni ato me një operacion bitor OR.
Një zgjidhje pak më e saktë do të ishte të përdorim grupimin. Për shembull, në grupe prej 50 dollarësh. Kjo do ta përshpejtonte procesin tonë 50 herë.
Por problemi gjithashtu zgjidhet lehtësisht duke përdorur një paraqitje të krijuar veçanërisht për këtë lloj kërkesash. Në punimet shkencore, ajo quhet bitmap-e të koduara në interval.
Në këtë paraqitje, ne nuk vendosim vetëm një bit për ndonjë vlerë (p.sh., 200), por vendosim këtë vlerë dhe gjithçka më lartë. 200 dhe më lart. E njëjta gjë për 300: 300 dhe më lart. Dhe kështu me radhë.
Duke këtë pamje, ne mund të përgjigjemi ndaj këtij lloji të kërkimit duke kaluar nëpër indeksin vetëm dy herë. Fillimisht do të marrim një listë hotelesh ku çmimi i dhomës është më pak se 300 dollarë, dhe më pas do t'i heqim ato ku çmimi i dhomës është më pak se 199 dollarë. Përfunduar.
Do të habiteni, por edhe kërkimet gjeografike janë të mundshme duke përdorur bitmap-indekset. Truku qëndron në përdorimin e paraqitjes gjeografike, e cila rrethon koordinatën tuaj me një figurë gjeometrike. Për shembull, S2 nga Google. Figura duhet të jetë e mundur të përfaqësohet si tre ose më shumë linja që prekin njëra-tjetrën, të cilat mund të numërohen. Kështu, ne do të jemi në gjendje ta kthejmë kërkesën tonë gjeografike në disa kërkesa "në interval" (për këto linja të numëruara).
Zgjidhje të gatshme
Shpresoj që të keni marrë pak interes dhe të keni shtuar një mjet tjetër të dobishëm në arsenalin tuaj. Nëse ndonjëherë do t'ju nevojitet të bëni diçka të ngjashme, do të dini se ku të shikoni.
Megjithatë, nuk të gjithë kanë kohën, durimin dhe burimet për të krijuar bitmap-indekse nga e para. Veçanërisht ato më të avancuara, duke përdorur SIMD, për shembull.
Në fat të mirë, ka disa zgjidhje të gatshme që do t'ju ndihmojnë.
Roaring bitmaps
Së pari, ka biblotekën e famshme roaring bitmaps, për të cilën kam folur më parë. Ajo përmban të gjitha enë dhe operacione bit që do t'ju nevojiten për të krijuar një bitmap-indeks të plotë.
Fatkeqësisht, për momentin asnjë nga realizimet në Go nuk përdorin SIMD, dhe kështu, realizimet në Go janë më pak efikase se ato në C, për shembull.
Pilosa
Një produkt tjetër që mund t'ju ndihmojë është DB Pilosa, e cila në thelb ka vetëm bitmap-indekse. Ky është një zgjidhje relativisht e re, por po fiton shpesh zemrat me një ritëm të madh.
Pilosa përdor roaring bitmaps brenda saj dhe ju jep mundësinë për t'i përdorur ato, duke thjeshtuar dhe shpjeguar të gjitha ato gjëra për të cilat kam folur më parë: grumbullim, bitmap-e të koduar me interval, konceptin e fushës dhe të tjerë.
Le të hedhim një shikim të shpejtë në një shembull të përdorimit të Pilosa për t'u përgjigjur në një pyetje që ju është njohur.
Shembulli është shumë i ngjashëm me atë që keni parë më parë. Ne krijojmë një klient për serverin Pilosa, krijojmë një indeks dhe fushat e nevojshme, pastaj mbushim fushat tona me të dhëna aksidente me probabilitete dhe, përfundimisht, ekzekutojmë kërkesën e njohur.
Pas kësaj, ne përdorim NOT në fushën "e shtrenjtë", pastaj kryqëzojmë rezultatin (ose AND-ojmë) me fushën "terace" dhe me fushën "rezervime". Dhe përfundimisht, marrim rezultatin përfundimtar.
Shpresoj shumë që në të ardhmen e afërt në DB-të si MySQL dhe PostgreSQL të ketë edhe këtë lloj të ri indeksesh – bitmap-indekse.
Përfundimi
Nëse nuk keni fjetur ende, faleminderit. Më duhej të preka shumë tema me kusht për kohën e kufizuar, por shpresoj se prezantimi ishte i dobishëm dhe ndoshta edhe motivues.
Është mirë të dini për bitmap-indekset, edhe nëse për momentin nuk ju nevojiten. Le t'i kemi ato si një mjet tjetër në kutinë tuaj.
Ne kemi shqyrtuar disa truke për rritjen e performancës për Go dhe ato gjëra që kompileri Go ende nuk i menaxhon mirë. Kjo është absolutisht diçka e dobishme për çdo programues Go.
Kjo është gjithçka që doja të flisja. Faleminderit!
Burimi: habr.com
