utangulizi
Nilitoa ripoti hii kwa Kiingereza katika mkutano wa GopherCon Russia 2019 huko Moscow na kwa Kirusi kwenye mkutano huko Nizhny Novgorod. Tunazungumzia index ya bitmap - chini ya kawaida kuliko B-mti, lakini si chini ya kuvutia. Kugawana hotuba katika mkutano kwa Kiingereza na nakala za maandishi kwa Kirusi.
Tutaangalia jinsi index ya bitmap inavyofanya kazi, wakati ni bora, wakati ni mbaya zaidi kuliko indexes nyingine, na katika hali gani ni kwa kasi zaidi kuliko wao; Wacha tuone ni DBMS zipi maarufu ambazo tayari zina faharisi za bitmap; Hebu tujaribu kuandika yetu katika Go. Na "kwa dessert" tutatumia maktaba zilizotengenezwa tayari kuunda hifadhidata yetu maalum ya haraka sana.
Ninatumai sana kuwa kazi zangu zitakuwa muhimu na za kupendeza kwako. Nenda!
Utangulizi
Salaam wote! Ni saa sita jioni na sote tumechoka sana. Wakati mzuri wa kuzungumza juu ya nadharia ya kuchosha ya hifadhidata, sivyo? Usijali, nitakuwa na mistari michache ya msimbo wa chanzo hapa na pale. π
Ucheshi wote kando, ripoti imejaa habari, na hatuna muda mwingi. Basi hebu tuanze.
Leo nitazungumzia yafuatayo:
- indexes ni nini;
- ni nini index ya bitmap;
- inatumika wapi na haitumiki na kwa nini;
- utekelezaji rahisi katika Go na mapambano kidogo na mkusanyaji;
- kidogo rahisi, lakini utekelezaji wenye tija zaidi katika Go assembler;
- "matatizo" ya faharisi za bitmap;
- utekelezaji uliopo.
Kwa hivyo indexes ni nini?
Faharasa ni muundo tofauti wa data ambao tunadumisha na kusasisha pamoja na data kuu. Inatumika kuharakisha utafutaji. Bila faharisi, kutafuta kutahitaji kupitia data kabisa (mchakato unaoitwa tambazo kamili), na mchakato huu una utata wa algoriti. Lakini hifadhidata kawaida huwa na idadi kubwa ya data na ugumu wa mstari ni polepole sana. Kwa kweli, tungepata logarithmic au ya kudumu.
Hii ni mada ngumu sana, iliyojaa hila na biashara, lakini baada ya kuangalia miongo kadhaa ya ukuzaji wa hifadhidata na utafiti, niko tayari kusema kwamba kuna njia chache tu zinazotumiwa sana kuunda faharisi za hifadhidata.
Njia ya kwanza ni kupunguza kihierarkia nafasi ya utaftaji, kugawanya nafasi ya utaftaji katika sehemu ndogo.
Kawaida tunafanya hivi kwa kutumia aina tofauti za miti. Mfano unaweza kuwa sanduku kubwa la nyenzo kwenye kabati lako ambalo lina visanduku vidogo vya nyenzo vilivyogawanywa katika mada tofauti. Ikiwa unahitaji nyenzo, huenda utazitafuta katika kisanduku kinachosema "Nyenzo" badala ya ile inayosema "Vidakuzi," sivyo?
Njia ya pili ni kuchagua mara moja kipengele kinachohitajika au kikundi cha vipengele. Tunafanya hivi katika ramani za hashi au faharasa za nyuma. Kutumia ramani za hashi ni sawa na mfano uliopita, lakini badala ya sanduku la masanduku, una rundo la masanduku madogo ya vitu vya mwisho kwenye kabati lako.
Njia ya tatu ni kuondoa hitaji la kutafuta. Tunafanya hivyo kwa kutumia vichungi vya Bloom au vichungi vya cuckoo. Wa kwanza hutoa jibu mara moja, kukuokoa kutokana na kutafuta.
Njia ya mwisho ni kutumia kikamilifu nguvu zote ambazo vifaa vya kisasa vinatupa. Hivi ndivyo tunavyofanya katika faharisi za bitmap. Ndio, tunapozitumia wakati mwingine tunahitaji kupitia fahirisi nzima, lakini tunaifanya kwa ufanisi mkubwa.
Kama nilivyosema, mada ya faharisi za hifadhidata ni kubwa na imejaa maelewano. Hii ina maana kwamba wakati mwingine tunaweza kutumia mbinu kadhaa kwa wakati mmoja: ikiwa tunahitaji kuharakisha utafutaji hata zaidi, au ikiwa tunahitaji kufunika aina zote za utafutaji zinazowezekana.
Leo nitazungumza juu ya njia isiyojulikana zaidi ya hizi - faharisi za bitmap.
Mimi ni nani wa kuzungumza juu ya mada hii?
Ninafanya kazi kama kiongozi wa timu katika Badoo (labda unaifahamu zaidi bidhaa yetu nyingine, Bumble). Tayari tuna zaidi ya watumiaji milioni 400 duniani kote na vipengele vingi vinavyowachagua vinavyowafaa zaidi. Tunafanya hivyo kwa kutumia huduma maalum, ikiwa ni pamoja na faharasa za bitmap.
Kwa hivyo index ya bitmap ni nini?
Faharisi za Bitmap, kama jina linavyopendekeza, tumia bitmaps au bitsets kutekeleza faharisi ya utaftaji. Kwa mwonekano wa jicho la ndege, faharasa hii inajumuisha ramani-biti moja au zaidi zinazowakilisha huluki zozote (kama vile watu) na sifa au vigezo vyao (umri, rangi ya macho, n.k.), na algoriti inayotumia utendakazi kidogo (NA, AU, SIO. ) kujibu swali la utafutaji.
Tunaambiwa kwamba faharasa za bitmap zinafaa zaidi na hufanya kazi vizuri katika hali ambapo kuna utafutaji unaochanganya hoja kwenye safu wima nyingi za chini kabisa (fikiria "rangi ya macho" au "hali ya ndoa" dhidi ya kitu kama "umbali kutoka katikati mwa jiji" ). Lakini nitaonyesha baadaye kuwa zinafanya kazi vizuri kwa safu wima za ukadinali wa hali ya juu pia.
Wacha tuangalie mfano rahisi zaidi wa faharisi ya bitmap.
Hebu fikiria kuwa tuna orodha ya migahawa ya Moscow yenye sifa kama hizi:
- karibu na metro;
- kuna maegesho ya kibinafsi;
- kuna veranda (ina mtaro);
- unaweza kuhifadhi meza (inakubali kutoridhishwa);
- yanafaa kwa walaji mboga (vegan friendly);
- ghali (ghali).
Hebu tupe kila mgahawa nambari ya mlolongo kuanzia 0 na tutenge kumbukumbu kwa bitmaps 6 (moja kwa kila sifa). Kisha tutajaza ramani hizi ndogo kulingana na ikiwa mkahawa una mali hii au la. Ikiwa mgahawa 4 una veranda, basi kidogo No 4 katika "ina veranda" bitmap itawekwa 1 (ikiwa hakuna veranda, basi kwa 0).
Sasa tunayo faharisi rahisi zaidi ya bitmap, na tunaweza kuitumia kujibu maswali kama:
- "Nionyeshe mikahawa isiyofaa kwa mboga";
- "Nionyeshe mikahawa ya bei nafuu iliyo na veranda ambapo unaweza kuhifadhi meza."
Vipi? Hebu tuangalie. Ombi la kwanza ni rahisi sana. Tunachohitaji kufanya ni kuchukua ramani ndogo ya "urafiki wa mboga" na kuigeuza kuwa orodha ya mikahawa ambayo biti zake ziko wazi.
Ombi la pili ni gumu zaidi. Tunahitaji kutumia NOT bitmap kwenye bitmap "ya gharama kubwa" ili kupata orodha ya migahawa ya bei nafuu, kisha NA kwa bitmap ya "naweza kuweka nafasi ya meza" na NA matokeo na "kuna veranda" bitmap. Bitmap inayotokana itakuwa na orodha ya mashirika ambayo yanakidhi vigezo vyetu vyote. Katika mfano huu, hii ni mgahawa wa Yunost pekee.
Kuna nadharia nyingi zinazohusika, lakini usijali, tutaona msimbo hivi karibuni.
Faharisi za bitmap zinatumika wapi?
Ukiweka alama kwenye Google bitmap, 90% ya majibu yatahusiana na Oracle DB kwa njia moja au nyingine. Lakini DBMS zingine labda pia zinaunga mkono kitu kizuri kama hicho, sivyo? Si kweli.
Wacha tupitie orodha ya washukiwa wakuu.
MySQL bado haiungi mkono faharisi za bitmap, lakini kuna Pendekezo linalopendekeza kuongeza chaguo hili ().
PostgreSQL haitumii faharasa za bitmap, lakini hutumia bitmaps rahisi na uendeshaji biti ili kuchanganya matokeo ya utafutaji kwenye faharasa nyingine nyingi.
Tarantool ina faharisi za bitset na inasaidia utafutaji rahisi juu yao.
Redis ina bitfields rahisi) bila uwezo wa kuzitafuta.
MongoDB bado haitumii faharasa za bitmap, lakini pia kuna Pendekezo linalopendekeza chaguo hili liongezwe.
Elasticsearch hutumia bitmaps ndani).
- Lakini jirani mpya ametokea katika nyumba yetu: Pilosa. Hii ni hifadhidata mpya isiyo ya uhusiano iliyoandikwa katika Go. Ina faharisi za bitmap tu na huweka kila kitu juu yao. Tutazungumza juu yake baadaye kidogo.
Utekelezaji katika Go
Lakini kwa nini faharisi za bitmap hazitumiwi sana? Kabla ya kujibu swali hili, ningependa kukuonyesha jinsi ya kutekeleza faharisi rahisi sana ya bitmap katika Go.
Bitmaps kimsingi ni vipande vya data. Katika Go, wacha tutumie vipande vya baiti kwa hili.
Tunayo ramani moja ya alama za mkahawa mmoja, na kila sehemu kwenye bitmap inaonyesha kama mkahawa fulani una mali hii au la.
Tutahitaji kazi mbili za msaidizi. Moja itatumika kujaza bitmaps zetu na data nasibu. Nasibu, lakini kwa uwezekano fulani kwamba mgahawa una kila mali. Kwa mfano, ninaamini kuwa kuna migahawa machache sana huko Moscow ambapo huwezi kuhifadhi meza, na inaonekana kwangu kuwa karibu 20% ya vituo vinafaa kwa mboga.
Chaguo la pili litabadilisha bitmap kuwa orodha ya mikahawa.
Ili kujibu swali "Nionyeshe migahawa ya bei nafuu ambayo ina patio na inaweza kuweka nafasi," tunahitaji uendeshaji wa biti mbili: SIO na NA.
Tunaweza kurahisisha msimbo wetu kidogo kwa kutumia opereta changamano zaidi NA SIO.
Tuna utendakazi kwa kila moja ya shughuli hizi. Wote wawili hupitia vipande, kuchukua vipengele vinavyolingana kutoka kwa kila mmoja, kuchanganya na operesheni kidogo na kuweka matokeo kwenye kipande kilichosababisha.
Na sasa tunaweza kutumia bitmaps zetu na vitendaji kujibu swali la utafutaji.
Utendaji sio wa juu kiasi hicho, ingawa utendakazi ni rahisi sana na tuliokoa pesa nyingi kwa kutorudisha kipande kipya kila mara chaguo la kukokotoa lilipoitwa.
Baada ya kufanya maelezo mafupi kidogo na pprof, niligundua kuwa mkusanyaji wa Go alikuwa anakosa uboreshaji mmoja rahisi sana lakini muhimu sana: ujumuishaji wa kazi.
Ukweli ni kwamba kikusanyaji cha Go kinaogopa sana vitanzi vinavyopitia vipande, na kinakataa kabisa kuweka vitendaji vya ndani ambavyo vina vitanzi kama hivyo.
Lakini siogopi na ninaweza kudanganya mkusanyaji kwa kutumia goto badala ya kitanzi, kama katika siku nzuri za zamani.
Na, kama unaweza kuona, sasa mkusanyaji ataweka kazi yetu kwa furaha! Kama matokeo, tunaweza kuokoa takriban 2 microseconds. Sio mbaya!
Kizuizi cha pili ni rahisi kuona ikiwa unatazama kwa karibu pato la mkutano. Mkusanyaji aliongeza ukaguzi wa mpaka wa kipande ndani ya kitanzi chetu moto zaidi. Ukweli ni kwamba Go ni lugha salama, mkusanyaji anaogopa kwamba hoja zangu tatu (vipande vitatu) ni vya ukubwa tofauti. Baada ya yote, basi kutakuwa na uwezekano wa kinadharia wa tukio la kinachojulikana kufurika kwa buffer.
Wacha tumhakikishie mkusanyaji kwa kuionyesha kuwa vipande vyote vina ukubwa sawa. Tunaweza kufanya hivyo kwa kuongeza hundi rahisi mwanzoni mwa kazi yetu.
Kuona hili, mkusanyaji anaruka hundi kwa furaha, na tunaishia kuokoa nanoseconds nyingine 500.
Mabucha makubwa
Sawa, tulifanikiwa kubana baadhi ya utendaji kutoka kwa utekelezaji wetu rahisi, lakini matokeo haya ni mabaya zaidi kuliko inavyowezekana na maunzi ya sasa.
Tunachofanya ni utendakazi wa kimsingi, na vichakataji wetu huzitekeleza kwa ufanisi mkubwa. Lakini, kwa bahati mbaya, "tunalisha" processor yetu na vipande vidogo sana vya kazi. Vipengele vyetu hufanya shughuli kwa misingi ya byte-byte. Tunaweza kubadilisha msimbo wetu kwa urahisi kufanya kazi na vipande vya 8-byte kwa kutumia vipande vya UInt64.
Kama unavyoona, mabadiliko haya madogo yaliharakisha programu yetu mara nane kwa kuongeza ukubwa wa kundi kwa mara nane. Faida inaweza kusemwa kuwa ya mstari.
Utekelezaji katika mkusanyiko
Lakini huu sio mwisho. Wachakataji wetu wanaweza kufanya kazi na vipande vya baiti 16, 32 na hata 64. Operesheni kama hizo "mpana" huitwa data nyingi za maagizo moja (SIMD; maagizo moja, data nyingi), na mchakato wa kubadilisha msimbo ili utumie shughuli kama hizo unaitwa vectorization.
Kwa bahati mbaya, mkusanyaji wa Go ni mbali na bora katika uboreshaji. Hivi sasa, njia pekee ya kuweka msimbo wa Go ni kuchukua na kuweka shughuli hizi kwa mikono kwa kutumia Go assembler.
Go assembler ni mnyama wa ajabu. Labda unajua kuwa lugha ya kusanyiko ni kitu ambacho kinahusishwa sana na usanifu wa kompyuta unayoandikia, lakini sivyo ilivyo katika Go. Go assembler ni kama IRL (lugha ya uwakilishi wa kati) au lugha ya kati: kwa kweli inajitegemea. Rob Pike alitoa utendaji bora juu ya mada hii miaka kadhaa iliyopita huko GopherCon huko Denver.
Kwa kuongeza, Go hutumia muundo usio wa kawaida wa Mpango wa 9, ambao hutofautiana na muundo unaokubaliwa kwa ujumla wa AT&T na Intel.
Ni salama kusema kwamba kuandika Go assembler kwa mkono sio jambo la kufurahisha zaidi.
Lakini, kwa bahati nzuri, tayari kuna zana mbili za kiwango cha juu ambazo hutusaidia kuandika Go assembler: PeachPy na avo. Huduma zote mbili hutoa mkusanyiko wa Go kutoka kwa nambari ya kiwango cha juu iliyoandikwa katika Python na Go, mtawaliwa.
Huduma hizi hurahisisha mambo kama vile ugawaji wa rejista, kuandika vitanzi, na kwa ujumla kurahisisha mchakato wa kuingia katika ulimwengu wa upangaji programu katika Go.
Tutatumia avo, kwa hivyo programu zetu zitakuwa karibu programu za Go za kawaida.
Hivi ndivyo mfano rahisi zaidi wa programu ya avo unavyoonekana. Tunayo kazi kuu () ambayo inafafanua ndani yake kazi ya Add(), maana yake ni kuongeza nambari mbili. Kuna kazi za msaidizi hapa ili kupata vigezo kwa jina na kupata moja ya rejista za bure na zinazofaa za processor. Kila operesheni ya kichakataji ina kazi inayolingana kwenye avo, kama inavyoonekana katika ADDQ. Hatimaye, tunaona kazi ya msaidizi ya kuhifadhi thamani inayotokana.
Kwa kupiga simu go zalisha, tutafanya programu kwenye avo na matokeo yake, faili mbili zitatolewa:
- add.s na msimbo unaotokana katika Go assembler;
- stub.go na vichwa vya chaguo za kukokotoa ili kuunganisha ulimwengu mbili: Nenda na ukutanishe.
Sasa kwa kuwa tumeona kile avo hufanya na jinsi gani, hebu tuangalie kazi zetu. Nilitekeleza matoleo ya scalar na vector (SIMD) ya kazi.
Hebu tuangalie matoleo ya scalar kwanza.
Kama ilivyo katika mfano uliopita, tunaomba rejista ya madhumuni ya jumla isiyolipishwa na halali, hatuhitaji kukokotoa viwango na ukubwa wa hoja. avo anatufanyia haya yote.
Tulikuwa tukitumia lebo na goto (au kuruka) ili kuboresha utendaji na kuhadaa kikusanyaji cha Go, lakini sasa tunaifanya tangu mwanzo. Jambo ni kwamba mizunguko ni dhana ya kiwango cha juu. Katika mkusanyiko, tunayo lebo na kuruka tu.
Nambari iliyobaki inapaswa kuwa tayari kujulikana na kueleweka. Tunaiga kitanzi na maandiko na kuruka, kuchukua kipande kidogo cha data kutoka kwa vipande vyetu viwili, kuchanganya na operesheni kidogo (NA SI katika kesi hii) na kisha kuweka matokeo kwenye kipande kilichosababisha. Wote.
Hivi ndivyo msimbo wa mwisho wa mkusanyiko unaonekana. Hatukuhitaji kukokotoa viwango na saizi (zilizoangaziwa kwa kijani) au kufuatilia rejista zilizotumiwa (zilizoangaziwa kwa rangi nyekundu).
Ikiwa tunalinganisha utendaji wa utekelezaji wa lugha ya mkusanyiko na utendakazi wa utekelezaji bora katika Go, tutaona kuwa ni sawa. Na hii inatarajiwa. Baada ya yote, hatukufanya chochote maalum - tulitoa tu kile ambacho mkusanyaji wa Go angefanya.
Kwa bahati mbaya, hatuwezi kulazimisha mkusanyaji kuweka utendakazi wetu ulioandikwa kwa lugha ya mkusanyiko. Kikusanyaji cha Go kwa sasa hakina kipengele kama hicho, ingawa kumekuwa na ombi la kuiongeza kwa muda mrefu.
Ndio maana haiwezekani kupata faida yoyote kutoka kwa kazi ndogo katika lugha ya kusanyiko. Tunahitaji ama kuandika vitendaji vikubwa, au kutumia kifurushi kipya cha hesabu/biti, au kukwepa lugha ya kiunganishi.
Hebu sasa tuangalie matoleo ya vekta ya kazi zetu.
Kwa mfano huu, niliamua kutumia AVX2, kwa hiyo tutatumia shughuli zinazofanya kazi kwenye vipande vya 32-byte. Muundo wa kanuni ni sawa na toleo la scalar: vigezo vya kupakia, kuomba rejista ya bure ya pamoja, nk.
Ubunifu mmoja ni kwamba shughuli za vekta pana hutumia rejista maalum pana. Kwa upande wa vijisehemu vya baiti 32, hizi ni rejista zilizowekwa awali na Y. Hii ndiyo sababu unaona YMM() chaguo za kukokotoa kwenye msimbo. Ikiwa ningekuwa nikitumia AVX-512 na chunks 64-bit, kiambishi awali kingekuwa Z.
Ubunifu wa pili ni kwamba niliamua kutumia uboreshaji unaoitwa unrolling ya kitanzi, ambayo inamaanisha kufanya shughuli nane za kitanzi kwa mikono kabla ya kuruka hadi mwanzo wa kitanzi. Uboreshaji huu hupunguza idadi ya matawi katika msimbo, na hupunguzwa na idadi ya rejista za bure zinazopatikana.
Vipi kuhusu utendaji? Yeye ni mrembo! Tulipata kasi ya takriban mara saba ikilinganishwa na suluhisho bora zaidi la Go. Inavutia, sawa?
Lakini hata utekelezaji huu unaweza kuharakishwa kwa kutumia AVX-512, kuleta mapema au JIT (mkusanyaji wa wakati tu) kwa mpangilio wa hoja. Lakini hii hakika ni mada kwa ripoti tofauti.
Matatizo na faharisi za bitmap
Sasa kwa kuwa tayari tumeangalia utekelezaji rahisi wa faharasa ya bitmap katika Go na yenye tija zaidi katika lugha ya kusanyiko, wacha tuzungumze juu ya kwa nini faharisi za bitmap hazitumiwi sana.
Karatasi za zamani zinataja shida tatu na faharisi za bitmap, lakini karatasi mpya zaidi na ninabishana kuwa hazifai tena. Hatutazama kwa undani katika kila moja ya matatizo haya, lakini tutayaangalia juu juu.
Tatizo la high cardinality
Kwa hivyo, tunaambiwa kuwa faharisi za bitmap zinafaa tu kwa uwanja ulio na kardinali ya chini, ambayo ni, zile ambazo zina maadili machache (kwa mfano, jinsia au rangi ya macho), na sababu ni kwamba uwakilishi wa kawaida wa uwanja kama huo (moja). kidogo kwa thamani) katika kesi ya kardinali ya juu, itachukua nafasi nyingi sana na, zaidi ya hayo, faharisi hizi za bitmap zitajazwa vibaya (mara chache).
Wakati mwingine tunaweza kutumia uwakilishi tofauti, kama vile uwakilishi wa kawaida tunaotumia kuwakilisha nambari. Lakini ilikuwa ujio wa algorithms ya compression ambayo ilibadilisha kila kitu. Katika miongo kadhaa iliyopita, wanasayansi na watafiti wamekuja na idadi kubwa ya algorithms ya compression kwa bitmaps. Faida yao kuu ni kwamba hakuna haja ya kupunguza bitmaps kufanya shughuli kidogo - tunaweza kufanya shughuli kidogo moja kwa moja kwenye bitmaps zilizoshinikizwa.
Hivi majuzi, mbinu mseto zimeanza kuonekana, kama vile bitmaps zinazonguruma. Wakati huo huo hutumia uwakilishi tatu tofauti kwa bitmaps - bitmaps zenyewe, safu na kinachojulikana kama kukimbia kidogo - na usawa kati yao ili kuongeza utendakazi na kupunguza matumizi ya kumbukumbu.
Unaweza kupata bitmaps zinazonguruma katika programu maarufu zaidi. Tayari kuna idadi kubwa ya utekelezaji wa anuwai ya lugha za upangaji, ikijumuisha zaidi ya utekelezwaji tatu wa Go.
Njia nyingine ambayo inaweza kutusaidia kukabiliana na ukadinali wa hali ya juu inaitwa binning. Fikiria una uwanja unaowakilisha urefu wa mtu. Urefu ni nambari ya sehemu inayoelea, lakini sisi wanadamu hatufikirii hivyo. Kwa sisi hakuna tofauti kati ya urefu wa 185,2 cm na 185,3 cm.
Inabadilika kuwa tunaweza kuweka maadili sawa katika vikundi ndani ya 1 cm.
Na ikiwa pia tunajua kuwa watu wachache sana ni wafupi kuliko cm 50 na mrefu kuliko cm 250, basi tunaweza kugeuza shamba lenye kardinali isiyo na kikomo kuwa shamba lenye kardinali ya maadili 200 hivi.
Bila shaka, ikiwa ni lazima, tunaweza kufanya uchujaji wa ziada baadaye.
Tatizo la Kipimo cha Juu
Shida inayofuata na faharisi za bitmap ni kwamba kusasisha kunaweza kuwa ghali sana.
Hifadhidata lazima ziwe na uwezo wa kusasisha data wakati uwezekano wa mamia ya hoja nyingine wanatafuta data. Tunahitaji kufuli ili kuepuka matatizo ya ufikiaji wa data kwa wakati mmoja au matatizo mengine ya kushiriki. Na ambapo kuna kufuli moja kubwa, kuna shida - ugomvi wa kufuli, wakati kufuli hii inakuwa kizuizi.
Tatizo hili linaweza kutatuliwa au kuzungushwa kwa kutumia sharding au kutumia faharasa zilizotolewa.
Sharding ni jambo rahisi na linalojulikana sana. Unaweza kugawa faharisi ya bitmap kama ungefanya data nyingine yoyote. Badala ya kufuli moja kubwa, utapata rundo la kufuli ndogo na hivyo kujiondoa ugomvi wa kufuli.
Njia ya pili ya kutatua shida ni kutumia faharisi zilizotolewa. Unaweza kuwa na nakala moja ya faharasa unayotumia kutafuta au kusoma, na ile unayotumia kuandika au kusasisha. Na mara moja katika kipindi fulani cha muda (kwa mfano, mara moja kila 100 ms au 500 ms) unazirudia na kuzibadilisha. Bila shaka, mbinu hii inatumika tu katika hali ambapo programu yako inaweza kushughulikia faharasa ya utafutaji iliyochelewa kidogo.
Mbinu hizi mbili zinaweza kutumika kwa wakati mmoja: unaweza kuwa na faharasa iliyogawanywa.
Maswali changamano zaidi
Shida ya mwisho ya faharasa za bitmap ni kwamba tunaambiwa hazifai kwa aina ngumu zaidi za maswali, kama vile maswali ya muda.
Hakika, ukifikiria juu yake, utendakazi kidogo kama NA, AU, n.k. haufai sana kwa maswali kama "Nionyeshe hoteli zilizo na viwango vya vyumba kutoka dola 200 hadi 300 kwa usiku."
Suluhisho la ujinga na lisilo la busara litakuwa kuchukua matokeo kwa kila thamani ya dola na kuyachanganya na operesheni ya busara AU.
Suluhisho bora zaidi itakuwa kutumia kuweka vikundi. Kwa mfano, katika vikundi vya dola 50. Hii ingeharakisha mchakato wetu kwa mara 50.
Lakini tatizo pia linatatuliwa kwa urahisi kwa kutumia mtazamo ulioundwa mahsusi kwa aina hii ya ombi. Katika karatasi za kisayansi inaitwa mbalimbali-encoded bitmaps.
Katika uwakilishi huu, hatuweka tu kidogo moja kwa thamani fulani (kwa mfano, 200), lakini kuweka thamani hii na kila kitu cha juu. 200 na zaidi. Sawa kwa 300: 300 na zaidi. Nakadhalika.
Kwa kutumia uwakilishi huu, tunaweza kujibu aina hii ya swali la utafutaji kwa kupitia faharasa mara mbili tu. Kwanza, tutapata orodha ya hoteli ambapo chumba kina gharama ya chini au $ 300, na kisha tutaondoa kutoka humo wale ambao gharama ya chumba ni chini au $ 199. Tayari.
Utashangaa, lakini hata jiografia zinawezekana kwa kutumia faharisi za bitmap. Ujanja ni kutumia uwakilishi wa kijiometri unaozunguka uratibu wako na takwimu ya kijiometri. Kwa mfano, S2 kutoka Google. Kielelezo lazima kiweze kuwakilisha kwa namna ya mistari mitatu au zaidi ya kuingiliana ambayo inaweza kuhesabiwa. Kwa njia hii tunaweza kugeuza jiografia yetu kuwa maswali kadhaa "kando ya pengo" (pamoja na mistari hii iliyohesabiwa).
Ufumbuzi tayari
Natumai nimekuvutia kidogo na sasa unayo zana nyingine muhimu kwenye safu yako ya ushambuliaji. Ikiwa utahitaji kufanya kitu kama hiki, utajua ni njia gani ya kuangalia.
Hata hivyo, si kila mtu ana wakati, subira, au nyenzo za kuunda faharasa za bitmap kutoka mwanzo. Hasa ya juu zaidi, kwa kutumia SIMD, kwa mfano.
Kwa bahati nzuri, kuna suluhisho kadhaa zilizotengenezwa tayari kukusaidia.
bitmaps zinazonguruma
Kwanza, kuna maktaba ile ile ya bitmaps inayonguruma ambayo tayari nimeizungumzia. Ina vyombo vyote muhimu na shughuli kidogo ambazo utahitaji kufanya index kamili ya bitmap.
Kwa bahati mbaya, kwa sasa, hakuna utekelezaji wowote wa Go unaotumia SIMD, ambayo ina maana kwamba utekelezaji wa Go hauna utendakazi mdogo kuliko utekelezwaji wa C, kwa mfano.
Pilosa
Bidhaa nyingine ambayo inaweza kukusaidia ni Pilosa DBMS, ambayo, kwa kweli, ina faharisi za bitmap tu. Hili ni suluhisho jipya, lakini linashinda mioyo kwa kasi kubwa.
Pilosa hutumia bitmaps zinazonguruma ndani na kukupa uwezo wa kuzitumia, hurahisisha na kuelezea mambo yote niliyozungumzia hapo juu: kuweka kambi, ramani zilizosimbwa kwa anuwai, dhana ya uwanja, nk.
Hebu tuangalie kwa haraka mfano wa kutumia Pilosa kujibu swali ambalo tayari unalifahamu.
Mfano huo ni sawa na ulivyoona hapo awali. Tunaunda mteja kwa seva ya Pilosa, tengeneza faharisi na sehemu zinazohitajika, kisha ujaze sehemu zetu na data isiyo ya kawaida na uwezekano na, mwishowe, kutekeleza swali linalojulikana.
Baada ya hapo, hatutumii NOT kwenye uwanja wa "ghali", kisha unganisha matokeo (au NA) na uwanja wa "mtaro" na uga wa "kuhifadhi". Na hatimaye, tunapata matokeo ya mwisho.
Ninatumai sana kwamba katika siku zijazo zinazoonekana aina hii mpya ya faharisi pia itaonekana katika DBMS kama MySQL na PostgreSQL - faharisi za bitmap.
Hitimisho
Ikiwa bado haujalala, asante. Ilinibidi kugusa kwa ufupi mada nyingi kwa sababu ya muda mdogo, lakini natumai mazungumzo yalikuwa muhimu na labda hata ya kutia moyo.
Faharisi za Bitmap ni vyema kujua kuhusu, hata kama huzihitaji hivi sasa. Wacha ziwe zana nyingine kwenye kisanduku chako cha zana.
Tumeangalia mbinu mbalimbali za utendakazi za Go na mambo ambayo kikusanyaji cha Go bado hakishughulikii vyema. Lakini hii ni muhimu kabisa kwa kila programu ya Go kujua.
Hiyo ndiyo yote nilitaka kukuambia. Asante!
Chanzo: mapenzi.com