ifihan
Mo fun ni ijabọ yii ni Gẹẹsi ni apejọ GopherCon Russia 2019 ni Ilu Moscow ati ni Russian ni ipade kan ni Nizhny Novgorod. A n sọrọ nipa atọka bitmap - ti ko wọpọ ju igi B, ṣugbọn kii ṣe igbadun diẹ. Pínpín awọn ọrọ ni apejọ ni Gẹẹsi ati awọn iwe afọwọkọ ọrọ ni Russian.
A yoo wo bi itọka bitmap ṣe n ṣiṣẹ, nigbati o dara julọ, nigbati o buru ju awọn atọka miiran lọ, ati ninu awọn ọran wo ni iyara yiyara ju wọn lọ; Jẹ ki a wo iru awọn DBMS olokiki ti ni awọn atọka bitmap tẹlẹ; Jẹ ki a gbiyanju lati kọ tiwa ni Go. Ati “fun desaati” a yoo lo awọn ile-ikawe ti a ti ṣetan lati ṣẹda data data amọja ti o yara-yara tiwa.
Mo nireti gaan pe awọn iṣẹ mi yoo wulo ati igbadun fun ọ. Lọ!
Ifihan
Bawo ni gbogbo eniyan! O ni aṣalẹ mẹfa ati pe gbogbo wa ni o rẹwẹsi pupọ. Akoko nla lati sọrọ nipa ilana atọka data alaidun, otun? Maṣe yọ ara rẹ lẹnu, Emi yoo ni awọn ila meji ti koodu orisun nibi ati nibẹ. 🙂
Gbogbo awọn awada ni apakan, ijabọ naa kun fun alaye, ati pe a ko ni akoko pupọ. Nitorinaa jẹ ki a bẹrẹ.
Loni Emi yoo sọrọ nipa atẹle naa:
- kini awọn atọka;
- kini atọka bitmap;
- ibi ti o ti lo ati ibi ti o ti wa ni KO lo ati idi ti;
- o rọrun imuse ni Go ati kekere kan Ijakadi pẹlu alakojo;
- die-die kere o rọrun, sugbon Elo siwaju sii productive imuse ni Go assembler;
- "awọn iṣoro" ti awọn atọka bitmap;
- tẹlẹ awọn imuṣẹ.
Nitorina kini awọn atọka?
Atọka naa jẹ eto data lọtọ ti a ṣetọju ati imudojuiwọn ni afikun si data akọkọ. O ti wa ni lo lati mu yara awọn àwárí. Laisi awọn atọka, wiwa yoo nilo lilọ nipasẹ data naa patapata (ilana kan ti a pe ni ọlọjẹ kikun), ati pe ilana yii ni eka algorithmic laini. Ṣugbọn awọn apoti isura infomesonu nigbagbogbo ni awọn oye nla ti data ati idiju laini jẹ o lọra pupọ. Bi o ṣe yẹ, a yoo gba logarithmic tabi ọkan nigbagbogbo.
Eyi jẹ koko-ọrọ ti o nira pupọ, ti o kun fun awọn arekereke ati awọn pipaṣẹ iṣowo, ṣugbọn lẹhin wiwo awọn ewadun ti idagbasoke data data ati iwadii, Mo fẹ lati sọ pe awọn ọna diẹ ti o lo pupọ lo wa si ṣiṣẹda awọn atọka data.
Ọna akọkọ ni lati dinku aaye wiwa ni ọna kika, pin aaye wiwa si awọn ẹya kekere.
A maa n ṣe eyi nipa lilo awọn oriṣiriṣi awọn igi. Apeere kan yoo jẹ apoti nla ti awọn ohun elo ninu ile-iyẹwu rẹ ti o ni awọn apoti kekere ti awọn ohun elo ti a pin si awọn akọle oriṣiriṣi. Ti o ba nilo awọn ohun elo, iwọ yoo wa wọn ninu apoti ti o sọ "Awọn ohun elo" dipo ọkan ti o sọ "Kukisi," ọtun?
Ọna keji ni lati yan nkan ti o fẹ lẹsẹkẹsẹ tabi ẹgbẹ awọn eroja. A ṣe eyi ni awọn maapu hash tabi awọn atọka yiyipada. Lilo awọn maapu hash jẹ iru pupọ si apẹẹrẹ ti tẹlẹ, ṣugbọn dipo apoti ti awọn apoti, o ni akojọpọ awọn apoti kekere ti awọn ohun ikẹhin ninu kọlọfin rẹ.
Ọna kẹta ni lati yọkuro iwulo fun wiwa. A ṣe eyi nipa lilo awọn asẹ Bloom tabi awọn asẹ cuckoo. Awọn akọkọ funni ni idahun lẹsẹkẹsẹ, fifipamọ ọ lati ni wiwa.
Ọna ti o kẹhin ni lati lo gbogbo agbara ti ohun elo ode oni fun wa. Eyi ni deede ohun ti a ṣe ni awọn atọka bitmap. Bẹẹni, nigba lilo wọn a ma nilo lati lọ nipasẹ gbogbo atọka, ṣugbọn a ṣe daradara daradara.
Bi mo ti sọ, koko-ọrọ ti awọn atọka data data jẹ ti o pọju o si kun fun awọn adehun. Eyi tumọ si pe nigbami a le lo awọn ọna pupọ ni akoko kanna: ti a ba nilo lati yara wiwa paapaa diẹ sii, tabi ti a ba nilo lati bo gbogbo awọn iru wiwa ti o ṣeeṣe.
Loni Emi yoo sọrọ nipa ọna ti o kere julọ ti awọn wọnyi - awọn atọka bitmap.
Tani emi lati sọrọ lori koko yii?
Mo ṣiṣẹ bi oludari ẹgbẹ kan ni Badoo (boya o mọ diẹ sii pẹlu ọja miiran, Bumble). A ti ni diẹ sii ju awọn olumulo miliọnu 400 ni agbaye ati ọpọlọpọ awọn ẹya ti o yan ere ti o dara julọ fun wọn. A ṣe eyi nipa lilo awọn iṣẹ aṣa, pẹlu awọn atọka bitmap.
Nitorina kini atọka bitmap kan?
Awọn atọka Bitmap, gẹgẹbi orukọ ṣe daba, lo bitmaps tabi bitsets lati ṣe atọka wiwa kan. Lati iwo oju eye, atọka yii ni ọkan tabi diẹ ẹ sii iru awọn maapu bii ti o nsoju eyikeyi awọn nkan (gẹgẹbi eniyan) ati awọn ohun-ini wọn tabi awọn paramita (ọjọ ori, awọ oju, ati bẹbẹ lọ), ati algorithm kan nipa lilo awọn iṣẹ bit (ATI, TABI, KO ) lati dahun ibeere wiwa.
A sọ fun wa pe awọn atọka bitmap ni o dara julọ ati ṣiṣe pupọ fun awọn ọran nibiti awọn iwadii wa ti o ṣajọpọ awọn ibeere kọja ọpọlọpọ awọn ọwọn Cardinality kekere (ronu “awọ oju” tabi “ipo igbeyawo” dipo ohunkan bi “ijinna lati aarin ilu”). Ṣugbọn Emi yoo fihan nigbamii pe wọn ṣiṣẹ ni itanran fun awọn ọwọn cardinality giga daradara.
Jẹ ki a wo apẹẹrẹ ti o rọrun julọ ti atọka bitmap kan.
Fojuinu pe a ni atokọ ti awọn ile ounjẹ Moscow pẹlu awọn ohun-ini alakomeji bii iwọnyi:
- nitosi metro;
- o wa ikọkọ pa;
- veranda wa (ni o ni filati);
- o le ṣeduro tabili kan (gba awọn ifiṣura);
- o dara fun awọn ajewebe (ọrẹ ajewebe);
- gbowolori (gbowolori).
Jẹ ki a fun ounjẹ kọọkan ni nọmba ọkọọkan ti o bẹrẹ lati 0 ati pin iranti fun awọn maapu 6 (ọkan fun abuda kọọkan). A yoo ṣe agbejade awọn maapu wọnyi da lori boya ile ounjẹ naa ni ohun-ini yii tabi rara. Ti ile ounjẹ 4 ba ni veranda, lẹhinna bit No.. 4 ni “ni o ni veranda” bitmap yoo ṣeto si 1 (ti ko ba si veranda, lẹhinna si 0).
Bayi a ni atọka bitmap ti o rọrun julọ ṣee ṣe, ati pe a le lo lati dahun awọn ibeere bii:
- "Fi mi han awọn ounjẹ ti o ni ore-ajewewe";
- "Fi awọn ile ounjẹ ti ko gbowolori han mi pẹlu veranda nibiti o le ṣe ifipamọ tabili kan.”
Bawo? Jẹ ki a wo. Ibere akọkọ rọrun pupọ. Gbogbo ohun ti a nilo lati ṣe ni mu bitmap “ọrẹ ajewewe” ki o tan-an sinu atokọ ti awọn ile ounjẹ ti awọn ege wọn ti han.
Ibeere keji jẹ diẹ idiju diẹ sii. A nilo lati lo NOT bitmap lori bitmap “gbowolori” lati gba atokọ ti awọn ile ounjẹ ti ko gbowolori, lẹhinna ATI pẹlu “Mo le ṣe iwe tabili kan” bitmap ati ATI abajade pẹlu “veranda” bitmap. Abajade bitmap yoo ni atokọ ti awọn idasile ti o pade gbogbo awọn ibeere wa. Ni apẹẹrẹ yii, ile ounjẹ Yunost nikan ni eyi.
Ilana pupọ lo wa, ṣugbọn maṣe yọ ara rẹ lẹnu, a yoo rii koodu naa laipẹ.
Nibo ni a ti lo awọn atọka bitmap?
Ti o ba awọn atọka bitmap Google, 90% ti awọn idahun yoo jẹ ibatan si Oracle DB ni ọna kan tabi omiiran. Ṣugbọn awọn DBMS miiran jasi tun ṣe atilẹyin iru nkan ti o tutu, otun? Be ko.
Jẹ ki a lọ nipasẹ atokọ ti awọn ifura akọkọ.
MySQL ko sibẹsibẹ ṣe atilẹyin awọn atọka bitmap, ṣugbọn imọran wa ni iyanju fifi aṣayan yii kun ().
PostgreSQL ko ṣe atilẹyin awọn atọka bitmap, ṣugbọn nlo awọn maapu bitmap ti o rọrun ati awọn iṣẹ bit lati ṣajọpọ awọn abajade wiwa kọja awọn atọka miiran lọpọlọpọ.
Tarantool ni awọn atọka bitset ati atilẹyin awọn wiwa ti o rọrun lori wọn.
Redis ni awọn aaye kekere ti o rọrun) laisi agbara lati wa wọn.
MongoDB ko sibẹsibẹ ṣe atilẹyin awọn atọka bitmap, ṣugbọn imọran tun wa ni iyanju pe ki o ṣafikun aṣayan yii
Elasticsearch nlo bitmaps inu).
- Ṣugbọn aládùúgbò tuntun kan ti farahan ninu ile wa: Pilosa. Eyi jẹ aaye data tuntun ti kii ṣe ibatan ti a kọ sinu Go. O ni awọn atọka bitmap nikan ati awọn ipilẹ ohun gbogbo lori wọn. A yoo soro nipa o kekere kan nigbamii.
Imuse ni Go
Ṣugbọn kilode ti awọn atọka bitmap ko ṣọwọn lo? Ṣaaju ki o to dahun ibeere yii, Emi yoo fẹ lati fihan ọ bi o ṣe le ṣe imuse atọka bitmap kan ti o rọrun pupọ ni Go.
Bitmaps jẹ pataki awọn ege data nikan. Ni Go, jẹ ki a lo awọn ege baiti fun eyi.
A ni bitmap kan fun iwa ile ounjẹ kan, ati pe ọkọọkan ninu bitmap naa tọka boya ile ounjẹ kan pato ni ohun-ini yii tabi rara.
A yoo nilo awọn iṣẹ oluranlọwọ meji. Ọkan yoo wa ni lo lati kun wa bitmaps pẹlu ID data. Laileto, ṣugbọn pẹlu iṣeeṣe kan pe ile ounjẹ ni ohun-ini kọọkan. Fun apẹẹrẹ, Mo gbagbọ pe awọn ile ounjẹ diẹ wa ni Ilu Moscow nibiti o ko le ṣeduro tabili kan, ati pe o dabi si mi pe nipa 20% ti awọn idasile jẹ o dara fun awọn ajewebe.
Iṣẹ keji yoo yi bitmap pada si atokọ ti awọn ile ounjẹ.
Lati dahun ibeere naa “Fihan awọn ile ounjẹ ti ko gbowolori ti o ni patio kan ti o le ṣe awọn ifiṣura,” a nilo awọn iṣẹ-bit meji: NOT ati AND.
A le jẹ ki koodu wa rọrun diẹ nipa lilo eka diẹ sii ATI NOT oniṣẹ.
A ni awọn iṣẹ fun ọkọọkan awọn iṣẹ wọnyi. Mejeji wọn lọ nipasẹ awọn ege, mu awọn eroja ti o baamu lati ọkọọkan, darapọ wọn pẹlu iṣẹ diẹ ki o fi abajade sinu bibẹ abajade.
Ati ni bayi a le lo awọn maapu kekere wa ati awọn iṣẹ lati dahun ibeere wiwa naa.
Išẹ ko ga julọ, botilẹjẹpe awọn iṣẹ naa rọrun pupọ ati pe a fipamọ ọpọlọpọ owo nipa ko pada bibẹ abajade tuntun ni igba kọọkan ti a pe iṣẹ naa.
Lẹhin ṣiṣe diẹ ninu profaili pẹlu pprof, Mo ṣe akiyesi pe Go compiler ti nsọnu ọkan ti o rọrun pupọ ṣugbọn iṣapeye pataki pupọ: inlining iṣẹ.
Otitọ ni pe Go alakojo bẹru ẹru ti awọn losiwajulosehin ti o lọ nipasẹ awọn ege, ati ni pato kọ awọn iṣẹ inline ti o ni iru awọn losiwajulosehin.
Ṣugbọn emi ko bẹru ati pe Mo le ṣe aṣiwere olupilẹṣẹ nipasẹ lilo goto dipo lupu, bii ni awọn ọjọ atijọ ti o dara.
Ati pe, bi o ti le rii, ni bayi olupilẹṣẹ yoo ni inudidun laini iṣẹ wa! Bi abajade, a ṣakoso lati fipamọ nipa awọn iṣẹju-aaya 2. Ko buru!
Igo igo keji jẹ rọrun lati rii ti o ba wo ni pẹkipẹki ni iṣelọpọ apejọ. Olupilẹṣẹ ṣafikun iṣayẹwo ala bibẹ kan ọtun inu lupu to gbona julọ wa. Otitọ ni pe Go jẹ ede ailewu, olupilẹṣẹ bẹru pe awọn ariyanjiyan mẹta mi (awọn ege mẹta) jẹ ti awọn titobi oriṣiriṣi. Lẹhinna, lẹhinna iṣeeṣe imọ-jinlẹ yoo wa ti iṣẹlẹ ti ohun ti a pe ni apọju ifipamọ.
Jẹ ki a ni idaniloju alakojo nipa fifihan pe gbogbo awọn ege jẹ iwọn kanna. A le ṣe eyi nipa fifi ayẹwo ti o rọrun ni ibẹrẹ iṣẹ wa.
Nigbati o rii eyi, olupilẹṣẹ naa fi ayọ fo ayẹwo naa, ati pe a pari fifipamọ 500 nanoseconds miiran.
Awọn ẹran nla
O dara, a ṣakoso lati fun pọ iṣẹ diẹ ninu imuse ti o rọrun wa, ṣugbọn abajade yii buru pupọ ju bi o ti ṣee ṣe pẹlu ohun elo lọwọlọwọ.
Gbogbo ohun ti a ṣe ni awọn iṣẹ bit ipilẹ, ati awọn olutọsọna wa ṣe wọn daradara daradara. Ṣugbọn, laanu, a “jẹun” ero isise wa pẹlu awọn ege iṣẹ kekere pupọ. Awọn iṣẹ wa ṣe awọn iṣẹ lori ipilẹ baiti-nipasẹ-baiti. A le ni irọrun tweak koodu wa lati ṣiṣẹ pẹlu awọn chunks 8-baiti ni lilo awọn ege UInt64.
Gẹgẹbi o ti le rii, iyipada kekere yii ṣe alekun eto wa ni igba mẹjọ nipa jijẹ iwọn ipele naa ni igba mẹjọ. A le sọ ere naa lati jẹ laini.
Imuse ni assembler
Ṣugbọn eyi kii ṣe opin. Awọn ilana wa le ṣiṣẹ pẹlu awọn chunks ti 16, 32 ati paapaa awọn baiti 64. Iru awọn iṣẹ-ṣiṣe “gbigboro” ni a pe ni itọnisọna kan ni ọpọlọpọ data (SIMD; itọnisọna kan, ọpọlọpọ data), ati ilana ti iyipada koodu ki o lo iru awọn iṣẹ bẹ ni a pe ni vectorization.
Laanu, Go alakojo jina lati o tayọ ni vectorization. Lọwọlọwọ, ọna kan ṣoṣo lati ṣe vectorize koodu Go ni lati mu ati fi awọn iṣẹ wọnyi si pẹlu ọwọ nipa lilo apejọ Go.
Lọ assembler ni a ajeji ẹranko. O ṣee ṣe ki o mọ pe ede apejọ jẹ nkan ti o ni asopọ pupọ si awọn faaji ti kọnputa ti o nkọwe fun, ṣugbọn iyẹn kii ṣe ọran ni Go. Go assembler jẹ diẹ sii bi IRL (ede asoju agbedemeji) tabi ede agbedemeji: o jẹ adaṣe ni ominira. Rob Pike fun iṣẹ ti o dara julọ lori koko yii ni ọpọlọpọ ọdun sẹyin ni GopherCon ni Denver.
Ni afikun, Go nlo ọna kika Eto 9 dani, eyiti o yatọ si awọn ọna kika AT&T ati Intel ti a gba ni gbogbogbo.
O jẹ ailewu lati sọ pe kikọ Go assembler pẹlu ọwọ kii ṣe igbadun julọ.
Ṣugbọn, ni oriire, awọn irinṣẹ ipele giga meji ti wa tẹlẹ ti o ṣe iranlọwọ fun wa lati kọ Go assembler: PeachPy ati avo. Awọn ohun elo mejeeji ṣe agbejade apejọ Go lati koodu ipele giga ti a kọ sinu Python ati Go, lẹsẹsẹ.
Awọn ohun elo wọnyi jẹ irọrun awọn nkan bii ipin iforukọsilẹ, kikọ awọn losiwajulosehin, ati ni gbogbogbo rọrun ilana ti gbigba sinu agbaye ti siseto apejọ ni Go.
A yoo lo avo, nitorina awọn eto wa yoo fẹrẹ jẹ awọn eto Go deede.
Eyi ni apẹẹrẹ ti o rọrun julọ ti eto avo kan dabi. A ni iṣẹ akọkọ () kan, eyiti o ṣalaye laarin ararẹ iṣẹ Fikun-un, itumọ eyiti o jẹ lati ṣafikun awọn nọmba meji. Awọn iṣẹ oluranlọwọ wa nibi lati gba awọn paramita nipasẹ orukọ ati gba ọkan ninu ọfẹ ati awọn iforukọsilẹ ero isise to dara. Išẹ isise kọọkan ni iṣẹ ti o baamu lori avo, bi a ti ri ninu ADDQ. Nikẹhin, a rii iṣẹ oluranlọwọ kan fun titoju iye abajade.
Nipa pipe go ina, a yoo ṣe eto naa lori avo ati bi abajade, awọn faili meji yoo ṣe ipilẹṣẹ:
- add.s pẹlu awọn Abajade koodu ni Go assembler;
- stub.go pẹlu awọn akọle iṣẹ lati so awọn aye meji pọ: Lọ ati apejọ.
Ni bayi ti a ti rii kini avo ṣe ati bii, jẹ ki a wo awọn iṣẹ wa. Mo ti ṣe imuse mejeeji scalar ati fekito (SIMD) awọn ẹya ti awọn iṣẹ.
Jẹ ki a wo awọn ẹya scalar akọkọ.
Gẹgẹbi apẹẹrẹ ti tẹlẹ, a n beere fun ọfẹ ati iforukọsilẹ idi gbogbogbo ti o wulo, a ko nilo lati ṣe iṣiro awọn aiṣedeede ati awọn iwọn fun awọn ariyanjiyan. avo ṣe gbogbo eyi fun wa.
A lo awọn akole ati goto (tabi fo) lati mu iṣẹ ṣiṣe dara si ati ki o tan-akọọlẹ Go, ṣugbọn ni bayi a n ṣe lati ibẹrẹ. Oro naa ni pe awọn iyipo jẹ imọran ipele ti o ga julọ. Ni assembler, a nikan ni akole ati fo.
Awọn koodu ti o ku yẹ ki o ti mọ tẹlẹ ati oye. A ṣe apẹẹrẹ lupu kan pẹlu awọn aami ati fo, mu nkan kekere ti data lati awọn ege meji wa, darapọ wọn pẹlu iṣẹ diẹ (ATI KO ninu ọran yii) ati lẹhinna fi abajade sinu bibẹ abajade. Gbogbo.
Eleyi jẹ ohun ti ik assembler koodu wulẹ. A ko ni lati ṣe iṣiro awọn aiṣedeede ati awọn iwọn (ti o ṣe afihan ni alawọ ewe) tabi tọju awọn iforukọsilẹ ti a lo (ti ṣe afihan ni pupa).
Ti a ba ṣe afiwe iṣẹ ti imuse ede apejọ pẹlu iṣẹ imuse ti o dara julọ ni Go, a yoo rii pe o jẹ kanna. Ati pe eyi ni a nireti. Lẹhinna, a ko ṣe ohunkohun pataki - a kan tun ṣe ohun ti Go alakojo yoo ṣe.
Laanu, a ko le fi ipa mu olupilẹṣẹ lati ṣe inline awọn iṣẹ wa ti a kọ ni ede apejọ. Olupilẹṣẹ Go lọwọlọwọ ko ni iru ẹya kan, botilẹjẹpe ibeere ti wa lati ṣafikun fun igba diẹ.
Eyi ni idi ti ko ṣee ṣe lati ni anfani eyikeyi lati awọn iṣẹ kekere ni ede apejọ. A nilo lati kọ awọn iṣẹ nla, tabi lo idii math/bits tuntun, tabi fori ede apejọ naa.
Jẹ ki a ni bayi wo awọn ẹya fekito ti awọn iṣẹ wa.
Fun apẹẹrẹ yii, Mo pinnu lati lo AVX2, nitorinaa a yoo lo awọn iṣẹ ṣiṣe ti o ṣiṣẹ lori awọn chunks 32-byte. Eto ti koodu naa jọra pupọ si ẹya ti iwọn: awọn aye ikojọpọ, beere fun iforukọsilẹ pinpin ọfẹ, ati bẹbẹ lọ.
Ọkan ĭdàsĭlẹ ni wipe gbooro fekito mosi lo pataki jakejado forukọsilẹ. Ninu ọran ti awọn chunks 32-baiti, iwọnyi jẹ awọn iforukọsilẹ ti a ti ṣaju pẹlu Y. Eyi ni idi ti o fi rii iṣẹ YMM () ninu koodu naa. Ti MO ba nlo AVX-512 pẹlu awọn ege 64-bit, ìpele yoo jẹ Z.
Ilọtuntun keji ni pe Mo pinnu lati lo iṣapeye ti a pe ni loop unrolling, eyiti o tumọ si ṣiṣe awọn iṣẹ lupu mẹjọ pẹlu ọwọ ṣaaju ki o to fo si ibẹrẹ ti lupu naa. Imudara yii dinku nọmba awọn ẹka ninu koodu, ati pe o ni opin nipasẹ nọmba awọn iforukọsilẹ ọfẹ ti o wa.
O dara, kini nipa iṣẹ ṣiṣe? O lẹwa! A ṣaṣeyọri iyara ti bii igba meje ni akawe si ojutu Go ti o dara julọ. Iwunilori, otun?
Ṣugbọn paapaa imuse yii le ni iyara nipasẹ lilo AVX-512, iṣaju tabi JIT kan (akojọ-akoko kan) fun oluṣeto ibeere naa. Ṣugbọn eyi jẹ esan koko kan fun ijabọ lọtọ.
Awọn iṣoro pẹlu awọn atọka bitmap
Ni bayi ti a ti wo imuse ti o rọrun ti atọka bitmap ni Go ati ọkan ti o ni eso pupọ diẹ sii ni ede apejọ, jẹ ki a sọrọ nipari nipa idi ti awọn atọka bitmap ko ṣọwọn lo.
Awọn iwe agbalagba mẹnuba awọn iṣoro mẹta pẹlu awọn atọka bitmap, ṣugbọn awọn iwe tuntun ati Emi jiyan pe wọn ko wulo mọ. A kii yoo jinlẹ jinlẹ sinu ọkọọkan awọn iṣoro wọnyi, ṣugbọn a yoo wo wọn ni aipe.
Awọn isoro ti ga cardinality
Nitorinaa, a sọ fun wa pe awọn atọka bitmap jẹ o dara nikan fun awọn aaye pẹlu kaadi iranti kekere, iyẹn ni, awọn ti o ni awọn iye diẹ (fun apẹẹrẹ, abo tabi awọ oju), ati idi ni pe aṣoju deede ti iru awọn aaye (ọkan bit fun iye) ninu ọran ti cardinality giga, yoo gba aaye pupọ pupọ ati, pẹlupẹlu, awọn atọka bitmap wọnyi yoo jẹ ibi (ṣọwọn) kun.
Nigba miiran a le lo aṣoju ti o yatọ, gẹgẹbi apẹrẹ ti a lo lati ṣe aṣoju awọn nọmba. Ṣugbọn o jẹ dide ti awọn algoridimu funmorawon ti o yi ohun gbogbo pada. Ni awọn ewadun to kọja, awọn onimo ijinlẹ sayensi ati awọn oniwadi ti wa pẹlu nọmba nla ti awọn algoridimu funmorawon fun bitmaps. Anfani akọkọ wọn ni pe ko si iwulo lati decompress bitmaps lati ṣe awọn iṣẹ bit - a le ṣe awọn iṣẹ bit taara lori awọn maapu fisinuirindigbindigbin.
Laipẹ, awọn isunmọ arabara ti bẹrẹ lati han, gẹgẹbi awọn bitmaps ramuramu. Nigbakanna wọn lo awọn aṣoju oriṣiriṣi mẹta fun awọn maapu-bitmaps funrara wọn, awọn ilana ati awọn ohun ti a pe ni ṣiṣe-bit - ati iwọntunwọnsi laarin wọn lati mu iṣẹ ṣiṣe pọ si ati dinku agbara iranti.
O le wa awọn bitmaps ramuramu ninu awọn ohun elo olokiki julọ. Nọmba nla ti awọn imuse ti wa tẹlẹ fun ọpọlọpọ awọn ede siseto, pẹlu diẹ sii ju awọn imuse mẹta fun Go.
Ona miiran ti o le ṣe iranlọwọ fun wa lati koju pẹlu cardinality giga ni a npe ni binning. Fojuinu pe o ni aaye kan ti o nsoju giga eniyan. Giga jẹ nọmba aaye lilefoofo, ṣugbọn awa eniyan ko ronu rẹ ni ọna yẹn. Fun wa ko si iyato laarin iga 185,2 cm ati 185,3 cm.
O wa ni pe a le ṣe akojọpọ awọn iye kanna si awọn ẹgbẹ laarin 1 cm.
Ati pe ti a ba tun mọ pe awọn eniyan diẹ ni kukuru ju 50 cm ati giga ju 250 cm lọ, lẹhinna a le ṣe pataki yi aaye kan pẹlu kadinali ailopin sinu aaye kan pẹlu kadinality ti awọn iye 200.
Nitoribẹẹ, ti o ba jẹ dandan, a le ṣe sisẹ afikun lẹhinna.
Ga bandiwidi isoro
Iṣoro atẹle pẹlu awọn atọka bitmap ni pe imudojuiwọn wọn le jẹ gbowolori pupọ.
Awọn aaye data gbọdọ ni anfani lati ṣe imudojuiwọn data lakoko ti o pọju awọn ọgọọgọrun awọn ibeere miiran n wa data naa. A nilo awọn titiipa lati yago fun awọn iṣoro pẹlu iraye si data nigbakan tabi awọn iṣoro pinpin miiran. Ati nibiti titiipa nla kan wa, iṣoro kan wa - ariyanjiyan titiipa, nigbati titiipa yii di igo.
Iṣoro yii le jẹ ojutu tabi yipo nipasẹ lilo sharding tabi lilo awọn atọka ti ikede.
Sharding jẹ ohun ti o rọrun ati olokiki daradara. O le fọ atọka bitmap kan bi o ṣe le ṣe eyikeyi data miiran. Dipo titiipa nla kan, iwọ yoo gba opo ti awọn titiipa kekere ati nitorinaa yọkuro ariyanjiyan titiipa.
Ọna keji lati yanju iṣoro naa ni lati lo awọn atọka ti ikede. O le ni ẹda kan ti atọka ti o lo fun wiwa tabi kika, ati ọkan ti o lo fun kikọ tabi imudojuiwọn. Ati ni ẹẹkan ni akoko kan (fun apẹẹrẹ, lẹẹkan ni gbogbo 100 ms tabi 500 ms) o ṣe ẹda wọn ki o paarọ wọn. Nitoribẹẹ, ọna yii wulo nikan ni awọn ọran nibiti ohun elo rẹ le mu itọka wiwa aisun diẹ.
Awọn ọna meji wọnyi le ṣee lo ni igbakanna: o le ni itọka ti ikede sharded.
Awọn ibeere ti o ni eka sii
Iṣoro ikẹhin pẹlu awọn atọka bitmap ni pe a sọ fun wọn pe wọn ko baamu daradara fun awọn iru ibeere ti eka sii, gẹgẹbi awọn ibeere igba.
Lootọ, ti o ba ronu nipa rẹ, awọn iṣẹ bii ATI, TABI, ati bẹbẹ lọ ko dara pupọ fun awọn ibeere “Fihan awọn ile itura pẹlu awọn oṣuwọn yara lati 200 si 300 dọla fun alẹ.”
Ojutu alaigbọran ati aimọgbọnwa pupọ yoo jẹ lati mu awọn abajade fun iye dola kọọkan ki o darapọ wọn pẹlu iṣẹ ṣiṣe bitwise OR.
Ojutu diẹ ti o dara julọ yoo jẹ lilo akojọpọ. Fun apẹẹrẹ, ni awọn ẹgbẹ ti 50 dọla. Eyi yoo mu ilana wa yara nipasẹ awọn akoko 50.
Ṣugbọn iṣoro naa tun ni irọrun ni irọrun nipasẹ lilo wiwo ti a ṣẹda ni pataki fun iru ibeere yii. Ninu awọn iwe ijinle sayensi o ni a npe ni ibiti o ti fi koodu pamọ bitmaps.
Ni aṣoju yii, a ko ṣeto diẹ kan fun iye diẹ (fun apẹẹrẹ, 200), ṣugbọn ṣeto iye yii ati ohun gbogbo ti o ga julọ. 200 ati loke. Kanna fun 300: 300 ati loke. Ati bẹbẹ lọ.
Lilo aṣoju yii, a le dahun iru ibeere wiwa yii nipa lilọ kiri itọka naa lẹẹmeji. Ni akọkọ, a yoo gba atokọ ti awọn hotẹẹli nibiti yara naa ti dinku tabi $ 300, lẹhinna a yoo yọ kuro ninu rẹ nibiti iye owo yara naa kere tabi $ 199. Ṣetan.
Iwọ yoo yà ọ, ṣugbọn paapaa awọn ibeere geoqueries ṣee ṣe nipa lilo awọn atọka bitmap. Ẹtan naa ni lati lo aṣoju jiometirika kan ti o yika ipoidojuko rẹ pẹlu eeya jiometirika kan. Fun apẹẹrẹ, S2 lati Google. Nọmba naa yẹ ki o ṣee ṣe lati ṣe aṣoju ni irisi awọn laini intersecting mẹta tabi diẹ sii ti o le jẹ nọmba. Ni ọna yii a le yi geoquery wa sinu ọpọlọpọ awọn ibeere “lẹgbẹẹ aafo” (pẹlu awọn laini nọmba wọnyi).
Awọn solusan ti o ṣetan
Mo nireti pe Mo nifẹ rẹ diẹ ati pe o ni ohun elo miiran ti o wulo ninu ohun ija rẹ. Ti o ba nilo lati ṣe iru nkan bayi, iwọ yoo mọ ọna wo lati wo.
Sibẹsibẹ, kii ṣe gbogbo eniyan ni akoko, sũru, tabi awọn orisun lati ṣẹda awọn atọka bitmap lati ibere. Paapa awọn to ti ni ilọsiwaju diẹ sii, lilo SIMD, fun apẹẹrẹ.
Ni Oriire, ọpọlọpọ awọn solusan ti a ti ṣetan wa lati ṣe iranlọwọ fun ọ.
ramuramu bitmaps
Ni akọkọ, ile-ikawe bitmaps ramuramu kanna wa ti Mo ti sọrọ tẹlẹ. O ni gbogbo awọn apoti pataki ati awọn iṣẹ-ṣiṣe bit ti iwọ yoo nilo lati ṣe atọka bitmap kikun-kikun.
Laanu, ni akoko yii, ko si ọkan ninu awọn imuse Go ti o lo SIMD, eyi ti o tumọ si pe awọn imuse Go ko kere ju awọn imuse C, fun apẹẹrẹ.
Pilosa
Ọja miiran ti o le ṣe iranlọwọ fun ọ ni Pilosa DBMS, eyiti, ni otitọ, nikan ni awọn atọka bitmap. Eleyi jẹ a jo titun ojutu, sugbon o ti wa ni gba ọkàn ni nla iyara.
Pilosa nlo awọn bitmaps ramuramu ninu inu ati fun ọ ni agbara lati lo wọn, jẹ ki o rọrun ati ṣalaye gbogbo awọn nkan ti Mo ti sọrọ nipa loke: ṣiṣe akojọpọ, awọn maapu ti a fi koodu si ibiti, imọran aaye kan, ati bẹbẹ lọ.
Jẹ ki a yara wo apẹẹrẹ ti lilo Pilosa lati dahun ibeere ti o ti mọ tẹlẹ.
Àpẹẹrẹ náà jọra gan-an sí ohun tó o rí tẹ́lẹ̀. A ṣẹda alabara kan si olupin Pilosa, ṣẹda atọka ati awọn aaye pataki, lẹhinna fọwọsi awọn aaye wa pẹlu data laileto pẹlu awọn iṣeeṣe ati, nikẹhin, ṣiṣẹ ibeere ti o faramọ.
Lẹhin iyẹn, a ko lo NOT lori aaye “gbowolori”, lẹhinna ṣoki abajade (tabi ATI rẹ) pẹlu aaye “filati” ati pẹlu aaye “awọn ifiṣura”. Ati nikẹhin, a gba abajade ikẹhin.
Mo nireti gaan pe ni ọjọ iwaju ti a ti rii tẹlẹ iru atọka tuntun yii yoo tun han ni awọn DBMS bi MySQL ati PostgreSQL - awọn atọka bitmap .
ipari
Ti o ko ba ti sun sibẹsibẹ, o ṣeun. Mo ni lati fi ọwọ kan ni ṣoki lori ọpọlọpọ awọn akọle nitori akoko to lopin, ṣugbọn Mo nireti pe ọrọ naa wulo ati boya paapaa iwuri.
Awọn atọka Bitmap dara lati mọ nipa, paapaa ti o ko ba nilo wọn ni bayi. Jẹ ki wọn jẹ ọpa miiran ninu apoti irinṣẹ rẹ.
A ti wo ọpọlọpọ awọn ẹtan iṣẹ ṣiṣe fun Go ati awọn nkan ti Go kojọpọ ko mu daradara daradara sibẹsibẹ. Ṣugbọn eyi wulo pupọ fun gbogbo olutọpa Go lati mọ.
Iyẹn ni gbogbo ohun ti Mo fẹ sọ fun ọ. E dupe!
orisun: www.habr.com