pagpapakilala
Ibinigay ko ang ulat na ito sa English sa GopherCon Russia 2019 conference sa Moscow at sa Russian sa isang meetup sa Nizhny Novgorod. Pinag-uusapan natin ang tungkol sa isang bitmap index - hindi gaanong karaniwan kaysa sa B-tree, ngunit hindi gaanong kawili-wili. Pagbabahagi mga talumpati sa kumperensya sa Ingles at mga transcript ng teksto sa Russian.
Titingnan natin kung paano gumagana ang isang bitmap index, kapag ito ay mas mahusay, kapag ito ay mas masahol kaysa sa iba pang mga index, at sa kung anong mga kaso ito ay makabuluhang mas mabilis kaysa sa kanila; Tingnan natin kung aling mga sikat na DBMS ang mayroon nang mga bitmap index; Subukan nating magsulat ng sarili natin sa Go. At "para sa panghimagas" gagamitin namin ang mga handa na aklatan upang lumikha ng aming sariling napakabilis na dalubhasang database.
Talagang inaasahan ko na ang aking mga gawa ay magiging kapaki-pakinabang at kawili-wili para sa iyo. Go!
Pagpapakilala
Kamusta kayong lahat! Alas sais na ng gabi at super pagod na kaming lahat. Mahusay na oras upang pag-usapan ang tungkol sa boring na teorya ng database index, tama ba? Huwag mag-alala, magkakaroon ako ng ilang linya ng source code dito at doon. π
Bukod sa mga biro, ang ulat ay punong-puno ng impormasyon, at wala kaming gaanong oras. Kaya simulan na natin.
Ngayon ay magsasalita ako tungkol sa mga sumusunod:
- ano ang mga index;
- ano ang bitmap index;
- kung saan ito ginagamit at kung saan ito HINDI ginagamit at bakit;
- simpleng pagpapatupad sa Go at kaunting pakikibaka sa compiler;
- bahagyang hindi gaanong simple, ngunit mas produktibong pagpapatupad sa Go assembler;
- "mga problema" ng mga index ng bitmap;
- umiiral na mga pagpapatupad.
Kaya ano ang mga index?
Ang index ay isang hiwalay na istraktura ng data na aming pinapanatili at ina-update bilang karagdagan sa pangunahing data. Ito ay ginagamit upang mapabilis ang paghahanap. Kung walang mga index, ang paghahanap ay mangangailangan ng ganap na pagdaan sa data (isang prosesong tinatawag na full scan), at ang prosesong ito ay may linear algorithmic complexity. Ngunit ang mga database ay karaniwang naglalaman ng malaking halaga ng data at ang linear na kumplikado ay masyadong mabagal. Sa isip, makakakuha tayo ng logarithmic o pare-pareho.
Ito ay isang napakakomplikadong paksa, na puno ng mga subtleties at trade-off, ngunit pagkatapos ng pagtingin sa mga dekada ng pagbuo at pananaliksik ng database, handa akong sabihin na mayroon lamang ilang malawak na ginagamit na mga diskarte sa paglikha ng mga database index.
Ang unang diskarte ay ang hierarchical na bawasan ang espasyo sa paghahanap, na hinahati ang espasyo sa paghahanap sa mas maliliit na bahagi.
Karaniwan naming ginagawa ito gamit ang iba't ibang uri ng mga puno. Ang isang halimbawa ay isang malaking kahon ng mga materyales sa iyong aparador na naglalaman ng mas maliliit na kahon ng mga materyales na hinati sa iba't ibang paksa. Kung kailangan mo ng mga materyales, malamang na hahanapin mo ang mga ito sa isang kahon na nagsasabing "Mga Materyales" sa halip na isang "Cookies," di ba?
Ang pangalawang diskarte ay ang agad na piliin ang nais na elemento o pangkat ng mga elemento. Ginagawa namin ito sa mga hash na mapa o reverse index. Ang paggamit ng mga hash na mapa ay halos kapareho sa nakaraang halimbawa, ngunit sa halip na isang kahon ng mga kahon, mayroon kang isang bungkos ng maliliit na kahon ng mga huling item sa iyong aparador.
Ang ikatlong diskarte ay upang alisin ang pangangailangan para sa paghahanap. Ginagawa namin ito gamit ang mga filter ng Bloom o mga filter ng cuckoo. Ang mga nauna ay agad na nagbibigay ng sagot, na nagliligtas sa iyo mula sa paghahanap.
Ang huling diskarte ay ang ganap na paggamit ng lahat ng kapangyarihan na ibinibigay sa atin ng modernong hardware. Ito mismo ang ginagawa namin sa mga index ng bitmap. Oo, kapag ginagamit ang mga ito minsan kailangan nating dumaan sa buong index, ngunit ginagawa natin ito nang napakahusay.
Tulad ng sinabi ko, ang paksa ng mga database index ay malawak at puno ng mga kompromiso. Nangangahulugan ito na kung minsan ay maaari tayong gumamit ng ilang mga diskarte nang sabay-sabay: kung kailangan nating pabilisin pa ang paghahanap, o kung kailangan nating saklawin ang lahat ng posibleng uri ng paghahanap.
Ngayon ay magsasalita ako tungkol sa hindi gaanong kilalang diskarte ng mga ito - mga index ng bitmap.
Sino ako para magsalita sa paksang ito?
Nagtatrabaho ako bilang isang team lead sa Badoo (marahil ay mas pamilyar ka sa aming iba pang produkto, Bumble). Mayroon na kaming higit sa 400 milyong user sa buong mundo at maraming feature na pumipili ng pinakamahusay na tugma para sa kanila. Ginagawa namin ito gamit ang mga custom na serbisyo, kabilang ang mga bitmap index.
Kaya ano ang isang bitmap index?
Ang mga index ng bitmap, gaya ng ipinahihiwatig ng pangalan, ay gumagamit ng mga bitmap o bitset upang magpatupad ng index ng paghahanap. Mula sa isang bird's eye view, ang index na ito ay binubuo ng isa o higit pang mga bitmap na kumakatawan sa anumang mga entity (gaya ng mga tao) at ang kanilang mga katangian o parameter (edad, kulay ng mata, atbp.), at isang algorithm na gumagamit ng mga bit operation (AT, O, HINDI. ) upang sagutin ang query sa paghahanap.
Sinabihan kami na ang mga bitmap index ay pinakaangkop at napakahusay para sa mga kaso kung saan may mga paghahanap na pinagsasama-sama ang mga query sa maraming column na mababa ang cardinality (isipin ang "kulay ng mata" o "marital status" kumpara sa isang bagay tulad ng "distansya mula sa sentro ng lungsod" ). Ngunit ipapakita ko sa ibang pagkakataon na gumagana rin ang mga ito para sa mataas na cardinality na mga column.
Tingnan natin ang pinakasimpleng halimbawa ng index ng bitmap.
Isipin na mayroon kaming isang listahan ng mga restawran sa Moscow na may mga binary na katangian tulad nito:
- malapit sa metro;
- may pribadong paradahan;
- may veranda (may terrace);
- maaari kang magpareserba ng mesa (tumatanggap ng mga reserbasyon);
- angkop para sa mga vegetarian (vegan friendly);
- mahal (mahal).
Bigyan natin ang bawat restaurant ng sequence number na nagsisimula sa 0 at maglaan ng memory para sa 6 na bitmaps (isa para sa bawat katangian). Pagkatapos ay i-populate namin ang mga bitmap na ito depende sa kung ang restaurant ay may ganitong property o wala. Kung ang restaurant 4 ay may veranda, ang bit No. 4 sa bitmap na "may veranda" ay itatakda sa 1 (kung walang veranda, pagkatapos ay sa 0).
Ngayon ay mayroon na kaming pinakasimpleng bitmap index na posible, at magagamit namin ito upang sagutin ang mga query tulad ng:
- "Ipakita sa akin ang mga vegetarian-friendly na restaurant";
- "Ipakita sa akin ang mga murang restaurant na may veranda kung saan maaari kang magpareserba ng mesa."
Paano? Tingnan natin. Ang unang kahilingan ay napaka-simple. Ang kailangan lang nating gawin ay kunin ang "vegetarian friendly" na bitmap at gawin itong isang listahan ng mga restaurant na ang mga bit ay nakalantad.
Ang pangalawang kahilingan ay medyo mas kumplikado. Kailangan nating gamitin ang NOT bitmap sa βmahalβ na bitmap para makakuha ng listahan ng mga murang restaurant, pagkatapos ay AT ito ng bitmap na βcan I book a tableβ at AT ang resulta na may bitmap na βthere is a verandaβ. Ang magreresultang bitmap ay maglalaman ng listahan ng mga establisyimento na nakakatugon sa lahat ng aming pamantayan. Sa halimbawang ito, ito lang ang Yunost restaurant.
Maraming teorya ang kasangkot, ngunit huwag mag-alala, makikita natin ang code sa lalong madaling panahon.
Saan ginagamit ang mga index ng bitmap?
Kung mag-i-index ka ng bitmap ng Google, 90% ng mga sagot ay mauugnay sa Oracle DB sa isang paraan o iba pa. Ngunit ang iba pang mga DBMS ay malamang na sumusuporta din sa isang cool na bagay, tama ba? Hindi naman.
Tingnan natin ang listahan ng mga pangunahing suspek.
Hindi pa sinusuportahan ng MySQL ang mga bitmap index, ngunit mayroong isang Panukala na nagmumungkahi ng pagdaragdag ng opsyong ito ().
Hindi sinusuportahan ng PostgreSQL ang mga index ng bitmap, ngunit gumagamit ng mga simpleng bitmap at bit operation upang pagsamahin ang mga resulta ng paghahanap sa marami pang ibang mga index.
Ang Tarantool ay may mga bitset index at sumusuporta sa mga simpleng paghahanap sa mga ito.
Ang Redis ay may mga simpleng bitfield) nang walang kakayahang hanapin ang mga ito.
Hindi pa sinusuportahan ng MongoDB ang mga bitmap index, ngunit mayroon ding Panukala na nagmumungkahi na idagdag ang opsyong ito
Ang Elasticsearch ay gumagamit ng mga bitmap sa loob).
- Ngunit may lumitaw na bagong kapitbahay sa aming bahay: Pilosa. Isa itong bagong database na hindi nauugnay na nakasulat sa Go. Naglalaman lamang ito ng mga bitmap index at ibinabatay ang lahat sa kanila. Mamaya na lang natin pag-usapan.
Pagpapatupad sa Go
Ngunit bakit bihirang gamitin ang mga index ng bitmap? Bago sagutin ang tanong na ito, gusto kong ipakita sa iyo kung paano magpatupad ng napakasimpleng bitmap index sa Go.
Ang mga bitmap ay mahalagang piraso lamang ng data. Sa Go, gamitin natin ang mga byte slice para dito.
Mayroon kaming isang bitmap para sa isang katangian ng restaurant, at ang bawat bit sa bitmap ay nagpapahiwatig kung ang isang partikular na restaurant ay may ganitong property o wala.
Kakailanganin namin ang dalawang function ng helper. Ang isa ay gagamitin upang punan ang aming mga bitmap ng random na data. Random, ngunit may tiyak na posibilidad na ang restaurant ay may bawat ari-arian. Halimbawa, naniniwala ako na napakakaunting mga restawran sa Moscow kung saan hindi ka maaaring magreserba ng isang mesa, at tila sa akin na ang tungkol sa 20% ng mga establisimiyento ay angkop para sa mga vegetarian.
Iko-convert ng pangalawang function ang bitmap sa isang listahan ng mga restaurant.
Upang masagot ang query na "Ipakita sa akin ang mga murang restaurant na may patio at maaaring magpareserba," kailangan namin ng dalawang bit na operasyon: HINDI at AT.
Maaari naming gawing simple ang aming code nang kaunti sa pamamagitan ng paggamit ng mas kumplikado AT HINDI operator.
Mayroon kaming mga function para sa bawat isa sa mga operasyong ito. Pareho silang dumaan sa mga hiwa, kunin ang mga kaukulang elemento mula sa bawat isa, pagsamahin ang mga ito ng kaunting operasyon at ilagay ang resulta sa nagresultang hiwa.
At ngayon ay magagamit na natin ang ating mga bitmap at function para sagutin ang query sa paghahanap.
Ang pagganap ay hindi ganoon kataas, kahit na ang mga pag-andar ay napaka-simple at nakatipid kami ng maraming pera sa pamamagitan ng hindi pagbabalik ng isang bagong resultang slice sa tuwing tinawag ang function.
Pagkatapos gumawa ng kaunting profiling sa pprof, napansin ko na ang Go compiler ay kulang ng isang napakasimple ngunit napakahalagang pag-optimize: function inlining.
Ang katotohanan ay ang Go compiler ay labis na natatakot sa mga loop na dumaan sa mga hiwa, at tiyak na tumanggi sa mga inline na function na naglalaman ng mga naturang loop.
Ngunit hindi ako natatakot at maaari kong lokohin ang compiler sa pamamagitan ng paggamit ng goto sa halip na isang loop, tulad ng sa magandang lumang araw.
At, tulad ng nakikita mo, ngayon ay masayang i-inline ng compiler ang aming function! Bilang resulta, nakakatipid kami ng humigit-kumulang 2 microseconds. Hindi masama!
Ang pangalawang bottleneck ay madaling makita kung titingnan mong mabuti ang output ng assembly. Nagdagdag ang compiler ng slice boundary check sa loob mismo ng aming pinakamainit na loop. Ang katotohanan ay ang Go ay isang ligtas na wika, ang compiler ay natatakot na ang aking tatlong argumento (tatlong hiwa) ay may iba't ibang laki. Pagkatapos ng lahat, pagkatapos ay magkakaroon ng isang teoretikal na posibilidad ng paglitaw ng isang tinatawag na buffer overflow.
Tiyakin natin ang compiler sa pamamagitan ng pagpapakita nito na ang lahat ng mga hiwa ay magkapareho ang laki. Magagawa natin ito sa pamamagitan ng pagdaragdag ng simpleng check sa simula ng ating function.
Nakikita ito, ang compiler ay masayang nilaktawan ang tseke, at nagtatapos kami sa pag-save ng isa pang 500 nanosecond.
Malaking butches
Okay, nagawa naming i-squeeze ang ilang performance mula sa aming simpleng pagpapatupad, ngunit ang resultang ito ay talagang mas masahol pa kaysa posible sa kasalukuyang hardware.
Ang ginagawa lang namin ay mga basic bit operations, at ang aming mga processor ay gumaganap ng mga ito nang napakahusay. Ngunit, sa kasamaang-palad, "pinapakain" namin ang aming processor ng napakaliit na piraso ng trabaho. Ang aming mga function ay gumaganap ng mga operasyon sa isang byte-by-byte na batayan. Madali naming mai-tweak ang aming code para gumana sa mga 8-byte na chunks gamit ang UInt64 slices.
Gaya ng nakikita mo, ang maliit na pagbabagong ito ay nagpabilis ng aming programa ng walong beses sa pamamagitan ng pagtaas ng laki ng batch ng walong beses. Ang nakuha ay masasabing linear.
Pagpapatupad sa assembler
Ngunit hindi ito ang katapusan. Ang aming mga processor ay maaaring gumana sa mga chunks ng 16, 32 at kahit na 64 byte. Ang ganitong mga "malawak" na operasyon ay tinatawag na solong pagtuturo ng maramihang data (SIMD; isang pagtuturo, maraming data), at ang proseso ng pagbabago ng code upang magamit nito ang mga naturang operasyon ay tinatawag na vectorization.
Sa kasamaang palad, ang Go compiler ay malayo sa mahusay sa vectorization. Sa kasalukuyan, ang tanging paraan para i-vector ang Go code ay ang kunin at ilagay ang mga operasyong ito nang manu-mano gamit ang Go assembler.
Ang Go assembler ay isang kakaibang hayop. Malamang na alam mo na ang wika ng pagpupulong ay isang bagay na lubos na nauugnay sa arkitektura ng computer na iyong sinusulatan, ngunit hindi iyon ang kaso sa Go. Ang Go assembler ay mas katulad ng isang IRL (intermediate representation language) o intermediate na wika: ito ay halos independyente sa platform. Nagbigay ng mahusay na pagganap si Rob Pike sa paksang ito ilang taon na ang nakalipas sa GopherCon sa Denver.
Bilang karagdagan, gumagamit si Go ng hindi pangkaraniwang format ng Plan 9, na naiiba sa karaniwang tinatanggap na mga format ng AT&T at Intel.
Ligtas na sabihin na ang pagsusulat ng Go assembler gamit ang kamay ay hindi ang pinakanakakatuwa.
Ngunit, sa kabutihang palad, mayroon nang dalawang high-level na tool na tumutulong sa amin na isulat ang Go assembler: PeachPy at avo. Ang parehong mga utility ay bumubuo ng Go assembler mula sa mas mataas na antas ng code na nakasulat sa Python at Go, ayon sa pagkakabanggit.
Pinapasimple ng mga utility na ito ang mga bagay tulad ng alokasyon sa pagrehistro, pagsusulat ng mga loop, at sa pangkalahatan ay pinapasimple ang proseso ng pagpasok sa mundo ng assembly programming sa Go.
Gagamitin namin ang avo, kaya ang aming mga programa ay halos regular na mga programa ng Go.
Ito ang hitsura ng pinakasimpleng halimbawa ng isang avo program. Mayroon kaming pangunahing() function, na tumutukoy sa loob mismo ng Add() function, ang kahulugan nito ay magdagdag ng dalawang numero. Mayroong mga function ng helper dito upang makakuha ng mga parameter ayon sa pangalan at makakuha ng isa sa libre at angkop na mga rehistro ng processor. Ang bawat operasyon ng processor ay may kaukulang function sa avo, tulad ng nakikita sa ADDQ. Sa wakas, nakikita namin ang isang function ng helper para sa pag-iimbak ng resultang halaga.
Sa pamamagitan ng pagtawag sa go generate, isasagawa namin ang program sa avo at bilang resulta, dalawang file ang bubuo:
- add.s na may resultang code sa Go assembler;
- stub.go gamit ang mga header ng function upang ikonekta ang dalawang mundo: Go at assembler.
Ngayon na nakita na natin kung ano ang ginagawa ng avo at kung paano, tingnan natin ang ating mga function. Ipinatupad ko ang parehong scalar at vector (SIMD) na mga bersyon ng mga function.
Tingnan muna natin ang mga scalar na bersyon.
Tulad ng sa nakaraang halimbawa, humihingi kami ng libre at wastong pangkalahatang layunin na rehistro, hindi namin kailangang kalkulahin ang mga offset at laki para sa mga argumento. ginagawa ni avo ang lahat ng ito para sa atin.
Gumagamit kami noon ng mga label at goto (o jumps) para pahusayin ang performance at linlangin ang Go compiler, ngunit ngayon ay ginagawa na namin ito sa simula. Ang punto ay ang mga cycle ay isang mas mataas na antas ng konsepto. Sa assembler, mayroon lang kaming mga label at jump.
Ang natitirang code ay dapat na pamilyar at naiintindihan. Tinutularan namin ang isang loop na may mga label at jump, kumuha ng isang maliit na piraso ng data mula sa aming dalawang hiwa, pagsamahin ang mga ito sa isang maliit na operasyon (AT HINDI sa kasong ito) at pagkatapos ay ilagay ang resulta sa resultang slice. Lahat.
Ito ang hitsura ng huling assembler code. Hindi namin kinailangang kalkulahin ang mga offset at laki (naka-highlight sa berde) o subaybayan ang mga ginamit na rehistro (naka-highlight sa pula).
Kung ihahambing natin ang pagganap ng pagpapatupad ng assembly language sa pagganap ng pinakamahusay na pagpapatupad sa Go, makikita natin na pareho ito. At ito ay inaasahan. Pagkatapos ng lahat, wala kaming ginawang espesyal - ginawa lang namin kung ano ang gagawin ng isang Go compiler.
Sa kasamaang palad, hindi namin mapipilit ang compiler na i-inline ang aming mga function na nakasulat sa assembly language. Kasalukuyang walang ganoong feature ang Go compiler, bagama't may kahilingang idagdag ito sa loob ng mahabang panahon.
Ito ang dahilan kung bakit imposibleng makakuha ng anumang benepisyo mula sa maliliit na function sa assembly language. Kailangan nating magsulat ng malalaking function, o gamitin ang bagong math/bits package, o i-bypass ang assembler language.
Tingnan natin ngayon ang mga bersyon ng vector ng aming mga function.
Para sa halimbawang ito, nagpasya akong gumamit ng AVX2, kaya gagamit kami ng mga operasyon na gumagana sa 32-byte na mga chunks. Ang istraktura ng code ay halos kapareho sa scalar na bersyon: naglo-load ng mga parameter, humihingi ng libreng nakabahaging rehistro, atbp.
Ang isang pagbabago ay ang mas malawak na mga operasyon ng vector ay gumagamit ng mga espesyal na malawak na rehistro. Sa kaso ng 32-byte na chunks, ito ay mga register na may prefix na Y. Ito ang dahilan kung bakit nakikita mo ang YMM() function sa code. Kung gumagamit ako ng AVX-512 na may mga 64-bit na chunks, ang prefix ay Z.
Ang pangalawang inobasyon ay nagpasya akong gumamit ng isang pag-optimize na tinatawag na loop unrolling, na nangangahulugang paggawa ng walong loop operation nang manu-mano bago tumalon sa simula ng loop. Binabawasan ng pag-optimize na ito ang bilang ng mga sangay sa code, at nililimitahan ng bilang ng mga libreng rehistro na magagamit.
Well, ano ang tungkol sa pagganap? Ang ganda niya! Nakamit namin ang bilis na humigit-kumulang pitong beses kumpara sa pinakamahusay na solusyon sa Go. Kahanga-hanga, tama?
Ngunit kahit na ang pagpapatupad na ito ay posibleng mapabilis sa pamamagitan ng paggamit ng AVX-512, prefetching o isang JIT (just-in-time compiler) para sa query scheduler. Ngunit ito ay tiyak na isang paksa para sa isang hiwalay na ulat.
Mga problema sa mga index ng bitmap
Ngayon na tiningnan na natin ang isang simpleng pagpapatupad ng isang bitmap index sa Go at isang mas produktibo sa wika ng pagpupulong, sa wakas ay pag-usapan natin kung bakit bihirang gamitin ang mga index ng bitmap.
Ang mga mas lumang papel ay nagbanggit ng tatlong mga problema sa mga index ng bitmap, ngunit ang mga mas bagong papel at pinagtatalunan ko na ang mga ito ay hindi na nauugnay. Hindi natin susuriin nang malalim ang bawat isa sa mga problemang ito, ngunit titingnan natin ang mga ito nang mababaw.
Ang problema ng mataas na cardinality
Kaya, sinabi sa amin na ang mga index ng bitmap ay angkop lamang para sa mga patlang na may mababang cardinality, iyon ay, ang mga may kaunting mga halaga (halimbawa, kasarian o kulay ng mata), at ang dahilan ay ang karaniwang representasyon ng naturang mga patlang (isa bit per value) sa kaso ng mataas na cardinality, ito ay kukuha ng masyadong maraming espasyo at, bukod pa rito, ang mga bitmap index na ito ay magiging mahina (bihirang) mapupunan.
Minsan maaari kaming gumamit ng ibang representasyon, tulad ng karaniwang ginagamit namin upang kumatawan sa mga numero. Ngunit ito ay ang pagdating ng mga algorithm ng compression na nagbago ng lahat. Sa nakalipas na mga dekada, nakabuo ang mga siyentipiko at mananaliksik ng malaking bilang ng mga compression algorithm para sa mga bitmap. Ang kanilang pangunahing bentahe ay hindi na kailangang i-decompress ang mga bitmap upang magsagawa ng mga bit operation - maaari tayong magsagawa ng mga bit operation nang direkta sa mga naka-compress na bitmap.
Kamakailan, nagsimulang lumitaw ang mga hybrid approach, tulad ng umuungal na mga bitmap. Sabay-sabay silang gumagamit ng tatlong magkakaibang representasyon para sa mga bitmap - mga bitmap mismo, mga array at tinatawag na bit run - at balanse sa pagitan ng mga ito upang mapakinabangan ang pagganap at mabawasan ang pagkonsumo ng memorya.
Makakahanap ka ng mga umuungal na bitmap sa mga pinakasikat na application. Mayroon nang isang malaking bilang ng mga pagpapatupad para sa isang malawak na iba't ibang mga programming language, kabilang ang higit sa tatlong mga pagpapatupad para sa Go.
Ang isa pang diskarte na makakatulong sa atin na harapin ang mataas na cardinality ay tinatawag na binning. Isipin na mayroon kang isang patlang na kumakatawan sa taas ng isang tao. Ang taas ay isang floating point na numero, ngunit tayong mga tao ay hindi ganoon ang iniisip. Para sa amin walang pagkakaiba sa pagitan ng taas na 185,2 cm at 185,3 cm.
Ito ay lumiliko na maaari naming pangkatin ang mga katulad na halaga sa mga grupo sa loob ng 1 cm.
At kung alam din natin na napakakaunting mga tao ay mas maikli sa 50 cm at mas mataas sa 250 cm, kung gayon maaari nating gawing isang patlang na may kardinal na humigit-kumulang 200 mga halaga ang isang field na may walang katapusang cardinality.
Siyempre, kung kinakailangan, maaari tayong gumawa ng karagdagang pag-filter pagkatapos.
Problema sa Mataas na Bandwidth
Ang susunod na problema sa mga index ng bitmap ay ang pag-update ng mga ito ay maaaring maging napakamahal.
Ang mga database ay dapat na makapag-update ng data habang posibleng daan-daang iba pang mga query ang naghahanap sa data. Kailangan namin ng mga kandado upang maiwasan ang mga problema sa kasabay na pag-access ng data o iba pang mga problema sa pagbabahagi. At kung saan mayroong isang malaking lock, mayroong isang problema - pagtatalo sa lock, kapag ang lock na ito ay naging isang bottleneck.
Ang problemang ito ay maaaring malutas o maiiwasan sa pamamagitan ng paggamit ng sharding o paggamit ng mga bersyon na index.
Ang shading ay isang simple at kilalang bagay. Maaari mong i-shard ang isang bitmap index tulad ng gagawin mo sa anumang iba pang data. Sa halip na isang malaking lock, makakakuha ka ng isang bungkos ng maliliit na kandado at sa gayon ay mapupuksa ang pagtatalo sa lock.
Ang pangalawang paraan upang malutas ang problema ay ang paggamit ng mga bersyon na index. Maaari kang magkaroon ng isang kopya ng index na ginagamit mo para sa paghahanap o pagbabasa, at isa na ginagamit mo para sa pagsusulat o pag-update. At isang beses sa isang tiyak na tagal ng panahon (halimbawa, isang beses sa bawat 100 ms o 500 ms) duplicate mo ang mga ito at palitan ang mga ito. Siyempre, ang diskarte na ito ay naaangkop lamang sa mga kaso kung saan ang iyong aplikasyon ay maaaring humawak ng bahagyang nahuhuli na index ng paghahanap.
Ang dalawang approach na ito ay maaaring gamitin nang sabay-sabay: maaari kang magkaroon ng sharded versioned index.
Mas kumplikadong mga query
Ang panghuling problema sa mga index ng bitmap ay sinasabi sa amin na hindi sila angkop para sa mas kumplikadong mga uri ng mga query, tulad ng mga span query.
Sa katunayan, kung iisipin mo, ang mga bit operation tulad ng AND, OR, atbp. ay hindi masyadong angkop para sa mga query a la "Ipakita sa akin ang mga hotel na may mga rate ng kuwarto mula 200 hanggang 300 dolyar bawat gabi."
Ang isang walang muwang at napaka hindi matalinong solusyon ay ang kunin ang mga resulta para sa bawat halaga ng dolyar at pagsamahin ang mga ito sa isang bitwise O operasyon.
Ang isang bahagyang mas mahusay na solusyon ay ang paggamit ng pagpapangkat. Halimbawa, sa mga grupo ng 50 dolyar. Ito ay magpapabilis sa aming proseso ng 50 beses.
Ngunit ang problema ay madaling malutas sa pamamagitan ng paggamit ng view na partikular na nilikha para sa ganitong uri ng kahilingan. Sa mga siyentipikong papel ito ay tinatawag na range-encoded bitmaps.
Sa representasyong ito, hindi lang namin itinatakda ang isang bit para sa ilang halaga (halimbawa, 200), ngunit itinatakda ang halagang ito at lahat ng mas mataas. 200 pataas. Pareho para sa 300: 300 at mas mataas. At iba pa.
Gamit ang representasyong ito, masasagot natin ang ganitong uri ng query sa paghahanap sa pamamagitan ng pagtawid sa index nang dalawang beses lang. Una, kukuha kami ng listahan ng mga hotel kung saan mas mababa ang halaga ng kuwarto o $300, at pagkatapos ay aalisin namin doon ang mga kung saan mas mababa ang halaga ng kuwarto o $199. handa na.
Magugulat ka, ngunit kahit na ang mga geoquery ay posible gamit ang mga index ng bitmap. Ang lansihin ay gumamit ng geometric na representasyon na pumapalibot sa iyong coordinate ng isang geometric na pigura. Halimbawa, S2 mula sa Google. Ang figure ay dapat na posible na kumatawan sa anyo ng tatlo o higit pang mga intersecting na linya na maaaring bilangin. Sa ganitong paraan maaari nating gawing ilang query ang geoquery natin "sa kahabaan ng gap" (kasama ang mga numerong linyang ito).
Handa Solusyon
Sana ay interesado ako sa iyo nang kaunti at mayroon ka na ngayong isa pang kapaki-pakinabang na tool sa iyong arsenal. Kung sakaling kailanganin mong gawin ang isang bagay na tulad nito, malalaman mo kung aling paraan ang titingnan.
Gayunpaman, hindi lahat ay may oras, pasensya, o mapagkukunan upang lumikha ng mga index ng bitmap mula sa simula. Lalo na ang mga mas advanced, gamit ang SIMD, halimbawa.
Sa kabutihang-palad, mayroong ilang mga handa na solusyon upang matulungan ka.
Umuungol na mga bitmap
Una, mayroong parehong umuungal na bitmaps library na napag-usapan ko na. Naglalaman ito ng lahat ng kinakailangang lalagyan at bit operation na kakailanganin mo upang makagawa ng isang ganap na index ng bitmap.
Sa kasamaang palad, sa ngayon, wala sa mga pagpapatupad ng Go ang gumagamit ng SIMD, na nangangahulugan na ang mga pagpapatupad ng Go ay hindi gaanong gumaganap kaysa sa mga pagpapatupad ng C, halimbawa.
mabalahibo
Ang isa pang produkto na makakatulong sa iyo ay ang Pilosa DBMS, na, sa katunayan, mayroon lamang mga bitmap index. Ito ay medyo bagong solusyon, ngunit ito ay nakakapanalo ng mga puso sa napakabilis.
Ang Pilosa ay gumagamit ng umuungal na mga bitmap sa loob at nagbibigay sa iyo ng kakayahang gamitin ang mga ito, pinapasimple at ipinapaliwanag ang lahat ng mga bagay na napag-usapan ko sa itaas: pagpapangkat, mga bitmap na naka-encode ng saklaw, ang konsepto ng isang field, atbp.
Tingnan natin ang isang halimbawa ng paggamit ng Pilosa upang sagutin ang isang tanong na pamilyar ka na.
Ang halimbawa ay halos kapareho ng nakita mo noon. Lumilikha kami ng isang kliyente sa server ng Pilosa, lumikha ng isang index at mga kinakailangang field, pagkatapos ay punan ang aming mga field ng random na data na may mga probabilidad at, sa wakas, isagawa ang pamilyar na query.
Pagkatapos nito, ginagamit namin ang HINDI sa field na "mahal", pagkatapos ay i-intersect ang resulta (o AT ito) sa field na "terrace" at sa field na "reservations". At sa wakas, nakuha namin ang huling resulta.
Talagang umaasa ako na sa hinaharap ang bagong uri ng index na ito ay lalabas din sa mga DBMS tulad ng MySQL at PostgreSQL - mga index ng bitmap.
Konklusyon
Kung hindi ka pa natutulog, salamat. Kinailangan kong saglit na talakayin ang maraming paksa dahil sa limitadong oras, ngunit umaasa ako na ang pag-uusap ay kapaki-pakinabang at maaaring maging motivating.
Ang mga index ng bitmap ay magandang malaman, kahit na hindi mo kailangan ang mga ito sa ngayon. Hayaan silang maging isa pang tool sa iyong toolbox.
Tiningnan namin ang iba't ibang mga trick sa pagganap para sa Go at mga bagay na hindi pa masyadong nahahawakan ng Go compiler. Ngunit ito ay ganap na kapaki-pakinabang para sa bawat Go programmer na malaman.
Yun lang ang gusto kong sabihin sayo. Salamat!
Pinagmulan: www.habr.com