pêşkêş
Min ev rapor bi Îngilîzî li konferansa GopherCon Russia 2019 li Moskowê û bi rûsî di civînek li Nizhny Novgorod de da. Em li ser navnîşek bitmap-ê dipeyivin - ji B-dara kêmtir hevpar, lê ne kêmtir balkêş. Parvekirin axaftinên di konferansê de bi Îngilîzî û transkriptên nivîsê bi rûsî.
Em ê binihêrin ka indexek bitmap çawa dixebite, kengê çêtir e, kengê ji indexên din xirabtir e, û di kîjan rewşan de ew ji wan bi girîngî zûtir e; Ka em bibînin ka kîjan DBMS-yên populer berê xwedan navnîşên bitmap hene; Werin em hewl bidin ku ya xwe di Go de binivîsin. Û "ji bo şîrîn" em ê pirtûkxaneyên amade bikar bînin da ku databasa xweya pisporî ya super-lez biafirînin.
Ez bi rastî hêvî dikim ku xebatên min ji bo we kêrhatî û balkêş bin. Ajotin!
Pîrozbahiyê
Silav hemû! Saet şeşê êvarê ye û em hemî pir westiyane. Demek girîng e ku meriv li ser teoriya navnîşa databasa bêzar biaxive, rast? Xem neke, ez ê çend rêzikên koda çavkaniyê li vir û wir hebin. 🙂
Hemî henek li hêlekê, rapor bi agahdarî tije ye, û wextê me zêde tune. Ji ber vê yekê em dest pê bikin.
Îro ez ê li ser van tiştan biaxivim:
- index çi ne;
- index bitmap çi ye;
- li ku derê tê bikaranîn û li ku nayê bikaranîn û çima;
- pêkanîna hêsan di Go de û têkoşînek piçûk bi berhevkerê re;
- di Go assembler de pêkanîna hinekî kêmtir hêsan, lê pir hilbertir;
- "Pirsgirêkên" indexes bitmap;
- pêkanînên heyî.
Ji ber vê yekê index çi ne?
Indeks avahiyek daneya cihê ye ku em ji bilî daneyên sereke diparêzin û nûve dikin. Ew ji bo bilezkirina lêgerînê tê bikar anîn. Bê indexan, lêgerîn dê hewce bike ku bi tevahî daneyan derbas bibe (pêvajoyek jê re skankirina tevahî tê gotin), û ev pêvajo xwedan tevliheviya algorîtmîkî ya xêz e. Lê databas bi gelemperî mîqdarên mezin dane hene û tevliheviya xêzikî pir hêdî ye. Bi îdeal, em ê yek logarîtmîkî an domdar bistînin.
Ev mijarek pir tevlihev e, bi hûrgulî û danûstendinan dagirtî ye, lê piştî ku bi dehsalan li pêşkeftin û lêkolîna databasê mêze kir, ez amade me ku bibêjim ku tenê çend nêzîkatiyên ku bi berfirehî têne bikar anîn hene ji bo afirandina navnîşên databasê.
Nêzîkatiya yekem ev e ku bi hiyerarşîk qada lêgerînê kêm bike, cîhê lêgerînê li beşên piçûktir dabeş bike.
Em bi gelemperî vê yekê bi karanîna celebên daran dikin. Nimûneyek dê qutiyek mezin a materyalan di dolaba we de be ku qutiyên piçûktir ên materyalan li ser mijarên cûda dabeşkirî vedihewîne. Ger hûn hewceyê materyalan bin, hûn ê belkî li wan di qutiyek ku dibêje "Materyal" li şûna ya ku dibêje "Cookies" li wan bigerin, rast?
Nêzîkatiya duyemîn ev e ku meriv tavilê element an koma hêmanan hilbijêrin. Em vê yekê di nexşeyên hash de an navnîşên berevajî de dikin. Bikaranîna nexşeyên haş pir dişibihe mînaka berê, lê li şûna qutiyek qutiyan, di dolaba we de komek qutiyên piçûk ên tiştên dawî hene.
Nêzîkatiya sêyemîn ji holê rakirina hewcedariya lêgerînê ye. Em vê yekê bi karanîna fîlterên Bloom an fîlterên cuckoo dikin. Yên yekem tavilê bersivek didin, we ji lêgerînê xilas dikin.
Nêzîkatiya paşîn ev e ku em hemî hêza ku hardware nûjen dide me bi tevahî bikar bînin. Ya ku em di navnîşên bitmap de dikin ev e. Erê, dema ku wan bikar tînin em carinan hewce ne ku tevahiya pêvekê derbas bikin, lê em wiya pir bi bandor dikin.
Wekî ku min got, mijara navnîşên databasê berfireh û tije lihevhatin e. Ev tê vê wateyê ku carinan em dikarin di heman demê de çend nêzîkatiyan bikar bînin: ger hewce be ku em lêgerînê hîn bêtir bilez bikin, an jî ger hewce be ku em hemî cûreyên lêgerînê yên gengaz veşêrin.
Îro ez ê li ser nêzîkatiya herî kêm naskirî ya van biaxivim - bitmap index.
Ez kî me ku li ser vê mijarê biaxivim?
Ez wekî pêşengek tîmê li Badoo dixebitim (dibe ku hûn bi hilbera meya din, Bumble re bêtir nas in). Jixwe zêdetirî 400 mîlyon bikarhênerên me li çaraliyê cîhanê hene û gelek taybetmendiyên me hene ku ji bo wan maça çêtirîn hilbijêrin. Em vê yekê bi karanîna karûbarên xwerû, tevî navnîşên bitmap, dikin.
Ji ber vê yekê navnîşek bitmap çi ye?
Indeksên Bitmap, wekî ku ji navê xwe diyar dike, bitmaps an bitsets bikar tînin ku navnîşek lêgerînê bicîh bikin. Ji dîtina çavê çûkan, ev index ji yek an çend bitmapên weha pêk tê ku her hebûnek (wek mirov) û taybetmendî an pîvanên wan (temen, rengê çav, hwd.) temsîl dikin, û algorîtmayek ku karên bit (Û, AN, NA) bikar tîne. ) ji bo pirsa lêgerînê bersiv bikin.
Ji me re tê gotin ku endeksên bitmap ji bo dozên ku lêgerên ku li ser gelek stûnên kardînalîteya nizm de lêpirsînan li hev dikin ("rengê çavan" an "rewşa zewacê" li hember tiştek wekî "dûrbûna ji navenda bajêr" bifikirin, çêtirîn guncan in û pir performans in. Lê ez ê paşê nîşan bidim ku ew ji bo stûnên kardînalîteya bilind jî baş dixebitin.
Werin em li mînaka herî hêsan a indexek bitmap binêrin.
Bifikirin ku me navnîşek xwaringehên Moskowê yên bi taybetmendiyên binary ên mîna van hene:
- nêzîkî metro;
- parkkirina taybet heye;
- eywanek heye (teras heye);
- hûn dikarin maseyek veqetînin (veqetandan qebûl dike);
- minasib ji bo vegetarians (vegan dostane);
- buha (biha).
Ka em ji her xwaringehekê re jimareyek rêzê bidin ku ji 0-yê dest pê dike û bîranînê ji bo 6 bitmaps (yek ji bo her taybetmendiyê) veqetînin. Dûv re em ê van bitmap-an li gorî ka xwaringeh xwediyê vê milkê ye an na tijî bikin. Ger restorana 4 verandayek hebe, wê hingê bitma 4 di bitmap "heye veranda" de dê bibe 1 (heke veranda tune be, wê hingê bibe 0).
Naha me navnîşa bitmapê ya herî hêsan heye, û em dikarin wê bikar bînin da ku bersivê bidin pirsên mîna:
- "Restoranên dostane yên vegetarian nîşanî min bidin";
- "Restoranên erzan ên bi verande nîşanî min bidin ku hûn dikarin maseyek veqetînin."
Çawa? Ka em lê binêrin. Daxwaza yekem pir hêsan e. Tişta ku divê em bikin ev e ku bitmap-a "hevalê zebzeyan" bigirin û wê bikin navnîşek xwaringehên ku bitkên wan têne eşkere kirin.
Daxwaza duyemîn hinekî tevlihevtir e. Pêdivî ye ku em bitmap-a NOT-ê li ser bitmap-a "biha" bikar bînin da ku navnîşek xwaringehên erzan bi dest bixin, dûv re Û ew bi bitmap-a "Ez dikarim maseyek veqetînim" û Û encamê bi bitmap-a "veranda heye". Bitmap-a encam dê navnîşek sazûmanan bigire ku hemî pîvanên me bicîh tîne. Di vê nimûneyê de, ev tenê xwaringeha Yunost e.
Gelek teorî tê de hene, lê xem neke, em ê kodê pir zû bibînin.
Indeksên bitmap li ku têne bikar anîn?
Ger hûn navnîşên bitmap-ê Google-ê bikin, dê% 90 ji bersivan bi rengekî an yekî din bi Oracle DB-ê ve girêdayî bin. Lê dibe ku DBMS-yên din jî piştgirî bidin tiştek wusa xweş, rast? Ne rast.
Werin em li lîsteya gumanbarên sereke bigerin.
MySQL hîna pêvekên bitmap piştgirî nake, lê Pêşniyarek heye ku vê vebijarkê lê zêde bike ().
PostgreSQL indexên bitmap-ê piştgirî nake, lê bitmapên hêsan û operasyonên bit-ê bikar tîne da ku encamên lêgerînê li gelek navnîşên din berhev bike.
Tarantool xwedan navnîşên bitset e û li ser wan lêgerînên hêsan piştgirî dike.
Redis bitfieldên hêsan hene) bê kapasîteya lêgerîna wan.
MongoDB hîna pêvekên bitmap piştgirî nake, lê di heman demê de Pêşniyarek jî heye ku pêşniyar dike ku ev vebijark were zêdekirin
Elasticsearch bitmaps di hundurê xwe de bikar tîne).
- Lê cîranek nû li mala me derketiye: Pilosa. Ev databasek nû ya ne-girêdayî ye ku di Go de hatî nivîsandin. Ew tenê navnîşên bitmap-ê vedihewîne û her tiştî li ser wan bingeh digire. Em ê hinekî paşê li ser biaxivin.
Pêkanîna li Go
Lê çima navnîşên bitmap pir kêm têne bikar anîn? Berî ku ez bersiva vê pirsê bidim, ez dixwazim nîşanî we bidim ka meriv çawa di Go de pêdekek bitmapek pir hêsan bicîh dike.
Bitmaps bi bingehîn tenê perçeyên daneyê ne. Di Go de, em ji bo vê yekê perçeyên byte bikar bînin.
Ji bo taybetmendiyek xwaringehekê yek bitmapek me heye, û her bitmap di bitmap-ê de destnîşan dike ka xwaringehek taybetî xwediyê vê milkê ye an na.
Em ê du fonksiyonên alîkar hewce ne. Yek dê were bikar anîn da ku bitmapên me bi daneyên rasthatî dagirtin. Tesadufî, lê bi îhtimalek diyarkirî ku xwaringeh her milk heye. Mînakî, ez bawer dikim ku li Moskowê pir hindik xwaringeh hene ku hûn nekarin maseyek veqetînin, û ji min re xuya dike ku ji% 20-ê saziyan ji bo vegetarians maqûl in.
Fonksiyona duyemîn dê bitmap-ê veguherîne navnîşek xwaringehan.
Ji bo bersivdana pirsa "Rojxaneyên erzan ên ku xwedan hewşek in û dikarin rezervan bikin nîşanî min bidin," ji me re du operasyonên bit lazim in: NE û Û.
Em dikarin bi karanîna operatora tevlihevtir Û NE koda xwe hinekî hêsan bikin.
Ji bo her yek ji van operasyonan fonksiyonên me hene. Her du jî di perçeyan re derbas dibin, hêmanên têkildar ji her yekê digirin, wan bi operasyonek bitûkê re tevdigerin û encamê di perçeya encam de dixin.
Û naha em dikarin bitmaps û fonksiyonên xwe bikar bînin da ku bersiva pirsa lêgerînê bidin.
Performansa ne ew qas bilind e, her çend fonksiyon pir hêsan in û me gelek drav xilas kir her gava ku fonksiyonê hate gazî kirin perçeyek encamek nû venegerand.
Piştî ku ez piçek profîlek bi pprof re kirim, min dît ku berhevkarê Go yek xweşbîniyek pir hêsan lê pir girîng winda dike: fonksiyona inlining.
Rastî ev e ku berhevkarê Go ji lûpên ku di perçeyan re derbas dibin bi tirsek ditirse, û bi kategorî fonksiyonên xêzkirî yên ku lûpên weha dihewîne red dike.
Lê ez natirsim û ez dikarim berhevkar bixapînim bi karanîna goto li şûna loopê, mîna rojên xweş ên berê.
Û, wekî ku hûn dikarin bibînin, naha berhevkar dê bi kêfxweşî fonksiyona me bike! Wekî encamek, em bi qasî 2 mîkrosaniyan xilas dikin. Xerab nîne!
Ger hûn ji nêz ve li hilberîna meclîsê mêze bikin, stûna duyemîn hêsan e ku meriv bibîne. Berhevkar kontrolek sînorê perçeyek rast di hundurê lûleya meya herî germ de zêde kir. Rastî ev e ku Go zimanek ewledar e, berhevkar ditirse ku sê argumanên min (sê perçe) ji mezinahiyên cihê ne. Beriya her tiştî, wê hingê dê îhtîmalek teorîkî ya ku jê re tê gotin zêdebûnek tampon hebe.
Werin em berhevkarê dilnizm bikin û jê re nîşan bidin ku hemî perçe heman mezinahî ne. Em dikarin vê yekê bi lê zêdekirina kontrolek hêsan di destpêka fonksiyona xwe de bikin.
Bi dîtina vê yekê, berhevkar bi kêfxweşî ji kontrolê derbas dibe, û em diqedin 500 nanosecondên din.
Kuçikên mezin
Baş e, me karî ku hin performansê ji pêkanîna xweya hêsan derxînin, lê ev encam bi rastî ji ya ku bi hardware ya heyî gengaz dibe pir xirabtir e.
Tiştê ku em dikin operasyonên bit-ê yên bingehîn in, û pêvajoyên me wan pir bi bandor pêk tînin. Lê, mixabin, em pêvajoya xwe bi karekî pir piçûk "xwar" dikin. Fonksiyonên me li ser bingeha byte-byte operasyonan pêk tînin. Em dikarin pir bi hêsanî koda xwe biguhezînin da ku bi perçeyên 8-byte bi karanîna perçeyên UInt64 bixebitin.
Wekî ku hûn dibînin, ev guheztina piçûk bernameya me bi heşt qat zêdekirina qebareya heviyê bi heşt qatan bileztir dike. Qezenc dikare were gotin ku xêzik e.
Pêkanîna di assembler
Lê ev ne dawî ye. Prosesorên me dikarin bi perçeyên 16, 32 û hetta 64 byte re bixebitin. Operasyonên weha "berfireh" jê re daneya pirjimar a yek fermanê (SIMD; yek rêwerz, gelek dane) tê gotin, û pêvajoya veguheztina kodê da ku ew karên weha bikar bîne jê re vektorîzasyon tê gotin.
Mixabin, berhevkarê Go di vektorîzasyonê de ji hêja dûr e. Heya nuha, yekane awayê vektorîzekirina koda Go ev e ku meriv van operasyonan bi destan bi karanîna Go assembler bigire û bixe.
Go assembler heywanek xerîb e. Dibe ku hûn dizanin ku zimanê meclîsê tiştek e ku bi mîmariya komputera ku hûn jê re dinivîsin ve girêdayî ye, lê di Go de ne wusa ye. Go assembler bêtir mîna IRL (zimanê nûnertiya navîn) an zimanek navîn e: ew bi pratîkî platformek serbixwe ye. Rob Pike performansek hêja da li ser vê mijarê çend sal berê li GopherCon li Denver.
Wekî din, Go formatek Plana 9-a neasayî bikar tîne, ku ji formatên AT&T û Intel bi gelemperî têne pejirandin cûda dibe.
Meriv dikare bêje ku nivîsandina Go assembler bi destan ne ya herî xweş e.
Lê, bextewar, jixwe du amûrên asta bilind hene ku ji me re dibe alîkar ku Go assembler binivîsin: PeachPy û avo. Her du karûbar komkerê Go ji koda asta bilind a ku bi rêzdarî bi Python û Go hatî nivîsandin diafirînin.
Van karûbar tiştên wekî veqetandina qeydkirinê, pêlên nivîsandinê, û bi gelemperî pêvajoya ketina cîhana bernameya kombûnê ya li Go hêsan dikin.
Em ê avo bikar bînin, ji ber vê yekê bernameyên me dê hema hema bernameyên Go bi rêkûpêk bin.
Ev e ku mînaka herî hêsan a bernameyek avo dixuye. Fonksiyona me ya sereke() heye, ku di nava xwe de fonksiyona Add() diyar dike, ku wateya wê lê zêdekirina du hejmaran e. Li vir fonksiyonên arîkar hene ku parametreyên bi navê xwe bistînin û yek ji qeydên pêvajoyek belaş û maqûl bistînin. Her operasyona pêvajoyê li ser avo fonksiyonek têkildar heye, wekî ku di ADDQ de tê dîtin. Di dawiyê de, em fonksiyonek arîkar ji bo hilanîna nirxa encam dibînin.
Bi gazîkirina go generate, em ê bernameyê li ser avo bicîh bikin û di encamê de dê du pel werin çêkirin:
- add.s bi kodê encam di Go assembler;
- stub.go bi sernavên fonksiyonê re ji bo girêdana du cîhanan: Biçe û komker.
Naha ku me dît ku avo çi dike û çawa dike, em li fonksiyonên xwe binêrin. Min guhertoyên fonksiyonan hem scalar û hem vektor (SIMD) bicîh kir.
Ka em pêşî li guhertoyên scalar binêrin.
Mîna ku di mînaka berê de, em ji bo qeydek armanca gelemperî ya belaş û derbasdar dipirsin, em ne hewce ne ku ji bo argumanan jihevdeng û mezinahiyê hesab bikin. avo van hemûyan ji bo me dike.
Me berê etîket û goto (an jî bazdan) bikar tanîn da ku performansê baştir bikin û berhevkarê Go bixapînin, lê naha em ji destpêkê ve wiya dikin. Mesele ev e ku çerx têgehek astek bilindtir e. Di assembler de, em tenê etîket û bazdan hene.
Divê koda mayî jixwe nas û têgihîştî be. Em pêlekek bi etîket û bazdan dişibînin, ji du perçeyên xwe perçeyek piçûk hildigirin, wan bi operasyonek bit (Û NE di vê rewşê de) berhev dikin û dûv re encamê di parça encam de datînin. Gişt.
Ya ku koda komkerê ya paşîn xuya dike ev e. Ne hewce bû ku em lihevhatin û mezinahîyan bihesibînin (bi kesk hatine ronî kirin) an qeydên hatine bikar anîn bişopînin (bi sor hatine destnîşan kirin).
Ger em performansa pêkanîna zimanê meclîsê bi performansa pêkanîna çêtirîn di Go de bidin ber hev, em ê bibînin ku ew yek e. Û ev tê hêvîkirin. Beriya her tiştî, me tiştek taybetî nekir - me tenê tiştê ku berhevkarek Go dê bike dubare kir.
Mixabin, em nikarin berhevkarê zorê bikin ku fonksiyonên me yên ku bi zimanê meclîsê hatine nivîsandin rêz bike. Berhevkarê Go naha xwedan taybetmendiyek wusa nîne, her çend demek pir daxwazek heye ku wê lê zêde bike.
Ji ber vê yekê ne gengaz e ku meriv di zimanê meclîsê de ji fonksiyonên piçûk sûd werbigire. Pêdivî ye ku em an fonksiyonên mezin binivîsin, an pakêta nû ya matematîkê/bitan bikar bînin, an jî zimanê assembler derbas bikin.
Ka em naha li guhertoyên vektorê yên fonksiyonên xwe binêrin.
Ji bo vê nimûneyê, min biryar da ku AVX2 bikar bînin, ji ber vê yekê em ê operasyonên ku li ser perçeyên 32-byte dixebitin bikar bînin. Struktura kodê pir dişibihe guhertoya skalar: barkirina pîvanan, daxwaza qeydek hevpar a belaş, hwd.
Yek nûbûn ev e ku operasyonên vektorê yên berfireh tomarên berfireh ên taybetî bikar tînin. Di doza perçeyên 32-byte de, ev qeydên bi pêşgira Y in. Ji ber vê yekê hûn fonksiyona YMM() di kodê de dibînin. Ger min AVX-512 bi perçeyên 64-bit bikar anîba, pêşgir dê Z be.
Nûbûniya duyemîn ev e ku min biryar da ku ez optimîzasyonek bi navê loop unrolling bikar bînim, ku tê vê wateyê ku berî ku ez biçim destpêka lûkê bi destan kirina heşt operasyonên lûkê bi destan bikim. Ev optîmîzekirin hejmara şaxên kodê kêm dike, û ji hêla hejmara tomarên belaş ên berdest ve sînorkirî ye.
Baş e, li ser performansa? Ew bedew e! Me li gorî çareseriya Go ya çêtirîn bi qasî heft carî lezek bi dest xist. Bi bandor, rast?
Lê tewra ev pêkanîn jî dibe ku bi karanîna AVX-512, pêşdibistanê an JIT (berhevkarek tenê-dem-demê) ji bo nexşerêya pirsê were bilez kirin. Lê bê guman ev mijarek ji bo raporek cuda ye.
Pirsgirêkên bi indexên bitmap
Naha ku me berê xwe da cîbicîkirina hêsan a pêvekek bitmap-ê ya li Go-yê û di zimanê meclîsê de pir hilberdartir, bila em di dawiyê de li ser biaxivin ka çima pêvekên bitmap pir kêm têne bikar anîn.
Kaxezên kevn sê pirsgirêkan bi indexên bitmap-ê re vedibêjin, lê kaxezên nûtir û ez nîqaş dikim ku ew êdî ne têkildar in. Em ê di her yek ji van pirsgirêkan de kûr neçin, lê bi rengekî rûkal li wan binêrin.
Pirsgirêka cardinality bilind
Ji ber vê yekê, ji me re tê gotin ku navnîşên bitmap tenê ji bo qadên bi kardinalîteya kêm, yanî yên ku kêm nirx hene (mînakî, zayend an rengê çav) minasib in, û sedem jî ev e ku temsîla asayî ya qadên weha (yek bit per nirxê) di rewşa kardinalîteya bilind de, ew ê pir cîh bigire û, ji bilî vê, ev indexên bitmap dê kêm (kêm caran) werin dagirtin.
Carinan dibe ku em nûnertiyek cûda bikar bînin, mîna ya standard ku em ji bo temsîlkirina hejmaran bikar tînin. Lê ew hatina algorîtmayên kompresyonê bû ku her tişt guherand. Di dehsalên borî de, zanyar û lêkolîner ji bo bitmaps hejmareke mezin ji algorîtmayên berhevkirinê peyda kirine. Feydeya wan a sereke ev e ku ne hewce ye ku bitmaps ji bo pêkanîna operasyonên bit-ê werin dakêşandin - em dikarin rasterast li ser bitmapsên pêçandî karên bit-ê bikin.
Di van demên dawî de, nêzîkatiyên hybrid dest pê kirine, wekî bitmapên rijandin. Ew di heman demê de ji bo bitmaps sê nûnertiyên cihêreng bikar tînin - bitmaps bixwe, array û bi navê bit runs - û di navbera wan de hevsengiyê dikin da ku performansê zêde bikin û xerckirina bîranînê kêm bikin.
Hûn dikarin di serîlêdanên herî populer de bitmapên rondik bibînin. Jixwe ji bo cûrbecûr zimanên bernamekirinê hejmareke mezin a pêkanînan hene, di nav de zêdetirî sê pêkanînên ji bo Go.
Nêzîktêdayînek din a ku dikare ji me re bibe alîkar ku bi kardînalîteya bilind re mijûl bibin binning tê gotin. Bifikirin ku we zeviyek heye ku bilindahiya kesek temsîl dike. Bilindahî jimareyek niqteya herikîn e, lê em mirov wisa nafikirin. Ji bo me ferq di navbera 185,2 cm û 185,3 cm de tune.
Derket holê ku em dikarin nirxên wekhev di nav 1 cm de kom bikin.
Û eger em jî bizanibin ku pir hindik kes ji 50 cm kintir û ji 250 cm dirêjtir in, wê demê em dikarin di bingeh de zeviyek bi qertafiya bêdawî veguherînin zeviyek ku bi qasî 200 nirxan kardîne.
Bê guman, ger hewce be, em dikarin paşê fîlterkirinek din jî bikin.
Pirsgirêka Bandwidth Bilind
Pirsgirêka din a bi indexên bitmap ev e ku nûvekirina wan dikare pir biha be.
Pêdivî ye ku databas karibin daneyan nûve bikin dema ku potansiyel bi sedan pirsên din li daneyê digerin. Pêdiviya me bi qefleyan heye da ku ji pirsgirêkên gihîştina daneya hevdem an pirsgirêkên din ên parvekirinê dûr nekevin. Û li ku derê yek kilîtek mezin hebe, pirsgirêkek heye - nakokiya kilît, gava ku ev kilît dibe kulmek.
Ev pirsgirêk dikare bi karanîna parvekirinê an jî bi karanîna indexên guhertoyî were çareser kirin an dorpêç kirin.
Şirandin tiştekî hêsan û naskirî ye. Hûn dikarin wekî ku hûn daneya din îndekek bitmap perçe bikin. Li şûna yek kilîtek mezin, hûn ê komek qefleyên piçûk bistînin û bi vî rengî ji nakokiya qeflê xilas bibin.
Awayê duyemîn ji bo çareserkirina pirsgirêkê ev e ku meriv navnîşên guhertoyî bikar bîne. Hûn dikarin yek kopiyek navnîşa ku hûn ji bo lêgerînê an xwendinê bikar tînin, û ya ku hûn ji bo nivîsandinê an nûvekirinê bikar tînin hebin. Û carekê di demeke diyarkirî de (mînak, her 100 ms an 500 ms carekê) hûn wan dubare dikin û wan diguhezînin. Bê guman, ev nêzîkatî tenê di rewşên ku serîlêdana we dikare navnîşek lêgerînê ya hindik dereng bigire de derbasdar e.
Van her du nêzîkatî dikarin bi hevdemî werin bikar anîn: hûn dikarin pêdekek guhertoya şikestî hebe.
Pirsên tevlihevtir
Pirsgirêka dawîn a bi indexên bitmap-ê ev e ku ji me re tê gotin ku ew ji bo cûreyên tevlihevtir ên lêpirsînan, wek pirsên span, ne baş in.
Bi rastî, heke hûn li ser bifikirin, operasyonên bit ên mîna AND, OR, hwd. ji bo pirsên a la ne pir guncan in "Otêlên bi rêjeyên jûreyê ji 200 heta 300 dolaran her şev nîşanî min bidin."
Çareseriyek neaqil û pir neaqilmend dê ev be ku meriv encaman ji bo her nirxê dolaran bigire û wan bi operasyonek OR ya bitwise re bike yek.
Çareserek hinekî çêtir dê karanîna komkirinê be. Mînakî, di komên 50 dolaran de. Ev ê pêvajoya me 50 qat lez bike.
Lê pirsgirêk di heman demê de bi karanîna nerînek ku bi taybetî ji bo vî rengî daxwaziyê hatî afirandin jî bi hêsanî çareser dibe. Di gotarên zanistî de jê re bitmaps-ancoded range-encoded tê gotin.
Di vê temsîlê de, em ne tenê bitekê ji bo hin nirxan (mînak, 200) destnîşan dikin, lê vê nirx û her tiştî bilindtir destnîşan dikin. 200 û jortir. Heman tişt ji bo 300: 300 û jor. Wate ya vê çîye.
Bi karanîna vê nûnertiyê, em dikarin bi vî rengî lêgerîna lêgerînê bersiv bidin ku tenê du caran pêvekê derbas dikin. Pêşî, em ê navnîşek otêlên ku lêçûna jûreyê kêmtir an 300 dolar tê de bistînin, û dûv re em ê yên ku lêçûna jûreyê kêmtir an 199 dolar e jê derxin. Amade.
Hûn ê şaş bimînin, lê tewra geoqueries jî bi karanîna pêvekên bitmap gengaz in. Xefet ev e ku hûn nûneriyek geometrîkî bikar bînin ku li dora hevrêziya we bi jimarek geometrîkî ve girêdayî ye. Mînakî, S2 ji Google. Pêdivî ye ku jimar di forma sê an bêtir rêzikên hevber ên ku dikarin bêne hejmartin de were temsîl kirin. Bi vî rengî em dikarin geoquery-ya xwe veguherînin çend pirsnameyên "li ser gapê" (li ser van rêzikên hejmarî).
Çareseriyên amade
Ez hêvî dikim ku min hinekî we eleqedar kir û naha di cebilxaneya we de amûrek din a kêrhatî heye. Ger hewce be ku hûn tiştek wusa bikin, hûn ê zanibin ku hûn li kîjan alî binêrin.
Lêbelê, ne her kes dem, bîhnfireh, an çavkaniyan heye ku ji nû ve navnîşên bitmap-ê biafirîne. Bi taybetî yên pêşkeftî, mînakî SIMD bikar tînin.
Xwezî, gelek çareseriyên amade hene ku ji we re bibin alîkar.
Bitmapên robar
Pêşîn, heman pirtûkxaneya bitmapsê ya ku min berê behs kiribû heye. Ew hemî konteyneran û operasyonên bit-ê yên pêwîst dihewîne ku hûn hewce ne ku pêvekek bitmap-a bêkêmasî biafirînin.
Mixabin, heya niha, yek ji pêkanînên Go SIMD-ê bikar nayîne, ku tê vê wateyê ku pêkanînên Go ji pêkanînên C-yê kêmtir performans in, mînakî.
Pilosa
Hilberek din a ku dikare ji we re bibe alîkar Pilosa DBMS e, ku di rastiyê de, tenê xwedan navnîşên bitmap e. Ev çareseriyek nisbeten nû ye, lê ew bi lezek mezin dilan qezenc dike.
Pilosa bitmapên bitmayên di hundurê xwe de bikar tîne û jêhatîbûnê dide we ku hûn wan bikar bînin, hemî tiştên ku min li jor behs kir hêsan dike û rave dike: komkirin, bitmapên kodkirî yên rêzê, têgeha zeviyek, hwd.
Werin em bi lez li mînakek bikar bînin Pilosa ji bo bersivdana pirsek ku hûn pê dizanin.
Nimûne pir dişibe ya ku we berê dîtiye. Em ji servera Pilosa re xerîdarek diafirînin, pêdekek û qadên pêwîst diafirînin, dûv re zeviyên xwe bi îhtîmalan bi daneyên rasthatî tijî dikin û, di dawiyê de, lêpirsîna naskirî pêk tînin.
Piştî wê, em NOT li ser qada "biha" bikar tînin, dûv re encamê (an Û wê) bi qada "terrace" û bi qada "veqetandî" re diqetînin. Û di dawiyê de, em encama dawîn bistînin.
Ez bi rastî hêvî dikim ku di pêşerojek pêş de ev celebek nû ya index dê di DBMS-ên mîna MySQL û PostgreSQL de jî xuya bibe - bitmap indexes.
encamê
Ger tu hê xew neketî, spas. Ez neçar bûm ku bi kurtî dest li ser gelek mijaran bikim ji ber dema kêm, lê ez hêvî dikim ku axaftin kêrhatî û belkî jî motîvasyon bû.
Indeksên Bitmap baş e ku meriv pê zanibe, tewra ku hûn niha hewce nebin. Bila ew bibin amûrek din di qutiya amûra we de.
Me ji bo Go û tiştên ku berhevkarê Go hîna jî pir baş bi dest naxe me li gelek hîleyên performansê nihêrî. Lê ev ji bo her bernamenûsê Go bê guman kêrhatî ye ku zanibe.
Tiştê ku min dixwest ji te re bibêjim ev bû. Sipas ji were!
Source: www.habr.com