esittely
Esitin tämän raportin englanniksi GopherCon Russia 2019 -konferenssissa Moskovassa ja venäjäksi tapaamisessa Nižni Novgorodissa. Puhumme bittikarttaindeksistä - vähemmän yleisestä kuin B-puu, mutta ei vähemmän kiinnostava. Jakaminen konferenssin puheet englanniksi ja tekstit venäjäksi.
Tarkastellaan kuinka bittikarttaindeksi toimii, milloin se on parempi, milloin se on huonompi kuin muut indeksit ja missä tapauksissa se on niitä huomattavasti nopeampi; Katsotaanpa, millä suosituilla DBMS-järjestelmillä on jo bittikarttaindeksit; Yritetään kirjoittaa omamme Go-sovellukseen. Ja "jälkiruoaksi" käytämme valmiita kirjastoja oman supernopean erikoistuneen tietokannan luomiseen.
Toivon todella, että teoksistani on sinulle hyötyä ja mielenkiintoa. Mennä!
Esittely
Hei kaikki! Kello on kuusi illalla ja olemme kaikki erittäin väsyneitä. Hyvä aika puhua tylsästä tietokantaindeksiteoriasta, eikö niin? Älä huoli, minulla on pari riviä lähdekoodia siellä täällä. 🙂
Kaikki vitsit sivuun, raportti on täynnä tietoa, eikä meillä ole paljon aikaa. Joten aloitetaan.
Tänään puhun seuraavista:
- mitä ovat indeksit;
- mikä on bittikarttaindeksi;
- missä sitä käytetään ja missä sitä EI käytetä ja miksi;
- yksinkertainen toteutus Gossa ja pieni kamppailu kääntäjän kanssa;
- hieman vähemmän yksinkertainen, mutta paljon tuottavampi toteutus Go assemblerissa;
- bittikarttaindeksien "ongelmat";
- olemassa olevista toteutuksista.
Mitä ovat indeksit?
Indeksi on erillinen tietorakenne, jota ylläpidämme ja päivitämme päätietojen lisäksi. Sitä käytetään nopeuttamaan hakua. Ilman indeksejä haku vaatisi tietojen läpikäymistä kokonaan (täysi skannaus), ja tällä prosessilla on lineaarinen algoritminen monimutkaisuus. Mutta tietokannat sisältävät yleensä valtavia määriä tietoa ja lineaarinen monimutkaisuus on liian hidasta. Ihannetapauksessa saisimme logaritmisen tai vakion.
Tämä on erittäin monimutkainen aihe, täynnä hienouksia ja kompromisseja, mutta vuosikymmeniä kestäneen tietokannan kehittämisen ja tutkimuksen jälkeen olen valmis sanomaan, että tietokantaindeksien luomiseen on vain muutamia laajalti käytettyjä lähestymistapoja.
Ensimmäinen lähestymistapa on hierarkkisesti pienentää hakutilaa jakamalla hakutila pienempiin osiin.
Yleensä teemme tämän käyttämällä erilaisia puita. Esimerkkinä voisi olla iso materiaalilaatikko kaapissasi, joka sisältää pienempiä laatikoita eri aiheisiin jaoteltuina. Jos tarvitset materiaaleja, etsit niitä luultavasti laatikosta, jossa lukee "Materiaalit" eikä "Evästeet", eikö niin?
Toinen tapa on valita haluttu elementti tai elementtiryhmä välittömästi. Teemme tämän hash-kartoissa tai käänteisissä indekseissä. Hash-karttojen käyttäminen on hyvin samanlaista kuin edellinen esimerkki, mutta laatikoiden sijaan sinulla on kaapissasi joukko pieniä laatikoita lopullisia esineitä.
Kolmas tapa on poistaa etsintätarve. Teemme tämän käyttämällä Bloom- tai käkisuodattimia. Ensimmäiset antavat vastauksen välittömästi, jolloin et joudu etsimään.
Viimeinen lähestymistapa on hyödyntää täysimääräisesti kaikkea nykyaikaisen laitteiston tarjoamaa voimaa. Tämä on juuri se, mitä teemme bittikarttahakemistoissa. Kyllä, niitä käytettäessä meidän täytyy joskus käydä läpi koko indeksi, mutta teemme sen erittäin tehokkaasti.
Kuten sanoin, tietokantahakemistojen aihe on laaja ja täynnä kompromisseja. Tämä tarkoittaa, että joskus voimme käyttää useita lähestymistapoja samanaikaisesti: jos meidän täytyy nopeuttaa hakua vielä enemmän tai jos meidän on katettava kaikki mahdolliset hakutyypit.
Tänään puhun näistä vähiten tunnetusta lähestymistavasta - bittikartta-indekseistä.
Kuka minä olen puhumaan tästä aiheesta?
Työskentelen ryhmäjohtajana Badoossa (ehkä tunnet paremmin toisen tuotteemme, Bumblen). Meillä on jo yli 400 miljoonaa käyttäjää ympäri maailmaa ja monia ominaisuuksia, jotka valitsevat heille parhaiten sopivan. Teemme tämän käyttämällä mukautettuja palveluita, mukaan lukien bittikarttahakemistot.
Joten mikä on bittikarttaindeksi?
Bittikarttaindeksit, kuten nimestä voi päätellä, käyttävät bittikarttoja tai bittijoukkoja hakuindeksin toteuttamiseen. Lintuperspektiivistä katsottuna tämä indeksi koostuu yhdestä tai useammasta tällaisesta bittikartasta, joka edustaa mitä tahansa entiteettiä (kuten ihmisiä) ja niiden ominaisuuksia tai parametreja (ikä, silmien väri jne.), sekä algoritmista, joka käyttää bittitoimintoja (AND, OR, NOT). ) vastataksesi hakukyselyyn.
Meille kerrotaan, että bittikarttahakemistot soveltuvat parhaiten ja ovat erittäin tehokkaita tapauksiin, joissa on hakuja, jotka yhdistävät kyselyitä useissa matalan kardinaalisuuden sarakkeissa (ajattele "silmien väriä" tai "siviilisäätyä" verrattuna esimerkiksi "etäisyys kaupungin keskustasta"). Mutta näytän myöhemmin, että ne toimivat hienosti myös korkean kardinaalisuuden sarakkeissa.
Katsotaanpa yksinkertaisinta esimerkkiä bittikarttaindeksistä.
Kuvittele, että meillä on luettelo Moskovan ravintoloista, joilla on seuraavat binaariset ominaisuudet:
- lähellä metroa;
- on yksityinen pysäköintialue;
- on veranta (on terassi);
- voit varata pöydän (hyväksyy varaukset);
- sopii kasvissyöjille (vegaaniystävällinen);
- kallis (kallis).
Annetaan jokaiselle ravintolalle järjestysnumero alkaen 0 ja varataan muisti 6 bittikartalle (yksi kullekin ominaisuudelle). Täytämme sitten nämä bittikartat sen mukaan, onko ravintolalla tämä omaisuus vai ei. Jos ravintolassa 4 on veranta, bitti nro 4 bittikartassa "on veranta" asetetaan arvoon 1 (jos verantaa ei ole, niin 0).
Nyt meillä on yksinkertaisin mahdollinen bittikarttaindeksi, ja voimme käyttää sitä vastaamaan kyselyihin, kuten:
- "Näytä minulle kasvissyöjille sopivia ravintoloita";
- "Näytä minulle edullisia ravintoloita, joissa on veranta, josta voit varata pöydän."
Miten? Katsotaanpa. Ensimmäinen pyyntö on hyvin yksinkertainen. Meidän tarvitsee vain ottaa "kasvissyöjille sopiva" bittikartta ja muuttaa se luetteloksi ravintoloista, joiden palaset ovat esillä.
Toinen pyyntö on hieman monimutkaisempi. Meidän on käytettävä EI-bittikartta "kallis" bittikartalla saadakseen luettelon edullisista ravintoloista, sitten JA sitä "Voinko varata pöydän" -bittikartan ja JA tulosta "on veranta" -bittikartan kanssa. Tuloksena oleva bittikartta sisältää luettelon laitoksista, jotka täyttävät kaikki kriteerimme. Tässä esimerkissä tämä on vain Yunost-ravintola.
Siihen liittyy paljon teoriaa, mutta älä huoli, näemme koodin hyvin pian.
Missä bittikartta-indeksejä käytetään?
Jos googletat bittikartta-indeksejä, 90% vastauksista liittyy tavalla tai toisella Oracle DB:hen. Mutta luultavasti myös muut DBMS:t tukevat tällaista hienoa asiaa, eikö? Ei oikeastaan.
Käydään läpi tärkeimpien epäiltyjen luettelo.
MySQL ei vielä tue bittikartta-indeksejä, mutta on olemassa ehdotus, joka ehdottaa tämän vaihtoehdon lisäämistä ().
PostgreSQL ei tue bittikartta-indeksejä, mutta käyttää yksinkertaisia bittikarttoja ja bittitoimintoja yhdistääkseen hakutuloksia useista muista indekseistä.
Tarantoolilla on bittijoukon indeksit ja se tukee niiden yksinkertaisia hakuja.
Redissä on yksinkertaiset bittikentät) ilman kykyä etsiä niitä.
MongoDB ei vielä tue bittikartta-indeksejä, mutta on myös ehdotus, joka ehdottaa tämän vaihtoehdon lisäämistä
Elasticsearch käyttää bittikarttoja sisäisesti).
- Mutta taloomme on ilmestynyt uusi naapuri: Pilosa. Tämä on uusi ei-relaatiotietokanta, joka on kirjoitettu Go-kielellä. Se sisältää vain bittikarttaindeksit ja perustaa kaiken niihin. Puhumme siitä hieman myöhemmin.
Toteutus Gossa
Mutta miksi bittikartta-indeksejä käytetään niin harvoin? Ennen kuin vastaan tähän kysymykseen, haluaisin näyttää sinulle, kuinka hyvin yksinkertainen bittikarttaindeksi toteutetaan Gossa.
Bittikartat ovat pohjimmiltaan vain datakappaleita. Käytetään Go:ssa tähän tavuviipaleita.
Meillä on yksi bittikartta yhdelle ravintolaominaisuudelle, ja jokainen bittikartan bitti osoittaa, onko tietyllä ravintolalla tämä ominaisuus vai ei.
Tarvitsemme kaksi aputoimintoa. Yhtä käytetään bittikarttojen täyttämiseen satunnaisilla tiedoilla. Satunnainen, mutta tietyllä todennäköisyydellä, että ravintolassa on jokainen omaisuus. Uskon esimerkiksi, että Moskovassa on hyvin vähän ravintoloita, joissa ei voi varata pöytää, ja minusta näyttää, että noin 20% laitoksista sopii kasvissyöjille.
Toinen toiminto muuntaa bittikartan ravintolaluetteloksi.
Vastataksemme kyselyyn "Näytä edullisia ravintoloita, joissa on patio ja jotka voivat tehdä varauksia" tarvitsemme kaksi bittioperaatiota: NOT ja AND.
Voimme yksinkertaistaa koodiamme hieman käyttämällä monimutkaisempaa AND NOT -operaattoria.
Meillä on toimintoja jokaiselle näistä toiminnoista. Molemmat käyvät siivujen läpi, ottavat kustakin vastaavat elementit, yhdistävät ne bittioperaatiolla ja laittavat tuloksen tuloksena olevaan viipaleeseen.
Ja nyt voimme käyttää bittikarttojamme ja toimintojamme vastataksemme hakukyselyyn.
Suorituskyky ei ole niin korkea, vaikka funktiot ovat hyvin yksinkertaisia ja säästimme paljon rahaa, kun emme palauttaneet uutta tuloksena olevaa viipaletta joka kerta, kun funktiota kutsuttiin.
Profiloinnin jälkeen pprofilla huomasin, että Go-kääntäjästä puuttui yksi hyvin yksinkertainen mutta erittäin tärkeä optimointi: funktion inlining.
Tosiasia on, että Go-kääntäjä pelkää hirveästi silmukoita, jotka kulkevat osien läpi, ja kieltäytyy kategorisesti sisällyttämästä toimintoja, jotka sisältävät tällaisia silmukoita.
Mutta en pelkää ja voin huijata kääntäjää käyttämällä gotoa silmukan sijaan, kuten vanhoina hyvinä aikoina.
Ja kuten näet, nyt kääntäjä lisää mielellään toimintaamme! Tämän seurauksena onnistumme säästämään noin 2 mikrosekuntia. Ei paha!
Toinen pullonkaula on helppo havaita, jos katsot tarkasti kokoonpanon tuottoa. Kääntäjä lisäsi viipaleiden rajatarkistuksen suoraan kuumimpaan silmukkaan. Tosiasia on, että Go on turvallinen kieli, kääntäjä pelkää, että kolme argumenttiani (kolme viipaletta) ovat erikokoisia. Loppujen lopuksi on olemassa teoreettinen mahdollisuus niin kutsutun puskurin ylivuodon esiintymiseen.
Vakuutetaan kääntäjää osoittamalla, että kaikki viipaleet ovat samankokoisia. Voimme tehdä tämän lisäämällä yksinkertaisen tarkistuksen toimintomme alkuun.
Tämän nähdessään kääntäjä ohittaa tyytyväisenä tarkistuksen, ja lopulta säästämme vielä 500 nanosekuntia.
Isoja paukkuja
Okei, onnistuimme puristamaan jonkin verran suorituskykyä yksinkertaisesta toteutuksestamme, mutta tämä tulos on itse asiassa paljon huonompi kuin nykyisellä laitteistolla on mahdollista.
Teemme vain perusbittitoimintoja, ja prosessorimme suorittavat ne erittäin tehokkaasti. Mutta valitettavasti "ruokimme" prosessorimme hyvin pienillä osilla. Toimintomme suorittavat toimintoja tavu kerrallaan. Voimme helposti muokata koodiamme toimimaan 8-tavuisten osien kanssa käyttämällä UInt64-lohkoja.
Kuten näette, tämä pieni muutos nopeutti ohjelmaamme kahdeksan kertaa suurentamalla eräkokoa kahdeksan kertaa. Voiton voidaan sanoa olevan lineaarinen.
Toteutus assemblerissä
Mutta tämä ei ole loppu. Prosessorimme voivat työskennellä 16, 32 ja jopa 64 tavun osien kanssa. Tällaisia "leveitä" operaatioita kutsutaan yhden käskyn useaksi dataksi (SIMD; yksi käsky, monta dataa), ja prosessia koodin muuntamiseksi siten, että se käyttää tällaisia operaatioita, kutsutaan vektoroinniksi.
Valitettavasti Go-kääntäjä ei ole kaukana erinomaisesta vektorisoinnissa. Tällä hetkellä ainoa tapa vektorisoida Go-koodi on ottaa ja laittaa nämä toiminnot manuaalisesti Go assemblerilla.
Go assembler on outo peto. Tiedät luultavasti, että kokoonpanokieli on vahvasti sidottu sen tietokoneen arkkitehtuuriin, jolle kirjoitat, mutta näin ei ole Gossa. Go assembler on enemmän kuin IRL (intermediate representation language) tai välikieli: se on käytännössä alustariippumaton. Rob Pike teki erinomaisen suorituksen tästä aiheesta useita vuosia sitten GopherConissa Denverissä.
Lisäksi Go käyttää epätavallista Plan 9 -muotoa, joka eroaa yleisesti hyväksytyistä AT&T- ja Intel-formaateista.
On turvallista sanoa, että Go assemblerin kirjoittaminen käsin ei ole hauskinta.
Mutta onneksi on jo olemassa kaksi korkean tason työkalua, jotka auttavat meitä kirjoittamaan Go assemblerin: PeachPy ja avo. Molemmat apuohjelmat luovat Go-asennusohjelman Pythonissa ja Gossa kirjoitetusta korkeamman tason koodista.
Nämä apuohjelmat yksinkertaistavat asioita, kuten rekisterien allokointia, kirjoitussilmukoita ja yleensä yksinkertaistavat prosessia päästäksesi kokoonpanoohjelmoinnin maailmaan Gossa.
Käytämme avo-ohjelmaa, joten ohjelmamme ovat lähes tavallisia Go-ohjelmia.
Tältä näyttää yksinkertaisin esimerkki avo-ohjelmasta. Meillä on main()-funktio, joka määrittelee itsessään Add()-funktion, jonka tarkoitus on lisätä kaksi numeroa. Täällä on aputoimintoja parametrien hakemiseen nimellä ja jonkin ilmaisista ja sopivista prosessorirekistereistä. Jokaisella prosessorin toiminnolla on vastaava toiminto avossa, kuten näkyy ADDQ:ssa. Lopuksi näemme aputoiminnon tuloksena olevan arvon tallentamiseksi.
Kutsumalla go generate, suoritamme ohjelman avolla ja tuloksena syntyy kaksi tiedostoa:
- add.s ja tuloksena oleva koodi Go assemblerissa;
- stub.go toimintootsikoilla yhdistääksesi kaksi maailmaa: Go ja assembler.
Nyt kun olemme nähneet mitä avo tekee ja miten, katsotaanpa toimintojamme. Toteutin funktioista sekä skalaari- että vektoriversiot (SIMD).
Katsotaanpa ensin skalaariversioita.
Kuten edellisessä esimerkissä, pyydämme ilmaista ja voimassa olevaa yleiskäyttöistä rekisteriä, meidän ei tarvitse laskea poikkeamia ja kokoja argumenteille. avo tekee kaiken tämän puolestamme.
Käytimme tunnisteita ja gotoa (tai hyppyjä) suorituskyvyn parantamiseen ja Go-kääntäjän huijaamiseen, mutta nyt teemme sen alusta alkaen. Asia on siinä, että syklit ovat korkeamman tason käsite. Assemblerissa meillä on vain etiketit ja hyppyjä.
Lopun koodin pitäisi olla jo tuttua ja ymmärrettävää. Emuloimme silmukkaa etiketeillä ja hyppyillä, otamme pienen osan dataa kahdesta siivuistamme, yhdistämme ne bittioperaatiolla (EI tässä tapauksessa) ja laitamme sitten tuloksen tuloksena olevaan siivuun. Kaikki.
Tältä lopullinen assembler-koodi näyttää. Meidän ei tarvinnut laskea siirtymiä ja kokoja (korostettu vihreällä) tai seurata käytettyjä rekistereitä (korostettu punaisella).
Jos vertaamme kokoonpanokielen toteutuksen suorituskykyä Go:n parhaan toteutuksen suorituskykyyn, näemme, että se on sama. Ja tätä odotetaan. Loppujen lopuksi emme tehneet mitään erityistä - toisimme vain sen, mitä Go-kääntäjä tekisi.
Valitettavasti emme voi pakottaa kääntäjää sisällyttämään toimintojamme kokoonpanokielellä. Go-kääntäjässä ei tällä hetkellä ole tällaista ominaisuutta, vaikka sen lisäämistä on pyydetty jo jonkin aikaa.
Tästä syystä on mahdotonta saada mitään hyötyä pienistä toiminnoista assembly-kielellä. Meidän täytyy joko kirjoittaa suuria funktioita tai käyttää uutta math/bits-pakettia tai ohittaa assembler-kieli.
Katsotaan nyt funktioidemme vektoriversioita.
Tässä esimerkissä päätin käyttää AVX2:ta, joten käytämme toimintoja, jotka toimivat 32-tavuisilla paloilla. Koodin rakenne on hyvin samanlainen kuin skalaariversio: parametrien lataaminen, ilmaisen jaetun rekisterin pyytäminen jne.
Yksi innovaatio on se, että laajemmissa vektorioperaatioissa käytetään erityisiä leveitä rekistereitä. 32-tavuisten kappaleiden tapauksessa nämä ovat rekistereitä, joiden etuliite on Y. Tästä syystä näet koodissa YMM()-funktion. Jos käyttäisin AVX-512:ta 64-bittisillä paloilla, etuliite olisi Z.
Toinen innovaatio on, että päätin käyttää optimointia nimeltä loop unrolling, mikä tarkoittaa kahdeksan silmukkaoperaation tekemistä manuaalisesti ennen kuin hyppään silmukan alkuun. Tämä optimointi vähentää koodin haarojen määrää, ja sitä rajoittaa käytettävissä olevien ilmaisten rekisterien määrä.
No, entä suorituskyky? Hän on kaunis! Saimme noin seitsemän kertaa nopeuden parhaaseen Go-ratkaisuun verrattuna. Vaikuttavaa, eikö?
Mutta jopa tätä toteutusta voitaisiin mahdollisesti nopeuttaa käyttämällä AVX-512:ta, esihakua tai JIT:tä (just-in-time-kääntäjä) kyselyn ajoittimessa. Mutta tämä on varmasti erillisen raportin aihe.
Ongelmia bittikarttahakemistojen kanssa
Nyt kun olemme jo tarkastelleet yksinkertaista bittikarttaindeksin toteutusta Gossa ja paljon tuottavampaa asennuskielellä, puhutaan lopuksi siitä, miksi bittikartta-indeksejä käytetään niin harvoin.
Vanhemmat paperit mainitsevat kolme ongelmaa bittikarttaindeksien kanssa, mutta uudemmat paperit ja väitän, että ne eivät ole enää relevantteja. Emme sukeltaa syvällisesti jokaiseen näistä ongelmista, vaan tarkastelemme niitä pinnallisesti.
Korkean kardinaalisuuden ongelma
Joten meille kerrotaan, että bittikarttaindeksit sopivat vain kentille, joilla on pieni kardinaliteetti, eli niille, joilla on vähän arvoja (esim. sukupuoli tai silmien väri), ja syynä on se, että tällaisten kenttien tavallinen esitystapa (yksi bit per arvo) suuren kardinaalisuuden tapauksessa se vie liikaa tilaa ja lisäksi nämä bittikarttaindeksit täyttyvät huonosti (harvoin).
Joskus saatamme käyttää erilaista esitystapaa, kuten tavallista, jota käytämme numeroiden esittämiseen. Mutta pakkausalgoritmien tulo muutti kaiken. Viime vuosikymmeninä tiedemiehet ja tutkijat ovat keksineet suuren määrän pakkausalgoritmeja bittikartoille. Niiden tärkein etu on, että bittikarttoja ei tarvitse purkaa bittitoimintojen suorittamiseksi - voimme suorittaa bittioperaatioita suoraan pakatuille bittikartoille.
Viime aikoina on alkanut ilmaantua hybridilähestymistapoja, kuten jylläävät bittikartat. Ne käyttävät samanaikaisesti kolmea erilaista bittikarttojen esitystapaa - itse bittikarttoja, taulukoita ja niin sanottuja bittiajoja - ja tasapainottavat niiden välillä suorituskyvyn maksimoimiseksi ja muistin kulutuksen minimoimiseksi.
Löydät mölyäviä bittikarttoja suosituimmista sovelluksista. Useille ohjelmointikielille on jo olemassa valtava määrä toteutuksia, mukaan lukien yli kolme toteutusta Golle.
Toinen lähestymistapa, joka voi auttaa meitä käsittelemään suurta kardinaalisuutta, on binning. Kuvittele, että sinulla on kenttä, joka edustaa henkilön pituutta. Korkeus on liukuluku, mutta me ihmiset emme ajattele sitä sillä tavalla. Meillä ei ole eroa 185,2 cm:n ja 185,3 cm:n välillä.
Osoittautuu, että voimme ryhmitellä samanlaiset arvot ryhmiin 1 cm:n sisällä.
Ja jos tiedämme myös, että hyvin harvat ihmiset ovat lyhyempiä kuin 50 cm ja pitkiä kuin 250 cm, voimme olennaisesti muuttaa kentän, jolla on ääretön kardinaliteetti, kenttään, jonka kardinaliteetti on noin 200 arvoa.
Tietysti voimme tarvittaessa tehdä lisäsuodatusta jälkikäteen.
Suuren kaistanleveyden ongelma
Seuraava ongelma bittikarttaindeksien kanssa on, että niiden päivittäminen voi olla erittäin kallista.
Tietokantojen on voitava päivittää tietoja samalla, kun mahdollisesti sadat muut kyselyt etsivät tietoja. Tarvitsemme lukkoja välttääksemme samanaikaiseen tiedonkäyttöön liittyviä ongelmia tai muita jakamisongelmia. Ja missä on yksi iso lukko, siellä on ongelma - lukkokiista, kun tästä lukosta tulee pullonkaula.
Tämä ongelma voidaan ratkaista tai kiertää käyttämällä sharing-toimintoa tai käyttämällä versioituja indeksejä.
Jakaminen on yksinkertainen ja tuttu asia. Voit sirpata bittikarttahakemiston kuten minkä tahansa muun datan. Yhden suuren lukon sijasta saat joukon pieniä lukkoja ja näin pääset eroon lukkokiistasta.
Toinen tapa ratkaista ongelma on käyttää versioidut indeksit. Sinulla voi olla yksi kopio hakemistosta, jota käytät etsimiseen tai lukemiseen, ja yksi kopio, jota käytät kirjoittamiseen tai päivittämiseen. Ja kerran tietyn ajan kuluessa (esimerkiksi kerran 100 ms tai 500 ms välein) kopioit ne ja vaihdat ne. Tämä lähestymistapa on tietysti sovellettavissa vain tapauksissa, joissa sovelluksesi pystyy käsittelemään hieman viivästynyttä hakuindeksiä.
Näitä kahta lähestymistapaa voidaan käyttää samanaikaisesti: sinulla voi olla sirpaloitu versioitu hakemisto.
Monimutkaisempia kyselyitä
Viimeinen ongelma bittikarttaindeksien kanssa on, että meille kerrotaan, että ne eivät sovellu hyvin monimutkaisempiin kyselytyyppeihin, kuten span-kyselyihin.
Todellakin, jos ajattelee sitä, bittioperaatiot, kuten AND, OR jne., eivät todellakaan sovellu kyselyihin a la "Näytä hotellit, joiden huonehinnat ovat 200-300 dollaria per yö."
Naiivi ja erittäin järjetön ratkaisu olisi ottaa kunkin dollarin arvon tulokset ja yhdistää ne bittikohtaiseen TAI-operaatioon.
Hieman parempi ratkaisu olisi käyttää ryhmittelyä. Esimerkiksi 50 dollarin ryhmissä. Tämä nopeuttaisi prosessiamme 50 kertaa.
Mutta ongelma on myös helppo ratkaista käyttämällä erityisesti tämäntyyppistä pyyntöä varten luotua näkymää. Tieteellisissä julkaisuissa sitä kutsutaan aluekoodatuiksi bittikartoiksi.
Tässä esityksessä emme aseta vain yhtä bittiä jollekin arvolle (esimerkiksi 200), vaan asetamme tämän arvon ja kaiken suuremmaksi. 200 ja yli. Sama 300:300 ja yli. Ja niin edelleen.
Käyttämällä tätä esitystapaa voimme vastata tällaiseen hakukyselyyn käymällä indeksin läpi vain kahdesti. Ensin saamme luettelon hotelleista, joissa huone maksaa alle 300 dollaria, ja sitten poistamme sieltä ne, joissa huone maksaa alle 199 dollaria. Valmis.
Tulet yllättymään, mutta jopa geokyselyt ovat mahdollisia bittikarttaindeksien avulla. Temppu on käyttää geometristä esitystapaa, joka ympäröi koordinaattisi geometrisella kuviolla. Esimerkiksi Googlen S2. Kuvan tulee olla mahdollista esittää kolmen tai useamman leikkaavan viivan muodossa, jotka voidaan numeroida. Tällä tavalla voimme muuttaa geokyselymme useiksi kyselyiksi "rakoa pitkin" (näitä numeroituja rivejä pitkin).
Valmiita ratkaisuja
Toivottavasti kiinnostuin sinusta hieman ja sinulla on nyt toinen hyödyllinen työkalu arsenaalissasi. Jos sinun on joskus tehtävä jotain tällaista, tiedät, mistä suunnasta katsoa.
Kaikilla ei kuitenkaan ole aikaa, kärsivällisyyttä tai resursseja luoda bittikarttahakemistoja tyhjästä. Varsinkin edistyneemmät, esimerkiksi SIMD:llä.
Onneksi on olemassa useita valmiita ratkaisuja, jotka auttavat sinua.
Huijaavat bittikartat
Ensinnäkin on sama jylläävä bittikarttakirjasto, josta jo puhuin. Se sisältää kaikki tarvittavat säiliöt ja bittitoiminnot, joita tarvitset täysimittaisen bittikarttaindeksin luomiseen.
Valitettavasti tällä hetkellä mikään Go-toteutuksista ei käytä SIMD:tä, mikä tarkoittaa, että Go-toteutukset ovat vähemmän suorituskykyisiä kuin esimerkiksi C-toteutukset.
hiukset
Toinen tuote, joka voi auttaa sinua, on Pilosa DBMS, jossa itse asiassa on vain bittikarttaindeksit. Tämä on suhteellisen uusi ratkaisu, mutta se voittaa sydämet suurella nopeudella.
Pilosa käyttää räjähtäviä bittikarttoja sisäisesti ja antaa sinulle mahdollisuuden käyttää niitä, yksinkertaistaa ja selittää kaikki asiat, joista puhuin edellä: ryhmittely, aluekoodatut bittikartat, kentän käsite jne.
Katsotaanpa nopeasti esimerkkiä Pilosan käyttämisestä vastaamaan jo tuntemaasi kysymykseen.
Esimerkki on hyvin samanlainen kuin aiemmin. Luomme Pilosa-palvelimelle asiakkaan, luomme indeksin ja tarvittavat kentät, täytämme kentämme satunnaisilla tiedoilla todennäköisyyksien kanssa ja lopuksi suoritamme tutun kyselyn.
Sen jälkeen käytämme "kallis"-kentässä EI, sitten leikkaamme tuloksen (tai JA sen) "terassi"-kentän ja "varaukset"-kentän kanssa. Ja lopuksi saamme lopputuloksen.
Toivon todella, että lähitulevaisuudessa tämä uudentyyppinen indeksi ilmestyy myös tietokantajärjestelmiin, kuten MySQL ja PostgreSQL - bittikarttaindeksit.
Johtopäätös
Jos et ole vielä nukahtanut, kiitos. Minun piti käsitellä lyhyesti monia aiheita rajallisen ajan vuoksi, mutta toivon, että puhe oli hyödyllinen ja ehkä jopa motivoiva.
Bittikarttaindeksit on hyvä tietää, vaikka et tarvitse niitä juuri nyt. Anna niiden olla toinen työkalu työkalupakkissasi.
Olemme tarkastelleet erilaisia Go:n suorituskykytemppuja ja asioita, joita Go-kääntäjä ei vielä käsittele kovin hyvin. Mutta tämä on ehdottoman hyödyllistä jokaisen Go-ohjelmoijan tiedossa.
Siinä kaikki, mitä halusin kertoa sinulle. Kiitos!
Lähde: will.com