introduzzjoni
Dan ir-rapport tajt bl-Ingliż fil-konferenza GopherCon Russia 2019 f'Moska u bir-Russu f'laqgħa f'Nizhny Novgorod. Qed nitkellmu dwar indiċi bitmap - inqas komuni minn siġra B, iżda mhux inqas interessanti. Qsim diskorsi fil-konferenza bl-Ingliż u traskrizzjonijiet tat-test bir-Russu.
Se nħarsu lejn kif jaħdem indiċi bitmap, meta jkun aħjar, meta jkun agħar minn indiċi oħra, u f'liema każijiet huwa ferm aktar mgħaġġel minnhom; Ejja naraw liema DBMSs popolari diġà għandhom indiċi bitmap; Ejja nippruvaw niktbu tagħna f'Go. U "għad-deżerta" se nużaw libreriji lesti biex noħolqu database speċjalizzat super-veloċi tagħna stess.
Verament nittama li x-xogħlijiet tiegħi jkunu utli u interessanti għalik. Mur!
Introduzzjoni
Hi kollha! Is-sitta ta’ filgħaxija u aħna lkoll għajjenin ħafna. Żmien tajjeb biex nitkellmu dwar it-teorija tal-indiċi tad-database boring, hux? Tinkwetax, ser ikolli ftit linji ta 'kodiċi sors hawn u hemm. 🙂
Ċajt kollu apparti, ir-rapport huwa mimli informazzjoni, u ma tantx għandna ħin. Mela ejja nibdew.
Illum se nitkellem dwar dan li ġej:
- x'inhuma l-indiċi;
- x'inhu indiċi bitmap;
- fejn jintuża u fejn MHUX jintuża u għaliex;
- implimentazzjoni sempliċi f'Go u ftit ġlieda mal-kompilatur;
- implimentazzjoni kemmxejn inqas sempliċi, iżda ħafna aktar produttiva f'Go assembler;
- "problemi" ta' indiċi bitmap;
- implimentazzjonijiet eżistenti.
Allura x'inhuma l-indiċi?
L-indiċi huwa struttura tad-dejta separata li aħna nżommu u naġġornaw flimkien mad-dejta ewlenija. Jintuża biex iħaffef it-tfittxija. Mingħajr indiċi, it-tiftix ikun jeħtieġ li tgħaddi mid-dejta kompletament (proċess imsejjaħ skan sħiħ), u dan il-proċess għandu kumplessità algoritmika lineari. Iżda d-databases normalment ikun fihom ammonti kbar ta 'dejta u l-kumplessità lineari hija bil-mod wisq. Idealment, inġibu waħda logaritmika jew kostanti.
Dan huwa suġġett kumpless ħafna, mimli b'irqaqat u kompromessi, iżda wara li nħares lejn għexieren ta 'snin ta' żvilupp u riċerka ta 'databases, jien lest ngħid li hemm biss ftit approċċi użati ħafna biex jinħolqu indiċi ta' database.
L-ewwel approċċ huwa li jitnaqqas b'mod ġerarkiku l-ispazju tat-tiftix, billi l-ispazju tat-tfittxija jiġi maqsum f'partijiet iżgħar.
Normalment nagħmlu dan billi nużaw tipi differenti ta’ siġar. Eżempju jkun kaxxa kbira ta 'materjali fil-closet tiegħek li fiha kaxxi iżgħar ta' materjali maqsuma f'suġġetti differenti. Jekk għandek bżonn materjali, inti probabilment tfittexhom f'kaxxa li tgħid "Materjali" aktar milli waħda li tgħid "Cookies," hux?
It-tieni approċċ huwa li tagħżel immedjatament l-element jew il-grupp ta 'elementi mixtieq. Nagħmlu dan f'mapep hash jew indiċi inversa. L-użu ta 'mapep tal-hash huwa simili ħafna għall-eżempju preċedenti, iżda minflok kaxxa ta' kaxxi, għandek mazz ta 'kaxxi żgħar ta' oġġetti finali fil-closet tiegħek.
It-tielet approċċ huwa li tiġi eliminata l-ħtieġa għat-tiftix. Nagħmlu dan bl-użu ta 'filtri Bloom jew filtri cuckoo. L-ewwel dawk jagħtu tweġiba istantanjament, u jiffrankaw milli jkollok tfittex.
L-aħħar approċċ huwa li nagħmlu użu sħiħ mill-qawwa kollha li jagħtina l-ħardwer modern. Dan huwa eżattament dak li nagħmlu fl-indiċi bitmap. Iva, meta nużawhom kultant jeħtieġ li ngħaddu mill-indiċi kollu, iżda nagħmluh b'mod super effiċjenti.
Kif għedt, is-suġġett tal-indiċi tad-database huwa vast u mimli kompromessi. Dan ifisser li kultant nistgħu nużaw diversi approċċi fl-istess ħin: jekk irridu nħaffu t-tfittxija saħansitra aktar, jew jekk ikollna nkopru t-tipi kollha ta’ tfittxija possibbli.
Illum se nitkellem dwar l-approċċ l-inqas magħruf minn dawn - indiċi bitmap.
Min jien biex nitkellem fuq dan is-suġġett?
Jien naħdem bħala mexxej ta' tim f'Badoo (forsi int aktar familjari mal-prodott l-ieħor tagħna, Bumble). Diġà għandna aktar minn 400 miljun utent madwar id-dinja u ħafna karatteristiċi li jagħżlu l-aħjar taqbila għalihom. Dan nagħmluh billi nużaw servizzi tad-dwana, inklużi indiċi tal-bitmap.
Allura x'inhu indiċi bitmap?
L-indiċi tal-bitmap, kif jissuġġerixxi l-isem, jużaw bitmaps jew bitsets biex jimplimentaw indiċi tat-tiftix. Mill-ħarsa tal-għasafar, dan l-indiċi jikkonsisti minn bitmap waħda jew aktar bħal dawn li jirrappreżentaw kwalunkwe entità (bħal nies) u l-proprjetajiet jew parametri tagħhom (età, kulur tal-għajnejn, eċċ.), u algoritmu li juża operazzjonijiet bit (U, JEW, MHUX). ) biex twieġeb il-mistoqsija tat-tfittxija.
Qalulna li l-indiċi tal-bitmap huma l-aktar adattati u effikaċi ħafna għal każijiet fejn hemm tfittxijiet li jgħaqqdu mistoqsijiet f'ħafna kolonni ta' kardinalità baxxa (aħseb "il-kulur tal-għajnejn" jew "l-istat ċivili" kontra xi ħaġa bħal "distanza miċ-ċentru tal-belt"). Imma jien ser nuri aktar tard li jaħdmu tajjeb ukoll għal kolonni ta 'kardinalità għolja.
Ejja nħarsu lejn l-aktar eżempju sempliċi ta 'indiċi bitmap.
Immaġina li għandna lista ta 'ristoranti ta' Moska bi proprjetajiet binarji bħal dawn:
- ħdejn il-metro;
- hemm parkeġġ privat;
- hemm veranda (għandha terrazzin);
- tista' tirriserva tabella (jaċċetta riżervi);
- addattat għal veġetarjani (adattat għall-vegan);
- għali (għali).
Ejja nagħtu lil kull ristorant numru ta' sekwenza li jibda minn 0 u talloka memorja għal 6 bitmaps (wieħed għal kull karatteristika). Imbagħad se nimlew dawn il-bitmaps skont jekk ir-ristorant għandux din il-proprjetà jew le. Jekk ir-restorant 4 għandu veranda, allura l-bit Nru 4 fil-bitmap "għandu veranda" se jkun issettjat għal 1 (jekk ma jkunx hemm veranda, allura għal 0).
Issa għandna l-aktar indiċi bitmap sempliċi possibbli, u nistgħu nużawh biex inwieġbu mistoqsijiet bħal:
- "Urini ristoranti veġetarjani-friendly";
- "Urini ristoranti rħas b'veranda fejn tista' tirriserva mejda."
Kif? Ejja nagħtu ħarsa. L-ewwel talba hija sempliċi ħafna. Kulma rridu nagħmlu hu li nieħdu l-bitmap "favur għall-vegetarian" u nibdluh f'lista ta 'ristoranti li l-bits tagħhom huma esposti.
It-tieni talba hija ftit aktar ikkumplikata. Irridu nużaw il-bitmap NOT fuq il-bitmap "għali" biex niksbu lista ta 'ristoranti rħas, imbagħad U bil-bitmap "nista' nibbukkja tabella" u U r-riżultat bil-bitmap "hemm veranda". Il-bitmap li tirriżulta jkun fiha lista ta’ stabbilimenti li jissodisfaw il-kriterji kollha tagħna. F'dan l-eżempju, dan huwa biss ir-ristorant Yunost.
Hemm ħafna teorija involuta, imma tinkwetax, naraw il-kodiċi dalwaqt.
Fejn jintużaw l-indiċi tal-bitmap?
Jekk inti Google bitmap indiċi, 90% tat-tweġibiet se jkunu relatati ma 'Oracle DB b'xi mod jew ieħor. Iżda DBMSs oħra probabbilment jappoġġjaw ukoll ħaġa bħal din friska, hux? Mhux ezatt.
Ejja ngħaddu mil-lista tas-suspettati ewlenin.
MySQL għadu ma jappoġġjax indiċi bitmap, iżda hemm Proposta li tissuġġerixxi li żżid din l-għażla ().
PostgreSQL ma jappoġġjax indiċi tal-bitmap, iżda juża bitmaps sempliċi u operazzjonijiet tal-bit biex jgħaqqad ir-riżultati tat-tfittxija fuq indiċijiet oħra multipli.
Tarantool għandu indiċi bitset u jappoġġja tfittxijiet sempliċi fuqhom.
Redis għandu bitfields sempliċi) mingħajr il-ħila li jfittxuhom.
MongoDB għadu ma jappoġġjax indiċi bitmap, iżda hemm ukoll Proposta li tissuġġerixxi li din l-għażla tiżdied
Elasticsearch juża bitmaps internament).
- Imma deher ġar ġdid fid-dar tagħna: Pilosa. Din hija database mhux relazzjonali ġdida miktuba f'Go. Fiha biss indiċi bitmap u tibbaża kollox fuqhom. Nitkellmu dwarha ftit aktar tard.
Implimentazzjoni f'Go
Imma għaliex l-indiċi tal-bitmap jintużaw daqshekk rari? Qabel ma nwieġeb din il-mistoqsija, nixtieq nurik kif timplimenta indiċi bitmap sempliċi ħafna f'Go.
Il-bitmaps huma essenzjalment biss biċċiet ta 'dejta. F'Go, ejja nużaw slices byte għal dan.
Għandna bitmap waħda għal karatteristika waħda tar-restorant, u kull bit fil-bitmap tindika jekk ristorant partikolari għandux din il-proprjetà jew le.
Ikollna bżonn żewġ funzjonijiet helper. Wieħed se jintuża biex jimla l-bitmaps tagħna b'dejta każwali. Bl-addoċċ, iżda b'ċerta probabbiltà li r-ristorant għandu kull proprjetà. Pereżempju, nemmen li hemm ftit ristoranti f'Moska fejn ma tistax tirriserva mejda, u jidhirli li madwar 20% tal-istabbilimenti huma adattati għall-veġetarjani.
It-tieni funzjoni se tikkonverti l-bitmap f'lista ta 'ristoranti.
Biex inwieġbu l-mistoqsija "Urini ristoranti rħas li għandhom patio u jistgħu jagħmlu riżervi," għandna bżonn żewġ operazzjonijiet bit: MHUX u U.
Nistgħu nissimplifikaw il-kodiċi tagħna ftit billi nużaw l-operatur U MHUX aktar kumpless.
Għandna funzjonijiet għal kull waħda minn dawn l-operazzjonijiet. It-tnejn li huma jgħaddu mill-flieli, ħu l-elementi korrispondenti minn kull wieħed, għaqqadhom b'operazzjoni daqsxejn u poġġi r-riżultat fil-porzjon li jirriżulta.
U issa nistgħu nużaw il-bitmaps u l-funzjonijiet tagħna biex inwieġbu l-mistoqsija tat-tfittxija.
Il-prestazzjoni mhix daqshekk għolja, minkejja li l-funzjonijiet huma sempliċi ħafna u ffrankajna ħafna flus billi ma rritornawx slice ġdida li tirriżulta kull darba li tissejjaħ il-funzjoni.
Wara li għamilt daqsxejn ta 'profiling ma' pprof, ndunajt li l-kompilatur Go kien nieqes ottimizzazzjoni waħda sempliċi ħafna iżda importanti ħafna: inlining tal-funzjoni.
Il-fatt hu li l-kompilatur Go jibża' ħafna minn loops li jgħaddu minn slices, u jirrifjuta kategorikament li funzjonijiet inline li fihom tali loops.
Imma ma nibżax u nista' nqarraq bil-kompilatur billi nuża goto minflok loop, bħal fl-antik.
U, kif tistgħu taraw, issa l-kompilatur se heureusement inline l-funzjoni tagħna! Bħala riżultat, irnexxielna niffrankaw madwar 2 mikrosekondi. Mhux ħażin!
It-tieni konġestjoni hija faċli biex tara jekk tħares mill-qrib lejn il-produzzjoni tal-assemblaġġ. Il-kompilatur żied verifika tal-konfini tal-porzjon dritt ġewwa l-iktar linja sħuna tagħna. Il-fatt hu li Go hija lingwa sigura, il-kompilatur jibża’ li t-tliet argumenti tiegħi (tliet slices) huma ta’ daqsijiet differenti. Wara kollox, allura jkun hemm possibbiltà teoretika tal-okkorrenza ta 'l-hekk imsejjaħ buffer overflow.
Ejja nassiguraw lill-kompilatur billi nuru li l-flieli kollha huma l-istess daqs. Nistgħu nagħmlu dan billi nżidu kontroll sempliċi fil-bidu tal-funzjoni tagħna.
Meta jara dan, il-kompilatur kuntenti jaqbeż il-kontroll, u nispiċċaw niffrankaw 500 nanosekondi oħra.
Biċċiet kbar
Tajjeb, irnexxielna nagħfas xi prestazzjoni mill-implimentazzjoni sempliċi tagħna, iżda dan ir-riżultat huwa fil-fatt ħafna agħar milli hu possibbli bil-ħardwer attwali.
Kulma nagħmlu huma operazzjonijiet bażiċi tal-bit, u l-proċessuri tagħna jwettquhom b'mod effiċjenti ħafna. Iżda, sfortunatament, aħna "nitimgħu" lill-proċessur tagħna b'biċċiet ta 'xogħol żgħar ħafna. Il-funzjonijiet tagħna jwettqu operazzjonijiet fuq bażi ta’ byte b’byte. Nistgħu faċilment intejbu l-kodiċi tagħna biex naħdmu ma 'biċċiet ta' 8 byte bl-użu ta 'slices UInt64.
Kif tistgħu taraw, din il-bidla żgħira għaġġlet il-programm tagħna tmien darbiet billi żiedet id-daqs tal-lott bi tmien darbiet. Il-qligħ jista 'jingħad li huwa lineari.
Implimentazzjoni fl-assembler
Imma dan mhux it-tmiem. Il-proċessuri tagħna jistgħu jaħdmu b'biċċiet ta' 16, 32 u anke 64 bytes. Operazzjonijiet "wesgħin" bħal dawn jissejħu data multipli ta 'struzzjoni waħda (SIMD; istruzzjoni waħda, ħafna data), u l-proċess tat-trasformazzjoni tal-kodiċi sabiex juża tali operazzjonijiet jissejjaħ vettorizzazzjoni.
Sfortunatament, il-kompilatur Go huwa 'l bogħod milli eċċellenti fil-vettorizzazzjoni. Bħalissa, l-uniku mod biex tiġi vettorizzata l-kodiċi Go huwa li tieħu u tpoġġi dawn l-operazzjonijiet manwalment billi tuża Go assembler.
Go assembler huwa kruha stramba. Probabilment taf li l-lingwa tal-assemblaġġ hija xi ħaġa li hija marbuta ħafna mal-arkitettura tal-kompjuter li qed tikteb għalih, iżda dan mhux il-każ f'Go. Go assembler huwa aktar bħal IRL (lingwa ta 'rappreżentazzjoni intermedja) jew lingwa intermedja: huwa prattikament indipendenti mill-pjattaforma. Rob Pike ta prestazzjoni eċċellenti dwar dan is-suġġett bosta snin ilu fil-GopherCon f'Denver.
Barra minn hekk, Go juża format Pjan 9 mhux tas-soltu, li huwa differenti mill-formati ġeneralment aċċettati ta 'AT&T u Intel.
Tajjeb ngħidu li l-kitba ta’ Go assembler bl-idejn mhix l-aktar pjaċevoli.
Iżda, fortunatament, diġà hemm żewġ għodod ta 'livell għoli li jgħinuna niktbu Go assembler: PeachPy u avo. Iż-żewġ utilitajiet jiġġeneraw Go assembler minn kodiċi ta 'livell ogħla miktub f'Python u Go, rispettivament.
Dawn l-utilitajiet jissimplifikaw affarijiet bħall-allokazzjoni tar-reġistru, il-loops tal-kitba, u ġeneralment jissimplifikaw il-proċess biex tidħol fid-dinja tal-ipprogrammar tal-assemblaġġ f'Go.
Aħna ser nużaw avo, għalhekk il-programmi tagħna jkunu kważi regolari Go programmi.
Dan huwa kif jidher l-aktar eżempju sempliċi ta 'programm avo. Għandna funzjoni main(), li tiddefinixxi fiha nfisha l-funzjoni Żid(), li t-tifsira tagħha hija li żżid żewġ numri. Hemm funzjonijiet helper hawn biex tikseb parametri bl-isem u tikseb wieħed mir-reġistri tal-proċessuri ħielsa u adattati. Kull operazzjoni tal-proċessur għandha funzjoni korrispondenti fuq avo, kif jidher fl-ADDQ. Fl-aħħarnett, naraw funzjoni helper għall-ħażna tal-valur li jirriżulta.
Billi nsejħu go genera, aħna se nwettqu l-programm fuq avo u bħala riżultat, se jiġu ġġenerati żewġ fajls:
- add.s bil-kodiċi li jirriżulta f'Go assembler;
- stub.go b'headers tal-funzjoni biex jgħaqqdu ż-żewġ dinjiet: Mur u assembler.
Issa li rajna x'jagħmel avo u kif, ejja nħarsu lejn il-funzjonijiet tagħna. I implimentajt verżjonijiet kemm skalari kif ukoll vettorjali (SIMD) tal-funzjonijiet.
Ejja nħarsu lejn il-verżjonijiet skalari l-ewwel.
Bħal fl-eżempju preċedenti, qed nitolbu għal reġistru ta 'skop ġenerali b'xejn u validu, m'għandniex bżonn nikkalkulaw l-offsets u d-daqsijiet għall-argumenti. avo jaghmel dan kollu ghalina.
Konna nużaw it-tikketti u goto (jew jumps) biex intejbu l-prestazzjoni u nqarrqu lill-kompilatur Go, iżda issa qed nagħmluh mill-bidu. Il-punt huwa li ċ-ċikli huma kunċett ta 'livell ogħla. Fl-assembler, għandna biss tikketti u jumps.
Il-kodiċi li jifdal għandu jkun diġà familjari u jinftiehem. Aħna nimitaw linja b'tikketti u qbiż, nieħdu biċċa żgħira ta 'dejta miż-żewġ slices tagħna, għaqqadhom b'operazzjoni daqsxejn (U MHUX f'dan il-każ) u mbagħad poġġi r-riżultat fil-porzjon li jirriżulta. Kollha.
Dan huwa kif jidher il-kodiċi finali tal-assemblatur. Ma kellniex għalfejn nikkalkulaw l-offsets u d-daqsijiet (enfasizzati bl-aħdar) jew inżommu kont tar-reġistri użati (enfasizzati bl-aħmar).
Jekk inqabblu l-prestazzjoni tal-implimentazzjoni tal-lingwa tal-assemblaġġ mal-prestazzjoni tal-aħjar implimentazzjoni f'Go, naraw li hija l-istess. U dan huwa mistenni. Wara kollox, aħna ma għamilna xejn speċjali - aħna biss irriproduċu dak li kompilatur Go jagħmel.
Sfortunatament, ma nistgħux inġegħlu lill-kompilatur biex inline l-funzjonijiet tagħna miktuba fil-lingwa tal-assemblaġġ. Il-kompilatur Go bħalissa m'għandux karatteristika bħal din, għalkemm kien hemm talba biex tiżdied għal żmien mhux ħażin.
Huwa għalhekk li huwa impossibbli li tikseb xi benefiċċju minn funzjonijiet żgħar fil-lingwa tal-assemblaġġ. Għandna bżonn jew niktbu funzjonijiet kbar, jew nużaw il-pakkett il-ġdid tal-matematika/bits, jew naqbdu l-lingwa tal-assemblatur.
Ejja issa nħarsu lejn il-verżjonijiet vector tal-funzjonijiet tagħna.
Għal dan l-eżempju, iddeċidejt li nuża AVX2, għalhekk se nużaw operazzjonijiet li joperaw fuq biċċiet ta '32 byte. L-istruttura tal-kodiċi hija simili ħafna għall-verżjoni skalari: tagħbija ta 'parametri, titlob għal reġistru kondiviż b'xejn, eċċ.
Innovazzjoni waħda hija li l-operazzjonijiet tal-vector usa' jużaw reġistri wiesgħa speċjali. Fil-każ ta 'biċċiet ta' 32 byte, dawn huma reġistri prefissati b'Y. Huwa għalhekk li tara l-funzjoni YMM() fil-kodiċi. Kieku kont qed nuża AVX-512 b'biċċiet ta' 64 bit, il-prefiss ikun Z.
It-tieni innovazzjoni hija li ddeċidejt li nuża ottimizzazzjoni msejħa loop unrolling, li jfisser li tagħmel tmien operazzjonijiet ta 'loop manwalment qabel ma taqbeż għall-bidu tal-linja. Din l-ottimizzazzjoni tnaqqas in-numru ta 'fergħat fil-kodiċi, u hija limitata bin-numru ta' reġistri ħielsa disponibbli.
Ukoll, xi ngħidu dwar il-prestazzjoni? Hija sabiħa! Ksibna speedup ta 'madwar seba' darbiet meta mqabbel mal-aħjar soluzzjoni Go. Impressjonanti, hux?
Iżda anke din l-implimentazzjoni tista' potenzjalment tiġi aċċellerata bl-użu ta' AVX-512, prefetching jew JIT (compilatur eżatt fil-ħin) għall-iskedar tal-mistoqsijiet. Iżda dan żgur huwa suġġett għal rapport separat.
Problemi bl-indiċi bitmap
Issa li diġà ħares lejn implimentazzjoni sempliċi ta 'indiċi bitmap f'Go u waħda ħafna aktar produttiva fil-lingwa tal-assemblaġġ, ejja fl-aħħar nitkellmu dwar għaliex l-indiċi bitmap huma tant rarament użati.
Karti antiki jsemmu tliet problemi bl-indiċi bitmap, iżda karti aktar ġodda u nargumenta li m'għadhomx rilevanti. Aħna mhux se ngħaddu fil-fond f'kull waħda minn dawn il-problemi, iżda se nħarsu lejhom b'mod superfiċjali.
Il-problema tal-kardinalità għolja
Allura, qalulna li l-indiċi tal-bitmap huma adattati biss għal oqsma b'kardinalità baxxa, jiġifieri, dawk li għandhom ftit valuri (per eżempju, sess jew kulur tal-għajnejn), u r-raġuni hija li r-rappreżentazzjoni tas-soltu ta 'dawn l-oqsma (wieħed bit għal kull valur) fil-każ ta 'kardinalità għolja, se tieħu wisq spazju u, barra minn hekk, dawn l-indiċi bitmap se jimtlew ħażin (rari).
Xi drabi nistgħu nużaw rappreżentazzjoni differenti, bħal dik standard li nużaw biex nirrappreżentaw in-numri. Iżda kien il-miġja ta 'algoritmi ta' kompressjoni li bidlu kollox. Matul l-aħħar deċennji, xjenzati u riċerkaturi ħarġu b'numru kbir ta 'algoritmi ta' kompressjoni għal bitmaps. Il-vantaġġ ewlieni tagħhom huwa li m'hemmx bżonn li dekompressaw bitmaps biex iwettqu operazzjonijiet bit - nistgħu nwettqu operazzjonijiet bit direttament fuq bitmaps kompressati.
Riċentement, bdew jidhru approċċi ibridi, bħal bitmaps roaring. Fl-istess ħin jużaw tliet rappreżentazzjonijiet differenti għal bitmaps - bitmaps infushom, arrays u hekk imsejħa bit runs - u jibbilanċjaw bejniethom biex jimmassimizzaw il-prestazzjoni u jimminimizzaw il-konsum tal-memorja.
Tista 'ssib bitmaps roaring fl-applikazzjonijiet l-aktar popolari. Diġà hemm numru kbir ta’ implimentazzjonijiet għal varjetà wiesgħa ta’ lingwi ta’ programmar, inklużi aktar minn tliet implimentazzjonijiet għal Go.
Approċċ ieħor li jista’ jgħinna nittrattaw kardinalità għolja jissejjaħ binning. Immaġina li għandek għalqa li tirrappreżenta l-għoli ta 'persuna. L-għoli huwa numru floating point, imma aħna l-bnedmin ma naħsbux hekk. Għalina m'hemm l-ebda differenza bejn għoli 185,2 ċm u 185,3 ċm.
Jirriżulta li nistgħu niġbru valuri simili fi gruppi fi ħdan 1 ċm.
U jekk nafu wkoll li ftit nies huma iqsar minn 50 ċm u ogħla minn 250 ċm, allura nistgħu essenzjalment inbiddlu qasam b'kardinalità infinita f'qasam b'kardinalità ta 'madwar 200 valur.
Naturalment, jekk meħtieġ, nistgħu nagħmlu filtrazzjoni addizzjonali wara.
Problema ta 'Bandwidth Għoli
Il-problema li jmiss bl-indiċi tal-bitmap hija li l-aġġornament tagħhom jista 'jkun għali ħafna.
Il-bażijiet tad-dejta għandhom ikunu jistgħu jaġġornaw id-dejta filwaqt li potenzjalment mijiet ta’ mistoqsijiet oħra qed ifittxu d-dejta. Għandna bżonn serraturi biex nevitaw problemi bl-aċċess tad-dejta konkorrenti jew problemi oħra ta 'qsim. U fejn hemm lock wieħed kbir, hemm problema - lock contention, meta dan lock isir konġestjoni.
Din il-problema tista' tissolva jew tiġi evitata bl-użu ta' sharding jew bl-użu ta' indiċi verżjoni.
Sharding hija ħaġa sempliċi u magħrufa sew. Tista 'taqsam indiċi bitmap bħal ma tagħmel kwalunkwe data oħra. Minflok lock kbir wieħed, int se tikseb mazz ta 'serraturi żgħar u b'hekk teħles mill-kontenzjoni tal-lock.
It-tieni mod biex issolvi l-problema huwa li tuża indiċi verżjoni. Jista' jkollok kopja waħda tal-indiċi li tuża biex tfittex jew taqra, u waħda li tuża biex tikteb jew taġġorna. U darba f'ċertu perjodu ta 'żmien (per eżempju, darba kull 100 ms jew 500 ms) inti tidduplikahom u tpartithom. Naturalment, dan l-approċċ huwa applikabbli biss f'każijiet fejn l-applikazzjoni tiegħek tista 'timmaniġġja indiċi ta' tfittxija kemmxejn lura.
Dawn iż-żewġ approċċi jistgħu jintużaw simultanjament: jista' jkollok indiċi sharded versioned.
Mistoqsijiet aktar kumplessi
Il-problema finali bl-indiċi tal-bitmap hija li qalulna li mhumiex adattati tajjeb għal tipi aktar kumplessi ta 'mistoqsijiet, bħal mistoqsijiet span.
Tabilħaqq, jekk taħseb dwarha, operazzjonijiet bit bħal AND, OR, eċċ. mhumiex adattati ħafna għal mistoqsijiet a la "Urini lukandi b'rati tal-kamra minn 200 sa 300 dollaru kull lejl."
Soluzzjoni naive u mhux għaqlija ħafna tkun li tieħu r-riżultati għal kull valur ta 'dollaru u tgħaqqadhom ma' operazzjoni OR bit-bit.
Soluzzjoni kemmxejn aħjar tkun li tuża l-grupp. Per eżempju, fi gruppi ta '50 dollaru. Dan iħaffef il-proċess tagħna b'50 darba.
Iżda l-problema tissolva wkoll faċilment bl-użu ta 'veduta maħluqa speċifikament għal dan it-tip ta' talba. F'dokumenti xjentifiċi huwa msejjaħ bitmaps kodifikati b'firxa.
F'din ir-rappreżentazzjoni, aħna mhux biss nissettjaw bit wieħed għal xi valur (per eżempju, 200), iżda nissettjaw dan il-valur u kollox ogħla. 200 u aktar. L-istess għal 300: 300 u aktar. U l-bqija.
Permezz ta 'din ir-rappreżentazzjoni, nistgħu nwieġbu din it-tip ta' mistoqsija ta 'tfittxija billi jaqsmu l-indiċi darbtejn biss. L-ewwel, se nġibu lista ta 'lukandi fejn il-kamra tiswa inqas jew $300, u mbagħad inneħħu minnha dawk fejn l-ispiża tal-kamra hija inqas jew $199. Lest.
Inti se tkun sorpriż, iżda anke ġeoqueries huma possibbli bl-użu ta 'indiċi bitmap. Il-trick huwa li tuża rappreżentazzjoni ġeometrika li ddawwar il-koordinata tiegħek b'figura ġeometrika. Per eżempju, S2 minn Google. Iċ-ċifra għandha tkun possibbli li tirrappreżenta fil-forma ta 'tliet linji jew aktar li jaqsmu li jistgħu jiġu nnumerati. B'dan il-mod nistgħu inbiddlu l-ġeoquery tagħna f'diversi mistoqsijiet "tul il-vojt" (tul dawn il-linji numerati).
Soluzzjonijiet lesti
Nispera li jinteressak ftit u issa għandek għodda oħra utli fl-armament tiegħek. Jekk qatt ikollok bżonn tagħmel xi ħaġa bħal din, tkun taf f'liema mod tfittex.
Madankollu, mhux kulħadd għandu l-ħin, il-paċenzja, jew ir-riżorsi biex joħloq indiċi bitmap mill-bidu. Speċjalment dawk aktar avvanzati, bl-użu ta' SIMD, pereżempju.
Fortunatament, hemm diversi soluzzjonijiet lesti biex jgħinuk.
Bitmaps roaring
L-ewwelnett, hemm dik l-istess librerija tal-bitmaps roaring li diġà tkellimt dwarha. Fiha l-kontenituri kollha meħtieġa u l-operazzjonijiet tal-bit li ser ikollok bżonn biex tagħmel indiċi bitmap sħiħ.
Sfortunatament, bħalissa, l-ebda waħda mill-implimentazzjonijiet Go ma tuża SIMD, li jfisser li l-implimentazzjonijiet Go huma inqas performanti mill-implimentazzjonijiet C, pereżempju.
Pilosa
Prodott ieħor li jista’ jgħinek huwa l-Pilosa DBMS, li, fil-fatt, għandu biss indiċi bitmap. Din hija soluzzjoni relattivament ġdida, iżda qed tirbaħ il-qlub b'veloċità kbira.
Pilosa juża bitmaps roaring internament u jagħtik il-ħila li tużahom, jissimplifika u jispjega l-affarijiet kollha li tkellimt dwarhom hawn fuq: grupp, bitmaps kodifikati b’firxa, il-kunċett ta’ qasam, eċċ.
Ejja nagħtu ħarsa malajr lejn eżempju ta 'użu ta' Pilosa biex twieġeb mistoqsija li diġà int familjari magħha.
L-eżempju huwa simili ħafna għal dak li rajt qabel. Aħna noħolqu klijent għas-server Pilosa, noħolqu indiċi u l-oqsma meħtieġa, imbagħad imla l-oqsma tagħna b'dejta każwali bi probabbiltajiet u, finalment, tesegwixxi l-mistoqsija familjari.
Wara dan, nużaw MHUX fuq il-qasam "għali", imbagħad jaqsam ir-riżultat (jew U dan) mal-qasam "terrazzin" u mal-qasam "riservazzjonijiet". U fl-aħħarnett, niksbu r-riżultat finali.
Tassew nittama li fil-futur qrib dan it-tip ġdid ta' indiċi jidher ukoll f'DBMSs bħal MySQL u PostgreSQL - indiċi bitmap.
Konklużjoni
Jekk għadek ma torqodx, grazzi. Kelli nmiss fil-qosor ħafna suġġetti minħabba ż-żmien limitat, imma nittama li t-taħdita kienet utli u forsi saħansitra motivanti.
Tajjeb li tkun taf dwar l-indiċi tal-bitmap, anki jekk m'għandekx bżonnhom bħalissa. Ħallihom ikunu għodda oħra fil-kaxxa tal-għodda tiegħek.
Ħaresna lejn diversi tricks tal-prestazzjoni għal Go u affarijiet li l-kompilatur Go għadu ma jimmaniġġjax tajjeb ħafna. Iżda dan huwa assolutament utli għal kull programmatur Go li jkun jaf.
Dak kollu xtaqt ngħidilkom. Grazzi!
Sors: www.habr.com