enkonduko
Mi donis ĉi tiun raporton angle ĉe la konferenco GopherCon Russia 2019 en Moskvo kaj en la rusa en renkontiĝo en Niĵnij Novgorod. Ni parolas pri bitmapa indekso - malpli ofta ol B-arbo, sed ne malpli interesa. Kundivido paroladoj en la konferenco en la angla kaj tekstaj transskribaĵoj en la rusa.
Ni rigardos kiel funkcias bitmapa indekso, kiam ĝi estas pli bona, kiam ĝi estas pli malbona ol aliaj indeksoj, kaj en kiuj kazoj ĝi estas signife pli rapida ol ili; Ni vidu, kiuj popularaj DBMS-oj jam havas bitmap-indeksojn; Ni provu skribi nian propran en Go. Kaj "por deserto" ni uzos pretajn bibliotekojn por krei nian propran superrapidan fakan datumbazon.
Mi vere esperas, ke miaj verkoj estos utilaj kaj interesaj por vi. Iru!
Enkonduko
Saluton al ĉiuj! Estas la sesa vespere kaj ni ĉiuj estas tre lacaj. Bonega tempo por paroli pri enuiga datumbaza indeksa teorio, ĉu ne? Ne maltrankviliĝu, mi havos kelkajn liniojn de fontkodo jen kaj jen. 🙂
Ĉiuj ŝercoj flankenmetite, la raporto estas plenplena de informoj, kaj ni ne havas multe da tempo. Do ni komencu.
Hodiaŭ mi parolos pri la jenaj:
- kio estas indeksoj;
- kio estas bitmap-indekso;
- kie ĝi estas uzata kaj kie ĝi NE estas uzata kaj kial;
- simpla efektivigo en Go kaj iom da lukto kun la kompililo;
- iomete malpli simpla, sed multe pli produktiva efektivigo en Go-asemblero;
- "problemoj" de bitmapaj indeksoj;
- ekzistantaj efektivigoj.
Do kio estas indeksoj?
La indekso estas aparta datumstrukturo, kiun ni konservas kaj ĝisdatigas krom la ĉefaj datumoj. Ĝi estas uzata por akceli la serĉon. Sen indeksoj, serĉado postulus trapasi la datumojn tute (procezo nomita plena skanado), kaj ĉi tiu procezo havas linearan algoritman kompleksecon. Sed datumbazoj kutime enhavas grandegajn kvantojn da datumoj kaj lineara komplekseco estas tro malrapida. Ideale, ni ricevus logaritman aŭ konstantan.
Ĉi tio estas tre kompleksa temo, plena de subtilecoj kaj kompromisoj, sed post rigardado de jardekoj da datumbaza disvolviĝo kaj esplorado, mi pretas diri, ke ekzistas nur kelkaj vaste uzataj aliroj por krei datumbazajn indeksojn.
La unua aliro estas hierarkie redukti la serĉspacon, dividante la serĉspacon en pli malgrandajn partojn.
Ni kutime faras tion uzante malsamajn specojn de arboj. Ekzemplo estus granda skatolo da materialoj en via ŝranko, kiu enhavas pli malgrandajn skatolojn da materialoj dividitaj en malsamaj temoj. Se vi bezonas materialojn, vi verŝajne serĉos ilin en skatolo kiu diras "Materialoj" prefere ol unu kiu diras "Kuketoj," ĉu ne?
La dua aliro estas tuj elekti la deziratan elementon aŭ grupon de elementoj. Ni faras tion en hashmapoj aŭ inversaj indeksoj. Uzi hashmapojn tre similas al la antaŭa ekzemplo, sed anstataŭ skatolo da skatoloj, vi havas amason da skatoletoj da finaj aĵoj en via ŝranko.
La tria aliro estas forigi la bezonon de serĉado. Ni faras tion uzante Bloom-filtrilojn aŭ kukolo-filtrilojn. La unuaj donas respondon tuj, savante vin de devi serĉi.
La lasta aliro estas plene uzi la tutan potencon, kiun donas al ni moderna aparataro. Ĝuste tion ni faras en bitmapaj indeksoj. Jes, uzante ilin ni foje bezonas trarigardi la tutan indekson, sed ni faras ĝin tre efike.
Kiel mi diris, la temo de datumbazaj indeksoj estas vasta kaj plena de kompromisoj. Tio signifas, ke foje ni povas uzi plurajn alirojn samtempe: se ni bezonas eĉ pli akceli la serĉon, aŭ se ni bezonas kovri ĉiujn eblajn serĉspecojn.
Hodiaŭ mi parolos pri la malplej konata aliro de ĉi tiuj - bitmapaj indeksoj.
Kiu mi estas por paroli pri ĉi tiu temo?
Mi laboras kiel teamgvidanto ĉe Badoo (eble vi pli konas nian alian produkton, Bumble). Ni jam havas pli ol 400 milionojn da uzantoj tra la mondo kaj multajn funkciojn, kiuj elektas la plej bonan kongruon por ili. Ni faras tion uzante kutimajn servojn, inkluzive de bitmapaj indeksoj.
Kio do estas bitmap-indekso?
Bitmapaj indeksoj, kiel la nomo sugestas, uzas bitmapojn aŭ pecetojn por efektivigi serĉindekson. El birda vido, tiu indekso konsistas el unu aŭ pluraj tiaj bitmapoj reprezentantaj iujn ajn unuojn (kiel ekzemple homoj) kaj iliajn trajtojn aŭ parametrojn (aĝo, okulkoloro, ktp.), kaj algoritmon uzantan bitoperaciojn (KAJ, AŬ, NE). ) por respondi la serĉdemandon.
Oni diras al ni, ke bitmapaj indeksoj estas plej taŭgaj kaj tre efikaj por kazoj kie ekzistas serĉoj kiuj kombinas demandojn tra multaj malaltaj kardinalaj kolumnoj (pensu "okulan koloron" aŭ "edzecan staton" kontraŭ io kiel "distanco de urbocentro"). Sed mi montros poste, ke ili funkcias bone ankaŭ por altkardinalaj kolumnoj.
Ni rigardu la plej simplan ekzemplon de bitmapa indekso.
Imagu, ke ni havas liston de Moskvaj restoracioj kun binaraj propraĵoj kiel ĉi tiuj:
- proksime de metroo;
- estas privata parkado;
- estas verando (havas teraso);
- vi povas rezervi tablon (akceptas rezervojn);
- taŭga por vegetaranoj (veganoj amika);
- multekosta (kosta).
Ni donu al ĉiu restoracio sinsekvon ekde 0 kaj asignu memoron por 6 bitmapoj (unu por ĉiu trajto). Ni tiam plenigos ĉi tiujn bitmapojn depende de ĉu la restoracio havas ĉi tiun posedaĵon aŭ ne. Se restoracio 4 havas verandon, tiam la bito n-ro 4 en la bitmapo "havas verandon" estos agordita al 1 (se ne estas verando, tiam al 0).
Nun ni havas la plej simplan bitmapan indekson ebla, kaj ni povas uzi ĝin por respondi demandojn kiel:
- "Montru al mi vegetaran-amikajn restoraciojn";
- "Montru al mi malmultekostajn restoraciojn kun verando, kie vi povas rezervi tablon."
Kiel? Ni rigardu. La unua peto estas tre simpla. Ĉio, kion ni devas fari, estas preni la "vegetaran amika" bitmapon kaj igi ĝin listo de restoracioj, kies pecoj estas elmontritaj.
La dua peto estas iom pli komplika. Ni devas uzi la NE-bitmapon sur la "multekosta" bitmapo por akiri liston de malmultekostaj restoracioj, tiam KAJ ĝin kun la "ĉu mi povas rezervi tablon" bitmapo kaj KAJ la rezulton kun la "estas verando" bitmapo. La rezulta bitmapo enhavos liston de establaĵoj, kiuj plenumas ĉiujn niajn kriteriojn. En ĉi tiu ekzemplo, ĉi tio estas nur la restoracio Yunost.
Estas multe da teorio implikita, sed ne maltrankviliĝu, ni vidos la kodon tre baldaŭ.
Kie estas uzataj bitmapaj indeksoj?
Se vi Guglos bitmap indeksoj, 90% de la respondoj estos rilataj al Oracle DB en unu maniero aŭ alia. Sed aliaj DBMS-oj verŝajne ankaŭ subtenas tian bonegan aferon, ĉu ne? Ne vere.
Ni trarigardu la liston de ĉefaj suspektatoj.
MySQL ankoraŭ ne subtenas bitmap-indeksojn, sed ekzistas Propono sugestanta aldoni ĉi tiun opcion ().
PostgreSQL ne subtenas bitmap-indeksojn, sed uzas simplajn bitmapojn kaj bitajn operaciojn por kombini serĉrezultojn tra multoblaj aliaj indeksoj.
Tarantool havas bitset-indeksojn kaj subtenas simplajn serĉojn sur ili.
Redis havas simplajn bitkampojn) sen la kapablo serĉi ilin.
MongoDB ankoraŭ ne subtenas bitmap-indeksojn, sed ekzistas ankaŭ Propono sugestanta, ke ĉi tiu opcio estu aldonita.
Elasticsearch uzas bitmapojn interne).
- Sed nova najbaro aperis en nia domo: Pilosa. Ĉi tio estas nova ne-rilata datumbazo skribita en Go. Ĝi enhavas nur bitmap-indeksojn kaj bazigas ĉion sur ili. Ni parolos pri ĝi iom poste.
Efektivigo en Go
Sed kial bitmapaj indeksoj estas tiel malofte uzataj? Antaŭ respondi ĉi tiun demandon, mi ŝatus montri al vi kiel efektivigi tre simplan bitmapan indekson en Go.
Bitmapoj esence estas nur pecoj de datumoj. En Go, ni uzu bajtajn tranĉaĵojn por tio.
Ni havas unu bitmapon por unu restoracio, kaj ĉiu bito en la bitmapo indikas ĉu aparta restoracio havas ĉi tiun posedaĵon aŭ ne.
Ni bezonos du helpajn funkciojn. Unu estos uzata por plenigi niajn bitmapojn kun hazardaj datumoj. Hazarda, sed kun certa probableco, ke la restoracio havas ĉiun posedaĵon. Ekzemple, mi kredas, ke estas tre malmultaj restoracioj en Moskvo, kie oni ne povas rezervi tablon, kaj ŝajnas al mi, ke ĉirkaŭ 20% de la establaĵoj taŭgas por vegetaranoj.
La dua funkcio konvertos la bitmapon en liston de restoracioj.
Por respondi la demandon "Montru al mi malmultekostajn restoraciojn, kiuj havas korton kaj povas fari rezervojn", ni bezonas du bitajn operaciojn: NE kaj KAJ.
Ni povas iomete simpligi nian kodon uzante la pli kompleksan AND NOT-funkciigiston.
Ni havas funkciojn por ĉiu el ĉi tiuj operacioj. Ambaŭ trapasas la tranĉaĵojn, prenu la respondajn elementojn de ĉiu, kombinu ilin per iom da operacio kaj metu la rezulton en la rezultan tranĉaĵon.
Kaj nun ni povas uzi niajn bitmapojn kaj funkciojn por respondi la serĉdemandon.
Efikeco ne estas tiom alta, kvankam la funkcioj estas tre simplaj kaj ni ŝparis multe da mono ne redonante novan rezultan tranĉaĵon ĉiufoje kiam la funkcio estis vokita.
Post iom da profilado kun pprof, mi rimarkis, ke la Go-kompililo mankas unu tre simpla sed tre grava optimumigo: funkcio enlinio.
La fakto estas, ke la Go-kompililo terure timas buklojn, kiuj trairas tranĉaĵojn, kaj kategorie rifuzas enliniajn funkciojn, kiuj enhavas tiajn buklojn.
Sed mi ne timas kaj mi povas trompi la kompililon uzante goto anstataŭ buklo, kiel en la bonaj tempoj.
Kaj, kiel vi povas vidi, nun la kompililo feliĉe enlinios nian funkcion! Kiel rezulto, ni sukcesas ŝpari ĉirkaŭ 2 mikrosekundojn. Ne malbona!
La dua botelkolo estas facile vidi se vi rigardas atente la kunigproduktaĵon. La kompililo aldonis tranĉan limkontrolon ĝuste ene de nia plej varma buklo. La fakto estas, ke Go estas sekura lingvo, la kompililo timas, ke miaj tri argumentoj (tri tranĉaĵoj) estas de malsamaj grandecoj. Post ĉio, tiam estos teoria ebleco de okazo de tiel nomata bufro-superfluo.
Ni trankviligu la kompililon montrante al ĝi, ke ĉiuj tranĉaĵoj estas samgrandaj. Ni povas fari tion aldonante simplan kontrolon komence de nia funkcio.
Vidante tion, la kompililo feliĉe preterlasas la kontrolon, kaj ni finas ŝpari aliajn 500 nanosekundojn.
Grandaj buĉoj
Bone, ni sukcesis elpremi iom da rendimento el nia simpla efektivigo, sed ĉi tiu rezulto estas fakte multe pli malbona ol eblas kun nuna aparataro.
Ĉio, kion ni faras, estas bazaj bitaj operacioj, kaj niaj procesoroj plenumas ilin tre efike. Sed, bedaŭrinde, ni "nutras" nian procesoron per tre malgrandaj pecoj de laboro. Niaj funkcioj faras operaciojn laŭ bajto-post-bajto. Ni povas tre facile agordi nian kodon por labori kun 8-bajtaj pecoj uzante UInt64-tranĉaĵojn.
Kiel vi povas vidi, ĉi tiu malgranda ŝanĝo rapidigis nian programon ok fojojn pliigante la aran grandecon je ok fojojn. Oni povas diri, ke la gajno estas linia.
Efektivigo en asemblero
Sed ĉi tio ne estas la fino. Niaj procesoroj povas labori kun pecoj de 16, 32 kaj eĉ 64 bajtoj. Tiaj "larĝaj" operacioj estas nomitaj ununuraj instrukciaj multoblaj datenoj (SIMD; unu instrukcio, multaj datenoj), kaj la procezo de transformado de kodo tiel ke ĝi uzas tiajn operaciojn estas nomita vektorizado.
Bedaŭrinde, la Go-kompililo estas malproksima de bonega pri vektorizado. Nuntempe, la sola maniero por vektorigi Go-kodon estas preni kaj meti ĉi tiujn operaciojn permane per Go-asemblero.
Go assembler estas stranga besto. Vi verŝajne scias, ke asembla lingvo estas ege ligita al la arkitekturo de la komputilo por kiu vi skribas, sed tio ne estas la kazo en Go. Go-asemblero estas pli kiel IRL (intermedia reprezenta lingvo) aŭ meza lingvo: ĝi estas praktike sendependa de platformo. Rob Pike donis bonegan prezenton pri ĉi tiu temo antaŭ pluraj jaroj ĉe GopherCon en Denvero.
Krome, Go uzas nekutiman Plan 9-formaton, kiu diferencas de la ĝenerale akceptitaj AT&T kaj Intel-formatoj.
Estas sekure diri, ke skribi Go assembler mane ne estas la plej amuza.
Sed, feliĉe, jam ekzistas du altnivelaj iloj, kiuj helpas nin skribi Go assembler: PeachPy kaj avo. Ambaŭ iloj generas Go-asembleron de pli alta nivela kodo skribita en Python kaj Go, respektive.
Ĉi tiuj utilecoj simpligas aferojn kiel registro-asignon, skribajn buklojn, kaj ĝenerale simpligas la procezon eniri la mondon de kunigprogramado en Go.
Ni uzos avo, do niaj programoj estos preskaŭ regulaj Go-programoj.
Jen kiel aspektas la plej simpla ekzemplo de avo-programo. Ni havas ĉef() funkcion, kiu difinas en si la Add() funkcion, kies signifo estas aldoni du nombrojn. Estas helpaj funkcioj ĉi tie por ricevi parametrojn laŭnome kaj akiri unu el la senpagaj kaj taŭgaj procesoraj registroj. Ĉiu procesoroperacio havas respondan funkcion sur avo, kiel vidite en ADDQ. Fine, ni vidas helpan funkcion por stoki la rezultan valoron.
Vokante go generi, ni ekzekutos la programon sur avo kaj kiel rezulto, du dosieroj estos generitaj:
- add.s kun la rezulta kodo en Go-asemblero;
- stub.go kun funkciokapoj por konekti la du mondojn: Go kaj asemblero.
Nun kiam ni vidis, kion faras avo kaj kiel, ni rigardu niajn funkciojn. Mi efektivigis ambaŭ skalarajn kaj vektorajn (SIMD) versiojn de la funkcioj.
Ni rigardu unue la skalarajn versiojn.
Kiel en la antaŭa ekzemplo, ni petas liberan kaj validan ĝeneraluzeblan registron, ni ne bezonas kalkuli ofsetojn kaj grandecojn por la argumentoj. avo faras ĉion ĉi por ni.
Ni kutimis uzi etikedojn kaj goto (aŭ saltoj) por plibonigi rendimenton kaj trompi la Go-kompililon, sed nun ni faras ĝin de la komenco. La punkto estas, ke cikloj estas pli altnivela koncepto. En asemblero, ni havas nur etikedojn kaj saltojn.
La restanta kodo devus jam esti konata kaj komprenebla. Ni kopias buklon kun etikedoj kaj saltoj, prenas malgrandan datumon el niaj du tranĉaĵoj, kombinas ilin per iom da operacio (KAJ NE ĉi-kaze) kaj poste metas la rezulton en la rezultan tranĉaĵon. Ĉiuj.
Jen kiel aspektas la fina asemblerkodo. Ni ne devis kalkuli ofsetojn kaj grandecojn (markitajn verde) aŭ konservi trakon de la uzataj registroj (markitaj ruĝe).
Se ni komparas la agadon de la asembla lingvo-efektivigo kun la agado de la plej bona efektivigo en Go, ni vidos, ke ĝi estas la sama. Kaj ĉi tio estas atendata. Ja ni faris nenion specialan - ni nur reproduktis tion, kion farus Go-kompililo.
Bedaŭrinde, ni ne povas devigi la kompililon enliniigi niajn funkciojn skribitajn en asembla lingvo. La Go-kompililo nuntempe ne havas tian funkcion, kvankam estis peto aldoni ĝin dum sufiĉe da tempo.
Tial estas neeble ricevi ajnan profiton de malgrandaj funkcioj en asembla lingvo. Ni devas aŭ skribi grandajn funkciojn, aŭ uzi la novan pakaĵon matematiko/bitoj, aŭ preteriri la asembleblan lingvon.
Ni nun rigardu la vektorajn versiojn de niaj funkcioj.
Por ĉi tiu ekzemplo, mi decidis uzi AVX2, do ni uzos operaciojn, kiuj funkcias sur 32-bajtaj pecoj. La strukturo de la kodo estas tre simila al la skalara versio: ŝarĝo de parametroj, peti senpagan komunan registron ktp.
Unu novigado estas ke pli larĝaj vektoroperacioj uzas specialajn larĝajn registrojn. En la kazo de 32-bajtaj pecoj, ĉi tiuj estas registroj prefiksitaj kun Y. Jen kial vi vidas la funkcion YMM() en la kodo. Se mi uzus AVX-512 kun 64-bitaj pecoj, la prefikso estus Z.
La dua novigo estas, ke mi decidis uzi optimumigon nomatan buklo unrolling, kio signifas fari ok buklooperaciojn permane antaŭ salti al la komenco de la buklo. Ĉi tiu optimumigo reduktas la nombron da branĉoj en la kodo, kaj estas limigita de la nombro da disponeblaj senpagaj registroj.
Nu, kio pri rendimento? Ŝi estas bela! Ni atingis plirapidigon de proksimume sep fojojn kompare kun la plej bona Go-solvo. Impresa, ĉu ne?
Sed eĉ ĉi tiu efektivigo povus esti akcelita per uzado de AVX-512, antaŭportado aŭ JIT (ĝustatempa kompililo) por la demandplanilo. Sed ĉi tio certe estas temo por aparta raporto.
Problemoj kun bitmapaj indeksoj
Nun kiam ni jam rigardis simplan efektivigon de bitmapa indekso en Go kaj multe pli produktiva en asembla lingvo, ni finfine parolu pri kial bitmapaj indeksoj estas tiel malofte uzataj.
Pli malnovaj artikoloj mencias tri problemojn kun bitmapaj indeksoj, sed pli novaj artikoloj kaj mi argumentas, ke ili ne plu rilatas. Ni ne plonĝos profunde en ĉiun el ĉi tiuj problemoj, sed rigardos ilin supraĵe.
La problemo de alta kardinaleco
Do, oni diras al ni, ke bitmapaj indeksoj taŭgas nur por kampoj kun malalta kardinaleco, tio estas, tiuj, kiuj havas malmultajn valorojn (ekzemple sekso aŭ okulkoloro), kaj la kialo estas, ke la kutima reprezento de tiaj kampoj (unu bito per valoro) en la kazo de alta kardinaleco, ĝi okupos tro da spaco kaj, krome, ĉi tiuj bitmapaj indeksoj estos malbone (malofte) plenigitaj.
Kelkfoje ni povas uzi malsaman prezenton, kiel la norman, kiun ni uzas por reprezenti nombrojn. Sed estis la apero de kunpremaj algoritmoj, kiuj ŝanĝis ĉion. Dum la pasintaj jardekoj, sciencistoj kaj esploristoj elpensis grandan nombron da kunpremaj algoritmoj por bitmapoj. Ilia ĉefa avantaĝo estas, ke ne necesas malkunpremi bitmapojn por fari bitajn operaciojn - ni povas fari bitajn operaciojn rekte sur kunpremitaj bitmapoj.
Lastatempe, hibridaj aliroj komencis aperi, kiel muĝantaj bitmapoj. Ili samtempe uzas tri malsamajn reprezentadojn por bitmapoj - bitmapoj mem, tabeloj kaj tielnomitaj bitaj kuroj - kaj ekvilibrigas inter ili por maksimumigi rendimenton kaj minimumigi memorkonsumon.
Vi povas trovi muĝantajn bitmapojn en la plej popularaj aplikoj. Jam ekzistas grandega nombro da efektivigoj por ampleksa vario de programlingvoj, inkluzive de pli ol tri efektivigoj por Go.
Alia aliro, kiu povas helpi nin trakti altan kardinalecon, estas nomata binning. Imagu, ke vi havas kampon reprezentantan la altecon de persono. Alteco estas glitkoma nombro, sed ni homoj ne pensas pri ĝi tiel. Por ni ne estas diferenco inter alteco 185,2 cm kaj 185,3 cm.
Rezultas, ke ni povas grupigi similajn valorojn en grupojn ene de 1 cm.
Kaj se ni ankaŭ scias, ke tre malmultaj homoj estas malpli longaj ol 50 cm kaj pli altas ol 250 cm, tiam ni povas esence turni kampon kun senfina kardinaleco en kampon kun kardinaleco de ĉirkaŭ 200 valoroj.
Kompreneble, se necese, ni povas fari plian filtradon poste.
Problemo de Alta Bandwidth
La sekva problemo kun bitmapaj indeksoj estas, ke ĝisdatigi ilin povas esti tre multekosta.
Datumbazoj devas povi ĝisdatigi datumojn dum eble centoj da aliaj demandoj serĉas la datumojn. Ni bezonas serurojn por eviti problemojn kun samtempa datuma aliro aŭ aliajn kundividajn problemojn. Kaj kie estas unu granda seruro, estas problemo - seruro disputo, kiam ĉi tiu seruro fariĝas botelkolo.
Ĉi tiu problemo povas esti solvita aŭ evitita per sharding aŭ uzado de versiigitaj indeksoj.
Sharding estas simpla kaj konata afero. Vi povas disigi bitmapan indekson kiel vi farus kun ajna alia datumo. Anstataŭ unu granda seruro, vi ricevos amason da malgrandaj seruroj kaj tiel forigos kluzdisputon.
La dua maniero solvi la problemon estas uzi versionitajn indeksojn. Vi povas havi unu kopion de la indekso, kiun vi uzas por serĉi aŭ legi, kaj unu, kiun vi uzas por skribi aŭ ĝisdatigi. Kaj unufoje en certa tempodaŭro (ekzemple, unufoje ĉiun 100 ms aŭ 500 ms) vi duobligas ilin kaj interŝanĝas ilin. Kompreneble, ĉi tiu aliro estas aplikebla nur en kazoj kie via aplikaĵo povas trakti iomete postrestantan serĉindekson.
Ĉi tiuj du aliroj povas esti uzataj samtempe: vi povas havi shared versionita indekso.
Pli kompleksaj demandoj
La fina problemo kun bitmapaj indeksoj estas, ke oni diras al ni, ke ili ne taŭgas por pli kompleksaj specoj de demandoj, kiel span-demandoj.
Efektive, se vi pensas pri tio, bitaj operacioj kiel AND, OR, ktp. ne tre taŭgas por demandoj al la "Montru al mi hotelojn kun ĉambraj tarifoj de 200 ĝis 300 dolaroj por nokto."
Naiva kaj tre malprudenta solvo estus preni la rezultojn por ĉiu dolarvaloro kaj kombini ilin kun bitbit-AŬ operacio.
Iomete pli bona solvo estus uzi grupigon. Ekzemple, en grupoj de 50 dolaroj. Ĉi tio plirapidigus nian procezon 50 fojojn.
Sed la problemo ankaŭ estas facile solvita per uzado de vido kreita specife por ĉi tiu tipo de peto. En sciencaj artikoloj ĝi estas nomita interval-kodigitaj bitmapoj.
En ĉi tiu reprezento, ni ne nur agordas unu biton por iu valoro (ekzemple, 200), sed starigas ĉi tiun valoron kaj ĉion pli altan. 200 kaj supre. Same por 300: 300 kaj supre. Kaj tiel plu.
Uzante ĉi tiun reprezenton, ni povas respondi ĉi tiun specon de serĉdemando trairante la indekson nur dufoje. Unue, ni ricevos liston de hoteloj, kie la ĉambro kostas malpli aŭ $300, kaj poste ni forigos el ĝi tiujn, kie la ĉambro kostas malpli aŭ $199. Preta.
Vi estos surprizita, sed eĉ geodemandadoj eblas per bitmapaj indeksoj. La lertaĵo estas uzi geometrian reprezenton, kiu ĉirkaŭas vian koordinaton per geometria figuro. Ekzemple, S2 de Guglo. La figuro devus esti ebla reprezenti en la formo de tri aŭ pli intersekcantaj linioj kiuj povas esti numeritaj. Tiel ni povas igi nian geodemandon en plurajn demandojn "laŭ la interspaco" (laŭ ĉi tiuj numeritaj linioj).
Pretaj solvoj
Mi esperas, ke mi iomete interesis vin kaj ke vi nun havas alian utilan ilon en via arsenalo. Se vi iam bezonos fari ion tian, vi scios kiun vojon rigardi.
Tamen, ne ĉiuj havas la tempon, paciencon aŭ rimedojn por krei bitmap-indeksojn de nulo. Precipe pli progresintaj, uzante SIMD, ekzemple.
Feliĉe, ekzistas pluraj pretaj solvoj por helpi vin.
Muĝantaj bitmapoj
Unue, ekzistas tiu sama muĝanta bitmapbiblioteko pri kiu mi jam parolis. Ĝi enhavas ĉiujn necesajn ujojn kaj bitajn operaciojn, kiujn vi bezonos por fari plentaŭgan bitmapan indekson.
Bedaŭrinde, nuntempe, neniu el la Go-efektivigoj uzas SIMD, kio signifas, ke Go-efektivigoj estas malpli efikaj ol C-efektivigoj, ekzemple.
Pilosa
Alia produkto, kiu povas helpi vin, estas Pilosa DBMS, kiu fakte nur havas bitmap-indeksojn. Ĉi tio estas relative nova solvo, sed ĝi gajnas korojn rapide.
Pilosa uzas muĝantajn bitmapojn interne kaj donas al vi la kapablon uzi ilin, simpligas kaj klarigas ĉiujn aferojn, pri kiuj mi parolis supre: grupiĝo, interval-kodigitaj bitmapoj, la koncepto de kampo, ktp.
Ni rapide rigardu ekzemplon pri uzado de Pilosa por respondi demandon, kiun vi jam konas.
La ekzemplo estas tre simila al tio, kion vi vidis antaŭe. Ni kreas klienton al la Pilosa-servilo, kreas indekson kaj la necesajn kampojn, poste plenigas niajn kampojn per hazardaj datumoj kun probabloj kaj, fine, plenumas la konatan demandon.
Post tio, ni uzas NE sur la kampo "multekosta", tiam intersekcas la rezulton (aŭ KAJ ĝin) kun la kampo "teraso" kaj kun la kampo "rezervoj". Kaj finfine, ni ricevas la finan rezulton.
Mi vere esperas, ke en antaŭvidebla estonteco ĉi tiu nova speco de indekso aperos ankaŭ en DBMS-oj kiel MySQL kaj PostgreSQL - bitmap-indeksoj.
konkludo
Se vi ankoraŭ ne ekdormis, dankon. Mi devis mallonge tuŝi multajn temojn pro limigita tempo, sed mi esperas, ke la parolado estis utila kaj eble eĉ motiviga.
Bitmapaj indeksoj estas bone scii, eĉ se vi ne bezonas ilin nun. Lasu ilin esti alia ilo en via ilujo.
Ni rigardis diversajn spektaklotrukojn por Go kaj aferojn, kiujn la Go-kompililo ankoraŭ ne tre bone traktas. Sed ĉi tio estas absolute utila por ĉiu Go-programisto scii.
Tion mi volis diri al vi. Dankon!
fonto: www.habr.com