kynning
Ég gaf þessa skýrslu á ensku á GopherCon Russia 2019 ráðstefnunni í Moskvu og á rússnesku á fundi í Nizhny Novgorod. Við erum að tala um bitmap index - sjaldgæfara en B-tré, en ekki síður áhugavert. Samnýting erindi á ráðstefnunni á ensku og textaafrit á rússnesku.
Við munum skoða hvernig bitmap vísitala virkar, hvenær hún er betri, hvenær hún er verri en aðrar vísitölur og í hvaða tilfellum er hún verulega hraðari en þau; Við skulum sjá hvaða vinsælar DBMS hafa þegar bitmap vísitölur; Við skulum reyna að skrifa okkar eigin í Go. Og „í eftirrétt“ munum við nota tilbúin bókasöfn til að búa til okkar eigin ofurhraða sérhæfða gagnagrunn.
Ég vona virkilega að verkin mín verði gagnleg og áhugaverð fyrir þig. Farðu!
Inngangur
Hæ allir! Klukkan er sex að kvöldi og við erum öll ofboðslega þreytt. Frábær tími til að tala um leiðinlega gagnagrunnsvísitölukenningu, ekki satt? Ekki hafa áhyggjur, ég mun hafa nokkrar línur af frumkóða hér og þar. 🙂
Að öllu gríni slepptu er skýrslan stútfull af upplýsingum og við höfum ekki mikinn tíma. Svo skulum við byrja.
Í dag mun ég tala um eftirfarandi:
- hvað eru vísitölur;
- hvað er bitmap index;
- hvar það er notað og hvar það er EKKI notað og hvers vegna;
- einföld útfærsla í Go og smá glíma við þýðandann;
- örlítið minna einfalt, en mun afkastameiri útfærsla í Go assembler;
- „vandamál“ með punktamyndavísitölum;
- núverandi útfærslur.
Svo hvað eru vísitölur?
Vísitalan er sérstakt gagnaskipulag sem við viðhaldum og uppfærum til viðbótar við aðalgögnin. Það er notað til að flýta fyrir leitinni. Án vísitölu myndi leit krefjast þess að fara algjörlega í gegnum gögnin (ferli sem kallast full skanna), og þetta ferli hefur línulega algrím. En gagnagrunnar innihalda venjulega mikið magn af gögnum og línuleg margbreytileiki er of hægur. Helst myndum við fá logaritmískan eða fastan.
Þetta er gríðarlega flókið viðfangsefni, uppfullt af fíngerðum og skiptingum, en eftir að hafa skoðað áratuga þróun og rannsóknir á gagnagrunni er ég tilbúinn að segja að það eru aðeins fáar aðferðir sem víða eru notaðar til að búa til gagnagrunnaskrár.
Fyrsta aðferðin er að minnka leitarrýmið stigveldis og skipta leitarrýminu í smærri hluta.
Við gerum þetta venjulega með mismunandi trjátegundum. Dæmi væri stór kassi af efni í skápnum þínum sem inniheldur smærri kassa af efnum skipt í mismunandi efni. Ef þú þarft efni, muntu líklega leita að þeim í kassa sem segir "Efni" frekar en einn sem segir "Kökur," ekki satt?
Önnur aðferðin er að velja strax viðkomandi frumefni eða hóp af þáttum. Við gerum þetta í kjötkássakortum eða öfugum vísitölum. Notkun kjötkássakorta er mjög svipuð og fyrra dæmið, en í staðinn fyrir kassa af kössum hefurðu fullt af litlum öskjum af lokahlutum í skápnum þínum.
Þriðja aðferðin er að útrýma þörfinni fyrir leit. Þetta gerum við með því að nota Bloom síur eða kúkafilter. Þeir fyrstu svara samstundis og bjarga þér frá því að þurfa að leita.
Síðasta aðferðin er að nýta til fulls allan þann kraft sem nútíma vélbúnaður gefur okkur. Þetta er nákvæmlega það sem við gerum í bitmap vísitölum. Já, þegar við notum þá þurfum við stundum að fara í gegnum alla vísitöluna, en við gerum það mjög skilvirkt.
Eins og ég sagði er umræðuefnið um gagnagrunnsvísitölur mikið og fullt af málamiðlunum. Þetta þýðir að stundum getum við notað nokkrar aðferðir á sama tíma: ef við þurfum að flýta leitinni enn meira, eða ef við þurfum að ná yfir allar mögulegar leitargerðir.
Í dag mun ég tala um minnst þekkta nálgun þessara - punktamyndavísitölur.
Hver er ég til að tala um þetta efni?
Ég vinn sem liðsstjóri hjá Badoo (kannski þekkir þú aðra vöru okkar, Bumble). Við höfum nú þegar meira en 400 milljónir notenda um allan heim og marga eiginleika sem velja bestu samsvörun fyrir þá. Við gerum þetta með því að nota sérsniðna þjónustu, þar á meðal bitmap vísitölur.
Svo hvað er bitmap index?
Bitmap indexs, eins og nafnið gefur til kynna, nota punktamyndir eða bitasett til að útfæra leitarvísitölu. Frá fuglasjónarmiði samanstendur þessi vísitala af einu eða fleiri slíkum punktamyndum sem tákna hvaða einingar (eins og fólk) og eiginleika þeirra eða færibreytur (aldur, augnlitur osfrv.), og reiknirit sem notar bitaaðgerðir (AND, OR, NOT) ) til að svara leitarfyrirspurninni.
Okkur er sagt að punktamyndavísitölur henti best og séu mjög árangursríkar fyrir tilvik þar sem það eru leitir sem sameina fyrirspurnir í mörgum dálkum með lágan kardináli (hugsaðu um "augnlit" eða "hjúskaparstöðu" á móti eitthvað eins og "fjarlægð frá miðbæ"). En ég mun sýna seinna að þeir virka bara fínt fyrir dálka með háan kardináli líka.
Við skulum skoða einfaldasta dæmið um bitmap index.
Ímyndaðu þér að við höfum lista yfir veitingastaði í Moskvu með tvöfalda eiginleika eins og þessar:
- nálægt neðanjarðarlestinni;
- það er einkabílastæði;
- það er verönd (er með verönd);
- þú getur pantað borð (samþykkir pantanir);
- hentugur fyrir grænmetisætur (vegan friendly);
- dýrt (dýrt).
Við skulum gefa hverjum veitingastað raðnúmer frá 0 og úthluta minni fyrir 6 punktamyndir (eitt fyrir hvern eiginleika). Við munum síðan fylla út þessi bitamynd eftir því hvort veitingastaðurinn hefur þessa eign eða ekki. Ef veitingastaður 4 er með verönd, þá verður biti nr. 4 í bitamyndinni „er með verönd“ stilltur á 1 (ef það er engin verönd, þá á 0).
Nú höfum við einfaldasta bitmap vísitöluna sem hægt er og við getum notað hana til að svara fyrirspurnum eins og:
- „Sýndu mér grænmetisvæna veitingastaði“;
- „Sýndu mér ódýra veitingastaði með verönd þar sem þú getur pantað borð.
Hvernig? Við skulum skoða. Fyrsta beiðnin er mjög einföld. Allt sem við þurfum að gera er að taka „grænmetisvæna“ punktamyndina og breyta því í lista yfir veitingastaði sem eru afhjúpaðir.
Önnur beiðnin er aðeins flóknari. Við þurfum að nota NOT punktamyndina á „dýra“ punktamyndinni til að fá lista yfir ódýra veitingastaði, þá OG það með „get ég pantað borð“ punktamyndina og OG útkomuna með „það er verönd“ punktamynd. Bitmapið sem myndast mun innihalda lista yfir starfsstöðvar sem uppfylla öll skilyrði okkar. Í þessu dæmi er þetta aðeins Yunost veitingastaðurinn.
Það er mikið af kenningum í gangi, en ekki hafa áhyggjur, við munum sjá kóðann mjög fljótlega.
Hvar eru punktamyndavísitölur notaðar?
Ef þú Googler punktamyndaskrár, munu 90% af svörunum tengjast Oracle DB á einn eða annan hátt. En önnur DBMS styðja líklega líka svona flottan hlut, ekki satt? Eiginlega ekki.
Við skulum fara í gegnum listann yfir helstu grunaða.
MySQL styður ekki enn bitmap vísitölur, en það er tillaga sem bendir til þess að bæta við þessum valkosti ().
PostgreSQL styður ekki bitamyndavísitölur, en notar einfaldar punktamyndir og bitaaðgerðir til að sameina leitarniðurstöður yfir margar aðrar vísitölur.
Tarantool er með bitavísitölum og styður einfalda leit á þeim.
Redis er með einföld bitasvið) án þess að geta leitað að þeim.
MongoDB styður ekki enn bitmap vísitölur, en það er líka tillaga sem leggur til að þessum valkosti verði bætt við
Elasticsearch notar punktamyndir innbyrðis).
- En nýr nágranni hefur birst í húsinu okkar: Pilosa. Þetta er nýr gagnagrunnur sem ekki tengist tengslunum skrifaður í Go. Það inniheldur aðeins bitmap vísitölur og byggir allt á þeim. Við tölum um það aðeins síðar.
Innleiðing í Go
En hvers vegna eru punktamyndavísitölur svo sjaldan notaðar? Áður en ég svara þessari spurningu langar mig að sýna þér hvernig á að útfæra mjög einfaldan punktamyndaskrá í Go.
Bitmaps eru í rauninni bara gögn. Í Go skulum við nota bætisneiðar fyrir þetta.
Við höfum eitt bitmap fyrir einn veitingastaðareiginleika og hver biti í bitmapinu gefur til kynna hvort tiltekinn veitingastaður hafi þennan eiginleika eða ekki.
Við þurfum tvær hjálparaðgerðir. Einn verður notaður til að fylla punktamyndir okkar af handahófi gögnum. Tilviljunarkennd, en þó með ákveðnum líkum á að veitingastaðurinn eigi hverja eign. Ég tel til dæmis að það séu mjög fáir veitingastaðir í Moskvu þar sem ekki er hægt að panta borð og mér sýnist að um 20% staða henti grænmetisætum.
Önnur aðgerðin mun breyta punktamyndinni í lista yfir veitingastaði.
Til að svara fyrirspurninni „Sýndu mér ódýra veitingastaði sem eru með verönd og geta pantað“ þurfum við tvær bita aðgerðir: EKKI og OG.
Við getum einfaldað kóðann okkar aðeins með því að nota flóknari AND NOT rekstraraðilann.
Við höfum aðgerðir fyrir hverja af þessum aðgerðum. Báðir fara þeir í gegnum sneiðarnar, taka samsvarandi þætti úr hverri, sameina þá með smáaðgerð og setja útkomuna í sneiðina sem myndast.
Og nú getum við notað punktamyndir okkar og aðgerðir til að svara leitarfyrirspurninni.
Afköst eru ekki svo mikil, jafnvel þó að aðgerðirnar séu mjög einfaldar og við höfum sparað mikla peninga með því að skila ekki nýrri sneið sem myndast í hvert skipti sem aðgerðin var kölluð.
Eftir að hafa gert smá snið með pprof tók ég eftir því að það vantaði eina mjög einfalda en mjög mikilvæga fínstillingu í Go þýðandanum: aðgerðainnbyggingu.
Staðreyndin er sú að Go þýðandinn er hræðilega hræddur við lykkjur sem fara í gegnum sneiðar og neitar því algjörlega að setja inn föll sem innihalda slíkar lykkjur.
En ég er ekki hræddur og ég get blekkt þýðandann með því að nota goto í stað lykkju, eins og í gamla góða daga.
Og eins og þú sérð, nú mun þýðandinn fúslega setja inn aðgerðina okkar! Fyrir vikið náum við að spara um 2 míkrósekúndur. Ekki slæmt!
Auðvelt er að sjá annan flöskuhálsinn ef þú horfir vel á samsetningarúttakið. Þýðandinn bætti við sneiðamörkum beint inn í heitustu lykkjuna okkar. Staðreyndin er sú að Go er öruggt tungumál, þýðandinn er hræddur um að rökin mín þrjú (þrjár sneiðar) séu af mismunandi stærð. Þegar öllu er á botninn hvolft, þá verður fræðilegur möguleiki á að svokallað biðminni yfirfall verði.
Við skulum fullvissa þýðandann með því að sýna honum að allar sneiðar eru jafnstórar. Við getum gert þetta með því að bæta við einfaldri ávísun í upphafi aðgerðarinnar okkar.
Þegar þýðandinn sér þetta sleppir þýðandinn glaður yfir ávísuninni og við endum á því að spara 500 nanósekúndur í viðbót.
Stórir bútar
Allt í lagi, okkur tókst að kreista frammistöðu út úr einföldu útfærslunni okkar, en þessi niðurstaða er í raun mun verri en hægt er með núverandi vélbúnaði.
Allt sem við gerum eru grunnbitaaðgerðir og örgjörvarnir okkar framkvæma þær á mjög skilvirkan hátt. En því miður „fæða“ við örgjörvann okkar með mjög litlum verkum. Aðgerðir okkar framkvæma aðgerðir á bæti fyrir bæti. Við getum mjög auðveldlega lagað kóðann okkar til að vinna með 8-bæta klumpur með því að nota UInt64 sneiðar.
Eins og þú sérð flýtti þessi litla breyting forritinu okkar átta sinnum með því að auka lotustærðina um átta sinnum. Segja má að ávinningurinn sé línulegur.
Innleiðing í assembler
En þetta er ekki endirinn. Örgjörvarnir okkar geta unnið með klumpur af 16, 32 og jafnvel 64 bætum. Slíkar „breiðar“ aðgerðir eru kallaðar margar gögn með einum leiðbeiningum (SIMD; ein leiðbeining, mörg gögn) og ferlið við að umbreyta kóða þannig að það noti slíkar aðgerðir er kallað vektormyndun.
Því miður er Go þýðandinn langt frá því að vera frábær í vektorgreiningu. Eins og er, eina leiðin til að vektorisera Go kóða er að taka og setja þessar aðgerðir handvirkt með Go assembler.
Go assembler er skrítið dýr. Þú veist líklega að samsetningartungumál er eitthvað sem er mjög bundið við arkitektúr tölvunnar sem þú ert að skrifa fyrir, en það er ekki tilfellið í Go. Go assembler er meira eins og IRL (intermediate representation language) eða millimál: það er nánast vettvangsóháð. Rob Pike gaf frábæra frammistöðu um þetta efni fyrir nokkrum árum á GopherCon í Denver.
Að auki notar Go óvenjulegt Plan 9 snið, sem er frábrugðið almennt viðurkenndum AT&T og Intel sniðum.
Það er óhætt að segja að það sé ekki það skemmtilegasta að skrifa Go assembler í höndunum.
En sem betur fer eru nú þegar tvö háþróuð verkfæri sem hjálpa okkur að skrifa Go assembler: PeachPy og avo. Bæði tólin búa til Go assembler úr kóða á hærra stigi sem er skrifaður í Python og Go, í sömu röð.
Þessar tólar einfalda hluti eins og úthlutun skráa, skrifa lykkjur og einfalda almennt ferlið við að komast inn í heim samsetningarforritunar í Go.
Við munum nota avo, þannig að forritin okkar verða nánast venjuleg Go forrit.
Svona lítur einfaldasta dæmið um avo forrit út. Við höfum aðal() fall, sem skilgreinir innra með sér Add() fallið, en merking þess er að leggja saman tvær tölur. Það eru hjálparaðgerðir hér til að fá breytur með nafni og fá einn af ókeypis og hentugum örgjörvaskrám. Hver örgjörvaaðgerð hefur samsvarandi aðgerð á avo, eins og sést í ADDQ. Að lokum sjáum við hjálparaðgerð til að geyma gildið sem myndast.
Með því að kalla á go generate munum við keyra forritið á avo og fyrir vikið verða tvær skrár búnar til:
- add.s með kóðanum sem myndast í Go assembler;
- stub.go með aðgerðahausum til að tengja saman heimana tvo: Go og assembler.
Nú þegar við höfum séð hvað avo gerir og hvernig, skulum við skoða aðgerðir okkar. Ég útfærði bæði scalar og vektor (SIMD) útgáfur af aðgerðunum.
Við skulum fyrst skoða scalar útgáfurnar.
Eins og í fyrra dæminu erum við að biðja um ókeypis og gilda almenna skrá, við þurfum ekki að reikna út frávik og stærðir fyrir rökin. avo gerir þetta allt fyrir okkur.
Við notuðum merkimiða og goto (eða stökk) til að bæta árangur og plata Go þýðandann, en núna erum við að gera það frá upphafi. Málið er að hringrásir eru hugtak á hærra stigi. Í assembler erum við bara með merkimiða og stökk.
Kóðinn sem eftir er ætti nú þegar að vera kunnuglegur og skiljanlegur. Við líkjum eftir lykkju með merkimiðum og stökkum, tökum lítið gagnastykki úr sneiðunum okkar tveimur, sameinum þær með smáaðgerð (OG EKKI í þessu tilfelli) og setjum svo niðurstöðuna í sneiðina sem myndast. Allt.
Svona lítur lokasamsetningarkóði út. Við þurftum ekki að reikna út frávik og stærðir (merktar með grænu) eða halda utan um skrárnar sem notaðar voru (merktar með rauðu).
Ef við berum saman frammistöðu samsetningarmálsútfærslunnar við frammistöðu bestu útfærslu í Go, sjáum við að það er það sama. Og þetta er gert ráð fyrir. Enda gerðum við ekkert sérstakt - við endurgerðum bara það sem Go þýðandi myndi gera.
Því miður getum við ekki þvingað þýðandann til að setja inn aðgerðir okkar sem eru skrifaðar á samsetningartungumáli. Go þýðandinn hefur ekki slíkan eiginleika eins og er, þó það hafi verið beðið um að bæta honum við í nokkuð langan tíma.
Þess vegna er ómögulegt að njóta góðs af litlum aðgerðum á samsetningarmáli. Við þurfum annað hvort að skrifa stórar aðgerðir, eða nota nýja stærðfræði/bita pakkann, eða framhjá assembler tungumálinu.
Við skulum nú líta á vektorútgáfur aðgerða okkar.
Fyrir þetta dæmi ákvað ég að nota AVX2, þannig að við munum nota aðgerðir sem starfa á 32-bæta klumpur. Uppbygging kóðans er mjög svipuð scalar útgáfunni: hleðsla breytur, biðja um ókeypis sameiginlega skrá o.s.frv.
Ein nýjung er sú að víðtækari vektoraðgerðir nota sérstaka breiðar skrár. Ef um 32-bæta klumpur er að ræða eru þetta skrár með Y. Þetta er ástæðan fyrir því að þú sérð YMM() fallið í kóðanum. Ef ég væri að nota AVX-512 með 64 bita klumpur væri forskeytið Z.
Önnur nýjungin er sú að ég ákvað að nota hagræðingu sem kallast loop unrolling, sem þýðir að gera átta lykkjuaðgerðir handvirkt áður en ég hoppaði í byrjun lykkjunnar. Þessi hagræðing dregur úr fjölda útibúa í kóðanum og takmarkast af fjölda ókeypis skráninga í boði.
Jæja, hvað með frammistöðu? Hún er falleg! Við náðum um það bil sjö sinnum hraða miðað við bestu Go lausnina. Áhrifamikið, ekki satt?
En jafnvel þessari útfærslu gæti hugsanlega verið hraðað með því að nota AVX-512, forsækni eða JIT (just-in-time þýðanda) fyrir fyrirspurnartímaáætlunina. En þetta er vissulega efni fyrir sérstaka skýrslu.
Vandamál með bitmap vísitölur
Nú þegar við höfum þegar skoðað einfalda útfærslu á bitmap index í Go og mun afkastameiri á samsetningarmáli, skulum við að lokum tala um hvers vegna bitmap indexs eru svo sjaldan notaðir.
Í eldri blöðum er minnst á þrjú vandamál með punktamyndaskrár, en nýrri blöð og ég höldum því fram að þau eigi ekki lengur við. Við munum ekki kafa djúpt í hvert og eitt þessara vandamála heldur skoða þau yfirborðslega.
Vandamálið við háan kardinalitet
Þannig að okkur er sagt að punktamyndavísitölur séu aðeins hentugar fyrir reiti með lágt aðalgildi, það er þá sem hafa fá gildi (til dæmis kyn eða augnlit), og ástæðan er sú að venjuleg framsetning slíkra reita (einn bita fyrir hvert gildi) ef um er að ræða háan kardinalitet mun það taka of mikið pláss og þar að auki verða þessar bitamyndavísitölur illa (sjaldan) fylltar.
Stundum gætum við notað aðra framsetningu, eins og staðlaða sem við notum til að tákna tölur. En það var tilkoma þjöppunaralgríma sem breytti öllu. Undanfarna áratugi hafa vísindamenn og vísindamenn komið með mikinn fjölda þjöppunaralgríma fyrir punktamyndir. Helsti kostur þeirra er sá að það er engin þörf á að þjappa bitamyndum niður til að framkvæma bitaaðgerðir - við getum framkvæmt bitaaðgerðir beint á þjöppuð bitamynd.
Nýlega hafa blendingsaðferðir farið að birtast, eins og öskrandi punktamyndir. Þeir nota samtímis þrjár mismunandi framsetningar fyrir punktamyndir - bitamyndir sjálfar, fylki og svokallaðar bitakeyrslur - og koma jafnvægi á milli þeirra til að hámarka afköst og lágmarka minnisnotkun.
Þú getur fundið öskrandi punktamyndir í vinsælustu forritunum. Nú þegar er til mikill fjöldi útfærslur fyrir margs konar forritunarmál, þar á meðal fleiri en þrjár útfærslur fyrir Go.
Önnur nálgun sem getur hjálpað okkur að takast á við mikla kardinalitet er kölluð binning. Ímyndaðu þér að þú sért með reit sem táknar hæð manns. Hæð er flottala en við mennirnir hugsum það ekki þannig. Fyrir okkur er enginn munur á hæð 185,2 cm og 185,3 cm.
Það kemur í ljós að við getum flokkað svipuð gildi í hópa innan 1 cm.
Og ef við vitum líka að mjög fáir eru lægri en 50 cm og hærri en 250 cm, þá getum við í raun og veru breytt sviði með óendanlega kardinalitet í reit með kardinalitet upp á um 200 gildi.
Auðvitað, ef nauðsyn krefur, getum við gert viðbótarsíun á eftir.
Vandamál með mikla bandbreidd
Næsta vandamál með bitmap vísitölur er að uppfærsla þeirra getur verið mjög dýr.
Gagnasöfn verða að geta uppfært gögn á meðan hugsanlega hundruð annarra fyrirspurna leita í gögnunum. Við þurfum læsingar til að forðast vandamál með samhliða gagnaaðgangi eða öðrum samnýtingarvandamálum. Og þar sem það er einn stór lás, það er vandamál - lás deilur, þegar þessi lás verður flöskuháls.
Þetta vandamál er hægt að leysa eða sniðganga með því að nota klippingu eða nota útgáfur af vísitölum.
Skurður er einfaldur og vel þekktur hlutur. Þú getur brotið bitamyndaskrá eins og önnur gögn. Í stað eins stórs læsingar færðu fullt af litlum læsingum og losnar þannig við læsingardeilur.
Önnur leiðin til að leysa vandamálið er að nota útgáfur af vísitölum. Þú getur haft eitt eintak af skránni sem þú notar til að leita eða lesa og eitt sem þú notar til að skrifa eða uppfæra. Og einu sinni á ákveðnu tímabili (til dæmis einu sinni á 100 ms eða 500 ms fresti) afritarðu þau og skiptir um þau. Auðvitað á þessi nálgun aðeins við í þeim tilvikum þar sem umsókn þín þolir örlítið seinkar leitarvísitölu.
Þessar tvær aðferðir er hægt að nota samtímis: þú getur haft brotna útgáfa vísitölu.
Flóknari fyrirspurnir
Lokavandamálið með punktamyndavísitölum er að okkur er sagt að þær henti ekki vel fyrir flóknari tegundir fyrirspurna, svo sem spanfyrirspurnir.
Reyndar, ef þú hugsar um það, þá eru bitaaðgerðir eins og AND, OR, osfrv. ekki mjög hentugar fyrir fyrirspurnir a la "Sýndu mér hótel með herbergisverði frá 200 til 300 dollara á nótt."
Barnlaus og mjög óskynsamleg lausn væri að taka niðurstöðurnar fyrir hvert dollaragildi og sameina þær með bitvísri OR-aðgerð.
Örlítið betri lausn væri að nota hópa. Til dæmis í hópum upp á 50 dollara. Þetta myndi flýta ferli okkar um 50 sinnum.
En vandamálið er líka auðvelt að leysa með því að nota útsýni sem er búið til sérstaklega fyrir þessa tegund af beiðnum. Í vísindaritum er það kallað sviðskóðuð bitamynd.
Í þessari framsetningu setjum við ekki bara einn bita fyrir eitthvað gildi (til dæmis 200), heldur setjum við þetta gildi og allt hærra. 200 og yfir. Sama fyrir 300:300 og yfir. Og svo framvegis.
Með því að nota þessa framsetningu getum við svarað þessari tegund leitarfyrirspurnar með því að fara aðeins tvisvar yfir vísitöluna. Fyrst fáum við lista yfir hótel þar sem herbergið kostar minna eða $300, og síðan munum við fjarlægja úr honum þau þar sem herbergiskostnaður er minna eða $199. Tilbúið.
Þú verður hissa, en jafnvel landaspurningar eru mögulegar með því að nota bitmap vísitölur. Galdurinn er að nota rúmfræðilega framsetningu sem umlykur hnitið þitt með rúmfræðilegri mynd. Til dæmis, S2 frá Google. Myndin verður að vera hægt að tákna í formi þriggja eða fleiri lína sem skerast sem hægt er að númera. Þannig getum við breytt landfræðilegri fyrirspurn okkar í nokkrar fyrirspurnir „meðfram bilinu“ (eftir þessum tölusettu línum).
Tilbúnar lausnir
Ég vona að ég hafi áhuga á þér og þú hefur nú annað gagnlegt tól í vopnabúrinu þínu. Ef þú þarft einhvern tíma að gera eitthvað eins og þetta, þá veistu í hvaða átt þú átt að leita.
Hins vegar hafa ekki allir tíma, þolinmæði eða fjármagn til að búa til punktamyndaskrár frá grunni. Sérstaklega fullkomnari, með SIMD, til dæmis.
Sem betur fer eru nokkrar tilbúnar lausnir til að hjálpa þér.
Öskrandi punktamyndir
Í fyrsta lagi er það sama öskrandi punktamyndasafnið og ég talaði þegar um. Það inniheldur öll nauðsynleg ílát og bitaaðgerðir sem þú þarft til að búa til fullgilda punktamyndavísitölu.
Því miður, í augnablikinu, notar engin af Go útfærslum SIMD, sem þýðir að Go útfærslur eru minna árangursríkar en C útfærslur, til dæmis.
loðinn
Önnur vara sem getur hjálpað þér er Pilosa DBMS, sem í rauninni hefur aðeins bitamyndavísitölur. Þetta er tiltölulega ný lausn, en hún vinnur hjörtu á miklum hraða.
Pilosa notar öskrandi punktamyndir innbyrðis og gefur þér möguleika á að nota þau, einfaldar og útskýrir allt það sem ég talaði um hér að ofan: flokkun, sviðskóðuð punktamynd, hugtakið reit o.s.frv.
Lítum fljótt á dæmi um notkun Pilosa til að svara spurningu sem þú ert nú þegar kunnugur.
Dæmið er mjög svipað því sem þú sást áður. Við búum til viðskiptavin á Pilosa þjóninum, búum til vísitölu og nauðsynlega reiti, fyllum síðan reiti okkar af handahófi gögnum með líkindum og að lokum framkvæmum við kunnuglega fyrirspurnina.
Eftir það notum við EKKI á "dýra" reitinn, skerum síðan niðurstöðuna (eða OG hana) við "verönd" reitinn og með reitnum "pantanir". Og loksins fáum við lokaniðurstöðuna.
Ég vona virkilega að í fyrirsjáanlegri framtíð muni þessi nýja tegund af vísitölu einnig birtast í DBMS eins og MySQL og PostgreSQL - bitmap indexes.
Ályktun
Ef þú hefur ekki sofnað ennþá, takk fyrir. Ég þurfti að koma stuttlega inn á mörg efni vegna takmarkaðs tíma, en ég vona að erindið hafi verið gagnlegt og jafnvel hvetjandi.
Bitmap vísitölur er gott að vita um, jafnvel þótt þú þurfir þá ekki núna. Láttu þá vera annað verkfæri í verkfærakistunni þinni.
Við höfum skoðað ýmis frammistöðubrellur fyrir Go og hluti sem Go þýðandinn höndlar ekki mjög vel ennþá. En þetta er algerlega gagnlegt fyrir alla Go forritara að vita.
Það var allt sem ég vildi segja þér. Þakka þér fyrir!
Heimild: www.habr.com