įžanga
Šį pranešimą skaitė anglų kalba „GopherCon Russia 2019“ konferencijoje Maskvoje ir rusų kalba per susitikimą Nižnij Novgorode. Mes kalbame apie bitmap indeksą - mažiau paplitęs nei B-medis, bet ne mažiau įdomus. Dalijimasis pasisakymai konferencijoje anglų kalba ir teksto stenogramos rusų kalba.
Pažiūrėsime, kaip veikia bitmap indeksas, kada jis geresnis, kada blogesnis už kitus indeksus ir kokiais atvejais žymiai greitesnis už juos; Pažiūrėkime, kurios populiarios DBVS jau turi bitmap indeksus; Pabandykime parašyti savo „Go“. O „desertui“ panaudosime paruoštas bibliotekas, kad sukurtume savo itin greitą specializuotą duomenų bazę.
Labai tikiuosi, kad mano darbai jums bus naudingi ir įdomūs. Pirmyn!
įvedimas
Sveiki visi! Jau šešta vakaro ir mes visi labai pavargę. Puikus laikas pakalbėti apie nuobodžią duomenų bazių indekso teoriją, tiesa? Nesijaudinkite, čia ir ten turėsiu kelias šaltinio kodo eilutes. 🙂
Atmetus juokelius, reportaže pilna informacijos, o laiko neturime daug. Taigi pradėkime.
Šiandien kalbėsiu apie šiuos dalykus:
- kas yra indeksai;
- kas yra bitmap indeksas;
- kur jis naudojamas ir kur NEnaudojamas ir kodėl;
- paprastas diegimas „Go“ ir šiek tiek kovos su kompiliatoriumi;
- šiek tiek mažiau paprastas, bet daug produktyvesnis diegimas „Go assembler“;
- bitmap indeksų „problemos“;
- esamus įgyvendinimus.
Taigi, kas yra indeksai?
Indeksas yra atskira duomenų struktūra, kurią prižiūrime ir atnaujiname kartu su pagrindiniais duomenimis. Jis naudojamas paieškai paspartinti. Be indeksų, ieškant reikėtų peržiūrėti duomenis iki galo (procesas vadinamas visišku nuskaitymu), o šis procesas yra linijinio algoritminio sudėtingumo. Tačiau duomenų bazėse paprastai yra didžiulis duomenų kiekis, o tiesinis sudėtingumas yra per lėtas. Idealiu atveju gautume logaritminį arba pastovųjį.
Tai labai sudėtinga tema, kupina subtilybių ir kompromisų, tačiau pažvelgęs į dešimtmečius trukusį duomenų bazių kūrimą ir tyrimus, noriu pasakyti, kad yra tik keli plačiai naudojami duomenų bazių indeksų kūrimo būdai.
Pirmasis būdas yra hierarchiškai sumažinti paieškos erdvę, padalijant paieškos erdvę į mažesnes dalis.
Paprastai tai darome naudodami įvairių rūšių medžius. Pavyzdys galėtų būti didelė medžiagų dėžė jūsų spintoje, kurioje yra mažesnės dėžės medžiagų, suskirstytų į skirtingas temas. Jei jums reikia medžiagų, tikriausiai jų ieškosite dėžutėje su užrašu „Medžiagos“, o ne „Slapukai“, tiesa?
Antrasis būdas – iš karto pasirinkti norimą elementą ar elementų grupę. Tai darome maišos žemėlapiuose arba atvirkštiniuose indeksuose. Maišos žemėlapių naudojimas yra labai panašus į ankstesnį pavyzdį, tačiau vietoj dėžių dėžės savo spintoje turite krūvą mažų dėžučių galutinių daiktų.
Trečias būdas – panaikinti paieškos poreikį. Tai darome naudodami Bloom arba gegutės filtrus. Pirmieji atsakymą pateikia akimirksniu, todėl nereikės ieškoti.
Paskutinis būdas yra visiškai išnaudoti visą galią, kurią mums suteikia šiuolaikinė aparatinė įranga. Būtent tai mes darome bitmap indeksuose. Taip, juos naudojant kartais reikia pereiti visą indeksą, bet tai darome itin efektyviai.
Kaip sakiau, duomenų bazių indeksų tema yra plati ir kupina kompromisų. Tai reiškia, kad kartais galime naudoti kelis būdus vienu metu: jei reikia dar labiau paspartinti paiešką arba aprėpti visus galimus paieškos tipus.
Šiandien kalbėsiu apie mažiausiai žinomą jų požiūrį – bitmap indeksus.
Kas aš toks, kad galėčiau kalbėti šia tema?
Dirbu kaip „Badoo“ komandos vadovas (galbūt esate labiau susipažinę su kitu mūsų produktu „Bumble“). Jau turime daugiau nei 400 milijonų vartotojų visame pasaulyje ir daug funkcijų, kurios pasirenka jiems tinkamiausią variantą. Tai darome naudodami pasirinktines paslaugas, įskaitant bitmap indeksus.
Taigi, kas yra bitmap indeksas?
Bitmap indeksai, kaip rodo pavadinimas, naudoja bitmaps arba bitsets, kad įdiegtų paieškos indeksą. Žvelgiant iš paukščio skrydžio, šį indeksą sudaro vienas ar daugiau tokių bitų schemų, vaizduojančių bet kokius subjektus (pvz., žmones) ir jų savybes arba parametrus (amžių, akių spalvą ir kt.), ir algoritmo, naudojant bitų operacijas (AND, OR, NOT). ), kad atsakytumėte į paieškos užklausą.
Mums sakoma, kad bitmap indeksai geriausiai tinka ir labai veiksmingi tais atvejais, kai atliekamos paieškos, kurios sujungia užklausas daugelyje mažo kardinalumo stulpelių (pagalvokite apie „akių spalvą“ arba „šeimyninę padėtį“, palyginti su „atstumu nuo miesto centro“). Bet vėliau parodysiu, kad jie puikiai tinka ir didelio kardinalumo kolonoms.
Pažvelkime į paprasčiausią bitmap indekso pavyzdį.
Įsivaizduokite, kad turime sąrašą Maskvos restoranų, turinčių tokias dvejetaines savybes:
- šalia metro;
- yra privati automobilių stovėjimo aikštelė;
- yra veranda (yra terasa);
- galite rezervuoti staliuką (priima rezervacijas);
- tinka vegetarams (tinka veganams);
- brangus (brangus).
Suteikime kiekvienam restoranui eilės numerį, prasidedantį nuo 0, ir paskirkime atmintį 6 bitmaps (po vieną kiekvienai charakteristikai). Tada mes užpildysime šias bitmaps, atsižvelgdami į tai, ar restoranas turi šią nuosavybę, ar ne. Jei restoranas 4 turi verandą, bitas Nr. 4 taškinėje „turi verandą“ bus nustatytas į 1 (jei verandos nėra, tada į 0).
Dabar turime paprasčiausią bitmap indeksą ir galime jį naudoti atsakydami į tokias užklausas kaip:
- „Parodyk vegetarams pritaikytus restoranus“;
- „Parodykite man nebrangių restoranų su veranda, kur galite rezervuoti staliuką“.
Kaip? Pažiūrėkime. Pirmas prašymas labai paprastas. Viskas, ką turime padaryti, tai paimti „vegetarams draugišką“ taškinę schemą ir paversti ją restoranų, kurių detalės yra atskleistos, sąrašu.
Antrasis prašymas yra šiek tiek sudėtingesnis. Kad gautume nebrangių restoranų sąrašą, turime naudoti NOT taškinę schemą „brangiame“ taškiniame paveikslėlyje, tada IR su taškais „ar galiu užsisakyti staliuką“ ir IR rezultatą su taškiniu „yra veranda“. Gautoje bitų schemoje bus sąrašas įstaigų, kurios atitinka visus mūsų kriterijus. Šiame pavyzdyje tai tik Yunost restoranas.
Yra daug teorijos, bet nesijaudinkite, kodą pamatysime labai greitai.
Kur naudojami bitmap indeksai?
Jei Google rodys bitmap indeksus, 90% atsakymų vienaip ar kitaip bus susiję su Oracle DB. Bet kitos DBVS tikriausiai taip pat palaiko tokį šaunų dalyką, tiesa? Ne visai.
Peržvelkime pagrindinių įtariamųjų sąrašą.
MySQL dar nepalaiko bitmap indeksų, tačiau yra pasiūlymas, siūlantis pridėti šią parinktį ().
PostgreSQL nepalaiko taškinių schemų indeksų, bet naudoja paprastas bitų struktūras ir bitų operacijas, kad sujungtų paieškos rezultatus keliuose kituose indeksuose.
Tarantool turi bitų rinkinių indeksus ir palaiko paprastas paieškas juose.
Redis turi paprastus bitų laukus) be galimybės jų ieškoti.
MongoDB dar nepalaiko bitmap indeksų, tačiau taip pat yra pasiūlymas, kuriame siūloma pridėti šią parinktį
Elasticsearch viduje naudoja bitmaps).
- Bet mūsų namuose atsirado naujas kaimynas: Pilosa. Tai nauja nesusijusi duomenų bazė, parašyta Go. Jame yra tik bitmap indeksai ir viskas jais grindžiama. Apie tai pakalbėsime šiek tiek vėliau.
Diegimas Go
Bet kodėl bitmap indeksai naudojami taip retai? Prieš atsakydamas į šį klausimą, norėčiau parodyti, kaip įdiegti labai paprastą bitmap indeksą Go.
Bitmaps iš esmės yra tik duomenų dalys. Programoje „Go“ tam naudokime baitų skilteles.
Turime vieną taškinę schemą vienai restorano charakteristikai ir kiekvienas bitų žemėlapis nurodo, ar konkretus restoranas turi šią savybę, ar ne.
Mums reikės dviejų pagalbinių funkcijų. Vienas bus naudojamas mūsų bitų žemėlapiams užpildyti atsitiktiniais duomenimis. Atsitiktinai, bet su tam tikra tikimybe, kad restoranas turi kiekvieną nuosavybę. Pavyzdžiui, manau, kad Maskvoje yra labai mažai restoranų, kuriuose negalima rezervuoti staliuko, ir man atrodo, kad apie 20% įstaigų yra tinkamos vegetarams.
Antroji funkcija konvertuos bitų žemėlapį į restoranų sąrašą.
Norėdami atsakyti į užklausą „Parodykite man nebrangius restoranus, kurie turi terasą ir gali rezervuoti“, mums reikia dviejų bitų operacijų: NOT ir AND.
Mes galime šiek tiek supaprastinti savo kodą naudodami sudėtingesnį AND NOT operatorių.
Kiekvienai iš šių operacijų turime savo funkcijas. Abu jie pereina pjūvius, iš kiekvieno paima atitinkamus elementus, sujungia juos bitų operacija ir įdeda rezultatą į gautą gabalą.
Ir dabar galime naudoti savo bitmaps ir funkcijas, kad atsakytume į paieškos užklausą.
Našumas nėra toks didelis, nors funkcijos yra labai paprastos ir sutaupėme daug pinigų, nes kiekvieną kartą, kai funkcija buvo iškviesta, negrąžinome naujos skilties.
Šiek tiek pasidaręs profiliavimą su pprof, pastebėjau, kad Go kompiliatoriui trūksta vieno labai paprasto, bet labai svarbaus optimizavimo: funkcijos inlining.
Faktas yra tas, kad „Go“ kompiliatorius siaubingai bijo kilpų, kurios eina per pjūvius, ir kategoriškai atsisako įtraukti funkcijas, kuriose yra tokių kilpų.
Bet aš nebijau ir galiu apgauti kompiliatorių naudodamas goto vietoj kilpos, kaip senais gerais laikais.
Ir, kaip matote, dabar kompiliatorius mielai įtrauks mūsų funkciją! Dėl to pavyksta sutaupyti apie 2 mikrosekundes. Neblogai!
Antrą kliūtį lengva pastebėti, jei atidžiai pažvelgsite į surinkimo produkciją. Kompiliatorius pridėjo pjūvio ribų patikrinimą tiesiai į mūsų karščiausią kilpą. Faktas yra tas, kad „Go“ yra saugi kalba, kompiliatorius bijo, kad mano trys argumentai (trys skiltys) yra skirtingo dydžio. Juk tada bus teorinė vadinamojo buferio perpildymo tikimybė.
Nuraminkime kompiliatorių parodydami, kad visi gabalai yra vienodo dydžio. Tai galime padaryti pridėdami paprastą patikrinimą funkcijos pradžioje.
Tai pamatęs kompiliatorius su džiaugsmu praleidžia patikrinimą ir galiausiai sutaupome dar 500 nanosekundžių.
Didelės bukos
Gerai, mums pavyko išspausti šiek tiek našumo iš mūsų paprasto diegimo, tačiau šis rezultatas iš tikrųjų yra daug prastesnis nei įmanoma naudojant dabartinę aparatinę įrangą.
Mes atliekame tik pagrindines bitų operacijas, o mūsų procesoriai jas atlieka labai efektyviai. Bet, deja, savo procesorių „maitiname“ labai mažais darbais. Mūsų funkcijos atlieka operacijas baitais po baitų. Mes galime labai lengvai pakoreguoti savo kodą, kad jis veiktų su 8 baitų dalimis, naudodami UInt64 dalis.
Kaip matote, šis nedidelis pakeitimas pagreitino mūsų programą aštuonis kartus, padidindamas partijos dydį aštuonis kartus. Galima sakyti, kad padidėjimas yra tiesinis.
Įdiegimas montažinėje
Bet tai dar ne pabaiga. Mūsų procesoriai gali dirbti su 16, 32 ir net 64 baitų gabalais. Tokios „plačios“ operacijos vadinamos vienos instrukcijos kelių duomenimis (SIMD; viena instrukcija, daug duomenų), o kodo transformavimo procesas, kad jis naudotų tokias operacijas, vadinamas vektorizavimu.
Deja, „Go“ kompiliatorius toli gražu nėra puikus vektorizavimo srityje. Šiuo metu vienintelis būdas vektorizuoti Go kodą yra imtis ir atlikti šias operacijas rankiniu būdu naudojant Go assembler.
Go assembleris yra keistas žvėris. Tikriausiai žinote, kad asamblėjos kalba yra kažkas, kas labai susieta su kompiuterio, kuriam rašote, architektūra, bet Go atveju taip nėra. „Go assembler“ labiau primena IRL (tarpinę vaizdavimo kalbą) arba tarpinę kalbą: ji praktiškai nepriklauso nuo platformos. Robas Pike'as puikiai pasirodė šia tema prieš keletą metų „GopherCon“ Denveryje.
Be to, Go naudoja neįprastą 9 plano formatą, kuris skiriasi nuo visuotinai priimtų AT&T ir Intel formatų.
Galima drąsiai teigti, kad rašyti „Go assembler“ ranka nėra pats smagiausias.
Bet, laimei, jau yra du aukšto lygio įrankiai, padedantys mums parašyti „Go assembler“: PeachPy ir avo. Abi programos generuoja „Go assembler“ iš aukštesnio lygio kodo, parašyto atitinkamai „Python“ ir „Go“.
Šios komunalinės paslaugos supaprastina tokius dalykus kaip registro paskirstymas, rašymo kilpos ir apskritai supaprastina patekimo į surinkimo programavimo pasaulį Go.
Mes naudosime avo, todėl mūsų programos bus beveik įprastos „Go“ programos.
Taip atrodo paprasčiausias avo programos pavyzdys. Turime funkciją main(), kuri apibrėžia savyje funkciją Add(), kurios reikšmė yra pridėti du skaičius. Čia yra pagalbinių funkcijų, leidžiančių gauti parametrus pagal pavadinimą ir gauti vieną iš nemokamų ir tinkamų procesorių registrų. Kiekviena procesoriaus operacija turi atitinkamą funkciją avo, kaip matyti ADDQ. Galiausiai matome pagalbinę funkciją gautai vertei išsaugoti.
Paskambinus go generuoti, mes vykdysime programą avo ir dėl to bus sugeneruoti du failai:
- add.s su gautu kodu Go assembler;
- stub.go su funkcijų antraštėmis, kad sujungtumėte du pasaulius: Go ir assembler.
Dabar, kai pamatėme, ką ir kaip veikia avo, pažvelkime į savo funkcijas. Įdiegiau tiek skaliarines, tiek vektorines (SIMD) funkcijų versijas.
Pirmiausia pažvelkime į skaliarines versijas.
Kaip ir ankstesniame pavyzdyje, mes prašome nemokamo ir galiojančio bendrosios paskirties registro, mums nereikia skaičiuoti argumentų poslinkių ir dydžių. avo visa tai daro už mus.
Anksčiau naudojome etiketes ir goto (arba šuolius), kad pagerintume našumą ir apgautume „Go“ kompiliatorių, bet dabar tai darome nuo pat pradžių. Esmė ta, kad ciklai yra aukštesnio lygio sąvoka. Montuotoje turime tik etiketes ir šuolius.
Likęs kodas jau turėtų būti pažįstamas ir suprantamas. Mes mėgdžiojame kilpą su etiketėmis ir šuoliais, paimame nedidelę duomenų dalį iš savo dviejų skilčių, sujungiame juos su bitų operacija (IR šiuo atveju NE) ir tada įdedame rezultatą į gautą skiltį. Visi.
Taip atrodo galutinis surinkėjo kodas. Mums nereikėjo skaičiuoti poslinkių ir dydžių (pažymėtų žaliai) ar sekti naudojamų registrų (pažymėtų raudonai).
Jei palyginsime asamblėjos kalbos diegimo našumą su geriausio diegimo „Go“ našumu, pamatysime, kad jis yra toks pat. Ir to tikimasi. Juk nieko ypatingo nedarėme – tik atgaminome tai, ką darytų „Go“ kompiliatorius.
Deja, negalime priversti kompiliatoriaus įtraukti mūsų funkcijas, parašytas asamblėjos kalba. „Go“ kompiliatorius šiuo metu tokios funkcijos neturi, nors jau gana seniai buvo prašoma ją pridėti.
Štai kodėl neįmanoma gauti jokios naudos iš mažų funkcijų surinkimo kalba. Turime arba parašyti dideles funkcijas, arba naudoti naują matematikos/bitų paketą, arba apeiti asemblerio kalbą.
Dabar pažvelkime į mūsų funkcijų vektorines versijas.
Šiame pavyzdyje nusprendžiau naudoti AVX2, todėl naudosime operacijas, kurios veikia 32 baitų gabalais. Kodo struktūra labai panaši į skaliarinę versiją: įkeliami parametrai, prašoma nemokamo bendro registro ir pan.
Viena naujovė yra ta, kad platesnėse vektorinėse operacijose naudojami specialūs platūs registrai. 32 baitų gabalų atveju tai yra registrai, kurių priešdėlis yra Y. Štai kodėl kode matote YMM() funkciją. Jei naudočiau AVX-512 su 64 bitų dalimis, priešdėlis būtų Z.
Antroji naujovė yra ta, kad aš nusprendžiau naudoti optimizavimą, vadinamą kilpos išvyniojimu, o tai reiškia, kad prieš pereinant į ciklo pradžią reikia atlikti aštuonias ciklo operacijas rankiniu būdu. Šis optimizavimas sumažina šakų skaičių kode ir riboja galimų nemokamų registrų skaičių.
Na, o kaip dėl pasirodymo? Ji yra graži! Mes pasiekėme maždaug septynis kartus pagreitį, palyginti su geriausiu „Go“ sprendimu. Įspūdinga, tiesa?
Tačiau net ir šis įgyvendinimas gali būti paspartintas naudojant AVX-512, išankstinį iškvietimą arba JIT (tiesiog laikui skirtą kompiliatorių) užklausų planuokliui. Bet tai tikrai atskiro pranešimo tema.
Problemos su bitmap indeksais
Dabar, kai jau apžvelgėme paprastą bitmap indekso diegimą programoje Go ir daug produktyvesnį asamblėjos kalba, pagaliau pakalbėkime apie tai, kodėl bitmap indeksai naudojami taip retai.
Senesniuose straipsniuose minimos trys bitmap indeksų problemos, tačiau naujesniuose straipsniuose teigiu, kad jie nebėra aktualūs. Mes nesigilinsime į kiekvieną iš šių problemų, o pažvelgsime į jas paviršutiniškai.
Aukšto kardinalumo problema
Taigi, mums sakoma, kad bitmap indeksai tinka tik mažo kardinalumo laukams, ty tiems, kurie turi mažai reikšmių (pavyzdžiui, lytis ar akių spalva), o priežastis ta, kad įprastas tokių laukų vaizdavimas (vienas bit per vertę) esant dideliam kardinalumui, jis užims per daug vietos, be to, šie bitų žemėlapių indeksai bus prastai (retai) užpildyti.
Kartais galime naudoti kitokį atvaizdavimą, pvz., standartinį, kurį naudojame skaičiams pavaizduoti. Tačiau viską pakeitė suspaudimo algoritmų atsiradimas. Per pastaruosius dešimtmečius mokslininkai ir tyrinėtojai sugalvojo daugybę bitmaps glaudinimo algoritmų. Pagrindinis jų privalumas yra tas, kad norint atlikti bitų operacijas nereikia išskleisti bitų schemų – bitų operacijas galime atlikti tiesiogiai suglaudintuose bitų žemėlapiuose.
Pastaruoju metu pradėjo atsirasti hibridinių metodų, pavyzdžiui, riaumojančios bitmaps. Jie vienu metu naudoja tris skirtingus bitų schemų vaizdus – pačius bitų žemėlapius, masyvus ir vadinamuosius bitų paleidimus – ir subalansuoja juos, kad padidintų našumą ir sumažintų atminties sąnaudas.
Populiariausiose programose galite rasti riaumojančių bitmapų. Jau yra daugybė įvairių programavimo kalbų diegimų, įskaitant daugiau nei tris „Go“ diegimus.
Kitas metodas, galintis padėti mums susidoroti su dideliu kardinalumu, vadinamas binning. Įsivaizduokite, kad turite lauką, vaizduojantį žmogaus ūgį. Aukštis yra slankiojo kablelio skaičius, bet mes, žmonės, apie tai negalvojame taip. Mums nėra skirtumo tarp 185,2 cm ir 185,3 cm ūgio.
Pasirodo, panašias reikšmes galime sugrupuoti į grupes 1 cm atstumu.
Ir jei dar žinome, kad labai mažai žmonių yra žemesni nei 50 cm ir aukštesni nei 250 cm, tai iš esmės begalinio kardinalumo lauką galime paversti lauku, kurio kardinalumas yra apie 200 reikšmių.
Žinoma, jei reikia, vėliau galime atlikti papildomą filtravimą.
Didelio pralaidumo problema
Kita bitmap indeksų problema yra ta, kad jų atnaujinimas gali būti labai brangus.
Duomenų bazės turi turėti galimybę atnaujinti duomenis, kol duomenų ieško šimtai kitų užklausų. Mums reikia užraktų, kad išvengtume problemų, susijusių su vienu metu pasiekiamais duomenimis ar kitų bendrinimo problemų. O ten, kur yra viena didelė spyna, iškyla problema – užrakto ginčas, kai ši spyna tampa kliūtimi.
Šią problemą galima išspręsti arba apeiti naudojant dalijimą arba versijų indeksus.
Dalijimasis yra paprastas ir gerai žinomas dalykas. Galite suskaidyti bitmap indeksą kaip ir bet kokius kitus duomenis. Vietoj vienos didelės spynos gausite krūvą mažų spynų ir taip atsikratysite ginčų dėl spynų.
Antrasis būdas išspręsti problemą yra naudoti versijų indeksus. Galite turėti vieną rodyklės kopiją, kurią naudojate ieškodami arba skaitydami, ir vieną, kurią naudojate rašydami ar atnaujindami. Ir vieną kartą per tam tikrą laikotarpį (pavyzdžiui, kartą per 100 ms arba 500 ms) juos dubliuojate ir pakeičiate. Žinoma, šis metodas taikomas tik tais atvejais, kai jūsų programa gali apdoroti šiek tiek atsiliekantį paieškos indeksą.
Šiuos du būdus galima naudoti vienu metu: galite turėti suskaidytų versijų indeksą.
Sudėtingesnės užklausos
Paskutinė bitmap indeksų problema yra ta, kad mums sakoma, kad jie nėra gerai pritaikyti sudėtingesnio tipo užklausoms, pvz., apimties užklausoms.
Iš tiesų, jei gerai pagalvotumėte, bitų operacijos, pvz., AND, OR ir tt, nėra labai tinkamos užklausoms a la „Parodykite man viešbučius, kurių kambarių kainos nuo 200 iki 300 USD už naktį“.
Naivus ir labai neprotingas sprendimas būtų paimti kiekvieno dolerio vertės rezultatus ir sujungti juos su bitų ARBA operacija.
Šiek tiek geresnis sprendimas būtų naudoti grupavimą. Pavyzdžiui, grupėse po 50 dolerių. Tai paspartintų mūsų procesą 50 kartų.
Tačiau problema taip pat lengvai išsprendžiama naudojant specialiai tokio tipo užklausoms sukurtą vaizdą. Moksliniuose straipsniuose tai vadinama diapazono koduotomis bitmaps.
Šiame vaizde mes ne tik nustatome vieną bitą kokiai nors vertei (pavyzdžiui, 200), bet nustatome šią reikšmę ir viską aukštesnę. 200 ir daugiau. Tas pats 300:300 ir daugiau. Ir taip toliau.
Naudodami šį atvaizdą galime atsakyti į tokio tipo paieškos užklausą perkeldami indeksą tik du kartus. Pirmiausia gausime sąrašą viešbučių, kuriuose kambarys kainuoja mažiau arba 300 USD, o tada iš jo pašalinsime tuos, kuriuose kambarys kainuoja mažiau arba 199 USD. Paruošta.
Nustebsite, tačiau naudojant bitmap indeksus galima atlikti net geografines užklausas. Triukas yra naudoti geometrinį vaizdą, kuris supa jūsų koordinates su geometrine figūra. Pavyzdžiui, S2 iš Google. Figūrą turi būti įmanoma pavaizduoti trijų ar daugiau susikertančių linijų, kurias galima sunumeruoti, forma. Tokiu būdu savo geografinę užklausą galime paversti keliomis užklausomis „išilgai tarpo“ (išilgai šių sunumeruotų eilučių).
Paruošti sprendimai
Tikiuosi, kad mane šiek tiek sudomino ir dabar jūsų arsenale yra dar vienas naudingas įrankis. Jei kada nors reikės ką nors panašaus padaryti, žinosite, kaip žiūrėti.
Tačiau ne visi turi laiko, kantrybės ar išteklių kurti bitmap indeksus nuo nulio. Ypač pažangesni, pavyzdžiui, naudojant SIMD.
Laimei, yra keletas paruoštų sprendimų, kurie jums padės.
Riaumojantys bitmaps
Pirma, yra ta pati riaumojanti bitmaps biblioteka, apie kurią jau kalbėjau. Jame yra visi reikalingi konteineriai ir bitų operacijos, kurių jums prireiks norint sukurti visavertį bitmap indeksą.
Deja, šiuo metu nė viena iš „Go“ diegimų nenaudoja SIMD, o tai reiškia, kad „Go“ diegimai yra mažiau našūs nei, pavyzdžiui, C.
plaukuotas
Kitas produktas, kuris gali jums padėti, yra Pilosa DBVS, kuri iš tikrųjų turi tik bitmap indeksus. Tai palyginti naujas sprendimas, tačiau jis užkariauja širdis dideliu greičiu.
„Pilosa“ viduje naudoja riaumojančius taškinius paveikslėlius ir suteikia galimybę juos naudoti, supaprastina ir paaiškina visus dalykus, apie kuriuos kalbėjau aukščiau: grupavimą, diapazono koduotus taškinius paveikslėlius, lauko sąvoką ir kt.
Greitai pažvelkime į Pilosa naudojimo pavyzdį atsakydami į jums jau pažįstamą klausimą.
Pavyzdys labai panašus į tai, ką matėte anksčiau. Sukuriame Pilosa serverio klientą, sukuriame indeksą ir reikiamus laukus, tada užpildome laukus atsitiktiniais duomenimis su tikimybėmis ir galiausiai vykdome pažįstamą užklausą.
Po to lauke „brangus“ naudojame NE, tada rezultatą (arba IR jį) sukirsime su laukeliu „terasa“ ir laukeliu „rezervacijos“. Ir galiausiai gauname galutinį rezultatą.
Labai tikiuosi, kad artimiausioje ateityje šis naujas indekso tipas atsiras ir tokiose DBVS, kaip MySQL ir PostgreSQL – bitmap indeksuose.
išvada
Jei dar neužmigote, ačiū. Turėjau trumpai paliesti daugybę temų dėl riboto laiko, bet tikiuosi, kad pokalbis buvo naudingas, o gal net motyvuojantis.
Verta žinoti apie bitmap indeksus, net jei jums jų šiuo metu nereikia. Tegul jie yra dar vienas įrankis jūsų įrankių dėžėje.
Išnagrinėjome įvairius „Go“ našumo triukus ir dalykus, su kuriais „Go“ kompiliatorius dar ne itin gerai susitvarko. Bet tai tikrai naudinga žinoti kiekvienam Go programuotojui.
Tai viskas, ką norėjau tau pasakyti. Ačiū!
Šaltinis: www.habr.com