pasiuna
Gihatag nako kini nga taho sa English sa komperensya sa GopherCon Russia 2019 sa Moscow ug sa Russian sa usa ka meetup sa Nizhny Novgorod. Naghisgot kami bahin sa usa ka bitmap index - dili kaayo komon kaysa B-tree, apan dili kaayo makapaikag. Pagpaambit mga pakigpulong sa komperensya sa English ug text transcript sa Russian.
Atong tan-awon kung giunsa ang usa ka bitmap index molihok, kung kini mas maayo, kung kini labi ka daotan kaysa sa ubang mga indeks, ug sa unsang mga kaso kini labi ka paspas kaysa kanila; Atong tan-awon kung unsang mga sikat nga DBMS ang aduna nay bitmap index; Atong sulayan pagsulat ang atong kaugalingon sa Go. Ug "alang sa dessert" mogamit kami og andam nga mga librarya sa paghimo sa among kaugalingon nga labing paspas nga espesyal nga database.
Naglaum gyud ko nga ang akong mga buhat mahimong mapuslanon ug makapaikag alang kanimo. Lakaw!
Pasiuna
Kumusta tanan! Alas sayis na sa gabii ug super kapoy namong tanan. Maayo nga panahon sa paghisgot bahin sa makalaay nga teorya sa indeks sa database, dili ba? Ayaw kabalaka, aduna koy pipila ka linya sa source code dinhi ug didto. π
Gawas sa tanan nga mga komedya, ang taho puno sa kasayuran, ug kami walaβy daghang oras. So sugdan na nato.
Karon maghisgot ako bahin sa mosunod:
- unsa ang mga indeks;
- unsa ang bitmap index;
- asa kini gigamit ug asa kini DILI gigamit ug ngano;
- yano nga pagpatuman sa Go ug gamay nga pakigbisog sa compiler;
- gamay nga dili kaayo yano, apan labi ka produktibo nga pagpatuman sa Go assembler;
- "mga problema" sa mga bitmap index;
- kasamtangan nga mga implementasyon.
Busa unsa ang mga indeks?
Ang indeks usa ka bulag nga istruktura sa datos nga among gipadayon ug gi-update dugang sa panguna nga datos. Gigamit kini aron mapadali ang pagpangita. Kung walay mga indeks, ang pagpangita kinahanglan nga moagi sa datos sa hingpit (usa ka proseso nga gitawag og full scan), ug kini nga proseso adunay linear algorithmic complexity. Apan ang mga database kasagaran adunay daghang mga datos ug ang linear nga pagkakomplikado hinay kaayo. Sa tinuud, makakuha kita usa ka logarithmic o kanunay.
Kini usa ka hilabihan ka komplikado nga hilisgutan, nga puno sa mga subtleties ug trade-offs, apan human sa pagtan-aw sa mga dekada sa database development ug research, ako andam sa pag-ingon nga adunay pipila lamang ka kaylap nga gigamit nga mga pamaagi sa paghimo sa database index.
Ang una nga pamaagi mao ang hierarchically pagpakunhod sa search space, pagbahin sa search space ngadto sa gagmay nga mga bahin.
Kasagaran atong buhaton kini gamit ang lain-laing klase sa mga kahoy. Usa ka pananglitan mao ang usa ka dako nga kahon sa mga materyales sa imong aparador nga adunay mas gagmay nga mga kahon sa mga materyales nga gibahin sa lainlaing mga hilisgutan. Kung kinahanglan nimo ang mga materyales, lagmit pangitaon nimo kini sa usa ka kahon nga nag-ingon nga "Mga Materyal" kaysa usa nga nag-ingon nga "Cookies," di ba?
Ang ikaduha nga paagi mao ang pagpili dayon sa gusto nga elemento o grupo sa mga elemento. Gihimo namo kini sa hash nga mga mapa o reverse index. Ang paggamit sa hash nga mga mapa susama kaayo sa miaging pananglitan, apan imbes nga usa ka kahon sa mga kahon, aduna kay usa ka hugpong sa gagmay nga mga kahon sa katapusang mga butang sa imong aparador.
Ang ikatulo nga paagi mao ang pagwagtang sa panginahanglan sa pagpangita. Gihimo namo kini gamit ang mga filter sa Bloom o mga filter sa cuckoo. Ang mga una naghatag dayon og tubag, nga nagluwas kanimo gikan sa pagpangita.
Ang kataposang paagi mao ang bug-os nga paggamit sa tanang gahom nga gihatag kanato sa modernong hardware. Mao gyud ni ang atong gibuhat sa mga bitmap index. Oo, kung gamiton kini usahay kinahanglan namon nga moagi sa tibuuk nga indeks, apan gihimo namon kini nga labi ka episyente.
Sama sa akong giingon, ang hilisgutan sa mga indeks sa database dako ug puno sa mga pagkompromiso. Nagpasabot kini nga usahay makagamit kita ug daghang mga pamaagi sa samang higayon: kung kinahanglan namong paspasan pa ang pagpangita, o kung kinahanglan natong tabonan ang tanang posibleng matang sa pagpangita.
Karon maghisgot ako bahin sa labing gamay nga nahibal-an nga pamaagi niini - mga indeks sa bitmap.
Kinsa man ako aron mamulong bahin niini nga hilisgutan?
Nagtrabaho ko isip lead team sa Badoo (tingali mas pamilyar ka sa among ubang produkto, Bumble). Kami adunay labaw pa sa 400 milyon nga mga tiggamit sa tibuuk kalibutan ug daghang mga bahin nga nagpili sa labing kaayo nga tugma alang kanila. Gihimo namo kini gamit ang custom nga mga serbisyo, lakip ang mga bitmap index.
Busa unsa ang usa ka bitmap index?
Ang mga index sa bitmap, sumala sa gisugyot sa ngalan, naggamit og mga bitmap o bitset aron ipatuman ang usa ka indeks sa pagpangita. Gikan sa panan-aw sa mata sa langgam, kini nga indeks naglangkob sa usa o daghan pa nga mga bitmap nga nagrepresentar sa bisan unsang mga entidad (sama sa mga tawo) ug ang ilang mga kabtangan o mga parameter (edad, kolor sa mata, ug uban pa), ug usa ka algorithm nga naggamit mga gamay nga operasyon (UG, O, DILI. ) aron matubag ang pangutana sa pagpangita.
Gisultihan kami nga ang mga indeks sa bitmap labing haum ug maayo kaayo alang sa mga kaso diin adunay mga pagpangita nga naghiusa sa mga pangutana sa daghang mga ubos nga kolum sa cardinality (hunahunaa ang "kolor sa mata" o "status sa kaminyoon" kumpara sa usa ka butang sama sa "distansya gikan sa sentro sa lungsod"). Apan akong ipakita sa ulahi nga sila nagtrabaho nga maayo alang sa taas nga mga kolum sa kardinal usab.
Atong tan-awon ang pinakasimple nga pananglitan sa usa ka bitmap index.
Hunahunaa nga kami adunay usa ka lista sa mga restawran sa Moscow nga adunay binary nga mga kabtangan sama niini:
- duol sa metro;
- adunay pribadong parkinganan;
- adunay beranda (adunay terrace);
- pwede ka magpareserba ug lamesa (modawat ug reserbasyon);
- angay alang sa mga vegetarian (vegan friendly);
- mahal (mahal).
Atong hatagan ang matag restawran og sequence number sugod sa 0 ug igahin ang memorya alang sa 6 ka bitmaps (usa alang sa matag kinaiya). Atong puy-an kini nga mga bitmap depende kung ang restawran adunay kini nga kabtangan o wala. Kung ang restawran 4 adunay beranda, unya ang bit No. 4 sa bitmap nga "adunay beranda" ibutang sa 1 (kung walay beranda, unya sa 0).
Karon aduna na kitay pinakasimple nga bitmap index nga posible, ug magamit nato kini sa pagtubag sa mga pangutana sama sa:
- "Ipakita kanako ang vegetarian-friendly nga mga restawran";
- "Ipakita kanako ang barato nga mga restawran nga adunay beranda diin mahimo kang magpareserba ug lamesa."
Giunsa? Atong tan-awon. Ang una nga hangyo yano ra kaayo. Ang kinahanglan lang natong buhaton mao ang pagkuha sa "vegetarian friendly" nga bitmap ug himoa kini nga usa ka lista sa mga restawran kansang mga piraso gibutyag.
Ang ikaduha nga hangyo mas komplikado. Kinahanglan natong gamiton ang DILI bitmap sa "mahal" nga bitmap aron makakuha og listahan sa mga barato nga restawran, unya UG kini sa bitmap nga "mahimo ba kong mag-book ug lamesa", ug UG ang resulta sa bitmap nga "adunay beranda". Ang resulta nga bitmap maglangkob sa usa ka lista sa mga establisemento nga nakab-ot ang tanan namong mga pamatasan. Niini nga pananglitan, kini lamang ang Yunost nga restawran.
Adunay daghang mga teorya nga nalangkit, apan ayaw kabalaka, makita namon ang code sa dili madugay.
Asa gigamit ang mga bitmap index?
Kung mag-index ka sa bitmap sa Google, 90% sa mga tubag adunay kalabutan sa Oracle DB sa usa ka paagi o lain. Apan ang ubang mga DBMS tingali nagsuporta usab sa usa ka cool nga butang, di ba? Dili gyud.
Atong susihon ang listahan sa mga nag-unang suspek.
Ang MySQL wala pa nagsuporta sa mga bitmap index, apan adunay usa ka Proposal nga nagsugyot sa pagdugang niini nga opsyon ().
Ang PostgreSQL wala nagsuporta sa mga bitmap index, apan naggamit sa yano nga mga bitmap ug bit nga mga operasyon aron makombinar ang mga resulta sa pagpangita sa daghang uban pang mga indeks.
Ang Tarantool adunay mga bitset index ug nagsuporta sa yano nga pagpangita niini.
Ang Redis adunay yano nga mga bitfield) nga walay abilidad sa pagpangita kanila.
Ang MongoDB wala pa nagsuporta sa mga bitmap index, apan adunay usa usab nga Proposal nga nagsugyot nga kini nga kapilian idugang
Ang Elasticsearch naggamit sa mga bitmap sa sulod).
- Apan bag-ong silingan ang mitungha sa among balay: Pilosa. Kini usa ka bag-ong non-relational database nga gisulat sa Go. Naglangkob lamang kini sa mga indeks sa bitmap ug gibase ang tanan niini. Atong hisgotan kini sa ulahi.
Implementasyon sa Go
Apan ngano nga ang mga indeks sa bitmap panagsa ra nga gigamit? Sa dili pa tubagon kini nga pangutana, gusto nako nga ipakita kanimo kung giunsa ang pagpatuman sa usa ka yano nga bitmap index sa Go.
Ang mga bitmaps esensya mga piraso lang sa datos. Sa Go, gamiton nato ang byte slices para niini.
Adunay kami usa ka bitmap alang sa usa ka kinaiya sa restawran, ug ang matag bit sa bitmap nagpaila kung ang usa ka partikular nga restawran adunay kini nga kabtangan o wala.
Magkinahanglan kita og duha ka mga function sa katabang. Ang usa gamiton aron pun-on ang atong mga bitmap sa random data. Random, apan adunay usa ka piho nga posibilidad nga ang restawran adunay matag kabtangan. Pananglitan, nagtuo ko nga gamay ra ang mga restawran sa Moscow diin dili ka makareserba ug usa ka lamesa, ug para nako mga 20% sa mga establisemento ang angay alang sa mga vegetarian.
Ang ikaduhang function mag-convert sa bitmap ngadto sa listahan sa mga restawran.
Aron matubag ang pangutana nga "Ipakita kanako ang mga barato nga restawran nga adunay patio ug mahimo nga magpareserba," kinahanglan namon ang duha ka gamay nga operasyon: DILI ug UG.
Mahimo natong pasimplehon og gamay ang atong code pinaagi sa paggamit sa mas komplikado UG DILI operator.
Kami adunay mga gimbuhaton alang sa matag usa niini nga mga operasyon. Ang duha moagi sa mga hiwa, kuhaa ang katugbang nga mga elemento gikan sa matag usa, isagol kini sa gamay nga operasyon ug ibutang ang resulta sa resulta nga hiwa.
Ug karon magamit na nato ang atong mga bitmaps ug functions para matubag ang search query.
Ang pasundayag dili ingon ka taas, bisan kung ang mga gimbuhaton yano ra ug nakadaginot kami og daghang salapi pinaagi sa dili pagbalik sa usa ka bag-ong resulta nga hiwa sa matag higayon nga ang function gitawag.
Human sa paghimo og gamay nga profiling sa pprof, akong namatikdan nga ang Go compiler kulang sa usa ka yano kaayo apan importante kaayo nga pag-optimize: function inlining.
Ang tinuod mao nga ang Go compiler nahadlok kaayo sa mga loops nga moagi sa mga hiwa, ug categorically nagdumili sa inline functions nga adunay sulod nga mga loops.
Apan wala ako mahadlok ug mahimo nako nga malimbongan ang compiler pinaagi sa paggamit sa goto imbes sa usa ka loop, sama sa maayong mga adlaw.
Ug, ingon sa imong nakita, karon ang compiler malipayon nga mag-inline sa among function! Ingon usa ka sangputanan, nakatipig kami mga 2 microseconds. Dili daotan!
Ang ikaduha nga bottleneck dali nga makita kung imong tan-awon pag-ayo ang output sa asembliya. Ang compiler midugang og slice boundary check sulod mismo sa among pinakainit nga loop. Ang tinuod mao nga ang Go usa ka luwas nga pinulongan, nahadlok ang compiler nga ang akong tulo ka argumento (tulo ka hiwa) lainlain ang gidak-on. Human sa tanan, unya adunay usa ka teoretikal nga posibilidad nga mahitabo ang usa ka gitawag nga buffer overflow.
Atong ipasalig ang compiler pinaagi sa pagpakita niini nga ang tanan nga mga hiwa parehas ang gidak-on. Mahimo nato kini pinaagi sa pagdugang og yano nga tseke sa sinugdanan sa atong function.
Sa pagkakita niini, malipayong gilaktawan sa tigkompiler ang tseke, ug natapos namo ang pagluwas ug laing 500 ka nanosecond.
Dako nga butch
Okay, nakahimo kami sa pagpiit sa pipila ka pasundayag gikan sa among yano nga pagpatuman, apan kini nga resulta sa tinuud labi ka daotan kaysa mahimo sa karon nga hardware.
Ang tanan nga among gibuhat mao ang sukaranan nga mga operasyon sa bit, ug ang among mga processor naghimo niini nga episyente kaayo. Apan, sa kasubo, among "gipakaon" ang among processor sa gagmay kaayo nga mga piraso sa trabaho. Ang among mga gimbuhaton naghimo sa mga operasyon sa usa ka byte-by-byte nga basehan. Sayon ra kaayo namo nga ma-tweak ang among code para magamit ang 8-byte nga mga tipak gamit ang UInt64 nga mga hiwa.
Sama sa imong nakita, kining gamay nga pagbag-o nagpadali sa among programa sa walo ka beses pinaagi sa pagdugang sa gidak-on sa batch sa walo ka beses. Ang ganansya maingon nga linear.
Pagpatuman sa assembler
Apan dili kini ang katapusan. Ang among mga processor makatrabaho sa mga tipik sa 16, 32 ug bisan 64 bytes. Ang ingon nga "halapad" nga mga operasyon gitawag nga usa ka panudlo nga daghang data (SIMD; usa ka panudlo, daghang datos), ug ang proseso sa pagbag-o sa code aron magamit ang ingon nga mga operasyon gitawag nga vectorization.
Ikasubo, ang Go compiler layo sa kaayo sa vectorization. Sa pagkakaron, ang bugtong paagi sa pag-vector sa Go code mao ang pagkuha ug pagbutang niini nga mga operasyon nga mano-mano gamit ang Go assembler.
Ang Go assembler usa ka katingad-an nga mananap. Tingali nahibal-an nimo nga ang sinultian nga asembliya usa ka butang nga nalambigit pag-ayo sa arkitektura sa kompyuter nga imong gisulatan, apan dili kana ang kaso sa Go. Ang Go assembler mas susama sa usa ka IRL (intermediate representation language) o intermediate nga pinulongan: kini halos independente sa plataporma. Naghatag si Rob Pike og maayo kaayo nga pasundayag sa niini nga hilisgutan pipila ka tuig na ang milabay sa GopherCon sa Denver.
Dugang pa, ang Go naggamit ug dili kasagaran nga Plano 9 nga pormat, nga lahi sa kasagarang gidawat nga AT&T ug Intel nga mga format.
Luwas nga isulti nga ang pagsulat sa Go assembler pinaagi sa kamot dili ang labing makalingaw.
Apan, maayo na lang, aduna nay duha ka taas nga lebel nga mga himan nga makatabang kanamo sa pagsulat sa Go assembler: PeachPy ug avo. Ang duha ka mga utilities makamugna og Go assembler gikan sa mas taas nga lebel nga code nga gisulat sa Python ug Go, matag usa.
Kini nga mga utilities nagpasimple sa mga butang sama sa pagrehistro sa alokasyon, pagsulat sa mga loop, ug sa kasagaran gipasimple ang proseso sa pagsulod sa kalibutan sa assembly programming sa Go.
Atong gamiton ang avo, mao nga ang atong mga programa mahimong halos regular nga mga programa sa Go.
Mao kini ang hitsura sa pinakasimple nga pananglitan sa usa ka avo program. Kita adunay usa ka main() function, nga naghubit sa sulod sa iyang kaugalingon sa Add() function, ang kahulogan niini mao ang pagdugang og duha ka numero. Adunay mga function sa katabang dinhi aron makuha ang mga parameter pinaagi sa ngalan ug makakuha usa sa libre ug angay nga mga rehistro sa processor. Ang matag operasyon sa processor adunay katugbang nga function sa avo, ingon sa makita sa ADDQ. Sa katapusan, nakita namon ang usa ka function sa katabang alang sa pagtipig sa sangputanan nga kantidad.
Pinaagi sa pagtawag sa go generate, atong ipatuman ang programa sa avo ug isip resulta, duha ka file ang mabuhat:
- add.s uban ang resulta nga code sa Go assembler;
- stub.go uban ang function header aron makonektar ang duha ka kalibutan: Lakaw ug assembler.
Karon nga nakita na nato kung unsa ang gibuhat sa avo ug giunsa, atong tan-awon ang atong mga gimbuhaton. Gipatuman nako ang mga bersyon sa scalar ug vector (SIMD) sa mga gimbuhaton.
Atong tan-awon una ang scalar nga mga bersyon.
Sama sa miaging pananglitan, nangayo kami og libre ug balido nga rehistro sa kinatibuk-ang katuyoan, dili na kinahanglan nga kuwentahon ang mga offset ug gidak-on alang sa mga argumento. gibuhat ni avo kining tanan para kanato.
Gigamit namo kaniadto ang mga label ug goto (o paglukso) aron mapalambo ang performance ug limbong sa Go compiler, apan karon gibuhat na namo kini gikan sa sinugdanan. Ang punto mao nga ang mga siklo usa ka mas taas nga lebel nga konsepto. Sa assembler, naa ra mi mga label ug paglukso.
Ang nahabilin nga code kinahanglan nga pamilyar ug masabtan. Gisundog namo ang usa ka loop nga adunay mga label ug paglukso, pagkuha og gamay nga piraso sa datos gikan sa among duha ka mga hiwa, isagol kini sa gamay nga operasyon (UG DILI niini nga kaso) ug dayon ibutang ang resulta ngadto sa resulta nga hiwa. Tanan.
Mao kini ang hitsura sa katapusang assembler code. Dili na namo kinahanglang kuwentahon ang mga offset ug gidak-on (gi-highlight sa berde) o bantayan ang mga rehistro nga gigamit (gi-highlight sa pula).
Kung atong itandi ang performance sa pagpatuman sa assembly language sa performance sa pinakamaayong implementasyon sa Go, atong makita nga parehas ra kini. Ug kini gipaabot. Human sa tanan, wala kami'y gibuhat nga espesyal - gi-reproduce lang namo kung unsa ang buhaton sa usa ka Go compiler.
Ikasubo, dili namo mapugos ang compiler sa pag-inline sa among mga function nga gisulat sa assembly language. Ang Go compiler sa pagkakaron walay ingon nga bahin, bisan kung adunay usa ka hangyo nga idugang kini sa dugay nga panahon.
Kini ang hinungdan nga imposible nga makakuha og bisan unsang kaayohan gikan sa gagmay nga mga gimbuhaton sa sinultian nga asembliya. Kinahanglan namong magsulat ug dagkong mga gimbuhaton, o gamiton ang bag-ong math/bits nga pakete, o laktawan ang assembler nga pinulongan.
Atong tan-awon karon ang mga bersyon sa vector sa atong mga gimbuhaton.
Alang niini nga pananglitan, nakahukom ko nga gamiton ang AVX2, mao nga gamiton namo ang mga operasyon nga naglihok sa 32-byte nga mga tipak. Ang istruktura sa code susama kaayo sa scalar nga bersyon: pag-load sa mga parameter, pagpangayo og libre nga shared register, etc.
Usa ka kabag-ohan mao nga ang mas lapad nga mga operasyon sa vector naggamit ug espesyal nga lapad nga mga rehistro. Sa kaso sa 32-byte chunks, kini ang mga rehistro nga prefix sa Y. Mao kini ang hinungdan nga imong makita ang YMM() function sa code. Kung gigamit nako ang AVX-512 nga adunay 64-bit nga mga tipak, ang prefix mao ang Z.
Ang ikaduha nga kabag-ohan mao nga nakahukom ko nga gamiton ang usa ka pag-optimize nga gitawag nga loop unrolling, nga nagpasabut nga mano-mano ang pagbuhat sa walo ka mga operasyon sa loop sa dili pa molukso sa sinugdanan sa loop. Kini nga pag-optimize nagpamenos sa gidaghanon sa mga sanga sa code, ug limitado sa gidaghanon sa libre nga mga rehistro nga magamit.
Aw, unsa ang mahitungod sa performance? Gwapa siya! Nakab-ot namon ang usa ka tulin nga mga pito ka beses kung itandi sa labing kaayo nga solusyon sa Go. Impressive, dili ba?
Apan bisan kini nga pagpatuman mahimoβg mapadali pinaagi sa paggamit sa AVX-512, prefetching o usa ka JIT (just-in-time compiler) para sa scheduler sa pangutana. Apan kini usa ka hilisgutan alang sa usa ka lahi nga taho.
Mga problema sa bitmap index
Karon nga ato nang gitan-aw ang usa ka yano nga pagpatuman sa usa ka bitmap index sa Go ug usa ka labi ka produktibo sa usa ka sinultian nga asembliya, sa katapusan atong hisgutan kung ngano nga ang mga indeks sa bitmap talagsa ra nga gigamit.
Ang mga daan nga mga papel naghisgot sa tulo ka mga problema sa mga indeks sa bitmap, apan ang mga bag-ong papel ug ako nangatarungan nga kini dili na may kalabutan. Dili nato tukion pag-ayo ang matag usa niini nga mga problema, apan tan-awon nato kini sa taphaw.
Ang problema sa taas nga kardinal
Mao nga, gisultihan kami nga ang mga indeks sa bitmap angay lamang alang sa mga natad nga adunay gamay nga kardinal, nga mao, kadtong adunay gamay nga kantidad (pananglitan, gender o kolor sa mata), ug ang hinungdan mao nga ang naandan nga representasyon sa ingon nga mga natad (usa. bit per value) sa kaso sa taas nga cardinality, magkinahanglan kini og sobra nga luna ug, dugang pa, kini nga mga bitmap index mahimong dili maayo (panagsa ra) mapuno.
Usahay mahimo natong gamiton ang laing representasyon, sama sa standard nga atong gigamit sa pagrepresentar sa mga numero. Apan kini ang pag-abut sa mga algorithm sa compression nga nagbag-o sa tanan. Sa milabay nga mga dekada, ang mga siyentista ug mga tigdukiduki nakahimo og daghang gidaghanon sa mga compression algorithm alang sa mga bitmaps. Ang ilang panguna nga bentaha mao nga dili kinahanglan nga i-decompress ang mga bitmap aron mahimo ang mga operasyon sa gamay - mahimo namon nga himuon ang mga operasyon sa gamay nga direkta sa mga naka-compress nga bitmap.
Bag-ohay lang, ang hybrid nga mga pamaagi nagsugod na sa pagpakita, sama sa nagngulob nga mga bitmap. Sila dungan nga naggamit sa tulo ka lain-laing mga representasyon alang sa mga bitmaps - bitmaps sa ilang kaugalingon, arrays ug sa gitawag nga bit run - ug balanse tali kanila aron sa pagpausbaw sa performance ug pagmenos sa memory konsumo.
Makita nimo ang nagngulob nga mga bitmap sa labing inila nga mga aplikasyon. Adunay na usa ka dako nga gidaghanon sa mga pagpatuman alang sa usa ka halapad nga lainlain nga mga programming language, lakip ang labaw pa sa tulo nga mga pagpatuman alang sa Go.
Ang laing paagi nga makatabang kanato sa pag-atubang sa taas nga cardinality gitawag nga binning. Hunahunaa nga ikaw adunay usa ka uma nga nagrepresentar sa gitas-on sa usa ka tawo. Ang gitas-on kay usa ka floating point nga numero, apan kitang mga tawo wala maghunahuna niini nga paagi. Alang kanamo walay kalainan tali sa gitas-on nga 185,2 cm ug 185,3 cm.
Kini nahimo nga mahimo natong igrupo ang parehas nga mga kantidad sa mga grupo sa sulod sa 1 cm.
Ug kung nahibal-an usab naton nga gamay ra nga mga tawo ang labi ka mubu kaysa 50 cm ug mas taas sa 250 cm, nan mahimo naton nga himuon ang usa ka uma nga adunay walay katapusan nga kardinal sa usa ka uma nga adunay kardinal nga mga 200 nga kantidad.
Siyempre, kon gikinahanglan, mahimo namong dugang nga pagsala pagkahuman.
Taas nga Bandwidth nga Problema
Ang sunod nga problema sa mga bitmap index mao nga ang pag-update niini mahimong mahal kaayo.
Ang mga database kinahanglan nga makahimo sa pag-update sa datos samtang posible nga gatusan ka ubang mga pangutana ang nangita sa datos. Kinahanglan namon ang mga kandado aron malikayan ang mga problema sa dungan nga pag-access sa datos o uban pang mga problema sa pagpaambit. Ug kung adunay usa ka dako nga kandado, adunay problema - panagbingkil sa kandado, kung kini nga kandado mahimong usa ka bottleneck.
Kini nga problema mahimong masulbad o malikayan pinaagi sa paggamit sa sharding o paggamit sa mga bersyon nga indeks.
Ang shading usa ka yano ug ilado nga butang. Mahimo nimong i-shard ang usa ka bitmap index sama sa imong buhaton sa ubang mga datos. Imbis nga usa ka dako nga kandado, makakuha ka usa ka hugpong sa gagmay nga mga kandado ug sa ingon mawala ang panagbingkil sa kandado.
Ang ikaduha nga paagi aron masulbad ang problema mao ang paggamit sa mga bersyon nga indeks. Mahimo kang adunay usa ka kopya sa indeks nga imong gigamit sa pagpangita o pagbasa, ug usa nga imong gigamit sa pagsulat o pag-update. Ug kausa sa usa ka piho nga yugto sa panahon (pananglitan, kausa sa matag 100 ms o 500 ms) imong doblehon ug ibaylo kini. Siyempre, kini nga pamaagi magamit lamang sa mga kaso diin ang imong aplikasyon makadumala sa usa ka gamay nga lagging nga indeks sa pagpangita.
Kining duha ka mga pamaagi mahimong gamiton nga dungan: mahimo kang adunay sharded versioned index.
Mas komplikado nga mga pangutana
Ang katapusang problema sa mga bitmap index mao nga gisultihan kami nga dili sila haum alang sa mas komplikado nga mga matang sa mga pangutana, sama sa span query.
Sa tinuud, kung imong hunahunaon kini, ang mga gamay nga operasyon sama sa AND, OR, ug uban pa dili kaayo angay alang sa mga pangutana nga "Ipakita kanako ang mga hotel nga adunay rate sa kwarto tali sa 200 ug 300 dolyar matag gabii."
Ang usa ka walay pulos ug dili maalamon nga solusyon mao ang pagkuha sa mga resulta alang sa matag dolyar nga kantidad ug isagol kini sa usa ka bitwise O operasyon.
Ang usa ka gamay nga mas maayo nga solusyon mao ang paggamit sa paggrupo. Pananglitan, sa mga grupo sa 50 dolyares. Kini makapadali sa atong proseso sa 50 ka beses.
Apan ang problema dali ra usab masulbad pinaagi sa paggamit sa usa ka pagtan-aw nga gimugna alang sa kini nga matang sa hangyo. Sa siyentipikong mga papel kini gitawag nga range-encoded bitmaps.
Niini nga representasyon, dili lang nato ibutang ang usa ka gamay alang sa pipila ka bili (pananglitan, 200), apan ibutang kini nga bili ug mas taas ang tanan. 200 ug pataas. Parehas alang sa 300: 300 ug pataas. Ug uban pa.
Gamit kini nga representasyon, makatubag kita niining matang sa pangutana sa pagpangita pinaagi sa paglatas sa indeks sa makaduha lang. Una, magkuha mi ug lista sa mga hotel diin ang kwarto mas mubu o $300, ug unya among tangtangon gikan niini kadtong diin ang kwarto gamay ra o $199. Andam.
Matingala ka, apan bisan ang mga geoquery posible gamit ang mga indeks sa bitmap. Ang lansis mao ang paggamit sa usa ka geometric nga representasyon nga naglibot sa imong coordinate sa usa ka geometric nga numero. Pananglitan, ang S2 gikan sa Google. Ang numero kinahanglan nga posible nga magrepresentar sa porma sa tulo o daghan pa nga mga linya sa intersecting nga mahimong maihap. Niining paagiha mahimo natong himoon ang atong geoquery ngadto sa daghang mga pangutana "abay sa gintang" (uban niining mga numero nga linya).
Andam nga mga solusyon
Nanghinaut ko nga interesado ako kanimo og gamay ug ikaw karon adunay laing mapuslanon nga himan sa imong arsenal. Kung kinahanglan nimo nga buhaton ang usa ka butang nga sama niini, mahibal-an nimo kung unsang paagiha ang pangitaon.
Bisan pa, dili tanan adunay oras, pasensya, o kahinguhaan sa paghimo og mga indeks sa bitmap gikan sa wala. Ilabi na ang mas abante, gamit ang SIMD, pananglitan.
Maayo na lang, adunay daghang mga andam nga solusyon nga makatabang kanimo.
Nagngulob nga mga bitmap
Una, adunay parehas nga nagngulob nga bitmaps library nga akong nahisgutan. Naglangkob kini sa tanan nga gikinahanglan nga mga sudlanan ug gamay nga operasyon nga kinahanglan nimo aron makahimo usa ka hingpit nga indeks sa bitmap.
Ikasubo, sa pagkakaron, walay bisan usa sa mga pagpatuman sa Go ang naggamit sa SIMD, nga nagpasabot nga ang mga pagpatuman sa Go dili kaayo maayo kay sa mga pagpatuman sa C, pananglitan.
Pilosa
Ang laing produkto nga makatabang kanimo mao ang Pilosa DBMS, nga, sa pagkatinuod, adunay mga bitmap index lamang. Kini usa ka bag-o nga solusyon, apan kini nakadaog sa mga kasingkasing sa kusog nga tulin.
Ang Pilosa naggamit sa nagngulob nga mga bitmap sa sulod ug naghatag kanimo og abilidad sa paggamit niini, gipasimple ug gipatin-aw ang tanan nga mga butang nga akong gihisgutan sa ibabaw: paggrupo, mga bitmap nga gi-encode sa range, ang konsepto sa usa ka field, ug uban pa.
Atong tan-awon dayon ang usa ka pananglitan sa paggamit sa Pilosa aron matubag ang usa ka pangutana nga pamilyar ka na.
Ang pananglitan susama kaayo sa imong nakita kaniadto. Naghimo kami usa ka kliyente sa server sa Pilosa, maghimo usa ka indeks ug ang kinahanglan nga mga natad, dayon pun-on ang among mga uma sa random nga datos nga adunay mga posibilidad ug, sa katapusan, ipatuman ang pamilyar nga pangutana.
Pagkahuman niana, gigamit namon ang DILI sa "mahal" nga uma, dayon i-intersect ang resulta (o UG kini) sa field nga "terrace" ug sa field nga "reservations". Ug sa katapusan, makuha namon ang katapusan nga resulta.
Naglaum gyud ko nga sa umaabot nga umaabot nga kini nga bag-ong klase sa indeks makita usab sa mga DBMS sama sa MySQL ug PostgreSQL - mga indeks sa bitmap.
konklusyon
Kung wala ka pa makatulog, salamat. Kinahanglan nakong hisgotan sa makadiyot ang daghang mga hilisgutan tungod sa limitado nga oras, apan nanghinaut ko nga ang pakigpulong mapuslanon ug tingali makadasig.
Ang mga indeks sa bitmap maayo nga mahibal-an, bisan kung dili nimo kini kinahanglan karon. Himoa sila nga laing himan sa imong toolbox.
Among gitan-aw ang lain-laing mga limbong sa pasundayag alang sa Go ug mga butang nga dili pa kaayo madumala sa Go compiler. Apan kini hingpit nga mapuslanon alang sa matag Go programmer nga mahibal-an.
Kana ra ang gusto nakong isulti kanimo. Salamat!
Source: www.habr.com