{"id":33793,"date":"2019-10-31T21:54:42","date_gmt":"2019-10-31T18:54:42","guid":{"rendered":"https:\/\/prohoster.info\/blog\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti\/"},"modified":"2019-10-31T21:54:42","modified_gmt":"2019-10-31T18:54:42","slug":"bitmap-indeksy-v-go-poisk-na-dikoj-skorosti","status":"publish","type":"post","link":"https:\/\/prohoster.info\/sk\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti","title":{"rendered":"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/86ef928e6741022b2c0e5885a031408a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<\/p>\n<h2>\u00davodn\u00e9 slovo<\/h2>\n<p>\nTento refer\u00e1t som predniesol v angli\u010dtine na konferencii GopherCon Russia 2019 v Moskve a v ru\u0161tine na meetupe v Ni\u017enom Novgorode. Hovor\u00ed sa v \u0148om o bitmapovom indexe \u2014 menej roz\u0161\u00edrenom ako B-tree, ale rovnako zauj\u00edmavom. Zdie\u013eam <noindex><a rel=\"nofollow\" href=\"https:\/\/youtu.be\/WvlUH6MjUuI?list=PL3xVZC4USRNSO_kb2lh_J_no6C-KJ7Phg\">nahr\u00e1vku<\/a><\/noindex> prezent\u00e1cie na konferencii v angli\u010dtine a textov\u00fa transkripciu v ru\u0161tine.<\/p>\n<p>Presk\u00famame, ako funguje bitmapov\u00fd index, kedy je lep\u0161\u00ed, kedy hor\u0161\u00ed ako in\u00e9 indexy a v ktor\u00fdch pr\u00edpadoch je v\u00fdrazne r\u00fdchlej\u0161\u00ed ako oni; uvid\u00edme, v ktor\u00fdch popul\u00e1rnych DBMS u\u017e existuj\u00fa bitmapov\u00e9 indexy; pok\u00fasime sa nap\u00edsa\u0165 svoj na Go. A na \u201edezert\u201c vyu\u017eijeme existuj\u00face kni\u017enice na vytvorenie na\u0161ej superr\u00fdchlej \u0161pecializovanej datab\u00e1zy.<\/p>\n<p>Ve\u013emi d\u00fafam, \u017ee moje \u00fasilie bude pre v\u00e1s u\u017eito\u010dn\u00e9 a zauj\u00edmav\u00e9. Po\u010fme na to!<br \/>\n<noindex><a rel=\"nofollow\" name=\"habracut\"><\/a><\/noindex><\/p>\n<h2>\u00davod<\/h2>\n<p>\n<center><div class=\"youtube-placeholder\" data-id=\"WvlUH6MjUuI\" onclick=\"loadVideo(this)\">\r\n        <img decoding=\"async\" src=\"https:\/\/img.youtube.com\/vi\/WvlUH6MjUuI\/hqdefault.jpg\" alt=\"Prehrajte video\" loading=\"lazy\" width=\"480\" height=\"360\" style=\"width:100%;height:auto;\">\r\n        <div class=\"play-button\"><\/div>\r\n    <\/div><\/center><br \/>\n<noindex><a rel=\"nofollow\" href=\"http:\/\/bit.ly\/bitmapindexes\">http:\/\/bit.ly\/bitmapindexes<\/a><\/noindex><br \/>\n<noindex><a rel=\"nofollow\" href=\"https:\/\/github.com\/mkevac\/gopherconrussia2019\">https:\/\/github.com\/mkevac\/gopherconrussia2019<\/a><\/noindex><\/p>\n<p>Ahojte v\u0161etci! Teraz je \u0161es\u0165 hod\u00edn ve\u010der, v\u0161etci sme ve\u013emi unaven\u00ed. Skvel\u00fd \u010das na to, aby sme hovorili o nudnej te\u00f3rii indexov datab\u00e1z, \u010do poviete? Nebojte sa, tu a tam budem ma\u0165 p\u00e1r riadkov zdrojov\u00e9ho k\u00f3du. \ud83d\ude42<\/p>\n<p>Bez \u017eartov, t\u00e1to prezent\u00e1cia je preplnen\u00e1 inform\u00e1ciami a nem\u00e1me ve\u013ea \u010dasu. Tak\u017ee za\u010dnime.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/e778e13727700f0335a4b5558a0d8db3.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nDnes budem hovori\u0165 o nasledovnom:<\/p>\n<ul>\n<li>\u010do s\u00fa indexy;\n<\/li>\n<li>\u010do je bitmapov\u00fd index;\n<\/li>\n<li>kde sa pou\u017e\u00edva a kde sa NEMA pou\u017e\u00edva a pre\u010do;\n<\/li>\n<li>jednoduch\u00e1 implement\u00e1cia na Go a trochu boja s kompil\u00e1torom;\n<\/li>\n<li>o nie\u010do menej jednoduch\u00e1, ale ove\u013ea v\u00fdkonej\u0161ia implement\u00e1cia na Go assembleri;\n<\/li>\n<li>probl\u00e9my bitmapov\u00fdch indexov;\n<\/li>\n<li>existuj\u00face implement\u00e1cie.\n<\/li>\n<\/ul>\n<h2>\u010co s\u00fa teda indexy?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/b80e5b990c44814afe9150a9a82351fd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nIndex je samostatn\u00e1 \u0161trukt\u00fara \u00fadajov, ktor\u00fa uchov\u00e1vame a aktualizujeme ako doplnok k hlavn\u00fdm \u00fadajom. Pou\u017e\u00edva sa na zr\u00fdchlenie vyh\u013ead\u00e1vania. Bez indexov by vy\u017eadovalo vyh\u013ead\u00e1vanie \u00fapln\u00fd priechod \u00fadajmi (proces naz\u00fdvan\u00fd full scan) a tento proces m\u00e1 line\u00e1rnu algoritmick\u00fa zlo\u017eitost. Ale datab\u00e1zy obvykle obsahuj\u00fa obrovsk\u00e9 mno\u017estvo \u00fadajov a line\u00e1rna zlo\u017eitost je pr\u00edli\u0161 pomal\u00e1. Ide\u00e1lne by sme chceli dosiahnu\u0165 logaritmick\u00fa alebo kon\u0161tantn\u00fa.<\/p>\n<p>Toto je obrovsk\u00e9 zlo\u017eit\u00e1 t\u00e9ma, preplnen\u00e1 nuansami a kompromismi, ale po poh\u013eade na desiatky rokov v\u00fdvoja a v\u00fdskumu r\u00f4znych datab\u00e1z som pripraven\u00fd tvrdi\u0165, \u017ee existuje len nieko\u013eko \u0161iroko pou\u017e\u00edvan\u00fdch pr\u00edstupov k vytv\u00e1raniu indexov DB.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/08a74dbb365035cd99bc94d72644a1b7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nPrv\u00fd pr\u00edstup spo\u010d\u00edva v hierarchickom z\u00fa\u017een\u00ed vyh\u013ead\u00e1vacej oblasti, rozdelen\u00ed vyh\u013ead\u00e1vacej oblasti na men\u0161ie \u010dasti.<\/p>\n<p>Zvy\u010dajne to rob\u00edme pomocou r\u00f4znych typov stromov. Pr\u00edkladom m\u00f4\u017ee by\u0165 ve\u013ek\u00e1 krabica s materi\u00e1lmi vo va\u0161ej skrini, v ktorej sa nach\u00e1dzaj\u00fa men\u0161ie krabice s materi\u00e1lmi rozdelen\u00fdmi pod\u013ea r\u00f4znych t\u00e9m. Ak potrebujete materi\u00e1ly, ur\u010dite ich budete h\u013eada\u0165 v krabici s n\u00e1pisom \u201eMateri\u00e1ly\u201c, nie v tej, na ktorej je nap\u00edsan\u00e9 \u201eSu\u0161ienky\u201c, \u017ee?<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/423fac47c748980b18af434644af4dae.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nDruh\u00fd pr\u00edstup spo\u010d\u00edva v tom, \u017ee okam\u017eite vy\u010dlen\u00edme po\u017eadovan\u00fd prvok alebo skupinu prvkov. Rob\u00edme to v hash map\u00e1ch alebo v reverzn\u00fdch indexoch. Pou\u017eitie hash m\u00e1p je ve\u013emi podobn\u00e9 predch\u00e1dzaj\u00facemu pr\u00edkladu, len namiesto krabice s krabicami m\u00e1te vo svojej skrini hromadu mal\u00fdch krab\u00edc s kone\u010dn\u00fdmi predmetmi.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/088fed0a2a0feea4a23edbf0ca654805.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nTret\u00ed pr\u00edstup \u2014 zbavi\u0165 sa potreby vyh\u013ead\u00e1vania. To rob\u00edme pomocou Bloom filtrov alebo cuckoo filtrov. Prv\u00e9 okam\u017eite poskytn\u00fa odpove\u010f, \u010d\u00edm v\u00e1s zbavuj\u00fa potreby uskuto\u010d\u0148ova\u0165 vyh\u013ead\u00e1vanie.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/493bc4f20baacc0a5dc0faf15cc46285.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nPosledn\u00fd pr\u00edstup spo\u010d\u00edva v plnom vyu\u017eit\u00ed v\u0161etk\u00fdch v\u00fdkonov, ktor\u00e9 n\u00e1m modern\u00fd hardv\u00e9r poskytuje. Presne to rob\u00edme v bitmapov\u00fdch indexoch. \u00c1no, pri ich pou\u017eit\u00ed niekedy mus\u00edme prejs\u0165 cel\u00fdm indexom, ale rob\u00edme to super efekt\u00edvne.<\/p>\n<p>Ako som u\u017e povedal, t\u00e9ma datab\u00e1zov\u00fdch indexov je rozsiahla a pln\u00e1 kompromisov. To znamen\u00e1, \u017ee niekedy m\u00f4\u017eeme pou\u017ei\u0165 viacero pr\u00edstupov s\u00fa\u010dasne: ak potrebujeme e\u0161te viac ur\u00fdchli\u0165 vyh\u013ead\u00e1vanie alebo ak je potrebn\u00e9 pokry\u0165 v\u0161etky mo\u017en\u00e9 typy vyh\u013ead\u00e1vania.<\/p>\n<p>Dnes v\u00e1m poviem o najmenej zn\u00e1mych pr\u00edstupoch z uveden\u00fdch \u2014 o bitmapov\u00fdch indexoch.<\/p>\n<h2>Kto som, aby som hovoril o tejto t\u00e9me?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/42a9d17a507c392bc202254a92dfaf41.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nPracujem ako t\u00edmov\u00fd l\u00edder v Badoo (mo\u017eno pozn\u00e1te n\u00e1\u0161 in\u00fd produkt \u2014 Bumble). U\u017e m\u00e1me viac ako 400 mili\u00f3nov pou\u017e\u00edvate\u013eov po celom svete a mno\u017estvo funkci\u00ed, ktor\u00e9 sa zaoberaj\u00fa t\u00fdm, \u017ee pre nich vyh\u013ead\u00e1vaj\u00fa najlep\u0161ie p\u00e1ry. Rob\u00edme to pomocou vlastn\u00fdch slu\u017eieb, ktor\u00e9 pou\u017e\u00edvaj\u00fa aj bitmapov\u00e9 indexy.<\/p>\n<h2>\u010co je to teda bitmapov\u00fd index?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/14f20f3697a20c02f6b3510dc7f0ae4d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nBitmap indexy, ako nazna\u010duje n\u00e1zov, pou\u017e\u00edvaj\u00fa bitmapy alebo bitov\u00e9 s\u00fabory na implement\u00e1ciu vyh\u013ead\u00e1vacieho indexu. Z v\u00fd\u0161ky vt\u00e1\u010dej perspekt\u00edvy pozost\u00e1va tento index z jedn\u00e9ho alebo viacer\u00fdch tak\u00fdch bitmapov, ktor\u00e9 predstavuj\u00fa nejak\u00e9 entity (napr\u00edklad \u013eud\u00ed) a ich vlastnosti alebo parametre (vek, farba o\u010d\u00ed at\u010f.) a z algoritmu, ktor\u00fd pou\u017e\u00edva bitov\u00e9 oper\u00e1cie (AND, OR, NOT) na odpove\u010f na vyh\u013ead\u00e1vac\u00ed dopyt.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/f815720330a51b1f0798e45d23160d3b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nHovor\u00ed sa, \u017ee bitmap indexy s\u00fa najlep\u0161ie a ve\u013emi efekt\u00edvne pre pr\u00edpady, kde je vyh\u013ead\u00e1vanie kombinuj\u00face dopyty na viacer\u00fdch st\u013apcoch s n\u00edzkou kardinalitou (predstavte si \u201efarbu o\u010d\u00ed\u201c alebo \u201erodinn\u00fd stav\u201c v porovnan\u00ed s nie\u010d\u00edm ako \u201evzdialenos\u0165 od centra mesta\u201c). Ale nesk\u00f4r uk\u00e1\u017eem, \u017ee funguj\u00fa skvele aj v pr\u00edpade st\u013apcov s vysokou kardinalitou.<\/p>\n<p>Pozrime sa na najjednoduch\u0161\u00ed pr\u00edklad bitmap indexu.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/33fe23476e0931c10345d7175b83d68b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPredstavte si, \u017ee m\u00e1me zoznam moskovsk\u00fdch re\u0161taur\u00e1ci\u00ed s bin\u00e1rnymi vlastnos\u0165ami, ako s\u00fa tieto:<\/p>\n<ul>\n<li>bl\u00edzko metra (near metro);\n<\/li>\n<li>m\u00e1 s\u00fakromn\u00e9 parkovanie (has private parking);\n<\/li>\n<li>m\u00e1 terasu (has terrace);\n<\/li>\n<li>je mo\u017en\u00e9 rezervova\u0165 st\u00f4l (accepts reservations);\n<\/li>\n<li>je vhodn\u00e1 pre vegetari\u00e1nov (vegan friendly);\n<\/li>\n<li>drah\u00e1 (expensive).\n<\/li>\n<\/ul>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/fcbad539ea12f79a9d06966ce308637e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nDajte ka\u017ed\u00e9mu re\u0161taur\u00e1cii poradov\u00e9 \u010d\u00edslo od 0 a vyhra\u010fte pam\u00e4\u0165 pre 6 bitmapov (jeden pre ka\u017ed\u00fa vlastnos\u0165). Potom tieto bitmapy vypln\u00edme v z\u00e1vislosti od toho, \u010di m\u00e1 re\u0161taur\u00e1cia dan\u00fa vlastnos\u0165 alebo nie. Ak m\u00e1 re\u0161taur\u00e1cia \u010d. 4 terasu, bit \u010d. 4 v bitmape \u201em\u00e1 terasu\u201c bude nastaven\u00fd na 1 (ak terasa nie je, potom na 0).<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/3709c426617d4364f392ee6b68f92b00.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTeraz m\u00e1me najjednoduch\u0161\u00ed bitmap index, ak\u00fd si vieme predstavi\u0165, a m\u00f4\u017eeme ho pou\u017ei\u0165 na odpovedanie na dopyty ako:<\/p>\n<ul>\n<li>\u201eZobraz mi re\u0161taur\u00e1cie, ktor\u00e9 s\u00fa vhodn\u00e9 pre vegetari\u00e1nov\u201c;\n<\/li>\n<li>\u201eZobraz mi lacn\u00e9 re\u0161taur\u00e1cie s terasou, kde je mo\u017en\u00e9 rezervova\u0165 st\u00f4l.\u201c\n<\/li>\n<\/ul>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/90acb0f890686bd52c3db1fc667f0b0b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/0fd0b7fe9f7b7039022ad5c79fe873bc.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAko? Pozrime sa. Prv\u00fd dopyt je ve\u013emi jednoduch\u00fd. V\u0161etko, \u010do potrebujeme, je vzia\u0165 bitmapu \u201evhodn\u00e9 pre vegetari\u00e1nov\u201c a premeni\u0165 ju na zoznam re\u0161taur\u00e1ci\u00ed, ktor\u00fdch bity s\u00fa nastaven\u00e9.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/ef4a5cfd658ff4ef8bc0c638c4522d11.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/9cc175bae55c16018fdf5ff95517a61a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nDruh\u00e1 ot\u00e1zka je trochu zlo\u017eitej\u0161ia. Mus\u00edme pou\u017ei\u0165 bitov\u00fa oper\u00e1ciu NOT na bitmapu \"drah\u00fd\", aby sme z\u00edskali zoznam lacn\u00fdch re\u0161taur\u00e1ci\u00ed, potom to spoj\u00edme s bitmapou \"je mo\u017en\u00e9 rezervova\u0165 st\u00f4l\" a v\u00fdsledok spoj\u00edme s bitmapou \"m\u00e1 terasu\". V\u00fdsledn\u00e1 bitmapa bude obsahova\u0165 zoznam zariaden\u00ed, ktor\u00e9 sp\u013a\u0148aj\u00fa v\u0161etky na\u0161e krit\u00e9ri\u00e1. V tomto pr\u00edpade je to len re\u0161taur\u00e1cia \"Junost\".<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/f1cdda0cbf7f15278553899cf876c17e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/126b50e0f622b6e36c461cd74e708c38.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTu je ve\u013ea te\u00f3rie, ale nebojte sa, \u010doskoro uvid\u00edme k\u00f3d.<\/p>\n<h2>Kde sa pou\u017e\u00edvaj\u00fa bitmapov\u00e9 indexy?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/406132236c71a4f66ae79957b6e633b3.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAk \"googlite\" bitmapov\u00e9 indexy, 90 % odpoved\u00ed bude nejak\u00fdm sp\u00f4sobom spojen\u00fdch s Oracle DB. Ale ostatn\u00e9 DBMS tie\u017e ur\u010dite podporuj\u00fa tak\u00fato skvel\u00fa vec, v\u0161ak? Nie \u00faplne. <\/p>\n<p>Prejdime si zoznam hlavn\u00fdch podozriv\u00fdch.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/d18d66451a8a26b0ddf121f8ec0204cd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nMySQL e\u0161te nepodporuje bitmapov\u00e9 indexy, ale existuje n\u00e1vrh na pridanie tejto mo\u017enosti (<noindex><a rel=\"nofollow\" href=\"https:\/\/dev.mysql.com\/worklog\/task\/?id=1524\">https:\/\/dev.mysql.com\/worklog\/task\/?id=1524<\/a><\/noindex>).<\/p>\n<p>PostgreSQL nepodporuje bitmapov\u00e9 indexy, ale pou\u017e\u00edva jednoduch\u00e9 bitmapy a bitov\u00e9 oper\u00e1cie na kombinovanie v\u00fdsledkov vyh\u013ead\u00e1vania pod\u013ea nieko\u013ek\u00fdch in\u00fdch indexov.<\/p>\n<p>Tarantool m\u00e1 bitset indexy, podporuje jednoduch\u00e9 vyh\u013ead\u00e1vanie pod\u013ea nich.<\/p>\n<p>Redis m\u00e1 jednoduch\u00e9 bitov\u00e9 polia<noindex><a rel=\"nofollow\" href=\"https:\/\/redis.io\/commands\/bitfield\"> (https:\/\/redis.io\/commands\/bitfield<\/a><\/noindex>) bez mo\u017enosti vyh\u013ead\u00e1vania pod\u013ea nich.<\/p>\n<p>MongoDB e\u0161te nepodporuje bitmapov\u00e9 indexy, ale tie\u017e existuje n\u00e1vrh na pridanie tejto mo\u017enosti. <noindex><a rel=\"nofollow\" href=\"https:\/\/jira.mongodb.org\/browse\/SERVER-1723\">https:\/\/jira.mongodb.org\/browse\/SERVER-1723<\/a><\/noindex><\/p>\n<p>Elasticsearch pou\u017e\u00edva bitmapy vo vn\u00fatri.<noindex><a rel=\"nofollow\" href=\"https:\/\/www.elastic.co\/blog\/frame-of-reference-and-roaring-bitmaps\"> (https:\/\/www.elastic.co\/blog\/frame-of-reference-and-roaring-bitmaps<\/a><\/noindex>).<\/p>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/232d335963603d6e6dec98839fc9f486.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<\/p>\n<ul>\n<li>Ale v na\u0161om dome sa objavil nov\u00fd sused: Pilosa. Toto je nov\u00e1 nerela\u010dn\u00e1 datab\u00e1za nap\u00edsan\u00e1 v Go. Obsahuje len bitmapov\u00e9 indexy a v\u0161etko zaklad\u00e1 na nich. O nej si povieme nesk\u00f4r.\n<\/li>\n<\/ul>\n<h2>Implement\u00e1cia v Go.<\/h2>\n<p>\nAle pre\u010do s\u00fa bitmapov\u00e9 indexy tak zriedkavo pou\u017e\u00edvan\u00e9? Predt\u00fdm, ako odpoviem na t\u00fato ot\u00e1zku, by som v\u00e1m chcel uk\u00e1za\u0165 implement\u00e1ciu ve\u013emi jednoduch\u00e9ho bitmapov\u00e9ho indexu v Go.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/ae7f4c1a4a740fe709b05dfaee27ac9b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nBitmaps s\u00fa v podstate reprezentovan\u00e9 jednoducho ako kusy \u00fadajov. V Go na to vyu\u017eijeme pl\u00e1tky bajtov.<\/p>\n<p>M\u00e1me jednu bitmapu pre jednu re\u0161taura\u010dn\u00fa charakteristiku a ka\u017ed\u00fd bit v bitmape hovor\u00ed o tom, \u010di konkr\u00e9tna re\u0161taur\u00e1cia m\u00e1 t\u00fato vlastnos\u0165 alebo nie.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/1ab628ee15887d6b3c6c99855aa610c8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPotrebujeme dve pomocn\u00e9 funkcie. Jedna bude pou\u017eit\u00e1 na naplnenie na\u0161ich bitmapov n\u00e1hodn\u00fdmi \u00fadajmi. N\u00e1hodn\u00fdmi, ale s ur\u010dit\u00fdmi pravdepodobnos\u0165ami, \u017ee re\u0161taur\u00e1cia m\u00e1 ka\u017ed\u00fa vlastnos\u0165. Napr\u00edklad si mysl\u00edm, \u017ee v Moskve je ve\u013emi m\u00e1lo re\u0161taur\u00e1ci\u00ed, kde nie je mo\u017en\u00e9 rezervova\u0165 st\u00f4l, a zd\u00e1 sa mi, \u017ee pribli\u017ene 20 % podnikov je vhodn\u00fdch pre vegetari\u00e1nov.<\/p>\n<p>Druh\u00e1 funkcia prevedie bitmapu na zoznam re\u0161taur\u00e1ci\u00ed.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/ab9c87a0ba63750116e2e7968f842a9a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/498cf7a33611d99b90197d4ee82e2834.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAby sme mohli odpoveda\u0165 na dopyt \u201eZobraz mi lacn\u00e9 re\u0161taur\u00e1cie, ktor\u00e9 maj\u00fa terasu a kde si m\u00f4\u017eem rezervova\u0165 st\u00f4l\u201c, budeme potrebova\u0165 dve bitov\u00e9 oper\u00e1cie: NOT a AND.<\/p>\n<p>M\u00f4\u017eeme trochu zjednodu\u0161i\u0165 n\u00e1\u0161 k\u00f3d pou\u017eit\u00edm zlo\u017eitej\u0161ej oper\u00e1cie AND NOT.<\/p>\n<p>M\u00e1me funkcie pre ka\u017ed\u00fa z t\u00fdchto oper\u00e1ci\u00ed. Obidve prech\u00e1dzaj\u00fa rezmi, ber\u00fa zodpovedaj\u00face prvky z ka\u017ed\u00e9ho a kombinuj\u00fa ich bitovou oper\u00e1ciou a ukladaj\u00fa v\u00fdsledok do v\u00fdsledn\u00e9ho rezu.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/ec5652a34f0370dfb03df199f341f153.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nA teraz m\u00f4\u017eeme vyu\u017ei\u0165 na\u0161e bitmapy a funkcie na odpovedanie na vyh\u013ead\u00e1vac\u00ed dopyt.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/cf9500ccfe75995a6008191c16729689.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nV\u00fdkon nie je a\u017e tak\u00fd vysok\u00fd, aj ke\u010f funkcie s\u00fa ve\u013emi jednoduch\u00e9 a dos\u0165 sme u\u0161etrili na tom, \u017ee sme nevracali nov\u00fd v\u00fdsledn\u00fd rez pri ka\u017edom volan\u00ed funkcie.<\/p>\n<p>Po profilovan\u00ed s pprof som si v\u0161imol, \u017ee kompil\u00e1tor Go prehliadol jednu ve\u013emi jednoduch\u00fa, ale ve\u013emi d\u00f4le\u017eit\u00fa optimaliz\u00e1ciu: inlinovanie funkci\u00ed.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/9092f5ba3940d0a4f3fbfa90b364d716.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nIde o to, \u017ee kompil\u00e1tor Go sa hrozne boj\u00ed cyklov, ktor\u00e9 prech\u00e1dzaj\u00fa rezmi, a kategoricky odmieta inlinova\u0165 funkcie, ktor\u00e9 obsahuj\u00fa tak\u00e9 cykly.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/d1bddd62b61b367dd1f680f223fa0ce7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAle ja sa neboj\u00edm a m\u00f4\u017eem oklama\u0165 kompil\u00e1tor, pri\u010dom pou\u017eijem goto namiesto cyklu, ako v star\u00fdch dobr\u00fdch \u010dasoch.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/5b1c3cb26b923972686047910ecd1c31.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/1ca31d12dc90931b674c6a86a4ea23bd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nA, ako vid\u00edte, teraz kompil\u00e1tor s rados\u0165ou inlinuje na\u0161u funkciu! Nakoniec sa n\u00e1m podar\u00ed u\u0161etri\u0165 pribli\u017ene 2 mikrosekundy. Nie je to zl\u00e9!<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/bdd6735d16082573e600bffe2cdd5662.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nDruh\u00e9 \u00fazke miesto nie je \u0165a\u017ek\u00e9 vidie\u0165, ak sa pozriete na v\u00fdstup assemblera. Kompil\u00e1tor pridal kontrolu na hranice rezu priamo do n\u00e1\u0161ho najru\u0161nej\u0161ieho cyklu. Faktom je, \u017ee Go je bezpe\u010dn\u00fd jazyk, kompil\u00e1tor sa ob\u00e1va, \u017ee moje tri argumenty (tr\u00ed rez) maj\u00fa r\u00f4znu ve\u013ekos\u0165. Ve\u010f by mohla teoreticky vznikn\u00fa\u0165 takzvan\u00e1 chyba prete\u010denia vyrovn\u00e1vacej pam\u00e4te (buffer overflow).<\/p>\n<p>Upokojme kompil\u00e1tor uk\u00e1zan\u00edm, \u017ee v\u0161etky slice maj\u00fa rovnak\u00fa ve\u013ekos\u0165. M\u00f4\u017eeme to urobi\u0165 pridan\u00edm jednoduch\u00e9ho overenia na za\u010diatok na\u0161ej funkcie.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/59b4ce687a11dd653e9f12fc3130d89a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nVed\u00faci to, kompil\u00e1tor s rados\u0165ou prejde overen\u00edm, a my nakoniec u\u0161etr\u00edme \u010fal\u0161\u00edch 500 nanosek\u00fand.<\/p>\n<h2>Ve\u013ek\u00e9 batch-y<\/h2>\n<p>\nDobre, podarilo sa n\u00e1m vytla\u010di\u0165 nejak\u00fd v\u00fdkon z na\u0161ej jednoduchej implement\u00e1cie, ale tento v\u00fdsledok je v skuto\u010dnosti ove\u013ea hor\u0161\u00ed, ne\u017e je mo\u017en\u00e9 s aktu\u00e1lnym hardv\u00e9rom.<\/p>\n<p>V\u0161etko, \u010do rob\u00edme, s\u00fa z\u00e1kladn\u00e9 bitov\u00e9 oper\u00e1cie, a na\u0161e procesory ich vykon\u00e1vaj\u00fa ve\u013emi efekt\u00edvne. Ale, bohu\u017eia\u013e, \"krm\u00edme\" n\u00e1\u0161 procesor ve\u013emi mal\u00fdmi k\u00f4pkami pr\u00e1ce. Na\u0161e funkcie vykon\u00e1vaj\u00fa oper\u00e1cie po bajtoch. M\u00f4\u017eeme ve\u013emi jednoducho upravi\u0165 n\u00e1\u0161 k\u00f3d tak, aby pracoval s 8-bajtov\u00fdmi k\u00f4pkami, pomocou slice UInt64.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/8d1b60ba4b7046c836601631cadd0b6a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nAko vid\u00edte, t\u00e1to mal\u00e1 zmena zr\u00fdchlila na\u0161u aplik\u00e1ciu osemkr\u00e1t zv\u00fd\u0161en\u00edm batch-u osemkr\u00e1t. Zisk je, d\u00e1 sa poveda\u0165, line\u00e1rny.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/0fc663412d04dd38b927de5c8776f69d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<h2>Implement\u00e1cia v assembleri<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/b3ef133167b89da983356b1c7389aecd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAle to e\u0161te nie je koniec. Na\u0161e procesory m\u00f4\u017eu pracova\u0165 s k\u00faskami po 16, 32 a dokonca 64 bajtoch. Tak\u00e9to \"\u0161irok\u00e9\" oper\u00e1cie sa naz\u00fdvaj\u00fa single instruction multiple data (SIMD; jedna in\u0161trukcia, ve\u013ea \u00fadajov), a proces transform\u00e1cie k\u00f3du tak, aby pou\u017e\u00edval tak\u00e9to oper\u00e1cie, sa naz\u00fdva vektoriz\u00e1cia.<\/p>\n<p>Bohu\u017eia\u013e, Go kompil\u00e1tor nie je v vektoriz\u00e1cii ve\u013emi dobr\u00fd. V s\u00fa\u010dasnosti je jedin\u00fd sp\u00f4sob vektoriz\u00e1cie k\u00f3du v Go vzia\u0165 a vlo\u017ei\u0165 \u00fadaje oper\u00e1cie ru\u010dne pomocou assemblera Go.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/91278be45df67e1f9572d68fab7ebad1.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nAssembler Go je zvl\u00e1\u0161tny \u017eivo\u010d\u00edch. Ur\u010dite viete, \u017ee assembler je nie\u010do, \u010do je ve\u013emi viazan\u00e9 na architekt\u00faru po\u010d\u00edta\u010da, pre ktor\u00fd p\u00ed\u0161ete, ale v Go to nie je tak. Assembler Go je viac podobn\u00fd IRL (intermediate representation language) alebo medzi\u010dinn\u00e9mu jazyku: je takmer platformovo nez\u00e1visl\u00fd. Rob Pike mal skvel\u00fa <noindex><a rel=\"nofollow\" href=\"https:\/\/www.youtube.com\/watch?v=KINIAgRpkDA\">predn\u00e1\u0161kou<\/a><\/noindex> predn\u00e1\u0161ku na t\u00fato t\u00e9mu pred nieko\u013ek\u00fdmi rokmi na GopherCon v Denveri.<\/p>\n<p>Okrem toho Go pou\u017e\u00edva neobvykl\u00fd form\u00e1t Plan 9, ktor\u00fd sa l\u00ed\u0161i od uzn\u00e1van\u00fdch form\u00e1tov AT&amp;T a Intel.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/526f75eb18edfc2f851f2725e9d6f69e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nM\u00f4\u017eeme s istotou poveda\u0165, \u017ee p\u00edsanie assemblera Go ru\u010dne nie je pr\u00e1ve najz\u00e1bavnej\u0161ia \u010dinnos\u0165.<\/p>\n<p>Ale na\u0161\u0165astie u\u017e existuj\u00fa dve vysok\u00farov\u0148ov\u00e9 n\u00e1stroje, ktor\u00e9 n\u00e1m pom\u00e1haj\u00fa pri p\u00edsan\u00ed assemblera Go: PeachPy a avo. Obe n\u00e1stroje generuj\u00fa Go-assembler z vysoko\u00farov\u0148ov\u00e9ho k\u00f3du nap\u00edsan\u00e9ho v Pythone a Go.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/b8a7aa2c585b805e9b1f2ada186b84e8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTieto utilitky zjednodu\u0161uj\u00fa tak\u00e9 veci, ako je alok\u00e1cia registrov (v\u00fdber procesorov\u00e9ho registra), p\u00edsanie cyklov a vo v\u0161eobecnosti zjednodu\u0161uj\u00fa proces vstupu do sveta assemblerov\u00e9ho programovania v Go.<\/p>\n<p>Budeme pou\u017e\u00edva\u0165 avo, tak\u017ee na\u0161e programy bud\u00fa takmer be\u017en\u00fdmi programami v Go.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/128e4adef14e5f2cf00fb5b6302ef58e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTakto vyzer\u00e1 najjednoduch\u0161\u00ed pr\u00edklad avo-programu. M\u00e1me funkciu main(), ktor\u00e1 v sebe definuje funkciu Add(), ktorej zmyslom je s\u010d\u00edta\u0165 dve \u010d\u00edsla. Nach\u00e1dzaj\u00fa sa tu pomocn\u00e9 funkcie na z\u00edskanie parametrov pod\u013ea n\u00e1zvu a na z\u00edskanie jedn\u00e9ho z dostupn\u00fdch a vhodn\u00fdch procesorov\u00fdch registrov. Ka\u017edej procesorovej oper\u00e1cii zodpoved\u00e1 pr\u00edslu\u0161n\u00e1 funkcia v avo, ako je vidie\u0165 na ADDQ. A nakoniec, vid\u00edme pomocn\u00fa funkciu na ulo\u017eenie v\u00fdslednej hodnoty.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/01ccaa6aa6d394ef598ea2dbc9257d87.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nZavolan\u00edm go generate vykon\u00e1me program v avo a v\u00fdsledkom bude generovanie dvoch s\u00faborov:<\/p>\n<ul>\n<li>add.s s v\u00fdsledn\u00fdm k\u00f3dom v Go-assembleri;\n<\/li>\n<li>stub.go s hlavi\u010dkami funkci\u00ed na prepojenie dvoch svetov: Go a assemblera.\n<\/li>\n<\/ul>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/72a9443776ecf45eef6fb97a4e08acba.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTeraz, ke\u010f sme videli, \u010do a ako rob\u00ed avo, pozrime sa na na\u0161e funkcie. Implementoval som ako skal\u00e1rne, tak aj vektorov\u00e9 (SIMD) verzie funkci\u00ed.<\/p>\n<p>Najprv sa pozrime na skal\u00e1rne verzie.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/ec31dbb8b97b9d7c1012a120fa18cdaf.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nRovnako ako v predch\u00e1dzaj\u00facom pr\u00edklade, po\u017eiadame o vo\u013en\u00fd a spr\u00e1vny register v\u0161eobecn\u00e9ho pou\u017eitia, nemus\u00edme po\u010d\u00edta\u0165 posuny a ve\u013ekosti pre argumenty. Toto v\u0161etko avo rob\u00ed za n\u00e1s.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/88085e927dd943ea0f808a28fb3ccf9b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPredt\u00fdm sme pou\u017e\u00edvali zna\u010dky a goto (alebo skoky) na zr\u00fdchlenie a oklamanie kompil\u00e1tora Go, ale teraz to rob\u00edme od za\u010diatku. Probl\u00e9m je v tom, \u017ee cykly s\u00fa vysoko\u00farov\u0148ov\u00fd koncept. V assembleri m\u00e1me len zna\u010dky a skoky.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/9a4181248eb279d89c1445a820b06649.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nZost\u00e1vaj\u00faci k\u00f3d by mal by\u0165 u\u017e zn\u00e1my a zrozumite\u013en\u00fd. Emulujeme cyklus zna\u010dkami a skokmi, berieme mal\u00fa \u010das\u0165 \u00fadajov z na\u0161ich dvoch zoznamov, kombinujeme ich bitovou oper\u00e1ciou (AND NOT v tomto pr\u00edpade) a potom uklad\u00e1me v\u00fdsledok do v\u00fdsledn\u00e9ho zoznamu. Hotovo.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/19275ead27f63092fc6596bed38a8d03.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTakto vyzer\u00e1 kone\u010dn\u00fd k\u00f3d v assembleri. Nebolo potrebn\u00e9 po\u010d\u00edta\u0165 posuny a ve\u013ekosti (vyzna\u010den\u00e9 zelenou), ani sledova\u0165 pou\u017e\u00edvan\u00e9 registre (vyzna\u010den\u00e9 \u010dervenou).<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/ed68528a6f852634a5b536670c6315f0.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAk porovn\u00e1me v\u00fdkon implement\u00e1cie v assembleri s v\u00fdkonom najlep\u0161ej implement\u00e1cie v Go, zist\u00edme, \u017ee s\u00fa rovnak\u00e9. A to je o\u010dak\u00e1van\u00e9. Predsa sme neurobili ni\u010d zvl\u00e1\u0161tne \u2014 len sme reprodukovali to, \u010do by robil Go kompil\u00e1tor.<\/p>\n<p>Bohu\u017eia\u013e, nem\u00f4\u017eeme don\u00fati\u0165 kompil\u00e1tor, aby inlinoval na\u0161e funkcie nap\u00edsan\u00e9 v assembleri. Go kompil\u00e1tor v s\u00fa\u010dasnosti t\u00fato funkciu nem\u00e1, aj ke\u010f \u017eiados\u0165 o jej pridanie existuje u\u017e dos\u0165 dlho.<\/p>\n<p>Presne preto nie je mo\u017en\u00e9 z\u00edska\u0165 \u017eiadne v\u00fdhody z mal\u00fdch funkci\u00ed v assembleri. Mus\u00edme bu\u010f p\u00edsa\u0165 ve\u013ek\u00e9 funkcie, alebo pou\u017ei\u0165 nov\u00fd bal\u00edk math\/bits, alebo sa vyhn\u00fa\u0165 assembleri.<\/p>\n<p>Po\u010fme sa teraz pozrie\u0165 na vektorov\u00e9 verzie na\u0161ich funkci\u00ed.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/7f67c3cc855908fb47c7900d6e5d7f54.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPre tento pr\u00edklad som sa rozhodol pou\u017ei\u0165 AVX2, tak\u017ee budeme vyu\u017e\u00edva\u0165 oper\u00e1cie pracuj\u00face s 32-bajtov\u00fdmi kusmi. \u0160trukt\u00fara k\u00f3du je ve\u013emi podobn\u00e1 skalarnej variante: na\u010d\u00edtanie parametrov, \u017eiados\u0165 o poskytnutie vo\u013en\u00e9ho spolo\u010dn\u00e9ho registra a pod.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/021e0424a0d733ec7db9edeb98ce1f65.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nJednou z noviniek je, \u017ee \u0161ir\u0161ie vektorov\u00e9 oper\u00e1cie pou\u017e\u00edvaj\u00fa \u0161peci\u00e1lne \u0161irok\u00e9 registre. V pr\u00edpade 32-bajtov\u00fdch kusov ide o registre s prefixom Y. Pr\u00e1ve preto vid\u00edte funkciu YMM() v k\u00f3de. Keby som pou\u017eil AVX-512 s 64-bitov\u00fdmi kusmi, prefix by bol Z.<\/p>\n<p>Druh\u00e1 novinka sa t\u00fdka toho, \u017ee som sa rozhodol pou\u017ei\u0165 optimaliz\u00e1ciu zvan\u00fa rozvinutie cyklu (loop unrolling), teda urobi\u0165 osem oper\u00e1ci\u00ed cyklu ru\u010dne, sk\u00f4r ne\u017e sa vr\u00e1ti\u0165 na za\u010diatok cyklu. T\u00e1to optimaliz\u00e1cia zni\u017euje po\u010det branchingov (vetven\u00ed) v k\u00f3de a je obmedzen\u00e1 po\u010dtom vo\u013en\u00fdch registrov, ktor\u00e9 s\u00fa k dispoz\u00edcii.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/f54631d9e8c69f6f70ecace3133ae1e8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nA \u010do v\u00fdkon? Je skvel\u00fd! Dosiahli sme zr\u00fdchlenie pribli\u017ene sedemkr\u00e1t v porovnan\u00ed s najlep\u0161\u00edm rie\u0161en\u00edm v Go. Impres\u00edvne, \u017ee?<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/d7e85c933eecb243cfb49225b4d92c6c.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAle aj t\u00fato implement\u00e1ciu by bolo potenci\u00e1lne mo\u017en\u00e9 ur\u00fdchli\u0165 pou\u017eit\u00edm AVX-512, prefetchingom alebo JIT (just-in-time compiler) pre pl\u00e1nova\u010d po\u017eiadaviek. Ale to je u\u017e ur\u010dite t\u00e9ma na samostatn\u00fa prezent\u00e1ciu.<\/p>\n<h2>Probl\u00e9my bitmapov\u00fdch indexov<\/h2>\n<p>\nTeraz, ke\u010f sme u\u017e presk\u00famali jednoduch\u00fa implement\u00e1ciu bitmapov\u00e9ho indexu v Go a ove\u013ea v\u00fdkonej\u0161iu v assembleri, po\u010fme kone\u010dne hovori\u0165 o tom, pre\u010do sa bitmapov\u00e9 indexy tak zriedka pou\u017e\u00edvaj\u00fa.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/83d36a5c92ba90fd680fe8afb6cfc11f.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nVo star\u0161\u00edch vedeck\u00fdch pr\u00e1cach sa spom\u00ednaj\u00fa tri probl\u00e9my bitmapov\u00fdch indexov, no nov\u0161ie \u0161t\u00fadie a aj ja tvrd\u00edme, \u017ee u\u017e nie s\u00fa aktu\u00e1lne. Nezaobera\u0165 sa ka\u017ed\u00fdm z t\u00fdchto probl\u00e9mov do h\u013abky, ale povrchne ich presk\u00famame.<\/p>\n<h2>Probl\u00e9m vysokej kardy<\/h2>\n<p>\nHovor\u00ed sa n\u00e1m, \u017ee bitmapov\u00e9 indexy s\u00fa vhodn\u00e9 iba pre polia s n\u00edzkou kardi\u00e1lnos\u0165ou, teda pre tak\u00e9, ktor\u00fdch hodn\u00f4t je m\u00e1lo (napr\u00edklad pohlavie alebo farba o\u010d\u00ed). D\u00f4vodom je to, \u017ee be\u017en\u00e9 zobrazenie tak\u00fdchto pol\u00ed (jeden bit na hodnotu) v pr\u00edpade vysokej kardi\u00e1lnosti by zaberalo pr\u00edli\u0161 ve\u013ea miesta a navy\u0161e by tieto bitmapov\u00e9 indexy boli slabooden\u0161en\u00e9 (zriedkav\u00e9).<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/0787efc4d2cb4ea4d404ca7888b33697.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/44ab4bc7c25d14fe2f53caf5d9da399d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nNiekedy m\u00f4\u017eeme pou\u017ei\u0165 in\u00e9 zobrazenie, napr\u00edklad \u0161tandardn\u00e9, ktor\u00e9 pou\u017e\u00edvame na zobrazenie \u010d\u00edsel. Ale pr\u00e1ve pr\u00edchod kompresn\u00fdch algoritmov v\u0161etko zmenil. V posledn\u00fdch desa\u0165ro\u010diach vedci a v\u00fdskumn\u00edci vymysleli mno\u017estvo kompresn\u00fdch algoritmov pre bitmapy. Ich hlavnou v\u00fdhodou je, \u017ee nie je potrebn\u00e9 dekompresova\u0165 bitmapy na vykon\u00e1vanie bitov\u00fdch oper\u00e1ci\u00ed \u2014 m\u00f4\u017eeme vykon\u00e1va\u0165 bitov\u00e9 oper\u00e1cie priamo na komprimovan\u00fdch bitmap\u00e1ch.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/ecb54fbf15aa11271bbbab01ecbda880.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nV poslednej dobe sa objavili aj hybridn\u00e9 pr\u00edstupy, ako napr\u00edklad roaring bitmapy. Tieto pou\u017e\u00edvaj\u00fa s\u00fa\u010dasne tri r\u00f4zne zobrazenia bitmapov \u2014 samotn\u00e9 bitmapy, polia a takzvan\u00e9 bit runs \u2014 a vyva\u017euj\u00fa ich, aby maximalizovali v\u00fdkon a minimalizovali v\u00fdkon pam\u00e4te.<\/p>\n<p>Roaring bitmapy m\u00f4\u017eete n\u00e1js\u0165 v najpopul\u00e1rnej\u0161\u00edch aplik\u00e1ci\u00e1ch. U\u017e existuje obrovsk\u00e9 mno\u017estvo implement\u00e1ci\u00ed pre r\u00f4zne programovacie jazyky, vr\u00e1tane viac ako troch implement\u00e1ci\u00ed pre Go.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/de2adfebc431ff48c996247b453f02ae.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n\u010eal\u0161\u00ed pr\u00edstup, ktor\u00fd n\u00e1m m\u00f4\u017ee pom\u00f4c\u0165 vysporiada\u0165 sa s vysokou kardi\u00e1lnos\u0165ou, sa naz\u00fdva skupinovanie (binning). Predstavte si, \u017ee m\u00e1te pole, ktor\u00e9 reprezentuje v\u00fd\u0161ku \u010dloveka. V\u00fd\u0161ka je \u010d\u00edslo s pl\u00e1vaj\u00facou desatinnou \u010diarkou, ale my, \u013eudia, o nej neuva\u017eujeme t\u00fdmto sp\u00f4sobom. Pre n\u00e1s nie je rozdiel medzi v\u00fd\u0161kou 185,2 cm a 185,3 cm.<\/p>\n<p>Tak\u017ee m\u00f4\u017eeme zhroma\u017edi\u0165 podobn\u00e9 hodnoty do skup\u00edn v r\u00e1mci 1 cm.<\/p>\n<p>A ak navy\u0161e vieme, \u017ee ve\u013emi m\u00e1lo \u013eud\u00ed m\u00e1 v\u00fd\u0161ku menej ako 50 cm a viac ako 250 cm, potom m\u00f4\u017eeme v podstate premeni\u0165 pole s nekone\u010dnou kardi\u00e1lnos\u0165ou na pole s kardi\u00e1lnos\u0165ou pribli\u017ene 200 hodn\u00f4t.<\/p>\n<p>Samozrejme, ak bude potrebn\u00e9, m\u00f4\u017eeme vykona\u0165 dodato\u010dn\u00fa filtr\u00e1ciu aj po.<\/p>\n<h2>Probl\u00e9m s ve\u013ekou priepustnos\u0165ou<\/h2>\n<p>\n\u010eal\u0161\u00ed probl\u00e9m bitmapov\u00fdch indexov spo\u010d\u00edva v tom, \u017ee ich aktualiz\u00e1cia m\u00f4\u017ee by\u0165 ve\u013emi n\u00e1kladn\u00e1.<\/p>\n<p>Datab\u00e1zy musia umo\u017eni\u0165 aktualiz\u00e1ciu \u00fadajov v momente, ke\u010f potenci\u00e1lne stovky \u010fal\u0161\u00edch po\u017eiadaviek vyh\u013ead\u00e1vaj\u00fa tieto \u00fadaje. Potrebujeme z\u00e1mky, aby sme sa vyhli probl\u00e9mom s paraleln\u00fdm pr\u00edstupom k \u00fadajom alebo in\u00fdm probl\u00e9mom zdie\u013ean\u00e9ho pr\u00edstupu. A tam, kde je jeden ve\u013ek\u00fd z\u00e1mok, tam je probl\u00e9m \u2014 lock contention, ke\u010f sa tento z\u00e1mok st\u00e1va \u00fazkym hrdlom.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/0ae1bf925542d286f8b7b245c160a35e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTento probl\u00e9m sa d\u00e1 vyrie\u0161i\u0165 alebo ob\u00eds\u0165 pomocou shardovania alebo vyu\u017eitia verzionovan\u00fdch indexov.<\/p>\n<p>Shardovanie je jednoduch\u00e1 a zn\u00e1ma vec. M\u00f4\u017eete shardova\u0165 bitmapov\u00fd index tak, ako by ste shardovali ak\u00e9ko\u013evek in\u00e9 d\u00e1ta. Namiesto jedn\u00e9ho ve\u013ek\u00e9ho z\u00e1mku z\u00edskate mno\u017estvo mal\u00fdch z\u00e1mkov a tak sa zbav\u00edte lock contention.<\/p>\n<p>Druh\u00fdm sp\u00f4sobom, ako tento probl\u00e9m vyrie\u0161i\u0165, je pou\u017eitie verzionovan\u00fdch indexov. M\u00f4\u017eete ma\u0165 jednu k\u00f3piu indexu, ktor\u00fa pou\u017e\u00edvate na vyh\u013ead\u00e1vanie alebo \u010d\u00edtanie, a jednu \u2013 na z\u00e1pis alebo aktualiz\u00e1ciu. A raz za ur\u010dit\u00fd interval (napr\u00edklad ka\u017ed\u00fdch 100 ms alebo 500 ms) ich duplikujete a men\u00edte miesta. Samozrejme, tento pr\u00edstup je aplikovate\u013en\u00fd len v t\u00fdch pr\u00edpadoch, ke\u010f va\u0161a aplik\u00e1cia m\u00f4\u017ee pracova\u0165 s trochu zaost\u00e1vaj\u00facim vyh\u013ead\u00e1vac\u00edm indexom.<\/p>\n<p>Tieto dva pr\u00edstupy je mo\u017en\u00e9 pou\u017ei\u0165 s\u00fa\u010dasne: m\u00f4\u017eete ma\u0165 shardovan\u00fd verzionovan\u00fd index.<\/p>\n<h2>Zlo\u017eitej\u0161ie dotazy<\/h2>\n<p>Posledn\u00fd probl\u00e9m bitmapov\u00fdch indexov spo\u010d\u00edva v tom, \u017ee, ako n\u00e1m hovoria, s\u00fa nevhodn\u00e9 pre zlo\u017eitej\u0161ie typy dotazov, napr\u00edklad pre dotazy \u201ev intervale\u201c.<\/p>\n<p>A skuto\u010dne, ak nad t\u00fdm prem\u00fd\u0161\u013eate, bitov\u00e9 oper\u00e1cie typu AND, OR a pod. nie s\u00fa ve\u013emi vhodn\u00e9 pre dotazy typu \u201eUk\u00e1\u017ete mi hotely s cenou izby od 200 do 300 dol\u00e1rov za noc\u201c.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/7bc2e129cad46fb5875c2b3018c39ff7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nNaivn\u00fdm a ve\u013emi nerozumn\u00fdm rie\u0161en\u00edm by bolo z\u00edska\u0165 v\u00fdsledky pre ka\u017ed\u00fa dol\u00e1rov\u00fa hodnotu a zl\u00fa\u010di\u0165 ich pomocou bitovej oper\u00e1cie OR.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/b9f8fc7945caa1866f8e0cfa8a04bd98.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTrochu spr\u00e1vnej\u0161\u00edm rie\u0161en\u00edm by bolo pou\u017ei\u0165 grupovanie. Napr\u00edklad do skup\u00edn po 50 dol\u00e1rov. To by ur\u00fdchlilo n\u00e1\u0161 proces 50-kr\u00e1t.<\/p>\n<p>Probl\u00e9m sa v\u0161ak \u013eahko rie\u0161i pou\u017eit\u00edm preh\u013eadu navrhnut\u00e9ho \u0161peci\u00e1lne pre tento typ dopytov. V akademick\u00fdch pr\u00e1cach sa naz\u00fdva range-encoded bitmaps.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/644a420628b21f220a7af1ff15c4031f.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nV tomto preh\u013eade neozna\u010dujeme len jeden bit pre ur\u010dit\u00fa hodnotu (napr\u00edklad 200), ale ozna\u010d\u00edme t\u00fato hodnotu a v\u0161etko, \u010do je nad \u0148ou. 200 a vy\u0161\u0161ie. To ist\u00e9 plat\u00ed pre 300: 300 a vy\u0161\u0161ie. A tak \u010falej.<\/p>\n<p>Pou\u017eit\u00edm tohto preh\u013eadu m\u00f4\u017eeme odpoveda\u0165 na tak\u00fdto typ vyh\u013ead\u00e1vacieho dopytu prech\u00e1dzaj\u00fac indexom len dvakr\u00e1t. Najprv z\u00edskame zoznam hotelov, kde cena za noc je menej ako 300 dol\u00e1rov, a potom ho zbav\u00edme t\u00fdch, kde cena za noc je ni\u017e\u0161ia ako 199 dol\u00e1rov. Hotovo.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/cc2bb58d7d7a51495c62ec7da81e2d12.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPrekvap\u00ed v\u00e1s, ale aj geografick\u00e9 dopyty s\u00fa mo\u017en\u00e9 pomocou bitmapov\u00fdch indexov. V trik spo\u010d\u00edva v pou\u017eit\u00ed geografick\u00e9ho preh\u013eadu, ktor\u00fd obklopuje va\u0161u koordin\u00e1tu geometrickou figurou. Napr\u00edklad S2 od Google. Fig\u00fara mus\u00ed by\u0165 vyjadren\u00e1 ako tri alebo viac prekr\u00fdvaj\u00facich sa priamok, ktor\u00e9 m\u00f4\u017eeme o\u010d\u00edslova\u0165. Takto m\u00f4\u017eeme premeni\u0165 n\u00e1\u0161 geografick\u00fd dopyt na nieko\u013eko dopytov \"pod\u013ea intervalov\" (pod\u013ea t\u00fdchto o\u010d\u00edslovan\u00fdch \u010diar).<\/p>\n<h2>Hotov\u00e9 rie\u0161enia<\/h2>\n<p>\nD\u00fafam, \u017ee som v\u00e1s aspo\u0148 trocha zaujal a m\u00e1te vo svojom arsen\u00e1li \u010fal\u0161\u00ed u\u017eito\u010dn\u00fd n\u00e1stroj. Ak by ste niekedy potrebovali urobi\u0165 nie\u010do podobn\u00e9, budete vedie\u0165, na ktor\u00fa stranu sa pozrie\u0165.<\/p>\n<p>Nie v\u0161etci v\u0161ak maj\u00fa \u010das, trpezlivos\u0165 a prostriedky, aby vytvorili bitmapov\u00e9 indexy od z\u00e1kladov. Obzvl\u00e1\u0161\u0165 pokro\u010dilej\u0161ie, s pou\u017eit\u00edm SIMD, napr\u00edklad.<\/p>\n<p>Na\u0161\u0165astie existuje nieko\u013eko hotov\u00fdch rie\u0161en\u00ed, ktor\u00e9 v\u00e1m m\u00f4\u017eu pom\u00f4c\u0165.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/817b47cb189a758756b602ec9cf319e1.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<h2>Roaring bitmaps<\/h2>\n<p>\nPo prv\u00e9, existuje t\u00e1 zn\u00e1ma kni\u017enica roaring bitmaps, o ktorej som u\u017e hovoril. Obsahuje v\u0161etky potrebn\u00e9 kontajnery a bitov\u00e9 oper\u00e1cie, ktor\u00e9 potrebujete na vytvorenie plnohodnotn\u00e9ho bitmapov\u00e9ho indexu.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/57f61a51485c174666b52dc2063fabe8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n\u017dia\u013e, v s\u00fa\u010dasnosti \u017eiadna z Go implement\u00e1ci\u00ed nepou\u017e\u00edva SIMD, \u010do znamen\u00e1, \u017ee Go implement\u00e1cie s\u00fa menej v\u00fdkonn\u00e9 ako implement\u00e1cie v C, napr\u00edklad.<\/p>\n<h2>Pilosa<\/h2>\n<p>\n\u010eal\u0161\u00ed produkt, ktor\u00fd v\u00e1m m\u00f4\u017ee pom\u00f4c\u0165, je datab\u00e1za Pilosa, ktor\u00e1 v podstate obsahuje len bitmapov\u00e9 indexy. Je to relat\u00edvne nov\u00e9 rie\u0161enie, ale r\u00fdchlo si z\u00edskava srdcia.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/d3870a979e1e73d093fe5d5e9bb71cd8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPilosa pou\u017e\u00edva roaring bitmaps vo svojom vn\u00fatri a poskytuje v\u00e1m mo\u017enos\u0165 ich pou\u017e\u00edva\u0165, zjednodu\u0161uje a vysvet\u013euje v\u0161etky veci, o ktor\u00fdch som hovoril vy\u0161\u0161ie: skupinovanie, range-encoded bitmaps, pojem po\u013ea at\u010f.<\/p>\n<p>R\u00fdchlo sa pozrime na pr\u00edklad pou\u017eitia Pilosa na odpove\u010f na ot\u00e1zku, ktor\u00fa u\u017e pozn\u00e1te.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/dfee7abfd653cc19d9aa8b64c64f3e4e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPr\u00edklad je ve\u013emi podobn\u00fd tomu, \u010do ste videli predt\u00fdm. Vytv\u00e1rame klienta k serveru Pilosa, vytv\u00e1rame index a potrebn\u00e9 polia, n\u00e1sledne napln\u00edme na\u0161e polia n\u00e1hodn\u00fdmi \u00fadajmi s pravdepodobnos\u0165ami a nakoniec vykon\u00e1vame zn\u00e1mu ot\u00e1zku.<\/p>\n<p>Potom pou\u017e\u00edvame NOT na pole \u201eexpensive\u201c, n\u00e1sledne prekr\u00fdvame v\u00fdsledok (alebo AND-\u00edme) s po\u013eom \u201eterrace\u201c a s po\u013eom \u201ereservations\u201c. A nakoniec, dost\u00e1vame fin\u00e1lny v\u00fdsledok.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/8d66c6d68019c2297b6c15b700f06a3a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nD\u00fafam, \u017ee v doh\u013eadnej bud\u00facnosti sa tento nov\u00fd typ indexov - bitmapov\u00e9 indexy - objav\u00ed aj v datab\u00e1zach ako MySQL a PostgreSQL.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/7a8e33d576c7fb6376a173ee038b4206.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<h2>Z\u00e1ver<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou\" src=\"\/wp-content\/uploads\/2019\/05\/c62caa9ad6f2d96056c80326f4fa9a0d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAk ste e\u0161te nezaspali, \u010fakujem. Musel som sa v r\u00fdchlosti dotkn\u00fa\u0165 mnoh\u00fdch t\u00e9m kv\u00f4li obmedzen\u00e9mu \u010dasu, ale d\u00fafam, \u017ee predn\u00e1\u0161ka bola u\u017eito\u010dn\u00e1 a mo\u017eno aj motivuj\u00faca.<\/p>\n<p>O bitmapov\u00fdch indexoch je dobr\u00e9 vedie\u0165, aj ke\u010f ich moment\u00e1lne nepotrebujete. Nech s\u00fa \u010fal\u0161\u00edm n\u00e1strojom vo va\u0161ej v\u00fdbave.<\/p>\n<p>Presk\u00famali sme r\u00f4zne triky na zv\u00fd\u0161enie v\u00fdkonu pre Go a veci, s ktor\u00fdmi si kompil\u00e1tor Go zatia\u013e nevie ve\u013emi dobre poradi\u0165. Toto je ur\u010dite u\u017eito\u010dn\u00e9 vedie\u0165 pre ka\u017ed\u00e9ho program\u00e1tora v Go.<\/p>\n<p>To je v\u0161etko, \u010do som chcel poveda\u0165. \u010eakujem!<br \/>\n<br \/>Zdroj: <a content=\"nofollow\" rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/company\/badoo\/blog\/451938\/\">habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"<p>\u0412\u0441\u0442\u0443\u043f\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e \u042f \u0432\u044b\u0441\u0442\u0443\u043f\u0438\u043b \u0441 \u044d\u0442\u0438\u043c \u0434\u043e\u043a\u043b\u0430\u0434\u043e\u043c \u043d\u0430 \u0430\u043d\u0433\u043b\u0438\u0439\u0441\u043a\u043e\u043c \u044f\u0437\u044b\u043a\u0435 \u043d\u0430 \u043a\u043e\u043d\u0444\u0435\u0440\u0435\u043d\u0446\u0438\u0438 GopherCon Russia 2019 \u0432 \u041c\u043e\u0441\u043a\u0432\u0435 \u0438 \u043d\u0430 \u0440\u0443\u0441\u0441\u043a\u043e\u043c \u2014 \u043d\u0430 \u043c\u0438\u0442\u0430\u043f\u0435 \u0432 \u041d\u0438\u0436\u043d\u0435\u043c \u041d\u043e\u0432\u0433\u043e\u0440\u043e\u0434\u0435. \u0420\u0435\u0447\u044c \u0432 \u043d\u0451\u043c \u0438\u0434\u0451\u0442 \u043e bitmap-\u0438\u043d\u0434\u0435\u043a\u0441\u0435 \u2014 \u043c\u0435\u043d\u0435\u0435 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0451\u043d\u043d\u043e\u043c, \u0447\u0435\u043c B-tree, \u043d\u043e \u043d\u0435 \u043c\u0435\u043d\u0435\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u043c. \u0414\u0435\u043b\u044e\u0441\u044c \u0437\u0430\u043f\u0438\u0441\u044c\u044e \u0432\u044b\u0441\u0442\u0443\u043f\u043b\u0435\u043d\u0438\u044f \u043d\u0430 \u043a\u043e\u043d\u0444\u0435\u0440\u0435\u043d\u0446\u0438\u0438 \u043d\u0430 \u0430\u043d\u0433\u043b\u0438\u0439\u0441\u043a\u043e\u043c \u0438 \u0442\u0435\u043a\u0441\u0442\u043e\u0432\u043e\u0439 \u0440\u0430\u0441\u0448\u0438\u0444\u0440\u043e\u0432\u043a\u043e\u0439 \u043d\u0430 \u0440\u0443\u0441\u0441\u043a\u043e\u043c. \u041c\u044b \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c, [&hellip;]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":25469,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-33793","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t<!-- All in One SEO 5.0.4 - aioseo.com -->\n\t<meta name=\"description\" content=\"\u0412\u0441\u0442\u0443\u043f\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e \u042f \u0432\u044b\u0441\u0442\u0443\u043f\u0438\u043b \u0441.\" \/>\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Yuri Gagarin\"\/>\n\t<link rel=\"canonical\" href=\"https:\/\/prohoster.info\/sk\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti\" \/>\n\t\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.4\" \/>\n\t\t<meta property=\"og:locale\" content=\"sk_SK\" \/>\n\t\t<meta property=\"og:site_name\" content=\"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"\ud83e\udd47Bitmap-\u0438\u043d\u0434\u0435\u043a\u0441\u044b \u0432 Go: \u043f\u043e\u0438\u0441\u043a \u043d\u0430 \u0434\u0438\u043a\u043e\u0439 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 | ProHoster\" \/>\n\t\t<meta property=\"og:description\" content=\"\u0412\u0441\u0442\u0443\u043f\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e \u042f \u0432\u044b\u0441\u0442\u0443\u043f\u0438\u043b \u0441.\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/prohoster.info\/sk\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti\" \/>\n\t\t<meta property=\"og:image\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:secure_url\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:width\" content=\"350\" \/>\n\t\t<meta property=\"og:image:height\" content=\"350\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2019-10-31T18:54:42+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2019-10-31T18:54:42+00:00\" \/>\n\t\t<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<meta property=\"article:author\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"\ud83e\udd47Bitmapov\u00e9 indexy v Go: vyh\u013ead\u00e1vanie neuverite\u013enou r\u00fdchlos\u0165ou | ProHoster","description":"\u00davodn\u00e9 slovo, vyst\u00fapil som s.","canonical_url":"https:\/\/prohoster.info\/sk\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"sk_SK","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47Bitmap-\u0438\u043d\u0434\u0435\u043a\u0441\u044b \u0432 Go: \u043f\u043e\u0438\u0441\u043a \u043d\u0430 \u0434\u0438\u043a\u043e\u0439 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 | ProHoster","og:description":"\u0412\u0441\u0442\u0443\u043f\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e \u042f \u0432\u044b\u0441\u0442\u0443\u043f\u0438\u043b \u0441.","og:url":"https:\/\/prohoster.info\/sk\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T18:54:42+00:00","article:modified_time":"2019-10-31T18:54:42+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"33793","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-21 16:43:19","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 02:33:25","updated":"2026-01-21 16:43:19","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/posts\/33793","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/comments?post=33793"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/posts\/33793\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/media\/25469"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/media?parent=33793"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/categories?post=33793"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/sk\/wp-json\/wp\/v2\/tags?post=33793"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}