selelekela
Ke fane ka tlaleho ena ka Senyesemane kopanong ea GopherCon Russia 2019 e neng e tšoaretsoe Moscow le ka Serussia kopanong e neng e tšoaretsoe Nizhny Novgorod. Re bua ka index ea bitmap - e sa tloaelehang ho feta B-tree, empa ha e thahasellise. Ho arolelana lipuo sebokeng ka Senyesemane le mongolo transcript ka Serussia.
Re tla sheba hore na index ea bitmap e sebetsa joang, ha e le betere, ha e le mpe ho feta li-index tse ling, 'me maemong afe e potlakile ho feta bona; Ha re boneng hore na ke li-DBMS life tse tsebahalang tse seng li na le li-index tsa bitmap; Ha re lekeng ho ngola tsa rona ho Go. 'Me "bakeng sa lijo tse theolelang" re tla sebelisa lilaeborari tse seng li entsoe ho theha polokelo ea rona e ikhethileng e potlakileng haholo.
Ke tšepa hore mesebetsi ea ka e tla ba molemo le e thahasellisang ho uena. Tsamaea!
Selelekela
Lumelang bohle! Ke hora ea botšelela mantsiboea 'me kaofela re khathetse haholo. Nako e monate ea ho bua ka khopolo ea index ea database e tenang, ho joalo? Seke oa tšoenyeha, ke tla ba le mela e 'maloa ea khoutu ea mohloli mona le mane. 🙂
Ka thoko metlae eohle, tlaleho e tletse litaba, 'me ha re na nako e ngata. Kahoo a re qaleng.
Kajeno ke tla bua ka tse latelang:
- li-index ke eng;
- index ea bitmap ke eng;
- moo e sebedisoang le moo E SA SEBEDISWANG le hobaneng;
- ts'ebetsong e bonolo ho Go le ho loana hanyenyane le moqapi;
- e seng bonolo hanyane, empa ts'ebetsong e behang litholoana haholo ho Go assembler;
- "mathata" a li-index tsa bitmap;
- ts'ebetsong tse teng.
Joale li-index ke eng?
Lenane ke sebopeho sa data se arohaneng seo re se bolokang le ho se ntlafatsa ho kenyelletsa lintlha tsa mantlha. E sebelisoa ho potlakisa ho batla. Ntle le li-index, ho batla ho tla hloka hore u fete data ka botlalo (ts'ebetso e bitsoang "Full scan"), mme ts'ebetso ena e na le ho rarahana ha algorithmic. Empa li-database hangata li na le lintlha tse ngata, 'me ho rarahana ha mela ho lieha haholo. Haele hantle, re ne re tla fumana logarithmic kapa kamehla.
Ena ke taba e rarahaneng haholo, e nang le lintlha tse poteletseng le li-trade-offs, empa ka mor'a ho sheba lilemo tse mashome tsa nts'etsopele ea database le lipatlisiso, ke ikemiselitse ho bolela hore ho na le mekhoa e seng mekae e sebelisoang haholo ea ho theha li-index tsa database.
Mokhoa oa pele ke ho fokotsa sebaka sa ho batla ka mokhoa o hlophisitsoeng, ho arola sebaka sa ho batla ka likarolo tse nyane.
Hangata re etsa sena re sebelisa mefuta e fapaneng ea lifate. Mohlala e ka ba lebokose le leholo la lisebelisoa ka phaposing ea hau e nang le mabokose a manyane a thepa a arotsoeng ka lihlooho tse fapaneng. Haeba u hloka lisebelisoa, mohlomong u tla li batla ka lebokoseng le reng "Lisebelisoa" ho e-na le le reng "Likuku," ho joalo?
Mokhoa oa bobeli ke ho khetha hang-hang ntho e lakatsehang kapa sehlopha sa likarolo. Re etsa sena ka limmapa tsa hash kapa li-index tsa morao-rao. Ho sebelisa limmapa tsa hash ho tšoana haholo le mohlala o fetileng, empa sebakeng sa lebokose la mabokose, u na le mabokose a manyane a lintho tsa ho qetela ka kamoreng ea hau.
Mokhoa oa boraro ke ho felisa tlhoko ea ho batla. Re etsa sena re sebelisa li-filters tsa Bloom kapa li-filters tsa cuckoo. Ba pele ba fana ka karabo hang-hang, ho u pholosa hore u se ke ua batla.
Mokhoa oa ho qetela ke ho sebelisa ka botlalo matla 'ohle ao hardware ea morao-rao e re fang eona. Sena ke sona seo re se etsang ho li-index tsa bitmap. Ee, ha re li sebelisa ka linako tse ling re hloka ho bala index eohle, empa re e etsa ka mokhoa o atlehileng haholo.
Joalokaha ke boletse, sehlooho sa li-index tsa database se seholo ebile se tletse ka ho sekisetsa. Sena se bolela hore ka linako tse ling re ka sebelisa mekhoa e mengata ka nako e le 'ngoe: haeba re hloka ho potlakisa patlo le ho feta, kapa haeba re hloka ho fana ka mefuta eohle ea ho batla.
Kajeno ke tla bua ka mokhoa o sa tsejoeng haholo oa tsena - li-index tsa bitmap.
Ke mang hore nka bua ka taba ee?
Ke sebetsa ke le moetapele oa sehlopha ho Badoo (mohlomong o tloaelane le sehlahisoa sa rona se seng, Bumble). Re se re ntse re e-na le basebelisi ba fetang limilione tse 400 lefatšeng ka bophara le likarolo tse ngata tse ba khethang. Re etsa sena re sebelisa litšebeletso tse tloaelehileng, ho kenyelletsa le li-index tsa bitmap.
Joale index ea bitmap ke eng?
Li-index tsa Bitmap, joalo ka ha lebitso le fana ka maikutlo, sebelisa li-bitmaps kapa li-bitsets ho kenya tšebetsong index ea lipatlisiso. Ho latela pono ea nonyana, lenane lena le na le "bitmaps" e le 'ngoe kapa tse ngata tse joalo tse emelang mekhatlo efe kapa efe (joalo ka batho) le thepa ea bona kapa liparamente (lilemo, 'mala oa mahlo, joalo-joalo), le algorithm e sebelisang li-bitmaps (LE, KAPA, HONA). ) ho araba potso ea ho batla.
Re bolelloa hore li-index tsa bitmap li loketse ka ho fetisisa 'me li sebetsa haholo maemong ao ho nang le lipatlisiso tse kopanyang lipotso ho lihlopha tse ngata tse tlaase (nahana "'mala oa mahlo" kapa "boemo ba lenyalo" khahlanong le ntho e kang "bohole ho tloha bohareng ba toropo"). Empa ke tla bontša hamorao hore li sebetsa hantle bakeng sa likholomo tse phahameng tsa mak'hadinale hape.
Ha re shebeng mohlala o bonolo ka ho fetisisa oa index ea bitmap.
Ak'u nahane re na le lethathamo la lireschorente tsa Moscow tse nang le thepa e kang ena:
- haufi le metro;
- ho na le sebaka sa ho paka makoloi;
- ho na le veranda (e na le terata);
- o ka boloka tafole (e amohela lipehelo);
- e loketseng bakeng sa batho ba jang meroho (ba botsoalle ba vegan);
- theko e boima (e turu).
Ha re fe reschorente e 'ngoe le e 'ngoe nomoro ea tatellano ho tloha ho 0 'me re fane ka memori bakeng sa li-bitmaps tse 6 (e le' ngoe bakeng sa tšobotsi ka 'ngoe). Re tla tlatsa li-bitmaps tsena ho latela hore na ntlo ea lijo e na le thepa ena kapa che. Haeba reschorente ea 4 e na le veranda, joale bitmap ea 4 "e na le veranda" e tla behoa ho 1 (haeba ho se na veranda, joale ho 0).
Joale re na le index ea bitmap e bonolo ka ho fetesisa, 'me re ka e sebelisa ho araba lipotso tse kang:
- “Mpontše lireschorente tse sa jeng nama”;
- Mpontše lireschorente tsa theko e tlaase tse nang le veranda moo u ka behelang tafole teng.
Joang? Ha re shebeng. Kopo ea pele e bonolo haholo. Seo re hlokang ho se etsa feela ke ho nka bitmap ea "meroho e bonolo" ebe re e fetola lethathamo la lireschorente tseo likarolo tsa tsona li pepesitsoeng.
Kopo ea bobeli e batla e rarahane haholoanyane. Re hloka ho sebelisa HASE bitmap ho "bitmap" e theko e boima ho fumana lethathamo la lireschorente tse theko e tlaase, ebe LE eona ka bitmap ea "na nka tsamaisa tafole" LE sephetho ka "ho na le veranda" bitmap. Sephetho sa bitmap se tla ba le lethathamo la litsi tse fihlelang litekanyetso tsohle tsa rona. Mohlaleng ona, ena ke sebaka sa thekiso ea lijo tsa Yunost feela.
Ho na le maikutlo a mangata a amehang, empa u se ke oa tšoenyeha, re tla bona khoutu haufinyane.
Li-index tsa bitmap li sebelisoa hokae?
Haeba u Google bitmap indexes, 90% ea likarabo li tla amana le Oracle DB ka tsela e 'ngoe kapa e' ngoe. Empa li-DBMS tse ling mohlomong le tsona li tšehetsa ntho e pholileng joalo, na? E seng joalo hantle.
Ha re hlahlobeng lethathamo la babelaelloa ba ka sehloohong.
MySQL ha e so tšehetse li-index tsa bitmap, empa ho na le Tlhahiso e fanang ka tlhahiso ea ho eketsa khetho ena ().
PostgreSQL ha e tšehetse li-index tsa bitmap, empa e sebelisa li-bitmaps tse bonolo le ts'ebetso e nyane ho kopanya liphetho tsa lipatlisiso ho li-index tse ling tse ngata.
Tarantool e na le li-index tsa bitset mme e tšehetsa lipatlisiso tse bonolo ho tsona.
Redis e na le li-bitfields tse bonolo) ntle le bokhoni ba ho li batla.
MongoDB ha e so tšehetse li-index tsa bitmap, empa ho boetse ho na le Tlhahiso e fanang ka maikutlo a hore khetho ena e eketsoe.
Elasticsearch e sebelisa li-bitmaps ka hare).
- Empa moahelani e mocha o hlahile ka tlung ea rona: Pilosa. Ena ke polokelongtshedimosetso e ntjha eo e seng ya kamano e ngotsweng ho Go. E na le li-index tsa bitmap feela 'me e theha ntho e' ngoe le e 'ngoe ho tsona. Re tla bua ka eona nakoana hamorao.
Phethahatso ho Go
Empa ke hobane'ng ha li-index tsa bitmap li sebelisoa seoelo? Pele ke araba potso ena, ke rata ho u bontša mokhoa oa ho kenya tšebetsong index ea bitmap e bonolo haholo ho Go.
Li-Bitmaps ha e le hantle ke likotoana tsa data. Ho Go, ha re sebeliseng lilae tsa byte bakeng sa sena.
Re na le bitmap e le 'ngoe bakeng sa sebopeho se le seng sa ntlo ea lijo, 'me karolo e' ngoe le e 'ngoe ho bitmap e bontša hore na ntlo ea lijo e na le thepa ena kapa che.
Re tla hloka mesebetsi e 'meli ea bathusi. E 'ngoe e tla sebelisoa ho tlatsa li-bitmaps tsa rona ka data e sa reroang. Ka tšohanyetso, empa ka monyetla o itseng oa hore reschorente e na le thepa ka 'ngoe. Ka mohlala, ke lumela hore ho na le lireschorente tse fokolang haholo Moscow moo u ke keng ua boloka tafole, 'me ho bonahala ho' na hore hoo e ka bang 20% ea mehaho e loketse batho ba jang meroho.
Mosebetsi oa bobeli o tla fetola bitmap lenaneng la lireschorente.
Ho araba potso ea "Mpontše libaka tsa ho jella tse sa tureng tse nang le patio 'me li ka etsa lipeeletso," re hloka tšebetso e 'meli: HASE le LE.
Re ka nolofatsa khoutu ea rona hanyane ka ho sebelisa opareitara e rarahaneng le eseng.
Re na le mesebetsi bakeng sa ts'ebetso e 'ngoe le e' ngoe ea tsena. Ka bobeli ba feta har'a lilae, ba nka likarolo tse tsamaellanang ho e 'ngoe le e' ngoe, ba li kopanye le ts'ebetso e nyane ebe o kenya sephetho ka har'a selae se hlahisoang.
'Me joale re ka sebelisa li-bitmaps le mesebetsi ea rona ho araba potso ea lipatlisiso.
Ts'ebetso ha e phahame hakaalo, le hoja mesebetsi e le bonolo haholo 'me re bolokile chelete e ngata ka ho se khutlisetse selae se secha se hlahisoang nako le nako ha mosebetsi o bitsoa.
Kamora ho etsa profil e nyane le pprof, ke hlokometse hore moqapi oa Go o ne a haelloa ke ts'ebetso e le 'ngoe e bonolo empa e le ea bohlokoa haholo: ts'ebetso ea inlining.
Taba ke hore motlalehi oa Go o tšaba loops tse fetang har'a lilae, 'me o hana ka botlalo ho kenya mesebetsi e nang le loops e joalo.
Empa ha ke tšabe 'me nka thetsa moqapi ka ho sebelisa goto sebakeng sa loop, joalo ka mehleng ea khale.
'Me, joalo ka ha u bona, joale moqapi o tla kenela tšebetso ea rona ka thabo! Ka lebaka leo, re khona ho boloka li-microseconds tse ka bang 2. Ha e mpe!
Botlolo ea bobeli bo bonolo ho bona haeba u sheba haufi-ufi tlhahiso ea kopano. Moqapi o kentse cheke ea moeli oa selae ka har'a loop ea rona e chesang ka ho fetesisa. 'Nete ke hore Go ke puo e sireletsehileng, moqapi o tšaba hore likhang tsa ka tse tharo (likotoana tse tharo) li na le boholo bo fapaneng. Ntle le moo, ho tla ba le monyetla oa theory oa ho hlaha ha se bitsoang buffer overflow.
Ha re tiiseng moqapi ka ho e bontša hore lilae tsohle li lekana ka boholo. Re ka etsa sena ka ho kenyelletsa cheke e bonolo qalong ea ts'ebetso ea rona.
Ha a bona sena, moqapi o tlola cheke ka thabo, 'me re qetella re bolokile li-nanoseconds tse ling tse 500.
Li-butches tse kholo
Ho lokile, re khonne ho pepesa ts'ebetso e itseng ts'ebetsong ea rona e bonolo, empa sephetho sena se mpe haholo ho feta kamoo se ka khonehang ka lisebelisoa tsa hajoale.
Seo re se etsang feela ke ts'ebetso ea mantlha ea li-bit, 'me li-processor tsa rona li li etsa hantle haholo. Empa, ka bomalimabe, re "fepa" processor ea rona ka likarolo tse nyane haholo tsa mosebetsi. Mesebetsi ea rona e etsa ts'ebetso ho latela mokhoa oa byte-by-byte. Re ka fetola khoutu ea rona habonolo ho sebetsa le likotoana tsa 8-byte re sebelisa lilae tsa UInt64.
Joalokaha u bona, phetoho ena e nyenyane e potlakisa lenaneo la rona ka makhetlo a robeli ka ho eketsa boholo ba batch ka makhetlo a robeli. Phaello e ka boleloa e le linear.
Ho kenngwa tshebetsong ka sekopanyi
Empa sena ha se pheletso. Li-processor tsa rona li ka sebetsa ka likarolo tsa 16, 32 esita le 64 byte. Ts'ebetso e joalo e "pharaletse" e bitsoa "single instruction multiple data" (SIMD; taeo e le 'ngoe, lintlha tse ngata),' me mokhoa oa ho fetola khoutu e le hore o sebelise ts'ebetso e joalo o bitsoa vectorization.
Ka bomalimabe, Go compiler e hole haholo le ho etsa vectorization. Hajoale, tsela e le 'ngoe feela ea ho etsa khoutu ea Go ke ho nka le ho beha lits'ebetso tsena ka letsoho u sebelisa Go assembler.
Go assembler ke sebata se makatsang. Mohlomong ua tseba hore puo ea kopano ke ntho e amanang haholo le meralo ea komporo eo u e ngollang, empa ha ho joalo ho Go. Go assembler e tšoana le IRL (puo ea boemeli ba mahareng) kapa puo ea mahareng: e batla e ikemetse ka sethala. Rob Pike o fane ka ts'ebetso e ntle haholo ka sehlooho sena lilemo tse 'maloa tse fetileng ho GopherCon e Denver.
Ho feta moo, Go e sebelisa sebopeho se sa tloaelehang sa Plan 9, se fapaneng le liforomo tse amoheloang ka kakaretso tsa AT&T le Intel.
Ho bolokehile ho bolela hore ho ngola Go assembler ka letsoho ha se monate ka ho fetisisa.
Empa, ka lehlohonolo, ho se ho na le lisebelisoa tse peli tsa boemo bo holimo tse re thusang ho ngola Go assembler: PeachPy le avo. Lisebelisoa tsena ka bobeli li hlahisa Go assembler ho tsoa ho khoutu ea boemo bo holimo e ngotsoeng ho Python le Go, ka ho latellana.
Lisebelisoa tsena li nolofatsa lintho tse kang kabo ea ngoliso, ho ngola loops, 'me ka kakaretso li nolofatsa mokhoa oa ho kena lefatšeng la mananeo a kopano ho Go.
Re tla sebelisa avo, kahoo mananeo a rona e tla ba mananeo a tloaelehileng a Go.
Sena ke seo mohlala o bonolo oa lenaneo la avo o shebahalang ka ona. Re na le ts'ebetso e kholo (), e hlalosang ka hare ho eona mosebetsi oa Add (), oo moelelo oa oona e leng ho eketsa linomoro tse peli. Ho na le mesebetsi ea bathusi mona ho fumana liparamente ka mabitso le ho fumana e 'ngoe ea lirekoto tsa mahala le tse loketseng tsa processor. Ts'ebetso e 'ngoe le e' ngoe ea processor e na le ts'ebetso e ts'oanang ho avo, joalo ka ha e bonoa ho ADDQ. Qetellong, re bona tšebetso ea mothusi bakeng sa ho boloka boleng bo hlahisitsoeng.
Ka ho letsetsa go hlahisa, re tla phethahatsa lenaneo ho avo mme ka lebaka leo, lifaele tse peli li tla hlahisoa:
- eketsa.s ka khoutu e hlahisoang ho Go assembler;
- stub.go e nang le lihlooho tsa tšebetso ho hokahanya mafatše a mabeli: E-ea 'me u kopane.
Kaha joale re se re bone seo avo e se etsang le hore na joang, a re shebeng mesebetsi ea rona. Ke kentse tšebetsong mefuta ea scalar le vector (SIMD) ea mesebetsi.
Ha re shebeng liphetolelo tsa scalar pele.
Joalo ka mohlala o fetileng, re kopa rejisetara ea sepheo sa mahala le e sebetsang, ha ho hlokahale hore re bale litheolelo le boholo ba likhang. o re etsetsa tsena tsohle.
Re ne re sebelisa li-labels le goto (kapa jumps) ho ntlafatsa ts'ebetso le ho qhekella moqapi oa Go, empa joale re ntse re e etsa ho tloha qalong. Taba ke hore lipotoloho ke mohopolo oa boemo bo holimo. Ho assembler, re na le li-labels le ho tlola feela.
Khoutu e setseng e lokela ho ba e se e ntse e tsebahala ebile e utloahala. Re etsisa lupu e nang le lileibole le ho tlola, re nka karoloana ea data ho lilae tsa rona tse peli, re li kopanye le ts'ebetso e nyane (MME HASE tabeng ena) ebe re kenya sephetho selae se hlahisoang. Tsohle.
Sena ke seo khoutu ea ho qetela e kopanyang e shebahalang ka eona. Re ne re sa tlameha ho bala li-offsets le boholo (tse totobalitsoeng ka botala) kapa ho boloka tlaleho ea lirejisete tse sebelisitsoeng (tse totobalitsoeng ka bofubelu).
Haeba re bapisa ts'ebetso ea ts'ebetsong ea puo ea kopano le ts'ebetso ea ts'ebetsong e ntle ka ho fetisisa ho Go, re tla bona hore e tšoana. 'Me sena se lebeletsoe. Ntle le moo, ha rea ka ra etsa letho le ikhethang - re sa tsoa hlahisa seo moqapi oa Go a neng a tla se etsa.
Ka bomalimabe, re ke ke ra qobella moqapi hore a kenye tšebetsong ea rona e ngotsoeng ka puo ea kopano. The Go compiler hajoale ha e na tšobotsi e joalo, leha ho bile le kopo ea ho e kenyelletsa nako e telele.
Ke ka lebaka leo ho ke keng ha khoneha ho fumana molemo leha e le ofe mesebetsing e nyenyane ka puo ea kopano. Re hloka ho ngola mesebetsi e meholo, kapa ho sebelisa sephutheloana se secha sa lipalo/bits, kapa ho feta puo e kopanyang.
Joale ha re shebeng mefuta ea vector ea mesebetsi ea rona.
Bakeng sa mohlala ona, ke nkile qeto ea ho sebelisa AVX2, kahoo re tla sebelisa ts'ebetso e sebetsang ka likotoana tsa 32-byte. Sebopeho sa khoutu se ts'oana haholo le mofuta oa scalar: ho kenya li-parameter, ho kopa ngoliso ea mahala e arolelanoang, joalo-joalo.
Ntho e 'ngoe e ncha ke hore lits'ebetso tse pharalletseng tsa li-vector li sebelisa lirekoto tse khethehileng tse pharalletseng. Tabeng ea li-chunk tsa 32-byte, tsena ke lirejisete tse ngotsoeng ka Y. Ke ka lebaka lena u bonang tšebetso ea YMM() khoutung. Haeba ke ne ke sebelisa AVX-512 ka likotoana tsa 64-bit, sehlomathiso e ne e tla ba Z.
Boqapi ba bobeli ke hore ke nkile qeto ea ho sebelisa optimization e bitsoang loop unrolling, e bolelang ho etsa lits'ebetso tse robeli tsa loop ka letsoho pele ke qhomela qalong ea lupu. Ntlafatso ena e fokotsa palo ea makala a khoutu, 'me e lekanyelitsoe ke palo ea li-registeri tsa mahala tse fumanehang.
Ho thoe'ng ka ts'ebetso? O motle! Re fihletse lebelo la makhetlo a ka bang supileng ho bapisoa le tharollo e ntle ka ho fetisisa ea Go. E khahla, ho joalo?
Empa le ts'ebetsong ena e kanna ea potlakisoa ka ho sebelisa AVX-512, prefetching kapa JIT (motlakase oa nako feela) bakeng sa kemiso ea lipotso. Empa ka sebele ena ke sehlooho bakeng sa tlaleho e arohaneng.
Mathata ka li-index tsa bitmap
Kaha joale re se re shebile ts'ebetsong e bonolo ea index ea bitmap ho Go le e behang litholoana haholoanyane puong ea kopano, qetellong a re bue ka hore na hobaneng li-index tsa bitmap li sebelisoa seoelo.
Lipampiri tsa khale li bua ka mathata a mararo ka li-index tsa bitmap, empa lipampiri tse ncha 'me ke pheha khang ea hore ha li sa sebetsa. Re ke ke ra ikakhela ka setotsoana ho e 'ngoe le e 'ngoe ea mathata ana, empa re tla a sheba ka holimo.
Bothata ba k'hadinale e phahameng
Kahoo, re bolelloa hore li-index tsa bitmap li loketse feela masimo a nang le khardinali e tlase, ke hore, a nang le boleng bo fokolang (mohlala, bong kapa mmala oa mahlo), mme lebaka ke hore kemiso e tloaelehileng ea masimo a joalo (e le 'ngoe). bit ka boleng) tabeng ea khardinali e phahameng, e tla nka sebaka se ngata haholo 'me, ho feta moo, li-index tsena tsa bitmap li tla tlatsoa hampe (ka seoelo).
Ka linako tse ling re ka sebelisa kemelo e fapaneng, joalo ka e tloaelehileng eo re e sebelisang ho emela lipalo. Empa e ne e le ho fihla ha li-algorithms tsa compression ho ileng ha fetola ntho e 'ngoe le e' ngoe. Lilemong tse mashome tse fetileng, bo-rasaense le bafuputsi ba hlahisitse palo e kholo ea li-algorithms tsa compression bakeng sa bitmaps. Monyetla oa bona o ka sehloohong ke hore ha ho na tlhoko ea ho theola li-bitmaps ho etsa ts'ebetso e nyane - re ka etsa ts'ebetso e nyane ka kotloloho ho limmapa tse hatelitsoeng.
Haufinyane tjena, mekhoa e nyalisitsoeng e se e qalile ho hlaha, joalo ka li-bitmaps tse purumang. Ka nako e ts'oanang ba sebelisa lipapiso tse tharo tse fapaneng bakeng sa li-bitmaps - li-bitmaps ka botsona, li-arrays le seo ho thoeng ke li-bit runs - le ho leka-lekanya lipakeng tsa tsona ho eketsa ts'ebetso le ho fokotsa ts'ebeliso ea mohopolo.
U ka fumana li-bitmaps tse purumang lits'ebetsong tse tsebahalang haholo. Ho se ho ntse ho e-na le palo e kholo ea ts'ebetsong bakeng sa lipuo tse ngata tse fapaneng tsa lenaneo, ho kenyelletsa le tse fetang tse tharo tsa ho kenya ts'ebetsong bakeng sa Go.
Mokhoa o mong o ka re thusang ho sebetsana le boemo bo phahameng ba k'hadinale o bitsoa binning. Ak'u nahane u e-na le tšimo e emelang bolelele ba motho. Bolelele ke palo ea ntlha e phaphametseng, empa rona batho ha re e nahane joalo. Ho rona ha ho na phapang pakeng tsa bolelele ba 185,2 cm le 185,3 cm.
Hoa fumaneha hore re ka arola litekanyetso tse tšoanang ka lihlopha ka har'a 1 cm.
'Me haeba re boetse re tseba hore batho ba fokolang haholo ba khutšoanyane ho feta 50 cm le ba molelele ho feta 250 cm, joale re ka fetola tšimo e nang le k'hadinali e sa feleng tšimong e nang le k'hadinari ea litekanyetso tse ka bang 200.
Ehlile, haeba ho hlokahala, re ka etsa sefa se eketsehileng kamora moo.
Bothata ba Bandwidth e Phahameng
Bothata bo latelang ka li-index tsa bitmap ke hore ho li nchafatsa ho ka bitsa chelete e ngata haholo.
Litsi tsa polokelo li tlameha ho khona ho ntlafatsa lintlha ha lipotso tse ling tse ka bang makholo li ntse li batlisisa datha. Re hloka linotlolo ho qoba mathata ka phihlello ea data ka nako e le 'ngoe kapa mathata a mang a ho arolelana. 'Me moo ho nang le senotlolo se le seng se seholo, ho na le bothata - likhang tsa senotlolo, ha senotlolo sena se fetoha botlolo.
Bothata bona bo ka rarolloa kapa ba qojoa ka ho sebelisa sharding kapa ka ho sebelisa li-index tsa mofuta.
Sharding ke ntho e bonolo le e tsebahalang. U ka arola index ea bitmap joalo ka ha u ka etsa data efe kapa efe. Ho e-na le senotlolo se le seng se seholo, u tla fumana letoto la liloko tse nyane, 'me kahoo u tlose likhohlano tsa senotlolo.
Tsela ea bobeli ea ho rarolla bothata ke ho sebelisa li-index tsa mofuta. U ka ba le kopi e le ’ngoe ea index eo u e sebelisang ha u batla kapa ua e bala, le eo u e sebelisetsang ho ngola kapa ho e ntlafatsa. 'Me hang ka nako e itseng (mohlala, hang ka mor'a 100 ms kapa 500 ms) u li kopitsa ebe u li fapanyetsana. Ehlile, mokhoa ona o sebetsa feela maemong ao kopo ea hau e ka sebetsanang le index ea patlo e salang hanyane.
Mekhoa ena e 'meli e ka sebelisoa ka nako e le' ngoe: o ka ba le index ea sharded version.
Lipotso tse thata haholoanyane
Bothata ba ho qetela ka li-index tsa bitmap ke hore re bolelloa hore ha li tšoanelehe bakeng sa mefuta e mengata ea lipotso, joalo ka lipotso tsa span.
Ha e le hantle, ha u nahana ka eona, ts'ebetso e nyane joalo ka AND, OR, joalo-joalo ha ea lokela ho botsa lipotso tse kang "Mpontše lihotele tse nang le litefiso tsa kamore ho tloha ho lidolara tse 200 ho isa ho tse 300 bosiu bo bong le bo bong."
Tharollo e hlokang kelello le e seng bohlale haholo e ka ba ho nka liphetho tsa boleng ba dolara e 'ngoe le e 'ngoe le ho li kopanya le ts'ebetso e nyane KAPA.
Tharollo e betere hanyane e ka ba ho sebelisa lihlopha. Ka mohlala, ka lihlopha tsa lidolara tse 50. Sena se ne se tla potlakisa ts'ebetso ea rona ka makhetlo a 50.
Empa bothata bo boetse bo rarolloa habonolo ka ho sebelisa pono e entsoeng ka ho khetheha bakeng sa mofuta ona oa kopo. Lipampiring tsa saense e bitsoa range-encoded bitmaps.
Setšoantšong sena, ha re behe karolo e le 'ngoe feela bakeng sa boleng bo itseng (mohlala, 200), empa beha boleng bona le ntho e' ngoe le e 'ngoe e phahameng. 200 le ho feta. E tšoanang bakeng sa 300: 300 le ho feta. Joalo joalo.
Ka ho sebelisa boemeli bona, re ka araba potso ea mofuta ona ka ho tšela index habeli feela. Taba ea pele, re tla fumana lethathamo la lihotele moo kamore e jang tlase kapa $300, ebe re tlosa ho eona tseo theko ea kamore e leng tlase kapa $199. E lokile.
U tla makala, empa le li-geoqueries lia khoneha ho sebelisa li-index tsa bitmap. Leqheka ke ho sebelisa setšoantšo sa geometri se potolohileng khokahanyo ea hau ka setšoantšo sa geometri. Ka mohlala, S2 ho tloha Google. Palo e lokela ho khoneha ho emela ka mokhoa oa mela e meraro kapa ho feta e intersecting e ka baloang. Ka tsela ena re ka fetola geoquery ea rona hore e be lipotso tse 'maloa "haufi le lekhalo" (hammoho le mela ena e nang le linomoro).
Litharollo tse itokiselitseng
Ke tšepa hore ke u thahasella hanyenyane 'me hona joale u na le sesebelisoa se seng sa bohlokoa ho arsenal ea hau. Haeba u hloka ho etsa ntho e kang ena, u tla tseba hore na u shebe tsela efe.
Leha ho le joalo, ha se motho e mong le e mong ea nang le nako, mamello, kapa lisebelisoa tsa ho etsa li-index tsa bitmap ho tloha qalong. Haholo-holo tse tsoetseng pele ho feta, ho sebelisa SIMD, mohlala.
Ka lehlohonolo, ho na le litharollo tse 'maloa tse lokiselitsoeng ho u thusa.
Li-bitmaps tse purumang
Taba ea pele, ho na le laebrari e tšoanang ea bitmaps eo ke seng ke buile ka eona. E na le lijana tsohle tse hlokahalang le lits'ebetso tse nyane tseo u tla li hloka ho etsa index ea bitmap e felletseng.
Ka bomalimabe, hajoale, ha ho le e 'ngoe ea lits'ebetso tsa Go e sebelisang SIMD, ho bolelang hore ts'ebetsong ea Go ha e sebetse ho feta ts'ebetsong ea C, mohlala.
Pilosa
Sehlahisoa se seng se ka u thusang ke Pilosa DBMS, eo, ha e le hantle, e nang le li-index tsa bitmap feela. Ena ke tharollo e batlang e le ncha, empa e hapa lipelo ka lebelo le leholo.
Pilosa e sebelisa li-bitmaps tse purumang ka hare 'me e u fa bokhoni ba ho li sebelisa, e nolofatsa le ho hlalosa lintho tsohle tseo ke buileng ka tsona ka holimo: lihlopha, li-bitmaps tsa mefuta-futa, khopolo ea tšimo, joalo-joalo.
Ha re shebeng ka potlako mohlala oa ho sebelisa Pilosa ho araba potso eo u seng u e tseba.
Mohlala o tšoana haholo le oo u o boneng pele. Re theha moreki ho seva sa Pilosa, re theha index le masimo a hlokahalang, ebe re tlatsa masimo a rona ka data e sa reroang ka menyetla mme, qetellong, re phethe potso e tloaelehileng.
Ka mor'a moo, ha re sebelise NOT ho lebaleng la "turu", ebe re kopanya sephetho (kapa LE eona) le sebaka sa "terrace" le sebaka sa "lipehelo". 'Me qetellong, re fumana sephetho sa ho qetela.
Ke ts'epa haholo hore nakong e tlang e lebelletsoeng pele mofuta ona o mocha oa index o tla hlaha hape ho li-DBMS joalo ka MySQL le PostgreSQL - li-index tsa bitmap.
fihlela qeto e
Haeba ha o eso robale, kea leboha. Ke ile ka tlameha ho ama ka bokhutšoanyane lihloohong tse ngata ka lebaka la nako e lekanyelitsoeng, empa ke tšepa hore puo e ne e le molemo mme mohlomong e bile e susumetsa.
Li-index tsa Bitmap li molemo ho tseba ka tsona, leha u sa li hloke hona joale. E re e be sesebelisoa se seng lebokoseng la hau la lithulusi.
Re shebile maqheka a fapaneng a ts'ebetso bakeng sa Go le lintho tseo motlalehi oa Go a sa li sebetseng hantle. Empa sena se na le thuso bakeng sa moqapi e mong le e mong oa Go ho tseba.
Ke phetho seo ke neng ke batla ho o bolella sona. Kea leboha!
Source: www.habr.com