sarrera
Txosten hau ingelesez eman nuen Moskuko GopherCon Russia 2019 konferentzian eta errusieraz Nizhny Novgoroden egindako topaketa batean. Bitmap indize bati buruz ari gara - B-zuhaitza baino ez hain ohikoa, baina ez hain interesgarria. Partekatzea hitzaldiak ingelesez eta testu-transkripzioak errusieraz.
Bitmap indize batek nola funtzionatzen duen aztertuko dugu, noiz den hobea, noiz okerragoa den beste indize batzuk baino eta zein kasutan den haiek baino nabarmen azkarragoa; Ikus dezagun zein DBMS ezagunek dituzten bitmapen indizeak; Saia gaitezen gurea idazten Go-n. Eta "postrerako" prest egindako liburutegiak erabiliko ditugu gure datu-base espezializatu super-bizkorra sortzeko.
Benetan espero dut nire lanak zuretzat erabilgarriak eta interesgarriak izatea. Joan!
Sarrera
Kaixo guztioi! Arratsaldeko seiak dira eta denok oso nekatuta gaude. Une bikaina datu-baseen indizeen teoria aspergarriaz hitz egiteko, ezta? Ez kezkatu, iturburu-kode pare bat lerro izango ditut han eta hemen. π
Txantxa guztiak alde batera utzita, txostena informazioz beteta dago, eta ez dugu denbora askorik. Beraz, has gaitezen.
Gaur honako hauetaz hitz egingo dut:
- zer dira indizeak;
- zer den bitmapen indizea;
- non erabiltzen den eta non EZ erabiltzen den eta zergatik;
- Go-n inplementazio sinplea eta konpilatzailearekin borroka apur bat;
- apur bat gutxiago sinplea, baina askoz emankorragoa Go assembler inplementazioa;
- bitmapen indizeen "arazoak";
- dauden inplementazioak.
Beraz, zer dira indizeak?
Indizea datu nagusiez gain mantentzen eta eguneratzen dugun datu-egitura bereizia da. Bilaketa bizkortzeko erabiltzen da. Indizerik gabe, bilaketak datuak zeharo zeharkatu beharko lituzke (full scan izeneko prozesua), eta prozesu honek konplexutasun algoritmiko lineala du. Baina datu-baseek datu-kopuru handiak izaten dituzte normalean eta konplexutasun lineala motelegia da. Egokiena, logaritmikoa edo konstantea lortuko genuke.
Oso konplexua den gaia da hau, sotiltasunez eta truke-offez betea, baina datu-baseen garapen eta ikerketa hamarkadetan zehar aztertu ondoren, prest nago datu-baseen indizeak sortzeko metodo oso erabiliak daudela esateko.
Lehenengo ikuspegia bilaketa-espazioa hierarkikoki murriztea da, bilaketa-espazioa zati txikiagotan banatuz.
Normalean zuhaitz mota desberdinak erabiliz egiten dugu. Adibide bat zure armairuko materialen kutxa handi bat izango litzateke, gai ezberdinetan banatutako material kutxa txikiagoak dituena. Materialak behar badituzu, ziurrenik "Materialak" dioen kutxa batean bilatuko dituzu "Cookieak" dioen batean baino, ezta?
Bigarren ikuspegia nahi den elementua edo elementu-taldea berehala hautatzea da. Hash mapetan edo alderantzizko indizeetan egiten dugu. Hash mapak erabiltzea aurreko adibidearen oso antzekoa da, baina kutxa-kutxa baten ordez, azken elementuen kaxa txiki mordoa dituzu zure armairuan.
Hirugarren ikuspegia bilaketaren beharra ezabatzea da. Bloom iragazkiak edo kuku iragazkiak erabiliz egiten dugu. Lehenengoek berehala ematen dute erantzuna, bilatu beharrik ez baduzu.
Azken planteamendua hardware modernoak ematen digun botere guztia guztiz aprobetxatzea da. Hauxe da bit-mapen indizeetan egiten duguna. Bai, erabiltzean batzuetan indize osoa aztertu behar dugu, baina oso eraginkortasunez egiten dugu.
Esan bezala, datu-baseen indizeen gaia zabala eta konpromisoz betea da. Horrek esan nahi du batzuetan hainbat ikuspegi erabil ditzakegula aldi berean: bilaketa are gehiago bizkortu behar badugu, edo bilaketa mota posible guztiak jorratu behar baditugu.
Gaur hauen hurbilketa gutxien ezagutzen denari buruz hitz egingo dut: bitmapen indizeak.
Nor naiz ni gai honi buruz hitz egiteko?
Badoo-n talde-buru gisa lan egiten dut (agian gehiago ezagutzen duzu gure beste produktua, Bumble). Dagoeneko 400 milioi erabiltzaile baino gehiago ditugu munduan zehar eta haien pareko onena hautatzen duten funtzio asko. Zerbitzu pertsonalizatuak erabiliz egiten dugu, bitmapen indizeak barne.
Beraz, zer da bitmapen indizea?
Bitmap-indizeek, ββizenak dioen bezala, bit-mapak edo bit-setak erabiltzen dituzte bilaketa-indize bat ezartzeko. Txori-ikuspegitik, indize hau edozein entitate (adibidez, pertsonak) eta haien propietateak edo parametroak (adina, begi-kolorea, etab.) eta bit-eragiketak erabiltzen dituen algoritmo batek (ETA, EDO, EZ) adierazten dituen bit-mapa batek edo gehiagok osatzen dute. ) bilaketa-kontsultari erantzuteko.
Esan digutenez, bitmapen indizeak egokienak eta oso eraginkorrak dira kardinaltasun baxuko zutabe askotan kontsultak konbinatzen dituzten bilaketak dauden kasuetarako (pentsa "begien kolorea" edo "egoera zibila" eta "hiriaren erdigunetik distantzia" bezalako zerbait). Baina geroago erakutsiko dut kardinaltasun handiko zutabeetarako ere ondo funtzionatzen dutela.
Ikus dezagun bitmap indize baten adibiderik errazena.
Imajinatu hauek bezalako propietate bitarrak dituzten Moskuko jatetxeen zerrenda bat dugula:
- metrotik gertu;
- aparkaleku pribatua dago;
- terraza bat dago (terraza du);
- mahai bat erreserbatu dezakezu (erreserbak onartzen ditu);
- barazkijaleentzat egokia (vegan friendly);
- garesti (garesti).
Eman diezaiogun jatetxe bakoitzari 0tik hasita sekuentzia-zenbaki bat eta esleitu diezaiogun memoria 6 bit-mapetarako (bat ezaugarri bakoitzeko). Ondoren, bitmap hauek beteko ditugu, jatetxeak jabetza hori duen ala ez kontuan hartuta. 4. jatetxea terraza bat badu, 4. zk. bit-a 1ean ezarriko da "beranda du" bit-mapan (berandarik ez badago, orduan 0 izango da).
Orain bitmap indizerik errazena dugu, eta honelako galderei erantzuteko erabil dezakegu:
- βErakutsi begetarianoak diren jatetxeakβ;
- "Erakutsi iezadazu jatetxe merkeak, mahai bat erreserbatu dezakezun terraza batekin."
Nola? Ikus dezagun. Lehenengo eskaera oso erraza da. Egin behar duguna da "vegetarian friendly" bitmap hartu eta ageri diren jatetxeen zerrenda bihurtzea.
Bigarren eskaera pixka bat konplexuagoa da. "Gastia" bitmap-an NOT bitmapa erabili behar dugu jatetxe merkeen zerrenda lortzeko, gero ETA "mahai bat erreserbatu al dezaket" bitmaparekin eta ETA emaitza "beranda bat dago" bitmaparekin. Lortutako bitmapak gure irizpide guztiak betetzen dituzten establezimenduen zerrenda izango du. Adibide honetan, hau Yunost jatetxea baino ez da.
Teoria asko dago tartean, baina ez kezkatu, laster ikusiko dugu kodea.
Non erabiltzen dira bitmapen indizeak?
Google bitmap indizeak egiten badituzu, erantzunen % 90 Oracle DBrekin erlazionatuta egongo da era batera edo bestera. Baina beste DBMS batzuek ere onartzen dute horrelako gauza polita, ezta? Benetan ez.
Goazen susmagarri nagusien zerrenda.
MySQL-k oraindik ez ditu bitmapen indizeak onartzen, baina aukera hau gehitzea proposatzen duen Proposamen bat dago ().
PostgreSQL-k ez ditu bitmapen indizeak onartzen, baina bitmap sinpleak eta bit-eragiketak erabiltzen ditu bilaketa-emaitzak beste hainbat indizetan konbinatzeko.
Tarantool-ek bitset indizeak ditu eta horietan bilaketa errazak onartzen ditu.
Redis-ek bit-eremu sinpleak ditu) horiek bilatzeko gaitasunik gabe.
MongoDB-k oraindik ez ditu bitmapen indizeak onartzen, baina aukera hau gehitzea iradokitzen duen Proposamen bat ere badago.
Elasticsearch-ek bitmapak erabiltzen ditu barnean).
- Baina gure etxean auzokide berri bat agertu da: Pilosa. Go-n idatzitako datu base ez-erlazional berria da. Bitmapen indizeak bakarrik ditu eta dena horietan oinarritzen da. Geroxeago hitz egingo dugu horretaz.
Ezartzea Go-n
Baina zergatik erabiltzen dira hain gutxi bitmapen indizeak? Galdera honi erantzun aurretik, Go-n bitmap indize sinple bat nola inplementatu erakutsi nahi dizut.
Bitmapak, funtsean, datu zatiak besterik ez dira. Go-n, erabil ditzagun byte xerrak horretarako.
Bitmap bat dugu jatetxearen ezaugarri baterako, eta bitmaparen bit bakoitzak jatetxe jakin batek propietate hori duen edo ez adierazten du.
Bi funtzio laguntzaile beharko ditugu. Bat erabiliko da gure bit-mapak ausazko datuekin betetzeko. Ausazko, baina jatetxea jabetza bakoitza izateko probabilitate jakin batekin. Esaterako, uste dut Moskun oso jatetxe gutxi daudela mahairik erreserbatu ezin den, eta iruditzen zait establezimenduen %20 inguru barazkijaleentzat egokiak direla.
Bigarren funtzioak bitmapa jatetxeen zerrenda bihurtuko du.
"Erakutsi patioa duten eta erreserbak egin ditzaketen jatetxe merkeak" galderari erantzuteko, bi bit eragiketak behar ditugu: EZ eta ETA.
Gure kodea apur bat erraztu dezakegu AND NOT operadore konplexuagoa erabiliz.
Eragiketa horietako bakoitzerako funtzioak ditugu. Biak xerren bidez igarotzen dira, bakoitzari dagozkion elementuak hartu, eragiketa bit batekin konbinatu eta emaitza xerrean jarri.
Eta orain gure bitmapak eta funtzioak erabil ditzakegu bilaketa-kontsultari erantzuteko.
Errendimendua ez da hain altua, nahiz eta funtzioak oso sinpleak diren eta funtzioa deitzen zen bakoitzean emaitzazko xerra berririk itzuli ezean diru asko aurreztu genuen.
Pprof-ekin profila pixka bat egin ondoren, Go konpilatzaileari optimizazio oso sinple baina oso garrantzitsua falta zitzaiola ohartu nintzen: funtzioen barneratzea.
Kontua da Go konpilatzaileak izugarri beldurtzen diela xertan zehar igarotzen diren begiztei, eta kategorikoki uko egiten diela begiztak dituzten funtzioak barneratzeari.
Baina ez dut beldurrik eta konpilatzailea engainatu dezaket goto erabiliz begizta baten ordez, garai onean bezala.
Eta, ikusten duzun bezala, orain konpilatzaileak pozik sartuko du gure funtzioa! Ondorioz, 2 mikrosegundo inguru aurreztea lortzen dugu. Ez dago gaizki!
Bigarren botila-lepoa erraz ikusten da muntaia-irteerari arretaz begiratuz gero. Konpilatzaileak zati-mugaren egiaztapena gehitu zuen gure begiztarik beroenaren barruan. Kontua da Go hizkuntza segurua dela, konpilatzailea beldur da nire hiru argumentuak (hiru xerra) tamaina ezberdinekoak direla. Azken finean, orduan buffer gainezka deritzon bat gertatzeko aukera teorikoa egongo da.
Lasai dezagun konpilatzailea xerra guztiak tamaina berekoak direla erakutsiz. Hau egin dezakegu gure funtzioaren hasieran egiaztapen sinple bat gehituz.
Hau ikusita, konpilatzaileak pozarren saltatzen du egiaztapena, eta azkenean beste 500 nanosegundo aurrezten ditugu.
Harategi handiak
Ados, gure inplementazio sinpleari errendimendu pixka bat kentzea lortu dugu, baina emaitza hau egungo hardwarearekin posible dena baino askoz okerragoa da.
Egiten dugun guztia oinarrizko bit-eragiketak dira, eta gure prozesadoreek oso eraginkortasunez egiten dituzte. Baina, zoritxarrez, gure prozesadorea oso lan txikiekin "elikatzen" dugu. Gure funtzioek bytez byte eragiketak egiten dituzte. Oso erraz molda dezakegu gure kodea UInt8 xerrak erabiliz 64 byteko zatiekin lan egiteko.
Ikus dezakezunez, aldaketa txiki honek gure programa zortzi aldiz bizkortu zuen lotearen tamaina zortzi aldiz handituz. Irabazia lineala dela esan daiteke.
Muntatzailean inplementatzea
Baina hau ez da amaiera. Gure prozesadoreek 16, 32 eta 64 byteko zatiekin lan egin dezakete. Eragiketa "zabal" horiei instrukzio bakarreko datu anitz deitzen zaie (SIMD; instrukzio bat, datu asko), eta eragiketa horiek erabil ditzan kodea eraldatzeko prozesuari bektorizazioa deritzo.
Zoritxarrez, Go konpilatzailea ez da bikaina bektorializazioan. Gaur egun, Go kodea bektorializatzeko modu bakarra eragiketa hauek eskuz hartu eta jartzea da Go assembler erabiliz.
Go assembler piztia arraroa da. Seguruenik badakizu mihiztadura hizkuntza idazten ari zaren ordenagailuaren arkitekturari oso lotuta dagoen zerbait dela, baina ez da hori gertatzen Go-n. Go assembler IRL (errepresentazio-lengoaia) edo bitarteko hizkuntza baten antzekoa da: ia plataforma independentea da. Rob Pike-k emanaldi bikaina eman zuen gai honi buruz duela urte batzuk Denverreko GopherCon-en.
Horrez gain, Go-k ezohiko Plan 9 formatua erabiltzen du, orokorrean onartutako AT&T eta Intel formatuetatik desberdina dena.
Esan daiteke Go assembler eskuz idaztea ez dela dibertigarriena.
Baina, zorionez, dagoeneko badaude goi-mailako bi tresna Go assembler idazten laguntzen digutenak: PeachPy eta avo. Bi utilitateek Go muntatzailea sortzen dute Python-en eta Go-n idatzitako goi-mailako kodetik, hurrenez hurren.
Utilitate hauek erregistroen esleipena, idazteko begiztak eta, oro har, Go-n muntaia-programazioaren munduan sartzeko prozesua errazten dute.
Avo erabiliko dugu, beraz, gure programak ia ohiko Go programak izango dira.
Hau da avo programa baten adibiderik errazena. Main() funtzioa dugu, bere baitan Gehitu() funtzioa definitzen duena, eta horren esanahia bi zenbaki gehitzea da. Hemen laguntzaile funtzioak daude parametroak izenaren arabera lortzeko eta prozesadore-erregistro libre eta egokietako bat lortzeko. Prozesadorearen eragiketa bakoitzak dagokion funtzio bat du avo-n, ADDQ-n ikusten den bezala. Azkenik, emaitzazko balioa gordetzeko funtzio laguntzaile bat ikusiko dugu.
Go generate deituz, programa avo-n exekutatuko dugu eta, ondorioz, bi fitxategi sortuko dira:
- add.s ondoriozko kodearekin Go muntatzailean;
- stub.go funtzioen goiburuekin bi munduak lotzeko: Go eta assembler.
Avo-k zer eta nola egiten duen ikusi dugunean, ikus ditzagun gure funtzioak. Funtzioen bertsio eskalar eta bektoriala (SIMD) inplementatu dut.
Ikus ditzagun lehenik bertsio eskalarrei.
Aurreko adibidean bezala, helburu orokorreko erregistro libre eta baliozko bat eskatzen ari gara, ez dugu argumentuetarako desplazamenduak eta tamainak kalkulatu beharrik. avok hau guztia egiten digu.
Etiketak eta goto (edo jauziak) erabiltzen genituen errendimendua hobetzeko eta Go konpilatzailea engainatzeko, baina orain hasieratik ari gara egiten. Kontua da zikloak goi-mailako kontzeptua direla. Muntatzailean, etiketak eta jauziak baino ez ditugu.
Gainerako kodea dagoeneko ezaguna eta ulergarria izan behar da. Etiketa eta jauziekin begizta bat emulatzen dugu, gure bi xerretan datu txiki bat hartzen dugu, bit-eragiketa batekin konbinatzen dugu (ETA EZ kasu honetan) eta gero emaitza xertan jartzen dugu. Denak.
Hau da azken muntatzaile-kodearen itxura. Ez genituen desplazamenduak eta tamainak kalkulatu behar (berdez nabarmenduta) edo erabilitako erregistroen jarraipena egin (gorriz nabarmenduta).
Mihiztadura-lengoaiaren inplementazioaren errendimendua Go-n inplementazio onenaren errendimendua konparatzen badugu, berdin dela ikusiko dugu. Eta hau espero da. Azken finean, ez dugu ezer berezirik egin - Go konpiladore batek egingo lukeena erreproduzitu dugu.
Zoritxarrez, ezin dugu konpilatzailea behartu gure funtzioak muntaia-lengoaian idatzita sartzera. Gaur egun Go konpilatzaileak ez du horrelako ezaugarririk, nahiz eta denbora luzez gehitzeko eskaera egin den.
Horregatik ezinezkoa da muntaia-lengoaian funtzio txikietatik etekinik ateratzea. Funtzio handiak idatzi behar ditugu, edo matematika/bit pakete berria erabili edo mihiztatzaile-lengoaia saihestu behar dugu.
Ikus ditzagun orain gure funtzioen bertsio bektorialak.
Adibide honetarako, AVX2 erabiltzea erabaki nuen, beraz, 32 byte-ko zatietan funtzionatzen duten eragiketak erabiliko ditugu. Kodearen egitura bertsio eskalarren oso antzekoa da: parametroak kargatu, doako erregistro partekatu bat eskatzea, etab.
Berrikuntzetako bat da eragiketa bektorial zabalagoek erregistro zabal bereziak erabiltzen dituztela. 32 byte-ko zatien kasuan, Y-ren aurrizkia duten erregistroak dira. Horregatik, YMM() funtzioa ikusten duzu kodean. AVX-512 64 biteko zatiekin erabiliko banu, aurrizkia Z izango litzateke.
Bigarren berrikuntza da loop unrolling izeneko optimizazioa erabiltzea erabaki nuela, hau da, zortzi begizta eragiketa eskuz egitea begiztaren hasierara salto egin aurretik. Optimizazio honek kodean adar kopurua murrizten du, eta eskuragarri dauden doako erregistro kopuruak mugatzen du.
Tira, zer gertatzen da errendimendua? Ederra da! Zazpi aldiz inguruko bizkortzea lortu dugu Go soluzio onenarekin alderatuta. Ikusgarria, ezta?
Baina inplementazio hau ere bizkortu liteke AVX-512, aurrez eskuratzea edo JIT (just-in-time konpilatzailea) erabiliz kontsulta-antolatzailerako. Baina hau da, zalantzarik gabe, aparteko txosten baterako gaia.
Arazoak bitmapen indizeekin
Orain bitmap-indize baten inplementazio soil bat ikusi dugulako Go-n eta askoz ere produktiboagoa den muntaia-lengoaian, azkenik, hitz egin dezagun zergatik bitmap-indizeak hain gutxi erabiltzen diren.
Paper zaharrek hiru arazo aipatzen dituzte bitmap-indizeekin, baina paper berriek eta nik argudiatzen dute jada ez direla garrantzitsuak. Ez gara arazo horietako bakoitzean sakonduko, baina azaletik begiratuko ditugu.
Kardinaltasun handiko arazoa
Beraz, esaten zaigu bitmap-indizeak kardinaltasun baxuko eremuetarako soilik egokiak direla, hau da, balio gutxi dituztenentzat (adibidez, generoa edo begien kolorea), eta arrazoia da eremu horien ohiko irudikapena (bat balio bakoitzeko bit) kardinaltasun handiko kasuan, leku gehiegi hartuko du eta, gainera, bitmap indize hauek gaizki (gutxi) beteko dira.
Batzuetan, beste irudikapen bat erabil dezakegu, adibidez, zenbakiak irudikatzeko erabiltzen dugun estandarra. Baina konpresio algoritmoen etorrera izan zen dena aldatu zuena. Azken hamarkadetan, zientzialariek eta ikertzaileek bitmapetarako konpresio-algoritmo ugari sortu dituzte. Haien abantaila nagusia da ez dagoela bitmapak deskonprimitu behar bit-eragiketak egiteko - bit-eragiketak zuzenean egin ditzakegu bit-mapa konprimituetan.
Azkenaldian, planteamendu hibridoak agertzen hasi dira, bitmap orroak adibidez. Bitmapetarako hiru irudikapen ezberdin erabiltzen dituzte aldi berean -bit-mapak beraiek, arrayak eta bit-exekuzio deiturikoak- eta haien arteko oreka egiten dute errendimendua maximizatzeko eta memoria-kontsumoa minimizatzeko.
Bitmap orroak aurki ditzakezu aplikazio ezagunenetan. Dagoeneko programazio-lengoaia askotarako inplementazio kopuru handia dago, Go-rako hiru inplementazio baino gehiago barne.
Kardinaltasun handiari aurre egiten lagun diezagukeen beste ikuspegi bat binning deritzo. Imajinatu pertsona baten altuera adierazten duen eremu bat duzula. Altuera koma mugikorreko zenbaki bat da, baina gizakiok ez dugu horrela pentsatzen. Guretzat ez dago 185,2 cm eta 185,3 cm-ko altueraren arteko alderik.
Antzeko balioak 1 cm barruko taldeetan taldeka ditzakegula ematen du.
Eta badakigu, gainera, oso pertsona gutxi direla 50 cm baino txikiagoak eta 250 cm baino altuagoak direla, orduan, funtsean, kardinaltasun infinitua duen eremu bat 200 balio inguruko kardinalitatea duen eremu batean bihur dezakegu.
Noski, behar izanez gero, iragazketa gehigarria egin dezakegu gero.
Banda zabalera handiko arazoa
Bitmap indizeen hurrengo arazoa da horiek eguneratzea oso garestia izan daitekeela.
Datu-baseek datuak eguneratzeko gai izan behar dute beste ehunka kontsultak datuak bilatzen dituzten bitartean. Blokeoak behar ditugu datuen aldi berean sartzeko arazoak edo partekatzeko beste arazo batzuk saihesteko. Eta blokeo handi bat dagoen tokian, arazo bat dago: blokeoen gatazka, blokeo hori botila-lepo bihurtzen denean.
Arazo hau konpon daiteke edo saihestu daiteke zatiketa erabiliz edo bertsiodun indizeak erabiliz.
Partekatzea gauza sinple eta ezaguna da. Bit-maparen indizea zatitu dezakezu beste edozein datu bezala. Sarraila handi baten ordez, sarraila txiki sorta bat lortuko duzu eta horrela blokeoen gatazka kentzeko.
Arazoa konpontzeko bigarren modua bertsiodun indizeak erabiltzea da. Bilatzeko edo irakurtzeko erabiltzen duzun indizearen kopia bat izan dezakezu, eta idazteko edo eguneratzeko erabiltzen duzun bat. Eta denbora tarte jakin batean behin (adibidez, 100 ms edo 500 ms behin) bikoiztu eta trukatzen dituzu. Jakina, ikuspegi hau zure aplikazioak apur bat atzeratutako bilaketa-indizea kudeatu dezakeen kasuetan bakarrik dago aplikagarri.
Bi ikuspegi hauek aldi berean erabil daitezke: zatitutako bertsio-indize bat izan dezakezu.
Kontsulta konplexuagoak
Bitmapen indizeen azken arazoa da ez direla ondo egokiak kontsulta mota konplexuagoetarako, hala nola span kontsultak egiteko.
Izan ere, pentsatzen baduzu, ETA, EDO, etab. bezalako bit-eragiketak ez dira oso egokiak kontsultak egiteko "Erakutsi iezadazu 200 eta 300 dolar arteko logelen prezioak dituzten hotelak gau bakoitzeko".
Irtenbide inozoa eta oso zentzugabea litzateke dolarearen balio bakoitzeko emaitzak hartu eta bitarteko EDO eragiketa batekin konbinatzea.
Irtenbide apur bat hobea taldekatzea erabiltzea litzateke. Adibidez, 50 dolarreko taldeetan. Honek gure prozesua 50 aldiz bizkortuko luke.
Baina arazoa erraz konpontzen da eskaera mota honetarako bereziki sortutako ikuspegia erabiliz. Lan zientifikoetan barruti-kodetutako bit-mapak deitzen dira.
Irudikapen honetan, ez dugu bit bat ezartzen balio baterako (adibidez, 200), baizik eta balio hau eta dena gorago ezarriko dugu. 200 eta gehiago. Berdin 300: 300 eta gehiago. Eta abar.
Irudikapen hau erabiliz, bilaketa mota honi erantzun diezaiokegu indizea bi aldiz zeharkatuz. Lehenik eta behin, logelak 300 $ gutxiago edo $199 balio duten hotelen zerrenda jasoko dugu, eta, ondoren, logelak XNUMX $ gutxiago edo $XNUMX duten hotelen zerrenda bat jasoko dugu. Prest.
Harrituta geratuko zara, baina geokontsultak ere posible dira bitmapen indizeak erabiliz. Trikimailua zure koordenatua irudi geometriko batekin inguratzen duen irudikapen geometrikoa erabiltzea da. Adibidez, Google-ren S2. Irudiak ebaki daitezkeen hiru lerro edo gehiagoren moduan irudikatu ahal izan behar du. Honela gure geokontsulta hainbat kontsulta bihur ditzakegu "hutsunean zehar" (zenbakizko lerro hauetan zehar).
Ready Solutions
Espero dut pixka bat interesatzea eta orain zure armategian beste tresna erabilgarria izatea. Inoiz horrelako zerbait egin behar baduzu, jakingo duzu zein modu begiratu.
Hala ere, denek ez dute astirik, pazientziarik edo baliabiderik bitmapen indizeak hutsetik sortzeko. Batez ere aurreratuagoak, SIMD erabiliz, adibidez.
Zorionez, prest dauden hainbat irtenbide daude laguntzeko.
Bitmap orroak
Lehenik eta behin, dagoeneko hitz egin dudan bitmapen liburutegi burrunbatsu bera dago. Bitmap indize osoa egiteko beharko dituzun beharrezko edukiontzi eta bit-eragiketa guztiak ditu.
Zoritxarrez, momentuz, Go inplementazio batek ere ez du SIMD erabiltzen, eta horrek esan nahi du Go inplementazioek C inplementazioek baino eraginkortasun txikiagoa dutela, adibidez.
Pilosa
Lagun zaitzakeen beste produktu bat Pilosa DBMS da, izan ere, bitmapen indizeak baino ez ditu. Irtenbide nahiko berria da, baina bihotzak abiadura handian irabazten ari da.
Pilosak barnean bitmap orroak erabiltzen ditu eta horiek erabiltzeko aukera ematen dizu, goian aipatu dudan gauza guztiak sinplifikatu eta azaltzen ditu: taldekatzea, tartean kodetutako bitmapak, eremu baten kontzeptua, etab.
Ikus dezagun azkar ezagutzen duzun galdera bati erantzuteko Pilosa erabiltzearen adibide bati.
Adibidea lehen ikusi duzunaren oso antzekoa da. Pilosa zerbitzarirako bezero bat sortzen dugu, indize bat eta beharrezko eremuak sortzen ditugu, gero gure eremuak probabilitatez ausazko datuekin betetzen ditugu eta, azkenik, kontsulta ezaguna egiten dugu.
Horren ostean, EZ erabiltzen dugu "garestia" eremuan, ondoren emaitza (edo ETA) "terraza" eremuarekin eta "erreserba" eremuarekin gurutzatuko dugu. Eta azkenik, azken emaitza lortuko dugu.
Benetan espero dut etorkizun hurbilean indize mota berri hau MySQL eta PostgreSQL bezalako DBMSetan ere agertzea - ββbitmap indizeak.
Ondorioa
Oraindik lo hartu ez bazara, eskerrik asko. Denbora gutxigatik gai asko ukitu behar izan nituen laburki, baina espero dut hitzaldia baliagarria eta agian motibagarria izatea.
Bitmap-en indizeak jakitea ona da, nahiz eta une honetan behar ez dituzun. Utzi zure tresna-kutxako beste tresna bat izan daitezen.
Go-rako hainbat trikimailu aztertu ditugu eta Go konpilatzaileak oraindik oso ondo kudeatzen ez dituen gauzak. Baina hau guztiz erabilgarria da Go programatzaile guztiek jakiteko.
Hori da kontatu nahi nuen guztia. Eskerrik asko!
Iturria: www.habr.com