okwu mmeghe
Enyere m akụkọ a n'asụsụ Bekee na GopherCon Russia 2019 ogbako na Moscow na na Russian na nzukọ na Nizhny Novgorod. Anyị na-ekwu maka ndepụta nke bitmap - nke na-adịkarịghị karịa osisi B, ma ọ dịghị ihe na-adọrọ mmasị. Ịkekọrịta okwu na ogbako na English na ederede transcripts na Russian.
Anyị ga-eleba anya ka ihe ntanetị bitmap si arụ ọrụ, mgbe ọ ka mma, mgbe ọ dị njọ karịa ndepụta ndị ọzọ, na n'ọnọdụ ndị ọ dị ngwa ngwa karịa ha; Ka anyị hụ nke DBMS ndị na-ewu ewu nwerelarị ntụzịaka bitmap; Ka anyị gbalịa ide nke anyị na Go. Na “maka eji megharịa ọnụ” anyị ga-eji ọba akwụkwọ emebere emebere iji mepụta nchekwa data pụrụiche nke anyị nwere oke ọsọ ọsọ.
Enwere m olileanya n'ezie na ọrụ m ga-abara gị uru ma na-atọ gị ụtọ. Gaba!
Okwu Mmalite
Ndewo, unu niile! Ọ bụ elekere isii nke mgbede, ike gwụrụ anyị niile. Oge dị ukwuu ikwu okwu gbasara tiori index data na-agwụ ike, nri? Echegbula m, m ga-enwe ahịrị koodu isi mmalite ebe a na ebe ahụ. 🙂
Njakịrị niile wepụrụ, akụkọ ahụ juputara na ozi, na anyị enweghị oge buru ibu. Ya mere, ka anyị malite.
Taa, m ga-ekwu maka ihe ndị a:
- Kedu ihe bụ index;
- Kedu ihe bụ index bitmap;
- ebe a na-eji ya na ebe a na-ejighị ya na ihe kpatara ya;
- mmemme dị mfe na Go na obere mgba na onye nchịkọta;
- dịtụ obere mfe, mana ọtụtụ ihe na-arụpụta ihe na Go assembler;
- "nsogbu" nke ọnụọgụ bitmap;
- mmemme dị adị.
Ya mere, ihe bụ index?
Ndekọ ndeksi bụ nhazi data dị iche nke anyị na-edobe ma na-emelite na mgbakwunye na data bụ isi. A na-eji ya mee ngwa ngwa nchọta. Enweghị ndeksi, ịchọgharị ga-achọ ịgafe data ahụ kpamkpam (usoro a na-akpọ nyocha zuru oke), na usoro a nwere mgbagwoju anya algorithmic linear. Mana ọdụ data na-enwekarị nnukwu data yana mgbagwoju anya ahịrị adịchaghị ngwa ngwa. Dị ka o kwesịrị, anyị ga-enweta logarithmic ma ọ bụ nke na-adịgide adịgide.
Nke a bụ isiokwu dị mgbagwoju anya nke jupụtara na aghụghọ na azụmaahịa, mana mgbe m lebachara anya na ọtụtụ iri afọ nke mmepe nchekwa data na nyocha, ọ dị m njikere ịsị na ọ bụ naanị ụzọ ole na ole a na-eji eme ihe iji mepụta ndepụta nchekwa data.
Ụzọ mbụ bụ ibelata oghere ọchụchọ n'usoro, kewaa oghere ọchụchọ n'ime obere akụkụ.
Anyị na-ejikarị ụdị osisi dị iche iche eme nke a. Otu ihe atụ ga-abụ nnukwu igbe ihe dị n'ime ụlọ gị nke nwere obere igbe ihe ndị e kewara n'ime isiokwu dị iche iche. Ọ bụrụ na ịchọrọ ihe, ị ga-achọ ha n'ime igbe nke na-ekwu "Materials" kama nke na-ekwu "Kuki," nri?
Ụzọ nke abụọ bụ ịhọrọ ngwa ngwa ma ọ bụ otu ihe achọrọ. Anyị na-eme nke a na maapụ hash ma ọ bụ ntụgharị ntụgharị. Iji maapụ hash yiri ihe atụ gara aga, mana kama igbe igbe, ị nwere ụyọkọ obere igbe nke ihe ikpeazụ na kọbọd gị.
Ụzọ nke atọ bụ ikpochapụ mkpa ịchọ. Anyị na-eme nke a site na nzacha Bloom ma ọ bụ ihe nzacha cuckoo. Ndị mbụ na-enye azịza ozugbo, na-azọpụta gị ịchọ.
Ụzọ ikpeazụ bụ iji ike niile nke ngwaike ọgbara ọhụrụ na-enye anyị n'ụzọ zuru ezu. Nke a bụ kpọmkwem ihe anyị na-eme na ntanetị bitmap. Ee, mgbe ị na-eji ha, anyị na-achọ mgbe ụfọdụ ịgafe index dum, mana anyị na-eme ya nke ọma.
Dịka m kwuru, isiokwu nke ndenye nchekwa data buru ibu ma juputara na nkwenye. Nke a pụtara na mgbe ụfọdụ, anyị nwere ike iji ọtụtụ ụzọ n'otu oge: ọ bụrụ na anyị kwesịrị ime ngwa ngwa nchọta karịa, ma ọ bụ ọ bụrụ na anyị kwesịrị ikpuchi ụdị ọchụchọ niile.
Taa, m ga-ekwu maka ụzọ kacha nta ama ama nke ndị a - bitmap indexes.
Kedu onye m ga-ekwu maka isiokwu a?
M na-arụ ọrụ dị ka onye ndu otu na Badoo (ikekwe ị maara nke ọma ngwaahịa anyị ndị ọzọ, Bumble). Anyị enweelarị ndị ọrụ karịrị nde 400 gburugburu ụwa yana ọtụtụ atụmatụ na-ahọrọ ha egwuregwu kacha mma. Anyị na-eme nke a site na iji ọrụ omenala, gụnyere ndeksi bitmap.
Yabụ kedu ihe bụ index bitmap?
Ndepụta Bitmap, dị ka aha ahụ na-egosi, jiri bitmaps ma ọ bụ bitsets mejuputa nchọta ọchụchọ. Site na anya nnụnụ, ndeksi a nwere otu ma ọ bụ karịa bitmaps dị otú ahụ na-anọchi anya ụlọ ọrụ ọ bụla (dị ka ndị mmadụ) na ihe onwunwe ha ma ọ bụ paramita (afọ, agba anya, wdg), yana algọridim na-eji ọrụ bit (NA, OR, BỤGHỊ). ) zaa ajụjụ ọchụchọ.
A na-agwa anyị na nrịbama bitmap kacha mma ma na-arụ ọrụ nke ọma maka ikpe ebe enwere ọchụchọ na-ejikọta ajụjụ n'ofe ọtụtụ kọlụm cardinality dị ala (chee "agba anya" ma ọ bụ "ọnọdụ alụmdi na nwunye" na ihe dịka "ebe dị anya site na etiti obodo"). Mana m ga-egosi ma emechaa na ha na-arụ ọrụ nke ọma maka kọlụm cardinality dị elu.
Ka anyị leba anya n'ihe atụ kachasị mfe nke ndeksi bitmap.
Were ya na anyị nwere ndepụta ụlọ oriri na ọṅụṅụ Moscow nwere ọnụọgụ ọnụọgụ abụọ dị ka ndị a:
- nso metro;
- enwere ebe a na-adọba ụgbọala nkeonwe;
- e nwere veranda (nwere terrace);
- ị nwere ike idowe tebụl (nabata ndoputa);
- dị mma maka ndị anaghị eri anụ (ọ na-amasị vegan);
- ọnụ (dị ọnụ).
Ka anyị nye ụlọ oriri na ọṅụṅụ ọ bụla nọmba usoro malite na 0 wee kenye ebe nchekwa maka bitmaps 6 (otu maka njirimara ọ bụla). Anyị ga-ejupụta bitmaps ndị a dabere ma ụlọ oriri na ọṅụṅụ nwere akụrụngwa a ma ọ bụ na ọ nweghị. Ọ bụrụ na ụlọ oriri na ọṅụṅụ 4 nwere veranda, mgbe ahụ, bit No. 4 na "nwere veranda" bitmap ga-edozi na 1 (ọ bụrụ na ọ dịghị veranda, wee gaa 0).
Ugbu a, anyị nwere index bitmap kacha mfe, anyị nwere ike iji ya zaa ajụjụ dịka:
- "Gosi m ụlọ oriri na ọṅụṅụ ndị anaghị eri anụ";
- "Gosi m ụlọ oriri na ọṅụṅụ ndị dị ọnụ ala nwere veranda ebe ị nwere ike idobe tebụl."
Kedu? Ka anyị lee anya. Arịrịọ nke mbụ dị nnọọ mfe. Naanị ihe anyị ga-eme bụ were “bitmap enyi anaghị eri anụ” wee tụgharịa ya ka ọ bụrụ ndepụta ụlọ oriri na ọ restaurantsụ restaurantsụ nke ekpughere ibe ha.
Arịrịọ nke abụọ dị ntakịrị mgbagwoju anya. Anyị kwesịrị iji NOT bitmap na "ọnụahịa" bitmap iji nweta ndepụta nke ụlọ oriri na ọṅụṅụ ndị dị ọnụ ala, wee NA ya na "enwere m ike idebe tebụl" bitmap na NA nsonaazụ ya na "enwere veranda" bitmap. bitmap ga-esi na ya pụta ga-enwe ndepụta ụlọ ọrụ na-emezu ụkpụrụ anyị niile. N'ihe atụ a, nke a bụ naanị ụlọ oriri na ọṅụṅụ Yunost.
Enwere otutu tiori gụnyere, mana echegbula, anyị ga-ahụ koodu ahụ n'oge adịghị anya.
Ebee ka eji index bitmap?
Ọ bụrụ na ị Google bitmap indexes, 90% nke azịza ga-metụtara Oracle DB n'otu ụzọ ma ọ bụ ọzọ. Mana DBMS ndị ọzọ nwere ike na-akwado ụdị ihe dị mma, nri? Ọ bụchaghị.
Ka anyị gaa na ndepụta nke ndị isi a na-enyo enyo.
MySQL akwadobeghị index bitmap, mana enwere atụmatụ na-atụ aro ịgbakwunye nhọrọ a ().
PostgreSQL anaghị akwado ntụzịaka bitmap, kama ọ na-eji bitmaps dị mfe yana arụmọrụ bit iji jikọta nsonaazụ ọchụchọ n'ofe ọtụtụ ndeksi ndị ọzọ.
Tarantool nwere ntụzịaka bitset ma na-akwado ọchụchọ dị mfe na ha.
Redis nwere ubi bit dị mfe) na-enweghị ike ịchọ ha.
MongoDB akwadobeghị ọnụọgụ bitmap, mana enwerekwa atụmatụ na-atụ aro ka agbakwunye nhọrọ a.
Elasticsearch na-eji bitmaps n'ime).
- Ma onye agbata obi ọhụrụ apụtala n'ụlọ anyị: Pilosa. Nke a bụ nchekwa data na-abụghị mmekọrịta nke edere na Go. Ọ nwere naanị ọnụọgụ bitmap ma dabere ihe niile na ha. Anyị ga-ekwu maka ya ntakịrị oge.
Mmejuputa na Go
Mana kedu ihe kpatara ejighi ihe nrịbama bitmap eme ihe? Tupu ịza ajụjụ a, ọ ga-amasị m igosi gị otu esi etinye ntụzịaka bitmap dị mfe na Go.
Bitmaps bụ naanị iberibe data. Na Go, ka anyị jiri mpekere byte mee nke a.
Anyị nwere otu bitmap maka otu njirimara ụlọ oriri na ọṅụṅụ, na nke ọ bụla na bitmap na-egosi ma otu ụlọ oriri na ọṅụṅụ nwere ihe onwunwe a ma ọ bụ na ọ nweghị.
Anyị ga-achọ ọrụ inyeaka abụọ. A ga-eji otu mejuo bitmaps anyị na data enweghị usoro. Random, ma na ụfọdụ ihe gbasara nke puru omume na ụlọ oriri na ọṅụṅụ nwere onye ọ bụla ihe onwunwe. Dịka ọmụmaatụ, ekwenyere m na enwere ụlọ oriri na ọṅụṅụ ole na ole na Moscow ebe ị na-enweghị ike idobe tebụl, ọ dịkwa m ka ihe dịka 20% nke ụlọ ọrụ dị mma maka ndị anaghị eri anụ.
Ọrụ nke abụọ ga-atụgharị bitmap ka ọ bụrụ ndepụta ụlọ oriri na ọṅụṅụ.
Iji zaa ajụjụ a "Gosi m ụlọ oriri na ọṅụṅụ ndị na-adịghị ọnụ nke nwere patio ma nwee ike ndoputa," anyị chọrọ arụmọrụ bit abụọ: Ọ BỤGHỊ na NA.
Anyị nwere ike ime ka koodu anyị dị mfe site na iji ihe mgbagwoju anya NA Ọ BỤGHỊ onye ọrụ.
Anyị nwere ọrụ maka nke ọ bụla n'ime ọrụ ndị a. Ha abụọ na-agafe na mpekere ahụ, were ihe ndị kwekọrọ na nke ọ bụla, jikọta ha na obere ọrụ ma tinye nsonaazụ n'ime ibe a na-esi na ya pụta.
Ma ugbu a, anyị nwere ike iji bitmaps na ọrụ anyị zaa ajụjụ ọchụchọ.
Ịrụ ọrụ abụghị nke dị elu, n'agbanyeghị na ọrụ ndị ahụ dị nnọọ mfe ma anyị zọpụtara ego buru ibu site n'ịlaghachi azụ ọhụrụ na-esi na ya pụta oge ọ bụla a na-akpọ ọrụ ahụ.
Mgbe m mechara ntakịrị profaịlụ na pprof, achọpụtara m na Go compiler na-efu otu dị mfe mana njikarịcha dị oke mkpa: inlining ọrụ.
Nke bụ eziokwu bụ na Go compiler na-atụ egwu loops nke na-aga na mpekere, ma jụkwa ịrụ ọrụ inline nke nwere loops dị otú ahụ.
Ma anaghị m atụ egwu ma enwere m ike ịghọgbu onye nchịkọta site na iji goto kama loop, dị ka n'oge ochie.
Ma, dị ka ị pụrụ ịhụ, ugbu a, ndị nchịkọta ga-eji obi ụtọ depụta ọrụ anyị! N'ihi ya, anyị jisiri ike ịchekwa ihe dịka 2 microseconds. Ọ dịghị njọ!
Ihe nkedo nke abụọ dị mfe ịhụ ma ọ bụrụ na ị na-eleba anya na mmepụta mgbakọ. Onye nchịkọta ahụ gbakwunyere nlele oke iberibe ozugbo n'ime loop anyị kacha ewu ewu. Nke bụ eziokwu bụ na Go bụ asụsụ dị nchebe, onye na-achịkọta egwu na-atụ egwu na arụmụka atọ m (mpịakọta atọ) dị iche iche. A sị ka e kwuwe, mgbe ahụ, a ga-enwe ike ịme ihe omume nke ihe a na-akpọ buffer.
Ka anyị mesie onye nchịkọta obi ike site n'igosi ya na mpekere niile bụ otu nha. Anyị nwere ike ime nke a site n'ịgbakwunye nlele dị mfe na mmalite nke ọrụ anyị.
N'ịhụ nke a, onye nchịkọta na-eji obi ụtọ wụpụ nlele ahụ, anyị na-ejedebe na-echekwa 500 nanoseconds ọzọ.
Nnukwu anụ ọhịa
Ọ dị mma, anyị jisiri ike wepụta ụfọdụ arụmọrụ na mmejuputa anyị dị mfe, mana nsonaazụ a dị njọ karịa ka enwere ike iji ngwaike dị ugbu a.
Naanị ihe anyị na-eme bụ ọrụ bit bụ isi, ndị na-arụ ọrụ anyị na-arụkwa ha nke ọma. Ma, ọ dị mwute ikwu, anyị "na-eri nri" anyị processor na nnọọ obere iberibe ọrụ. Ọrụ anyị na-arụ ọrụ na ndabere byte-byte. Anyị nwere ike ịmegharị koodu anyị n'ụzọ dị mfe iji jiri 8-byte chunks rụọ ọrụ site na iji mpekere UInt64.
Dị ka ị na-ahụ, obere mgbanwe a mere ka mmemme anyị gbasaa ugboro asatọ site n'ịba ụba nke batch ugboro asatọ. Enwere ike ịsị uru ahụ bụ linear.
Mmejuputa na mgbakọ
Ma nke a abụghị ọgwụgwụ. Ndị nhazi anyị nwere ike ịrụ ọrụ na 16, 32 na ọbụna 64 bytes. A na-akpọ ọrụ ndị dị otú ahụ "sara mbara" otu ntụziaka ọtụtụ data (SIMD; otu ntụziaka, ọtụtụ data), na usoro nke ịgbanwe koodu ka ọ na-eji ọrụ dị otú ahụ ka a na-akpọ vectorization.
N'ụzọ dị mwute, Go compiler adịchaghị mma na vectorization. Ugbu a, naanị otu ụzọ ị ga-esi megharịa koodu Go bụ iji aka tinye ọrụ ndị a site na iji Go assembler.
Go assembler bụ anụ ọhịa iju. O nwere ike ịbụ na ị maara na asụsụ mgbakọ bụ ihe ejikọtara ya na nhazi kọmpụta ị na-ede maka ya, mana ọ bụghị nke ahụ na Go. Go assembler dị ka IRL (asụsụ nnọchite anya etiti) ma ọ bụ asụsụ etiti: ọ na-enwere onwe ya n'elu ikpo okwu. Rob Pike nyere ezigbo ọrụ na isiokwu a ọtụtụ afọ gara aga na GopherCon na Denver.
Na mgbakwunye, Go na-eji usoro atụmatụ 9 pụrụ iche, nke dị iche na ụdị AT&T na Intel anabatakarị.
Ọ dị mma ịsị na iji aka dee Go assembler abụghị ihe kacha atọ ụtọ.
Mana, ọ dabara nke ọma, enweelarị ngwaọrụ abụọ dị elu na-enyere anyị aka ide Go assembler: PeachPy na avo. Ụlọ ọrụ abụọ a na-emepụta Go assembler site na koodu ọkwa dị elu nke edere na Python na Go, n'otu n'otu.
Ngwa ndị a na-eme ka ihe dị mfe dị ka ntinye aha aha, ide loops, na n'ozuzu na-eme ka usoro ịbanye n'ime ụwa nke mmemme mgbakọ na Go.
Anyị ga-eji avo, yabụ mmemme anyị ga-abụ mmemme Go mgbe niile.
Nke a bụ ihe atụ kachasị mfe nke mmemme avo dị ka. Anyị nwere isi () ọrụ, nke na-akọwa n'ime onwe ya ọrụ Add(), ihe ọ pụtara bụ ịgbakwunye ọnụọgụ abụọ. Enwere ọrụ enyemaka ebe a iji nweta paramita site na aha wee nweta otu n'ime ndebanye aha nhazi n'efu na dabara adaba. Ọrụ nhazi ọ bụla nwere ọrụ kwekọrọ na avo, dị ka a hụrụ na ADDQ. N'ikpeazụ, anyị na-ahụ ọrụ enyemaka maka ịchekwa uru na-arụpụta.
Site n'ịkpọ go mepụta, anyị ga-eme mmemme na avo na n'ihi ya, a ga-emepụta faịlụ abụọ:
- tinye.s na koodu ga-esi na ya pụta na Go assembler;
- stub.go nwere nkụnye eji isi mee iji jikọọ ụwa abụọ: Gaa na mgbakọ.
Ugbu a anyị ahụla ihe avo na-eme na otu, ka anyị leba anya n'ọrụ anyị. Emebere m ụdịrị scalar na vector (SIMD) nke ọrụ ahụ.
Ka anyị buru ụzọ leba anya na ụdị scalar.
Dị ka ọ dị na ihe atụ gara aga, anyị na-arịọ maka ndebanye aha n'efu ma dị irè, ọ dịghị anyị mkpa ịgbakọ nkwụsị na nha maka arụmụka. avo emere anyi ihe ndia.
Anyị na-eji akara na goto (ma ọ bụ jumps) iji melite arụmọrụ wee ghọgbuo Go compiler, mana ugbu a anyị na-eme ya site na mmalite. Isi ihe bụ na cycles bụ echiche dị elu. Na mgbakọ, anyị nwere naanị akara na jumps.
Koodu fọdụrụ kwesịrị ịbụ nke a maara nke ọma na nghọta. Anyị na-eṅomi loop na labels na jumps, na-ewere obere data site na mpekere abụọ anyị, jikọta ha na obere ọrụ (MA Ọ BỤGHỊ na nke a) wee tinye nsonaazụ ya na ibe ya. Ha niile.
Nke a bụ ka koodu nchịkọta ikpeazụ dị ka. Anyị ekwesịghị ịgbakọ nkwụghachi na nha (nke a na-egosipụta na akwụkwọ ndụ akwụkwọ ndụ) ma ọ bụ debe ndekọ aha ejiri (nke a na-egosipụta na uhie).
Ọ bụrụ na anyị atụnyere arụmọrụ nke mmejuputa asụsụ mgbakọ na arụmọrụ nke mmejuputa kachasị mma na Go, anyị ga-ahụ na ọ bụ otu ihe ahụ. Na nke a na-atụ anya. A sị ka e kwuwe, anyị emeghị ihe ọ bụla pụrụ iche - anyị megharịrị ihe Go compiler ga-eme.
N'ụzọ dị mwute, anyị enweghị ike ịmanye onye nchịkọta ka ọ depụta ọrụ anyị nke edere n'asụsụ mgbakọ. Ihe nchịkọta Go ugbu a enweghị ụdị atụmatụ a, n'agbanyeghị na ọ dịlarị arịrịọ ka ịgbakwunye ya ruo nwa oge.
Nke a bụ ya mere na ọ gaghị ekwe omume ịnweta uru ọ bụla site na obere ọrụ na asụsụ mgbakọ. Anyị kwesịrị ide nnukwu ọrụ, ma ọ bụ jiri ngwugwu mgbakọ na mwepụ/bits ọhụrụ, ma ọ bụ gafere asụsụ ndị na-ezukọ.
Ka anyị leba anya ugbu a na ụdị vector nke ọrụ anyị.
Maka ihe atụ a, ekpebiri m iji AVX2, yabụ anyị ga-eji arụ ọrụ na-arụ ọrụ na 32-byte chunks. Usoro nke koodu ahụ dị nnọọ ka ụdị scalar: nbudata paramita, na-arịọ maka ndekọ nkekọrịta n'efu, wdg.
Otu ihe ọhụrụ bụ na arụmọrụ vector sara mbara na-eji ndekọ obosara pụrụ iche. N'ihe gbasara 32-byte chunks, ndị a bụ ndekọ ahaziri na Y. Ọ bụ ya mere ị ga-eji hụ ọrụ YMM () na koodu. Ọ bụrụ na m na-eji AVX-512 nwere 64-bit chunks, prefix ga-abụ Z.
Ihe ọhụrụ ọhụrụ nke abụọ bụ na m kpebiri iji njikarịcha a na-akpọ loop unrolling, nke pụtara na-eme ọrụ akaghị aka asatọ tupu ịwụ elu na mmalite nke loop. Nke a kacha mma na-ebelata ọnụ ọgụgụ nke alaka na koodu, na-ejedebeghị na ọnụ ọgụgụ nke free ndekọ dị.
Ọfọn, gịnị banyere arụmọrụ? Ọ mara mma! Anyị nwetara ọsọ ọsọ nke ihe dị ka ugboro asaa ma e jiri ya tụnyere ihe ngwọta Go kacha mma. Na-adọrọ mmasị, nri?
Mana ọbụlagodi mmejuputa a nwere ike ime ngwa ngwa site na iji AVX-512, prefetching ma ọ bụ JIT (onye na-achịkọta naanị oge) maka onye nhazi ajụjụ. Mana nke a bụ n'ezie isiokwu maka akụkọ dị iche.
Nsogbu dị na ntanetị bitmap
Ugbu a anyị lebagoro anya na mmemme dị mfe nke ndeksi bitmap na Go yana nke na-arụpụta nke ọma n'asụsụ mgbakọ, ka anyị kwuchaa maka ihe kpatara eji adịkarịghị eji ntụnye bitmap.
Akwụkwọ ochie kwuru nsogbu atọ nwere nrịbama bitmap, mana m na akwụkwọ ọhụrụ na-arụ ụka na ha adịkwaghị mkpa. Anyị agaghị amaba miri emi na nke ọ bụla n'ime nsogbu ndị a, kama anyị ga-ele ha anya nke ọma.
Nsogbu nke kadinality dị elu
Ya mere, anyị na-gwara na bitmap index bụ naanị adabara ubi na ala cardinality, ya bụ, ndị nwere ole na ole ụkpụrụ (dịka ọmụmaatụ, okike ma ọ bụ anya agba), na ihe kpatara ya bụ na-emebu ihe nnọchianya nke ndị dị otú ahụ ubi (otu). bit kwa uru) n'ihe banyere cardinality dị elu, ọ ga-ewe oke ohere ma, ọzọkwa, ndepụta bitmap ndị a ga-adị nke ọma (adịkarịghị).
Mgbe ụfọdụ, anyị nwere ike iji nnochite anya dị iche, dị ka ọkọlọtọ nke anyị na-eji nọchite anya ọnụọgụ. Mana ọ bụ ọbịbịa nke algọridim mkpakọ gbanwere ihe niile. N'ime iri afọ gara aga, ndị ọkà mmụta sayensị na ndị nchọpụta ewepụtala ọnụ ọgụgụ dị ukwuu nke mkpakọ algọridim maka bitmaps. Isi uru ha bara bụ na ọ dịghị mkpa ịkwatu bitmaps iji rụọ ọrụ bit - anyị nwere ike ịrụ ọrụ bit ozugbo na bitmaps abịakọrọ.
Na nso nso a, ụzọ ngwakọ amalitela ịpụta, dị ka bitmap na-ebigbọ. Ha na-eji nnochite anya atọ dị iche iche n'otu oge maka bitmaps - bitmaps n'onwe ha, nhazi na ihe a na-akpọ bit runs - na itule n'etiti ha iji bulie arụmọrụ yana belata oriri ebe nchekwa.
Ị nwere ike ịhụ bitmaps na-ebigbọ n'ime ngwa kachasị ewu ewu. Enweelarị ọnụ ọgụgụ dị ukwuu nke mmemme maka asụsụ mmemme dị iche iche, gụnyere ihe karịrị mmemme atọ maka Go.
Ụzọ ọzọ nke nwere ike inyere anyị aka imeri kadinality dị elu bụ nke a na-akpọ binning. Were ya na ị nwere ubi na-anọchi anya ogo mmadụ. Ogo bụ ọnụọgụ na-ese n'elu mmiri, mana anyị bụ ụmụ mmadụ anaghị eche ya otu a. Maka anyị ọ nweghị ọdịiche dị n'etiti ịdị elu 185,2 cm na 185,3 cm.
Ọ tụgharịrị na anyị nwere ike ikpokọta ụkpụrụ ndị yiri ya n'ime otu n'ime 1 cm.
Ma ọ bụrụ na anyị makwaara na mmadụ ole na ole dị mkpụmkpụ karịa 50 cm na ogologo karịa 250 cm, mgbe ahụ anyị nwere ike ịtụgharị ubi nwere kadinality na-enweghị ngwụcha n'ime ubi nwere kadinality nke ihe dịka 200 ụkpụrụ.
N'ezie, ọ bụrụ na ọ dị mkpa, anyị nwere ike ime nzacha ọzọ ma emechaa.
Nsogbu bandwit dị elu
Nsogbu na-esote na ntanetị bitmap bụ na imelite ha nwere ike ịdị oke ọnụ.
Ebe nchekwa data ga-enwerịrị ike imelite data ebe enwere ike ọtụtụ narị ajụjụ ndị ọzọ na-achọ data ahụ. Anyị chọrọ mkpọchi iji zere nsogbu na ịnweta data n'otu oge ma ọ bụ nsogbu nkekọrịta ndị ọzọ. Na ebe enwere otu nnukwu mkpọchi, enwere nsogbu - esemokwu mkpọchi, mgbe mkpọchi a ghọrọ ihe mgbochi.
Enwere ike idozi nsogbu a ma ọ bụ gbachie ya site na iji sharding ma ọ bụ iji ndenye aha mbipute.
Sharding bụ ihe dị mfe na nke a maara nke ọma. Ị nwere ike ihichapụ index bitmap ka ị na-eme data ọ bụla ọzọ. Kama otu nnukwu mkpọchi, ị ga-enweta ụyọkọ obere mkpọchi wee si otú ahụ wepụ esemokwu mkpọchi.
Ụzọ nke abụọ a ga-esi dozie nsogbu ahụ bụ iji indexed version. Ị nwere ike ịnwe otu ntọhapụ nke ị na-eji eme nchọpụta ma ọ bụ ịgụ ihe, na nke ị na-eji ede ma ọ bụ imelite. Na otu oge n'ime oge ụfọdụ (dịka ọmụmaatụ, otu ugboro kwa 100 ms ma ọ bụ 500 ms) ị na-emegharị ha ma gbanwee ha. N'ezie, usoro a na-adabara naanị n'ọnọdụ ebe ngwa gị nwere ike ijikwa nchọta ọchụchọ na-adịghị ala azụ.
Enwere ike iji ụzọ abụọ a n'otu oge: ị nwere ike ịnwe ntụzịaka mbipute nke chara acha.
Ajụjụ ndị dị mgbagwoju anya
Nsogbu ikpeazụ dị na nrịbama bitmap bụ na a gwara anyị na ha adabaghị nke ọma maka ụdị ajụjụ dị mgbagwoju anya karị, dị ka ajụjụ ogologo oge.
N'ezie, ọ bụrụ na ị na-eche banyere ya, bit arụmọrụ dị ka AND, OR, wdg adịghị mma maka ajụjụ a la "Gosi m hotels nwere ọnụ ụlọ site na 200 ruo 300 dollars kwa abalị."
Ihe ngwọta na-enweghị isi na nke na-enweghị amamihe ga-abụ iwere nsonaazụ maka uru dollar ọ bụla wee jikọta ha na ọrụ bitwise OR.
Ngwọta dịtụ mma ga-abụ iji otu. Dị ka ihe atụ, n'ìgwè nke 50 dollar. Nke a ga-eme ka usoro anyị dị ngwa site ugboro 50.
Mana a na-edozikwa nsogbu ahụ n'ụzọ dị mfe site n'iji nlele emepụtara kpọmkwem maka ụdị arịrịọ a. N'akwụkwọ sayensị, a na-akpọ ya bitmaps nwere akara nso.
Na nnọchite a, anyị anaghị edobe otu ntakịrị maka uru ụfọdụ (dịka ọmụmaatụ, 200), mana debe uru a na ihe niile dị elu. 200 na karịa. Otu maka 300: 300 na karịa. Were gabazie.
N'iji nnochite anya a, anyị nwere ike ịza ụdị ajụjụ ọchụchọ a site n'ịgafe index naanị ugboro abụọ. Nke mbụ, anyị ga-enweta ndepụta nke ụlọ oriri na ọṅụṅụ ebe ọnụ ụlọ ahụ na-efu ma ọ bụ $ 300, mgbe ahụ, anyị ga-ewepụ na ya ndị ebe ọnụ ụlọ dị obere ma ọ bụ $ 199. Njikere.
Ọ ga-eju gị anya, mana ọbụlagodi geoqueries ga-ekwe omume site na iji ndeksi bitmap. Aghụghọ a bụ iji ihe nnochi anya geometric gbara gburugburu gị na ọnụ ọgụgụ geometric. Dịka ọmụmaatụ, S2 sitere na Google. Ọnụ ọgụgụ ahụ kwesịrị inwe ike ịnọchite anya n'ụdị ahịrị atọ ma ọ bụ karịa nke enwere ike ịgụta ọnụ. N'ụzọ dị otú a, anyị nwere ike ịtụgharị geoquery anyị n'ọtụtụ ajụjụ "n'akụkụ oghere" (n'akụkụ ahịrị ndị a).
Ngwọta dị njikere
Enwere m olileanya na m nwere mmasị na gị ntakịrị ma ugbu a ị nwere ngwá ọrụ ọzọ bara uru na ngwa agha gị. Ọ bụrụ na ọ dị gị mkpa ime ụdị ihe a, ị ga-ama ụzọ ị ga-esi ele anya.
Agbanyeghị, ọ bụghị onye ọ bụla nwere oge, ndidi, ma ọ bụ akụrụngwa iji mepụta ndeksi bitmap site na ọkọ. Karịsịa ndị dị elu karịa, na-eji SIMD, dịka ọmụmaatụ.
Ọ dabara nke ọma, enwere ọtụtụ ngwọta emebere ga-enyere gị aka.
bitmaps na-ebigbọ
Mbụ, e nwere otu ọbá akwụkwọ bitmaps ahụ nke m kwuburu okwu ya. O nwere ihe niile dị mkpa na arụ ọrụ bit nke ị ga-achọ iji mee ndepụta bitmap zuru oke.
N'ụzọ dị mwute, n'oge a, ọ dịghị otu n'ime mmemme Go na-eji SIMD, nke pụtara na mmejuputa Go adịghị arụ ọrụ karịa mmejuputa C, dịka ọmụmaatụ.
Pilosa
Ngwaahịa ọzọ nwere ike inyere gị aka bụ Pilosa DBMS, nke, n'ezie, nwere naanị ọnụọgụ bitmap. Nke a bụ ngwọta ọhụrụ dị ọhụrụ, mana ọ na-emeri obi na nnukwu ọsọ ọsọ.
Pilosa na-eji bitmaps na-ebigbọ n'ime ma na-enye gị ike iji ha, na-eme ka ọ dị mfe ma kọwaa ihe niile m kwuru n'elu: nchịkọta, bitmaps nke nwere akara, echiche nke ubi, wdg.
Ka anyị leba anya ngwa ngwa n'ihe atụ nke iji Pilosa zaa ajụjụ ị maara nke ọma.
Ihe atụ a yiri nnọọ ihe ị hụburu. Anyị na-emepụta onye ahịa na ihe nkesa Pilosa, mepụta index na ubi ndị dị mkpa, wee jupụta n'ubi anyị na data na-enweghị usoro na ihe omume na, n'ikpeazụ, mebie ajụjụ a maara nke ọma.
Mgbe nke ahụ gasịrị, anyị na-eji Ọ BỤGHỊ na mpaghara "dị ọnụ", wee jikọta nsonaazụ (ma ọ bụ NA ya) na mpaghara "terrace" yana mpaghara "ndokwa". N'ikpeazụ, anyị na-enweta nsonaazụ ikpeazụ.
Enwere m olile anya na n'ọdịnihu a na-ahụ anya na ụdị ndeksi ọhụrụ a ga-apụtakwa na DBMS dị ka MySQL na PostgreSQL - bitmap indexes.
nkwubi
Ọ bụrụ na ị dabeghị ụra, daalụ. Ekwesịrị m imetụ aka n'ọtụtụ isiokwu dị mkpirikpi n'ihi obere oge, mana enwere m olileanya na okwu ahụ bara uru na ikekwe na-akpali akpali.
Ndekọ Bitmap dị mma ịmara maka ya, ọbụlagodi na ịchọghị ha ugbu a. Ka ha bụrụ ngwá ọrụ ọzọ na igbe ngwaọrụ gị.
Anyị elelela aghụghọ arụ ọrụ dị iche iche maka Go yana ihe ndị nchịkọta Go anaghị ejizi nke ọma. Mana nke a bara ezigbo uru maka onye mmemme Go ọ bụla ịmara.
Nke ahụ bụ ihe m chọrọ ịgwa gị. Daalụ!
isi: www.habr.com