Vërejtje hyrëse
E mbajta këtë fjalim në anglisht në konferencën GopherCon Russia 2019 në Moskë dhe në rusisht në një takim në Nizhny Novgorod. Ai diskuton një indeks bitmap - më pak i zakonshëm se një pemë B, por jo më pak interesant. Po e ndaj. Prezantimet në konferencë në anglisht dhe transkriptet në rusisht.
Do të shqyrtojmë se si funksionon një indeks bitmap, kur është më i mirë dhe më i keq se indekset e tjera, dhe në cilat raste është dukshëm më i shpejtë. Do të shohim se cilat DBMS të njohura kanë tashmë indekse bitmap; do të përpiqemi të shkruajmë tonat në Go. Dhe së fundmi, do të përdorim biblioteka të gatshme për të krijuar bazën tonë të të dhënave super të shpejtë të specializuar.
Shpresoj vërtet që puna ime të jetë e dobishme dhe interesante. Le të fillojmë!
Paraqitje
Tungjatjeta të gjithëve! Është ora gjashtë e mbrëmjes dhe të gjithë jemi shumë të lodhur. Koha ideale për të folur për teorinë e mërzitshme të indeksit të bazës së të dhënave, apo jo? Mos u shqetësoni, do të kem disa rreshta kodi burimor këtu e atje. 🙂
Seriozisht, ky raport është plot me informacione dhe nuk kemi shumë kohë. Pra, le të fillojmë.
Sot do të flas për sa vijon:
- Çfarë janë indekset?
- Çfarë është një indeks bitmap?
- ku përdoret dhe ku NUK përdoret dhe pse;
- implementim i thjeshtë në Go dhe pak përmirësime në kompajler;
- një implementim pak më pak i thjeshtë, por shumë më produktiv në Go assembler;
- "probleme" të indekseve bitmap;
- implementimet ekzistuese.
Pra, çfarë janë indekset?
Një indeks është një strukturë e veçantë e të dhënave që ne e mirëmbajmë dhe e përditësojmë përveç të dhënave kryesore. Përdoret për të shpejtuar kërkimet. Pa indekse, kërkimi do të kërkonte një skanim të plotë të të dhënave dhe ky proces ka kompleksitet algoritmik linear. Por bazat e të dhënave zakonisht përmbajnë sasi të mëdha të dhënash dhe kompleksiteti linear është shumë i ngadaltë. Idealisht, do të kishim kompleksitet logaritmik ose konstant.
Është një temë e madhe dhe komplekse, plot me hollësi dhe kompromise, por pas dekadash zhvillimi dhe kërkimi në baza të ndryshme të dhënash, jam i gatshëm të them se ekzistojnë vetëm disa qasje të përdorura gjerësisht për krijimin e indekseve të bazave të të dhënave.
Qasja e parë është zvogëlimi hierarkik i hapësirës së kërkimit, duke e ndarë atë në pjesë më të vogla.
Zakonisht e bëjmë këtë duke përdorur lloje të ndryshme pemësh. Një shembull do të ishte një kuti e madhe me materiale në dollapin tuaj, që përmban kuti më të vogla me materiale të kategorizuara sipas temës. Nëse keni nevojë për materiale, ndoshta do t'i kërkoni ato në kutinë e etiketuar "Materiale" në vend të asaj të etiketuar "Biskota", apo jo?
Qasja e dytë është të zgjidhni menjëherë elementin ose grupin e dëshiruar të elementeve. Ne e bëjmë këtë duke përdorur harta hash ose indekse inverse. Përdorimi i hartave hash është shumë i ngjashëm me shembullin e mëparshëm, përveçse në vend të një kutie plot me kuti, keni një tufë kutish të vogla në dollapin tuaj që përmbajnë artikujt përfundimtarë.
Qasja e tretë është eliminimi i nevojës për kërkim. Ne e bëjmë këtë duke përdorur filtra Bloom ose filtra Cuckoo. Të parët ofrojnë një përgjigje të menjëhershme, duke eliminuar nevojën për kërkim.
Qasja përfundimtare është shfrytëzimi i plotë i të gjithë fuqisë që kemi në dispozicion në pajisjet moderne. Kjo është pikërisht ajo që bëjmë me indekset bitmap. Po, kur i përdorim ato, ndonjëherë na duhet të përshkojmë të gjithë indeksin, por e bëjmë këtë në mënyrë shumë efikase.
Siç e kam përmendur tashmë, tema e indekseve të bazave të të dhënave është e gjerë dhe plot me kompromise. Kjo do të thotë që ndonjëherë mund të na duhet të përdorim qasje të shumëfishta njëkohësisht: nëse duhet të përshpejtojmë më tej kërkimet ose nëse duhet të mbulojmë të gjitha llojet e mundshme të kërkimit.
Sot do të flas për qasjen më pak të njohur nga ato të përmendura: indekset bitmap.
Kush jam unë që të flas për këtë temë?
Unë jam një drejtues ekipi në Badoo (mund të jeni më të njohur me produktin tonë tjetër, Bumble). Ne tashmë kemi mbi 400 milionë përdorues në të gjithë botën dhe shumë veçori që ndihmojnë në gjetjen e përputhjeve më të mira për ta. Ne e bëjmë këtë duke përdorur shërbime të personalizuara, duke përfshirë indekset bitmap.
Pra, çfarë është një indeks bitmap?
Indekset bitmap, siç sugjeron edhe vetë emri, përdorin bitmap ose bitsete për të zbatuar një indeks kërkimi. Në përgjithësi, ky indeks përbëhet nga një ose më shumë bitmap që përfaqësojnë entitete (siç janë njerëzit) dhe vetitë ose parametrat e tyre (mosha, ngjyra e syve, etj.), dhe një algoritëm që përdor operacione bitwise (ANDE, OSE, JO) për t'iu përgjigjur një pyetjeje kërkimi.
Na thuhet se indekset bitmap janë më të përshtatshmet dhe shumë efikase për rastet kur ka kërkime që kombinojnë pyetje nëpër kolona të shumëfishta me kardinalitet të ulët (mendoni për "ngjyrën e syve" ose "gjendjen civile" kundrejt diçkaje si "distanca nga qendra e qytetit"). Por më vonë do të tregoj se ato funksionojnë po aq mirë për kolonat me kardinalitet të lartë.
Le të shohim shembullin më të thjeshtë të një indeksi bitmap.
Imagjinoni që kemi një listë të restoranteve në Moskë me prona binare si këto:
- afër metrosë;
- ka parkim privat;
- ka një verandë (ka tarracë);
- Mund të rezervoni një tavolinë (pranohen rezervime);
- i përshtatshëm për vegjetarianë (miqësor ndaj veganëve);
- i shtrenjtë (i shtrenjtë).
Le t'i caktojmë secilit restorant një numër rendor duke filluar nga 0 dhe të ndajmë memorie për gjashtë bitmap-e (një për secilën karakteristikë). Pastaj do t'i popullojmë këto bitmap-e bazuar në faktin nëse restoranti ka një karakteristikë të caktuar. Nëse restoranti 4 ka një verandë, biti 4 në bitmap-in "ka një verandë" do të vendoset në 1 (nëse nuk ka, do të vendoset në 0).
Tani kemi indeksin më të thjeshtë të mundshëm bitmap dhe mund ta përdorim atë për t'iu përgjigjur pyetjeve si:
- "Më trego restorante që janë miqësore për vegjetarianët"
- "Më trego disa restorante të lira me verandë ku mund të bëj rezervime."
Si? Le të hedhim një vështrim. Pyetja e parë është shumë e thjeshtë. E tëra çfarë na duhet është të marrim bitmapin "miqësor për vegjetarianët" dhe ta shndërrojmë atë në një listë restorantesh, pjesët e të cilave janë të ekspozuara.
Pyetja e dytë është pak më komplekse. Duhet të përdorim operacionin NOT në mënyrë bitwise në bitmap-in "i shtrenjtë" për të marrë një listë të restoranteve të lira, pastaj DHE me bitmap-in "rezervime të disponueshme", dhe pastaj DHE rezultatin me bitmap-in "verandë e disponueshme". Bitmapi që rezulton do të përmbajë një listë të lokaleve që plotësojnë të gjitha kriteret tona. Në këtë shembull, ky është vetëm restoranti "Yunost".
Ka shumë teori këtu, por mos u shqetësoni, do ta shohim kodin shumë shpejt.
Ku përdoren indekset bitmap?
Nëse kërkoni në Google indekse bitmap, 90% e rezultateve do të lidhen me Oracle DB në një farë mënyre. Por sigurisht që edhe DBMS-të e tjera e mbështesin këtë veçori të mirë, apo jo? Jo tamam.
Le të shqyrtojmë listën e të dyshuarve kryesorë.
MySQL nuk mbështet ende indekset bitmap, por ekziston një propozim për të shtuar këtë opsion ().
PostgreSQL nuk mbështet indekset bitmap, por përdor bitmap të thjeshtë dhe operacione bitwise për të kombinuar rezultatet e kërkimit nëpër indekse të shumta të tjera.
Tarantool ka indekse bitsetesh dhe mbështet kërkim të thjeshtë në to.
Redis ka fusha të thjeshta bit-esh) pa mundësinë për t'i kërkuar ato.
MongoDB nuk i mbështet ende indekset bitmap, por ka një propozim për ta shtuar këtë veçori.
Elasticsearch përdor bitmap-e në mënyrë të brendshme).
- Por ne kemi një fqinj të ri në shtëpinë tonë: Pilosa. Është një bazë të dhënash e re jo-relacionale e shkruar në Go. Ajo përmban vetëm indekse bitmap dhe bazon gjithçka në to. Do të flasim për këtë pak më vonë.
Implementimi në Go
Por pse indekset bitmap përdoren kaq rrallë? Përpara se t'i përgjigjem kësaj pyetjeje, do të doja të demonstroja zbatimin e një indeksi bitmap shumë të thjeshtë në Go.
Bitmap-et janë në thelb vetëm pjesë të të dhënave. Në Go, le të përdorim feta bajtesh për këtë.
Ne kemi një bitmap për çdo karakteristikë restoranti, dhe çdo bit në bitmap tregon nëse një restorant i caktuar e ka këtë karakteristikë apo jo.
Do të na duhen dy funksione ndihmëse. Njëra do të përdoret për të populluar bitmapet tona me të dhëna të rastësishme. Të rastësishme, por me një probabilitet të caktuar që një restorant të ketë secilën pronë. Për shembull, besoj se ka shumë pak restorante në Moskë ku nuk mund të pranohen rezervime dhe mendoj se rreth 20% e tyre janë miqësore me vegjetarianët.
Funksioni i dytë do ta konvertojë bitmapin në një listë restorantesh.
Për t'iu përgjigjur pyetjes "Më trego restorante të lira që kanë një verandë dhe ku mund të bësh rezervime", na duhen dy operacione bitwise: NOT dhe AND.
Mund ta thjeshtojmë pak kodin tonë duke përdorur veprimin më kompleks DHE NOT.
Ne kemi funksione për secilin prej këtyre operacioneve. Të dy iterojnë mbi feta, marrin elementët përkatës nga secili, i kombinojnë ato duke përdorur një operacion bitwise dhe e vendosin rezultatin në fetën që rezulton.
Dhe tani mund të përdorim bitmapet dhe funksionet tona për t'iu përgjigjur pyetjes së kërkimit.
Performanca nuk është aq e mirë, edhe pse funksionet janë shumë të thjeshta dhe ne kursyem mjaft kohë duke mos kthyer një fetë të re rezultati sa herë që thirrej funksioni.
Pasi bëra pak profilizim me pprof, vura re se kompilatorit Go i mungonte një optimizim shumë i thjeshtë, por shumë i rëndësishëm: rreshtimi i funksioneve.
Çështja është se kompiluesi Go ka shumë frikë nga sythet që kalojnë nëpër feta dhe refuzon kategorikisht të inline funksionet që përmbajnë sythe të tilla.
Por nuk kam frikë dhe mund ta mashtroj kompiluesin duke përdorur goto në vend të një cikli, si në kohët e vjetra të mira.
Dhe siç mund ta shihni, kompiluesi tani e fut funksionin tonë në rreshta me kënaqësi! Si rezultat, kemi kursyer rreth 2 mikrosekonda. Jo keq!
Vështirësia e dytë dallohet lehtë nëse shikoni nga afër rezultatin e montimit. Kompiluesi shtoi një kontroll të kufijve të fetave brenda ciklit tonë më të nxehtë. Meqenëse Go është një gjuhë e sigurt, kompiluesi është i kujdesshëm ndaj madhësive të ndryshme të tre argumenteve të mia (tre feta). Kjo teorikisht do të krijonte një të ashtuquajtur mbingarkesë buffer-i.
Le ta sigurojmë kompiluesin se të gjitha fetat janë të së njëjtës madhësi. Mund ta bëjmë këtë duke shtuar një kontroll të thjeshtë në fillim të funksionit tonë.
Duke e parë këtë, kompiluesi me kënaqësi e anashkalon kontrollin dhe ne kursejmë edhe 500 nanosekonda të tjera.
Sasi të mëdha
Në rregull, pra arritëm të nxjerrim pak performancë nga implementimi ynë i thjeshtë, por rezultati është në fakt shumë më i keq se sa është e mundur me harduerin aktual.
Çdo gjë që bëjmë është operacione bazë bit-by-bit, dhe procesorët tanë i kryejnë ato me shumë efikasitet. Por për fat të keq, ne i ushqejmë procesorit tonë pjesë shumë të vogla pune. Funksionet tona kryejnë operacione bajt për bajt. Ne mund ta modifikojmë shumë lehtë kodin tonë që të funksionojë me pjesë 8-bajtëshe duke përdorur feta UInt64.
Siç mund ta shihni, ky ndryshim i vogël e përshpejtoi programin tonë me tetë herë, falë një rritjeje tetëfish të madhësisë së grupit. Fitimi është, në thelb, linear.
Implementimi i gjuhës Asamble
Por kjo nuk është fundi. Procesorët tanë mund të funksionojnë në pjesë prej 16, 32 dhe madje 64 bajtesh. Këto operacione "të gjera" quhen të dhëna të shumëfishta me një udhëzim të vetëm (SIMD), dhe procesi i transformimit të kodit për të përdorur këto operacione quhet vektorizim.
Fatkeqësisht, kompiluesi Go nuk është tamam një mjeshtër i vektorizimit. Aktualisht, e vetmja mënyrë për të vektorizuar kodin Go është zbatimi manual i këtyre operacioneve duke përdorur assemblerin Go.
Gjuha asamblere Go është një "bishë" e çuditshme. Ju ndoshta e dini që gjuha asamblere është diçka që është e lidhur ngushtë me arkitekturën e kompjuterit për të cilin po shkruani, por kjo nuk është rasti me Go. Gjuha asamblere Go është më shumë si një IRL (gjuhë përfaqësimi e ndërmjetme): është praktikisht e pavarur nga platforma. Rob Pike mbajti një fjalim të shkëlqyer rreth saj. mbi këtë temë disa vite më parë në GopherCon në Denver.
Përveç kësaj, Go përdor një format të pazakontë Plan 9 që ndryshon nga formatet e vendosura të AT&T dhe Intel.
Mund të thuhet me siguri se shkrimi i asamblesë në Go me dorë nuk është gjëja më argëtuese për të bërë.
Për fat të mirë, ekzistojnë tashmë dy mjete të nivelit të lartë që na ndihmojnë të shkruajmë asamblenë Go: PeachPy dhe avo. Të dy programet gjenerojnë asamblenë Go nga kodi i nivelit të lartë i shkruar në Python dhe Go, përkatësisht.
Këto shërbime thjeshtojnë gjëra të tilla si caktimi i regjistrave, ciklet e shkrimit dhe në përgjithësi e bëjnë më të lehtë fillimin e programimit në gjuhën assembly në Go.
Do të përdorim avo, kështu që programet tona do të jenë pothuajse si programet e rregullta Go.
Ja se si duket shembulli më i thjeshtë i një programi avo. Kemi një funksion main(), i cili përcakton në mënyrë të brendshme një funksion Add(), i cili mbledh dy numra. Ekzistojnë funksione ndihmëse për të rikuperuar parametrat me emër dhe për të rikuperuar një nga regjistrat e lirë të procesorit në dispozicion. Çdo operacion i procesorit ka një funksion avo përkatës, siç shihet në ADDQ. Së fundmi, shohim një funksion ndihmës për ruajtjen e vlerës që rezulton.
Duke thirrur go generate, ne do të ekzekutojmë programin në avo dhe si rezultat, do të gjenerohen dy skedarë:
- add.s me kodin që rezulton në Go assembler;
- stub.go me tituj funksionesh për të lidhur dy botët: Go dhe assembler.
Tani që pamë se çfarë bën avo dhe si, le të shohim funksionet tona. Unë kam zbatuar versione skalare dhe vektoriale (SIMD) të funksioneve.
Le të shohim së pari versionet skalare.
Ashtu si në shembullin e mëparshëm, ne kërkojmë një regjistër të lirë dhe të vlefshëm për qëllime të përgjithshme; nuk kemi nevojë të llogarisim zhvendosjet dhe madhësitë për argumentet. avo i bën të gjitha këto për ne.
Më parë, përdornim etiketat dhe goto (ose kërcimet) për të përmirësuar performancën dhe për të mashtruar kompiluesin Go, por tani po e bëjmë këtë që nga fillimi. Çështja është se laqet janë një koncept i nivelit më të lartë. Në assembly, kemi vetëm etiketa dhe kërcime.
Pjesa tjetër e kodit duhet të jetë e njohur dhe e thjeshtë deri tani. Ne imitojmë një cikël me etiketa dhe kërcime, marrim një pjesë të vogël të të dhënave nga dy fetat tona, i kombinojmë ato me një operacion bitwise (DHE JO në këtë rast) dhe pastaj e ruajmë rezultatin në fetën që rezulton. Kaq është.
Ja si duket kodi përfundimtar i asamblesë. Nuk na u desh të llogarisnim zhvendosjet dhe madhësitë (të theksuara me jeshile) ose të mbanim gjurmët e regjistrave të përdorur (të theksuar me të kuqe).
Nëse krahasojmë performancën e implementimit të gjuhës assembly me implementimin më të mirë të Go, do të shohim se është identik. Kjo është e pritshme. Në fund të fundit, ne nuk bëmë asgjë të veçantë - ne thjesht replikuam atë që do të bënte kompiluesi Go.
Fatkeqësisht, nuk mund ta detyrojmë kompiluesin të përfshijë funksionet tona të shkruara në assembly. Kompiluesi Go aktualisht nuk e ka këtë aftësi, megjithëse një kërkesë për të ka qenë në vazhdim për një kohë të gjatë.
Kjo është arsyeja pse është e pamundur të përfitojmë nga funksionet e vogla në asamble. Ne duhet ose të shkruajmë funksione të mëdha, të përdorim paketën e re math/bits, ose ta shmangim tërësisht asamblenë.
Le të shohim tani versionet vektoriale të funksioneve tona.
Për këtë shembull, kam vendosur të përdor AVX2, kështu që do të përdorim operacione që funksionojnë në pjesë 32-bajtëshe. Struktura e kodit është shumë e ngjashme me versionin skalar: ngarkimi i parametrave, kërkesa për një regjistër të lirë për qëllime të përgjithshme, etj.
Një nga risitë është se operacionet vektoriale më të gjera përdorin regjistra të gjerë specialë. Në rastin e fragmenteve 32-bajtëshe, këto janë regjistra me prefiks Y. Kjo është arsyeja pse e shihni funksionin YMM() në kod. Nëse do të përdorja AVX-512 me fragmente 64-bitëshe, prefiksi do të ishte Z.
Risia e dytë lidhet me vendimin tim për të përdorur një optimizim të quajtur shpalosje e ciklit, i cili përfshin kryerjen manuale të tetë operacioneve të ciklit përpara se të kalohet në fillim të tij. Ky optimizim zvogëlon numrin e degëve në kod dhe kufizohet nga numri i regjistrave të lirë në dispozicion.
Po performanca? Është fantastike! Kemi një shpejtësi prej rreth shtatëfishi krahasuar me zgjidhjen më të mirë Go. Mbresëlënëse, apo jo?
Edhe ky implementim mund të përshpejtohet potencialisht duke përdorur AVX-512, para-kërkimin ose një planifikues pyetjesh JIT (përpilues vetëm në kohë). Por kjo është padyshim një temë për një diskutim të veçantë.
Probleme me indekset bitmap
Tani që kemi trajtuar një implementim të thjeshtë të një indeksi bitmap në Go dhe një implementim shumë më performues në assembly, le të flasim më në fund pse indekset bitmap përdoren kaq rrallë.
Punimet më të vjetra akademike përmendin tre probleme me indekset bitmap, por unë dhe punimet më të reja argumentojmë se ato nuk janë më relevante. Ne nuk do të futemi thellë në secilin prej këtyre problemeve, por do t'i trajtojmë shkurtimisht.
Problemi i kardinalitetit të madh
Pra, na thuhet se indekset bitmap janë të përshtatshme vetëm për fushat me kardinalitet të ulët, d.m.th. ato me pak vlera (si gjinia ose ngjyra e syve), dhe arsyeja është se përfaqësimi i zakonshëm i fushave të tilla (një bit për vlerë) në rast të kardinalitetit të lartë do të zinte shumë hapësirë dhe, për më tepër, këto indekse bitmap do të ishin të populluara rrallë (rrallë).
Ndonjëherë mund të përdorim një përfaqësim të ndryshëm, siç është ai standard që përdorim për përfaqësimin e numrave. Por ishte ardhja e algoritmeve të kompresimit që ndryshoi gjithçka. Gjatë dekadave të fundit, shkencëtarët dhe studiuesit kanë zhvilluar një numër të madh algoritmesh të kompresimit bitmap. Avantazhi i tyre kryesor është se nuk kërkojnë dekompresim të bitmap-it për të kryer operacione bitmap - ne mund të kryejmë operacione bitmap direkt në bitmap-et e kompresuara.
Kohët e fundit, kanë filluar të shfaqen qasje hibride, të tilla si bitmap-et e fuqishme. Ato përdorin njëkohësisht tre përfaqësime të ndryshme bitmap - vetë bitmap-et, vargjet dhe të ashtuquajturat ekzekutime bit - dhe balancojnë midis tyre për të maksimizuar performancën dhe për të minimizuar konsumin e memories.
Mund të gjeni bitmap-e të shkëlqyera në aplikacionet më të njohura. Tashmë ekziston një numër i madh implementimesh për një gamë të gjerë gjuhësh programimi, duke përfshirë më shumë se tre implementime për Go.
Një qasje tjetër që mund të na ndihmojë të përballojmë kardinalitetin e lartë quhet grumbullim në kuti. Imagjinoni që keni një fushë që përfaqëson gjatësinë e një personi. Gjatësia është një numër me pikë lundruese, por ne njerëzit nuk e mendojmë në atë mënyrë. Për ne, nuk ka ndryshim midis një gjatësie prej 185,2 cm dhe një gjatësie prej 185,3 cm.
Rezulton se ne mund të grupojmë vlera të ngjashme në grupe brenda 1 cm.
Dhe nëse e dimë gjithashtu se shumë pak njerëz janë më të shkurtër se 50 cm dhe më të gjatë se 250 cm, atëherë në thelb mund ta transformojmë një fushë me kardinalitet të pafund në një fushë me një kardinalitet prej afërsisht 200 vlerash.
Sigurisht, nëse është e nevojshme, mund të bëjmë filtrim shtesë më pas.
Problemi i bandwidth-it të lartë
Problemi tjetër me indekset bitmap është se përditësimi i tyre mund të jetë shumë i kushtueshëm.
Bazat e të dhënave duhet të jenë në gjendje të përditësojnë të dhënat ndërsa potencialisht qindra pyetje të tjera po i kërkojnë ato. Ne kemi nevojë për bllokime për të shmangur problemet e aksesit të njëkohshëm dhe problemet e tjera të aksesit të përbashkët. Dhe aty ku ka një bllokim të vetëm të madh, ka një problem - grindje për bllokime - kur ai bllokim bëhet një pengesë.
Ky problem mund të zgjidhet ose të anashkalohet duke bërë sharding ose duke përdorur indekse të versionuara.
Shardimi është i thjeshtë dhe i njohur mirë. Ju mund të shardoni një indeks bitmap në të njëjtën mënyrë siç do të shardonit çdo të dhënë tjetër. Në vend të një brave të madhe, ju merrni një mori bravash të vogla, duke eliminuar kështu grindjen për brava.
Zgjidhja e dytë është të përdorni indekse të versionuara. Mund të keni një kopje të indeksit, të cilën e përdorni për kërkim ose lexim, dhe një për shkrim ose përditësim. Pastaj, çdo disa sekonda (për shembull, çdo 100 ms ose 500 ms), i dublikoni dhe i ndërroni ato. Sigurisht, kjo qasje është e zbatueshme vetëm nëse aplikacioni juaj mund të trajtojë një indeks kërkimi paksa të vonuar.
Këto dy qasje mund të përdoren njëkohësisht: mund të keni një indeks të versionuar të copëtuar.
Pyetje më komplekse
Problemi i fundit me indekset bitmap është se na thuhet se ato nuk janë të përshtatshme për lloje më komplekse pyetjesh, siç janë pyetjet e diapazonit.
Në të vërtetë, nëse mendoni për këtë, operacionet bit-si DHE, OSE, etj. nuk janë shumë të përshtatshme për pyetje të tilla si "Më trego hotele me çmime dhomash midis 200 dhe 300 dollarëve për natë".
Një zgjidhje naive dhe shumë e pamatur do të ishte të merreshin rezultatet për secilën vlerë të dollarit dhe t'i kombinoheshin ato me një operacion OSE sipas biteve.
Një zgjidhje pak më e mirë do të ishte përdorimi i grupimit. Për shembull, në grupe prej 50 dollarësh. Kjo do ta përshpejtonte procesin tonë 50 herë.
Por problemi zgjidhet lehtësisht edhe duke përdorur një përfaqësim të krijuar posaçërisht për këtë lloj pyetjeje. Në punimet shkencore, quhet bitmap i koduar sipas diapazonit.
Në këtë përfaqësim, ne nuk caktojmë vetëm një bit për një vlerë (le të themi, 200), por caktojmë atë vlerë dhe çdo gjë mbi të. 200 e lart. E njëjta gjë për 300: 300 e lart. E kështu me radhë.
Duke përdorur këtë përfaqësim, mund t'i përgjigjemi këtij lloj pyetjeje kërkimi duke përshkuar indeksin vetëm dy herë. Së pari, do të marrim një listë hotelesh me një çmim dhome më të vogël ose të barabartë me 300 dollarë dhe më pas do të eliminojmë ato me një çmim dhome më të vogël ose të barabartë me 199 dollarë. U krye.
Mund të habiteni, por edhe pyetjet gjeografike janë të mundshme duke përdorur indekse bitmap. Truku është të përdorni një përfaqësim gjeografik që rrethon koordinatën tuaj me një formë gjeometrike. Për shembull, S2 e Google. Forma duhet të jetë e përfaqësueshme si tre ose më shumë vija kryqëzuese që mund të numërohen. Në këtë mënyrë, ne mund ta shndërrojmë pyetjen tonë gjeografike në pyetje të shumëfishta "boshllëku" (përgjatë këtyre vijave të numëruara).
Zgjidhje të gatshme
Shpresoj se të kam zgjuar interesin dhe të kam dhënë një mjet tjetër të dobishëm në arsenalin tënd. Nëse ndonjëherë ke nevojë të bësh diçka të ngjashme, do të dish ku të kërkosh.
Megjithatë, jo të gjithë kanë kohën, durimin dhe burimet për të krijuar indekse bitmap nga e para, veçanërisht ato më të përparuara, siç janë ato që përdorin SIMD.
Për fat të mirë, ka disa zgjidhje të gatshme që do t'ju ndihmojnë.
Bitmap-e të fuqishme
Së pari, është biblioteka e fuqishme e bitmap-eve që përmenda më parë. Ajo përmban të gjithë kontejnerët dhe operacionet bitwise të nevojshme që do t'ju nevojiten për të krijuar një indeks bitmap plotësisht funksional.
Fatkeqësisht, për momentin, asnjë nga implementimet Go nuk përdor SIMD, që do të thotë se implementimet Go janë më pak performuese se implementimet C, për shembull.
Pilosa
Një produkt tjetër që mund t'ju ndihmojë është Pilosa DBMS, i cili në thelb ka vetëm indekse bitmap. Është një zgjidhje relativisht e re, por po fiton popullaritet me një ritëm të pabesueshëm.
Pilosa përdor bitmap-e të fuqishme në mënyrë të brendshme dhe ju jep mundësinë t'i përdorni ato, thjeshton dhe shpjegon të gjitha gjërat për të cilat fola më sipër: grupimin, bitmap-et e koduara sipas diapazonit, konceptin e fushave, etj.
Le të shohim shpejt një shembull se si Pilosa mund të përdoret për t'iu përgjigjur një pyetjeje me të cilën jeni tashmë të 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 i mbushim fushat tona me të dhëna dhe probabilitete të rastësishme dhe së fundmi, ekzekutojmë pyetjen e njohur.
Pas kësaj, NUK e prekim fushën "e shtrenjtë", pastaj e kryqëzojmë (ose DHE) rezultatin me fushën "tarracë" dhe fushën "rezervime". Së fundmi, marrim rezultatin përfundimtar.
Shpresoj vërtet që në të ardhmen e parashikueshme, DBMS-të si MySQL dhe PostgreSQL do të përfshijnë gjithashtu këtë lloj të ri indeksi - indekse bitmap.
Përfundim
Nëse je ende zgjuar, faleminderit. Më është dashur të prek shkurtimisht shumë tema për shkak të kufizimeve kohore, por shpresoj që biseda të ketë qenë e dobishme dhe ndoshta edhe motivuese.
Indekset bitmap janë të mira për t’u ditur, edhe nëse nuk ju nevojiten tani. Konsiderojini si një mjet tjetër në kutinë tuaj të veglave.
Ne kemi trajtuar truke të ndryshme për rritjen e performancës për Go dhe disa gjëra në të cilat kompiluesi Go nuk është ende shumë i mirë. Kjo është diçka që çdo programues Go duhet ta dijë patjetër.
Kjo është e gjitha që doja të thoja. Faleminderit!
Burimi: www.habr.com
