Prezantimi
E dhashë këtë raport në anglisht në konferencën GopherCon Russia 2019 në Moskë dhe në Rusisht në një takim në Nizhny Novgorod. Ne po flasim për një indeks bitmap - më pak i zakonshëm se B-tree, por jo më pak interesant. Ndarja fjalimet në konferencë në anglisht dhe transkriptet e teksteve në rusisht.
Ne do të shikojmë se si funksionon një indeks bitmap, kur është më i mirë, kur është më i keq se indekset e tjera dhe në cilat raste është dukshëm më i shpejtë se ata; Le të shohim se cilat DBMS të njohura kanë tashmë indekse bitmap; Le të përpiqemi të shkruajmë tonat në Go. Dhe "për ëmbëlsirë" ne do të përdorim biblioteka të gatshme për të krijuar bazën tonë të të dhënave super të shpejtë të specializuar.
Unë me të vërtetë shpresoj që veprat e mia të jenë të dobishme dhe interesante për ju. Shkoni!
Paraqitje
Pershendetje te gjitheve! Është ora gjashtë e mbrëmjes dhe të gjithë jemi shumë të lodhur. Koha e shkëlqyeshme 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, unë do të kem disa rreshta kodi burimi këtu dhe atje. 🙂
Të gjitha shakatë mënjanë, raporti është plot 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;
- zbatim i thjeshtë në Go dhe pak luftë me përpiluesin;
- zbatim pak më pak i thjeshtë, por shumë më produktiv në Go assembler;
- “Problemet” e indekseve bitmap;
- implementimet ekzistuese.
Pra, çfarë janë indekset?
Indeksi është një strukturë e veçantë e të dhënave që ne e ruajmë dhe përditësojmë përveç të dhënave kryesore. Përdoret për të shpejtuar kërkimin. Pa indekse, kërkimi do të kërkonte kalimin e plotë të të dhënave (një proces i quajtur skanim i plotë), 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ë. Në mënyrë ideale, do të merrnim një logaritmike ose konstante.
Kjo është një temë jashtëzakonisht komplekse, e mbushur me hollësi dhe kompromise, por pasi kam parë dekada të zhvillimit dhe kërkimit të bazës së të dhënave, jam i gatshëm të them se ekzistojnë vetëm disa qasje të përdorura gjerësisht për krijimin e indekseve të bazës së të dhënave.
Qasja e parë është zvogëlimi hierarkik i hapësirës së kërkimit, duke e ndarë hapësirën e kërkimit në pjesë më të vogla.
Ne zakonisht e bëjmë këtë duke përdorur lloje të ndryshme pemësh. Një shembull do të ishte një kuti e madhe materialesh në dollapin tuaj që përmban kuti më të vogla materialesh të ndara në tema të ndryshme. Nëse keni nevojë për materiale, ndoshta do t'i kërkoni në një kuti që thotë "Materiale" në vend të një ku shkruhet "Cookies", apo jo?
Qasja e dytë është të zgjidhni menjëherë elementin ose grupin e elementeve të dëshiruar. Ne e bëjmë këtë në harta hash ose indekse të kundërta. Përdorimi i hartave hash është shumë i ngjashëm me shembullin e mëparshëm, por në vend të një kutie me kuti, ju keni një tufë kutish të vogla me sende përfundimtare në dollapin tuaj.
Qasja e tretë është eliminimi i nevojës për kërkim. Ne e bëjmë këtë duke përdorur filtrat Bloom ose filtrat e qyqeve. Të parët japin një përgjigje në çast, duke ju shpëtuar nga nevoja për të kërkuar.
Qasja e fundit është të përdorim plotësisht të gjithë fuqinë që na jep hardueri modern. Kjo është pikërisht ajo që ne bëjmë në indekset bitmap. Po, kur i përdorim ato, ndonjëherë duhet të kalojmë të gjithë indeksin, por ne e bëjmë atë në mënyrë super efikase.
Siç thashë, tema e indekseve të bazës së të dhënave është e gjerë dhe plot kompromise. Kjo do të thotë që ndonjëherë mund të përdorim disa qasje në të njëjtën kohë: nëse duhet të përshpejtojmë kërkimin edhe më shumë, 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 të këtyre - indekseve bitmap.
Kush jam unë që të flas për këtë temë?
Unë punoj si drejtues ekipi në Badoo (ndoshta ju jeni më të njohur me produktin tonë tjetër, Bumble). Tashmë kemi më shumë se 400 milionë përdorues në mbarë botën dhe shumë veçori që zgjedhin përputhjen më të mirë 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 emri, përdorin bitmaps ose bitset për të zbatuar një indeks kërkimi. Nga pikëpamja e syve të shpendëve, ky indeks përbëhet nga një ose më shumë bitmap të tillë që përfaqësojnë çdo entitet (siç janë njerëzit) dhe vetitë ose parametrat e tyre (mosha, ngjyra e syve, etj.), dhe një algoritëm që përdor operacionet bit (AND, OSE, JO ) për t'iu përgjigjur pyetjes së kërkimit.
Na është thënë se indekset bitmap janë më të përshtatshmet dhe shumë performuese për rastet kur ka kërkime që kombinojnë pyetje në shumë kolona me kardinalitet të ulët (mendoni "ngjyrën e syve" ose "statusin martesor" kundrejt diçkaje si "distanca nga qendra e qytetit"). Por do të tregoj më vonë se ato funksionojnë mirë edhe për kolonat me kardinalitet të lartë.
Le të shohim shembullin më të thjeshtë të një indeksi bitmap.
Imagjinoni që ne kemi një listë të restoranteve të Moskës me veti binare si këto:
- pranë metrosë;
- ka parking privat;
- ka verandë (ka tarracë);
- mund të rezervoni një tavolinë (pranon rezervime);
- i përshtatshëm për vegjetarianë (miqësorë për veganët);
- i shtrenjtë (i shtrenjtë).
Le t'i japim çdo restoranti një numër sekuence duke filluar nga 0 dhe të ndajmë memorie për 6 bitmaps (një për secilën karakteristikë). Më pas do t'i plotësojmë këto bitmap në varësi të faktit nëse restoranti e ka këtë pronë apo jo. Nëse restoranti 4 ka një verandë, atëherë biti nr. 4 në bitmap "ka verandë" do të vendoset në 1 (nëse nuk ka verandë, atëherë në 0).
Tani ne kemi indeksin më të thjeshtë të mundshëm të bitmap-it dhe mund ta përdorim atë për t'iu përgjigjur pyetjeve si:
- “Më trego restorante të përshtatshme për vegjetarianët”;
- "Më tregoni restorante të lira me një verandë ku mund të rezervoni një tavolinë."
Si? Le të hedhim një vështrim. Kërkesa e parë është shumë e thjeshtë. Gjithçka që duhet të bëjmë është të marrim bitmap-in "miqësor për vegjetarianët" dhe ta kthejmë atë në një listë restorantesh, pjesët e të cilave janë të ekspozuara.
Kërkesa e dytë është pak më e ndërlikuar. Ne duhet të përdorim bitmap NOT në bitmap "të shtrenjtë" për të marrë një listë të restoranteve të lira, më pas DHE atë me bitmap "mund të rezervoj një tryezë" dhe DHE rezultatin me bitmap "ka një verandë". Bitmap që rezulton do të përmbajë një listë të institucioneve që plotësojnë të gjitha kriteret tona. Në këtë shembull, ky është vetëm restoranti Yunost.
Ka shumë teori të përfshira, por mos u shqetësoni, ne do ta shohim kodin shumë shpejt.
Ku përdoren indekset bitmap?
Nëse ju indeksoni Google bitmap, 90% e përgjigjeve do të lidhen me Oracle DB në një mënyrë ose në një tjetër. Por DBMS-të e tjera ndoshta gjithashtu mbështesin një gjë kaq të lezetshme, apo jo? Jo ne te vertete.
Le të kalojmë nëpër listën e të dyshuarve kryesorë.
MySQL nuk mbështet ende indekset bitmap, por ka një Propozim që sugjeron shtimin e këtij opsioni ().
PostgreSQL nuk mbështet indekset bitmap, por përdor bitmap të thjeshtë dhe operacione bit për të kombinuar rezultatet e kërkimit nëpër indekse të tjera të shumta.
Tarantool ka indekse bitset dhe mbështet kërkime të thjeshta në to.
Redis ka fusha të thjeshta bit) pa aftësinë për t'i kërkuar ato.
MongoDB nuk mbështet ende indekset bitmap, por ka gjithashtu një Propozim që sugjeron që ky opsion të shtohet
Elasticsearch përdor bitmaps brenda).
- Por në shtëpinë tonë është shfaqur një fqinj i ri: Pilosa. Kjo është një bazë të dhënash e re jo-relacionale e shkruar në Go. Ai përmban vetëm indekse bitmap dhe bazon gjithçka mbi to. Ne do të flasim për të pak më vonë.
Zbatimi në Go
Por pse indekset bitmap përdoren kaq rrallë? Para se t'i përgjigjem kësaj pyetjeje, do të doja t'ju tregoja se si të zbatoni një indeks shumë të thjeshtë bitmap në Go.
Bitmaps janë në thelb vetëm pjesë të dhënash. Në Go, le të përdorim feta bajt për këtë.
Ne kemi një bitmap për një karakteristikë restoranti, dhe çdo pjesë në bitmap tregon nëse një restorant i caktuar e ka këtë pronë apo jo.
Do të na duhen dy funksione ndihmëse. Njëra do të përdoret për të mbushur bitmap-ët tanë me të dhëna të rastësishme. Të rastësishme, por me një probabilitet të caktuar që restoranti të ketë çdo pronë. Për shembull, besoj se ka shumë pak restorante në Moskë ku nuk mund të rezervosh një tryezë dhe më duket se rreth 20% e lokaleve janë të përshtatshme për vegjetarianët.
Funksioni i dytë do të konvertojë bitmap në një listë restorantesh.
Për t'iu përgjigjur pyetjes "Më trego restorante të lira që kanë një oborr spanjol dhe mund të bëjnë rezervime", na duhen veprime me dy bit: NOT dhe DHE.
Ne mund ta thjeshtojmë pak kodin tonë duke përdorur operatorin më kompleks DHE JO.
Ne kemi funksione për secilin prej këtyre operacioneve. Të dyja kalojnë nëpër feta, marrin elementët përkatës nga secila, i bashkojnë me një veprim të vogël dhe e vendosin rezultatin në fetën që rezulton.
Dhe tani ne mund të përdorim bitmaps dhe funksionet tona për t'iu përgjigjur pyetjes së kërkimit.
Performanca nuk është aq e lartë, edhe pse funksionet janë shumë të thjeshta dhe ne kemi kursyer shumë para duke mos kthyer një pjesë të re që rezulton sa herë që thirrej funksioni.
Pasi bëra pak profilizimin me pprof, vura re se përpiluesit Go i mungonte një optimizim shumë i thjeshtë por shumë i rëndësishëm: inlinimi i funksionit.
Fakti është se përpiluesi Go ka tmerrësisht frikë nga sythe që kalojnë nëpër feta dhe kategorikisht refuzon të vendosë funksione që përmbajnë sythe të tilla.
Por unë nuk kam frikë dhe mund ta mashtroj përpiluesin duke përdorur goto në vend të një loop, si në ditët e mira të vjetra.
Dhe, siç mund ta shihni, tani përpiluesi do të përfshijë me kënaqësi funksionin tonë! Si rezultat, ne arrijmë të kursejmë rreth 2 mikrosekonda. Jo keq!
Gryka e dytë e ngushtë është e lehtë për t'u parë nëse shikoni nga afër daljen e montimit. Përpiluesi shtoi një kontroll të kufirit të pjesëve pikërisht brenda ciklit tonë më të nxehtë. Fakti është se Go është një gjuhë e sigurt, përpiluesi ka frikë se tre argumentet e mia (tre feta) janë të madhësive të ndryshme. Në fund të fundit, atëherë do të ekzistojë një mundësi teorike e shfaqjes së të ashtuquajturit tejmbushje tampon.
Le ta sigurojmë përpiluesin duke i treguar se të gjitha pjesët kanë të njëjtën madhësi. Këtë mund ta bëjmë duke shtuar një kontroll të thjeshtë në fillim të funksionit tonë.
Duke parë këtë, përpiluesi e kalon me kënaqësi kontrollin dhe ne përfundojmë duke kursyer 500 nanosekonda të tjera.
Butat e mëdha
Mirë, ne arritëm të shtrydhnim disa performancë nga zbatimi ynë i thjeshtë, por ky rezultat është në fakt shumë më i keq se sa është e mundur me harduerin aktual.
Gjithçka që bëjmë janë operacionet bazë të biteve dhe procesorët tanë i kryejnë ato me shumë efikasitet. Por, për fat të keq, ne "ushqejmë" procesorin tonë me pjesë shumë të vogla të punës. Funksionet tona kryejnë operacione në bazë bajt pas bajt. Ne mund ta shkulim shumë lehtë kodin tonë për të punuar me copa 8-byte duke përdorur feta UInt64.
Siç mund ta shihni, ky ndryshim i vogël e shpejtoi programin tonë tetë herë duke rritur madhësinë e grupit me tetë herë. Fitimi mund të thuhet se është linear.
Zbatimi në asembler
Por ky nuk është fundi. Procesorët tanë mund të punojnë me copa prej 16, 32 dhe madje 64 bajt. Operacione të tilla "të gjera" quhen të dhëna të shumëfishta me një instruksion të vetëm (SIMD; një instruksion, shumë të dhëna), dhe procesi i transformimit të kodit në mënyrë që të përdorë operacione të tilla quhet vektorizim.
Fatkeqësisht, përpiluesi Go nuk është i shkëlqyer në vektorizim. Aktualisht, mënyra e vetme për të vektorizuar kodin Go është t'i merrni dhe t'i vendosni këto operacione manualisht duke përdorur Go assembler.
Go assembler është një kafshë e çuditshme. Ju ndoshta e dini se gjuha e asamblesë është diçka që është shumë e lidhur me arkitekturën e kompjuterit për të cilin po shkruani, por ky nuk është rasti në Go. Go assembler është më shumë si një IRL (gjuhë e ndërmjetme e përfaqësimit) ose gjuhë e ndërmjetme: është praktikisht e pavarur nga platforma. Rob Pike dha një paraqitje të shkëlqyer mbi këtë temë disa vite më parë në GopherCon në Denver.
Për më tepër, Go përdor një format të pazakontë Plan 9, i cili ndryshon nga formatet e pranuara përgjithësisht AT&T dhe Intel.
Është e sigurt të thuhet se shkrimi i Go assembler me dorë nuk është gjëja më argëtuese.
Por, për fat të mirë, ekzistojnë tashmë dy mjete të nivelit të lartë që na ndihmojnë të shkruajmë Go assembler: PeachPy dhe avo. Të dy shërbimet gjenerojnë assembler Go nga kodi i nivelit më të lartë të shkruar në Python dhe Go, përkatësisht.
Këto shërbime thjeshtojnë gjëra të tilla si shpërndarja e regjistrave, unazat e shkrimit dhe në përgjithësi thjeshtojnë procesin e hyrjes në botën e programimit të montimit në Go.
Ne do të përdorim avo, kështu që programet tona do të jenë pothuajse programe të rregullta Go.
Kështu duket shembulli më i thjeshtë i një programi avo. Kemi një funksion main(), i cili përcakton brenda vetes funksionin Add(), kuptimi i të cilit është mbledhja e dy numrave. Këtu ka funksione ndihmëse për të marrë parametrat me emër dhe për të marrë një nga regjistrat falas dhe të përshtatshëm të procesorit. Çdo operacion procesori ka një funksion përkatës në avo, siç shihet në ADDQ. Më në fund, ne shohim një funksion ndihmës për ruajtjen e vlerës që rezulton.
Duke thirrur gogene, 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 titujt e funksionit për të lidhur dy botët: Go dhe assembler.
Tani që kemi parë se çfarë bën avo dhe si, le të shohim funksionet tona. Kam zbatuar versionet skalar dhe vektoriale (SIMD) të funksioneve.
Le të shohim së pari versionet skalare.
Ashtu si në shembullin e mëparshëm, ne po kërkojmë një regjistër të përgjithshëm falas dhe të vlefshëm, nuk kemi nevojë të llogarisim kompensimet dhe madhësitë për argumentet. Avo i bën të gjitha këto për ne.
Dikur përdornim etiketa dhe goto (ose kërcime) për të përmirësuar performancën dhe për të mashtruar përpiluesin Go, por tani po e bëjmë që nga fillimi. Çështja është se ciklet janë një koncept i nivelit më të lartë. Në assembler, ne kemi vetëm etiketa dhe kërcime.
Kodi i mbetur duhet të jetë tashmë i njohur dhe i kuptueshëm. Ne emulojmë një lak me etiketa dhe kërcime, marrim një pjesë të vogël të të dhënave nga dy fetat tona, i kombinojmë ato me një veprim bit (DHE JO në këtë rast) dhe më pas vendosim rezultatin në fetën që rezulton. Të gjitha.
Kështu duket kodi përfundimtar i asamblerit. Nuk na duhej të llogaritnim kompensimet dhe madhësitë (të theksuara me të gjelbër) ose të mbanin gjurmët e regjistrave të përdorur (të theksuara me të kuqe).
Nëse krahasojmë performancën e zbatimit të gjuhës së asamblesë me performancën e implementimit më të mirë në Go, do të shohim se është e njëjtë. Dhe kjo është e pritshme. Në fund të fundit, ne nuk bëmë asgjë të veçantë - ne thjesht riprodhuam atë që do të bënte një përpilues Go.
Fatkeqësisht, ne nuk mund ta detyrojmë përpiluesin të vendosë funksionet tona të shkruara në gjuhën e asamblesë. Përpiluesi Go aktualisht nuk ka një veçori të tillë, megjithëse ka pasur një kërkesë për ta shtuar për mjaft kohë.
Kjo është arsyeja pse është e pamundur të përfitohet nga funksionet e vogla në gjuhën e asamblesë. Duhet ose të shkruajmë funksione të mëdha, ose të përdorim paketën e re matematikore/bit, ose të anashkalojmë gjuhën e asemblerit.
Le të shohim tani versionet vektoriale të funksioneve tona.
Për këtë shembull, vendosa të përdor AVX2, kështu që ne do të përdorim operacione që funksionojnë në copa 32 byte. Struktura e kodit është shumë e ngjashme me versionin skalar: ngarkimi i parametrave, kërkimi i një regjistri të përbashkët falas, etj.
Një risi është se operacionet më të gjera vektoriale përdorin regjistra specialë të gjerë. Në rastin e copave 32-byte, këto janë regjistra të prefiksuar me Y. Kjo është arsyeja pse ju shihni funksionin YMM() në kod. Nëse do të përdorja AVX-512 me copa 64-bit, prefiksi do të ishte Z.
Inovacioni i dytë është se vendosa të përdor një optimizim të quajtur unrolling, që do të thotë të bësh tetë operacione të ciklit manualisht përpara se të hidhesh në fillim të ciklit. Ky optimizim redukton numrin e degëve në kod dhe kufizohet nga numri i regjistrave falas në dispozicion.
Epo, po në lidhje me performancën? Ajo eshte e bukur! Ne arritëm një shpejtësi prej rreth shtatë herë në krahasim me zgjidhjen më të mirë Go. Impresionuese, apo jo?
Por edhe ky implementim potencialisht mund të përshpejtohet duke përdorur AVX-512, marrjen paraprake ose një JIT (përpilues vetëm në kohë) për planifikuesin e pyetjeve. Por kjo është sigurisht një temë për një raport të veçantë.
Probleme me indekset bitmap
Tani që kemi parë tashmë një zbatim të thjeshtë të një indeksi bitmap në Go dhe një shumë më produktiv në gjuhën e asamblesë, le të flasim më në fund përse indekset bitmap përdoren kaq rrallë.
Gazetat e vjetra përmendin tre probleme me indekset bitmap, por letrat më të reja dhe unë argumentoj se ato nuk janë më relevante. Ne nuk do të zhytemi thellë në secilën prej këtyre problemeve, por do t'i shikojmë ato sipërfaqësisht.
Problemi i kardinalitetit të lartë
Pra, na thuhet se indekset bitmap janë të përshtatshme vetëm për fusha me kardinalitet të ulët, domethënë ato që kanë pak vlera (për shembull, 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ë rastin e kardinalitetit të lartë, do të zërë shumë hapësirë dhe, për më tepër, këto indekse bitmap do të mbushen dobët (rrallë).
Ndonjëherë ne mund të përdorim një paraqitje të ndryshme, siç është ai standard që përdorim për të paraqitur numrat. Por ishte ardhja e algoritmeve të kompresimit që ndryshoi gjithçka. Gjatë dekadave të fundit, shkencëtarët dhe studiuesit kanë dalë me një numër të madh algoritmesh kompresimi për bitmaps. Avantazhi i tyre kryesor është se nuk ka nevojë të dekompresohen bitmaps për të kryer operacione bit - ne mund të kryejmë operacione bit direkt në bitmaps të ngjeshur.
Kohët e fundit, qasjet hibride kanë filluar të shfaqen, të tilla si bitmaps zhurmues. Ata përdorin njëkohësisht tre paraqitje të ndryshme për bitmap - vetë bitmap, vargje dhe të ashtuquajturat bit runs - dhe balancojnë mes tyre për të maksimizuar performancën dhe për të minimizuar konsumin e kujtesës.
Ju mund të gjeni bitmap zhurmues në aplikacionet më të njohura. Tashmë ka një numër të madh zbatimesh për një shumëllojshmëri të gjerë të gjuhëve programuese, duke përfshirë më shumë se tre zbatime për Go.
Një qasje tjetër që mund të na ndihmojë të përballemi me kardinalitetin e lartë quhet binning. Imagjinoni që keni një fushë që përfaqëson lartësinë e një personi. Lartësia është një numër me pikë lundruese, por ne njerëzit nuk e mendojmë kështu. Për ne nuk ka dallim mes lartësisë 185,2 cm dhe 185,3 cm.
Rezulton se ne mund të grupojmë vlera të ngjashme në grupe brenda 1 cm.
Dhe nëse 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 kthejmë një fushë me kardinalitet të pafund në një fushë me një kardinalitet prej rreth 200 vlerash.
Sigurisht, nëse është e nevojshme, mund të bëjmë filtrim shtesë më pas.
Problem me gjerësinë e lartë të brezit
Problemi tjetër me indekset bitmap është se përditësimi i tyre mund të jetë shumë i shtrenjtë.
Bazat e të dhënave duhet të jenë në gjendje të përditësojnë të dhënat ndërsa qindra pyetje të tjera potencialisht po kërkojnë të dhënat. Ne kemi nevojë për kyçje për të shmangur problemet me aksesin e njëkohshëm të të dhënave ose probleme të tjera të ndarjes. Dhe aty ku ka një bravë të madhe, ka një problem - grindje bllokimi, kur ky bllokim bëhet një pengesë.
Ky problem mund të zgjidhet ose anashkalohet duke përdorur ndarjen ose duke përdorur indekse të versionuara.
Thyerja është një gjë e thjeshtë dhe e njohur. Ju mund të copëtoni një indeks bitmap si çdo të dhënë tjetër. Në vend të një bllokimi të madh, do të merrni një tufë brava të vogla dhe kështu do të shpëtoni nga grindja e bllokimit.
Mënyra e dytë për të zgjidhur problemin është përdorimi i indekseve të versionuara. Ju mund të keni një kopje të indeksit që përdorni për të kërkuar ose lexuar, dhe një që përdorni për të shkruar ose përditësuar. Dhe një herë në një periudhë të caktuar kohe (për shembull, një herë në 100 ms ose 500 ms) ju i dublikoni ato dhe i ndërroni ato. Sigurisht, kjo qasje është e zbatueshme vetëm në rastet kur aplikacioni juaj mund të trajtojë një indeks kërkimi pak 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 të pyetjeve, siç janë pyetjet e hapësirës.
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 a la "Më trego hotele me tarifa dhomash nga 200 deri në 300 dollarë për natë."
Një zgjidhje naive dhe shumë e pamatur do të ishte marrja e rezultateve për çdo vlerë dollari dhe kombinimi i tyre me një operacion OR.
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ë me 50 herë.
Por problemi gjithashtu zgjidhet lehtësisht duke përdorur një pamje të krijuar posaçërisht për këtë lloj kërkese. Në punimet shkencore quhet bitmaps i koduar me rreze.
Në këtë paraqitje, ne nuk vendosim vetëm një bit për ndonjë vlerë (për shembull, 200), por vendosim këtë vlerë dhe gjithçka më të lartë. 200 e lart. E njëjta gjë për 300: 300 dhe më lart. Dhe kështu me radhë.
Duke përdorur këtë paraqitje, ne mund t'i përgjigjemi këtij lloji të pyetjes së kërkimit duke përshkuar indeksin vetëm dy herë. Së pari, do të marrim një listë të hoteleve ku dhoma kushton më pak ose 300 dollarë dhe më pas do të heqim prej saj ato ku kostoja e dhomës është më pak ose 199 dollarë. Gati.
Do të habiteni, por edhe gjeoqueries janë të mundshme duke përdorur indekset bitmap. Truku është të përdorni një paraqitje gjeometrike që rrethon koordinatat tuaja me një figurë gjeometrike. Për shembull, S2 nga Google. Figura duhet të jetë e mundur të përfaqësohet në formën e tre ose më shumë vijave të kryqëzuara që mund të numërohen. Në këtë mënyrë ne mund ta kthejmë gjeokerin tonë në disa pyetje "përgjatë hendekut" (përgjatë këtyre vijave të numëruara).
Zgjidhje të gatshme
Shpresoj se ju kam interesuar pak dhe tani keni një mjet tjetër të dobishëm në arsenalin tuaj. Nëse ndonjëherë ju duhet të bëni diçka të tillë, do të dini se në cilën anë të shikoni.
Sidoqoftë, jo të gjithë kanë kohë, durim ose burime për të krijuar indekse bitmap nga e para. Sidomos ato më të avancuara, duke përdorur SIMD, për shembull.
Për fat të mirë, ka disa zgjidhje të gatshme për t'ju ndihmuar.
Bitmap zhurmues
Së pari, ekziston e njëjta bibliotekë e zhurmshme bitmaps për të cilën kam folur tashmë. Ai përmban të gjithë kontejnerët e nevojshëm dhe operacionet e biteve që do t'ju nevojiten për të krijuar një indeks të plotë bitmap.
Për fat të keq, për momentin, asnjë nga implementimet Go nuk përdor SIMD, që do të thotë se implementimet Go janë më pak performuese sesa implementimet C, për shembull.
Pilosa
Një tjetër produkt që mund t'ju ndihmojë është Pilosa DBMS, i cili, në fakt, ka vetëm indekse bitmap. Kjo është një zgjidhje relativisht e re, por po fiton zemrat me shpejtësi të madhe.
Pilosa përdor bitmaps zhurmues nga brenda dhe ju jep mundësinë për t'i përdorur ato, thjeshton dhe shpjegon të gjitha gjërat për të cilat fola më lart: grupimi, bitmap-të e koduara nga diapazoni, koncepti i një fushe, etj.
Le të hedhim një vështrim të shpejtë në një shembull të përdorimit të Pilosa për t'iu përgjigjur një pyetjeje me të cilën jeni njohur tashmë.
Shembulli është shumë i ngjashëm me atë që keni parë më parë. Ne krijojmë një klient në serverin Pilosa, krijojmë një indeks dhe fushat e nevojshme, më pas mbushim fushat tona me të dhëna të rastësishme me probabilitete dhe, në fund, ekzekutojmë pyetjen e njohur.
Pas kësaj, ne përdorim NOT në fushën "e shtrenjtë", pastaj kryqëzojmë rezultatin (ose DHE atë) me fushën "tarrace" dhe me fushën "rezervime". Dhe së fundi, marrim rezultatin përfundimtar.
Unë me të vërtetë shpresoj që në të ardhmen e parashikueshme ky lloj i ri indeksi do të shfaqet edhe në DBMS si MySQL dhe PostgreSQL - indekset bitmap.
Përfundim
Nëse nuk ju ka zënë gjumi ende, faleminderit. Më është dashur të prek shkurtimisht shumë tema për shkak të kohës së kufizuar, por shpresoj se biseda ishte e dobishme dhe ndoshta edhe motivuese.
Indekset e Bitmap-it janë të mira për t'u ditur, edhe nëse nuk keni nevojë për to tani. Lërini të jenë një mjet tjetër në kutinë tuaj të veglave.
Ne kemi parë truket e ndryshme të performancës për Go dhe gjëra që përpiluesi Go nuk i trajton ende shumë mirë. Por kjo është absolutisht e dobishme për çdo programues Go të dijë.
Kjo është gjithçka që doja t'ju thoja. Faleminderit!
Burimi: www.habr.com