{"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\/cs\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti","title":{"rendered":"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/86ef928e6741022b2c0e5885a031408a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<\/p>\n<h2>\u00davodn\u00ed slovo<\/h2>\n<p>\nTento p\u0159\u00edsp\u011bvek jsem p\u0159ednesl v angli\u010dtin\u011b na konferenci GopherCon Russia 2019 v Moskv\u011b a v ru\u0161tin\u011b na meetupu v Ni\u017en\u00edm Novgorod\u011b. Mluv\u00ed o bitmapov\u00e9m indexu, kter\u00fd je m\u00e9n\u011b b\u011b\u017en\u00fd ne\u017e B-tree, ale ne m\u00e9n\u011b zaj\u00edmav\u00fd. Sd\u00edl\u00edm <noindex><a rel=\"nofollow\" href=\"https:\/\/youtu.be\/WvlUH6MjUuI?list=PL3xVZC4USRNSO_kb2lh_J_no6C-KJ7Phg\">z\u00e1znam<\/a><\/noindex> sv\u00e9ho vystoupen\u00ed na konferenci v angli\u010dtin\u011b a textov\u00fd p\u0159epis v ru\u0161tin\u011b.<\/p>\n<p>Pod\u00edv\u00e1me se na to, jak bitmapov\u00fd index funguje, kdy je lep\u0161\u00ed a kdy hor\u0161\u00ed ne\u017e jin\u00e9 indexy a v jak\u00fdch p\u0159\u00edpadech je v\u00fdrazn\u011b rychlej\u0161\u00ed ne\u017e ony; uvid\u00edme, v jak\u00fdch popul\u00e1rn\u00edch DBMS ji\u017e existuj\u00ed bitmapov\u00e9 indexy; pokus\u00edme se napsat sv\u016fj v Go. A na \"z\u00e1v\u011br\" vyu\u017eijeme hotov\u00e9 knihovny, abychom vytvo\u0159ili na\u0161i superrychlou specializovanou datab\u00e1zi.<\/p>\n<p>Hodn\u011b douf\u00e1m, \u017ee m\u00e9 pr\u00e1ce budou pro v\u00e1s u\u017eite\u010dn\u00e9 a zaj\u00edmav\u00e9. Jdeme 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=\"P\u0159ehr\u00e1t 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>Ahoj v\u0161ichni! Je \u0161est hodin ve\u010der, jsme super unaven\u00ed. Skv\u011bl\u00fd \u010das na to, abychom mluvili o nudn\u00e9 teorii datab\u00e1zov\u00fdch index\u016f, \u017ee? Nebojte se, m\u00e1m tu a tam p\u00e1r \u0159\u00e1dk\u016f zdrojov\u00e9ho k\u00f3du. \ud83d\ude42<\/p>\n<p>Pokud v\u0161ak mluv\u00edme v\u00e1\u017en\u011b, tak je prezentace nabita informacemi a nem\u00e1me tolik \u010dasu. Tak\u017ee poj\u010fme za\u010d\u00edt.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/e778e13727700f0335a4b5558a0d8db3.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nDnes budu mluvit o n\u00e1sleduj\u00edc\u00edm:<\/p>\n<ul>\n<li>co jsou indexy;\n<\/li>\n<li>co je bitmapov\u00fd index;\n<\/li>\n<li>kde se pou\u017e\u00edv\u00e1 a kde se NEN\u00cd pou\u017e\u00edv\u00e1 a pro\u010d;\n<\/li>\n<li>jednoduch\u00e1 implementace v Go a trochu boj s kompil\u00e1torem;\n<\/li>\n<li>o n\u011bco slo\u017eit\u011bj\u0161\u00ed, ale mnohem v\u00fdkonn\u011bj\u0161\u00ed implementaci v Go-assembleru;\n<\/li>\n<li>\"probl\u00e9my\" bitmapov\u00fdch index\u016f;\n<\/li>\n<li>existuj\u00edc\u00ed implementace.\n<\/li>\n<\/ul>\n<h2>Tak co jsou indexy?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/b80e5b990c44814afe9150a9a82351fd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nIndex je samostatn\u00e1 datov\u00e1 struktura, kterou uchov\u00e1v\u00e1me a aktualizujeme nav\u00edc k hlavn\u00edm dat\u016fm. Pou\u017e\u00edv\u00e1 se k urychlen\u00ed vyhled\u00e1v\u00e1n\u00ed. Bez index\u016f by vyhled\u00e1v\u00e1n\u00ed vy\u017eadovalo \u00fapln\u00e9 proch\u00e1zen\u00ed dat (proces naz\u00fdvan\u00fd full scan), a tento proces m\u00e1 line\u00e1rn\u00ed algoritmickou slo\u017eitost. Ale datab\u00e1ze obvykle obsahuj\u00ed obrovsk\u00e9 mno\u017estv\u00ed dat a line\u00e1rn\u00ed slo\u017eitost je p\u0159\u00edli\u0161 pomal\u00e1. Ide\u00e1ln\u011b bychom m\u011bli m\u00edt logaritmickou nebo konstantn\u00ed.<\/p>\n<p>Je to obrovsk\u00e9 slo\u017eit\u00e9 t\u00e9ma, p\u0159epln\u011bn\u00e9 nuancemi a kompromisy, ale po des\u00edtk\u00e1ch let v\u00fdvoje a zkoum\u00e1n\u00ed r\u016fzn\u00fdch datab\u00e1z\u00ed jsem p\u0159ipraven tvrdit, \u017ee existuje pouze n\u011bkolik \u0161iroce pou\u017e\u00edvan\u00fdch p\u0159\u00edstup\u016f k vytv\u00e1\u0159en\u00ed index\u016f datab\u00e1ze.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/08a74dbb365035cd99bc94d72644a1b7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nPrvn\u00ed p\u0159\u00edstup spo\u010d\u00edv\u00e1 v hierarchick\u00e9m z\u00fa\u017een\u00ed oblasti hled\u00e1n\u00ed, rozd\u011blen\u00ed oblasti hled\u00e1n\u00ed na men\u0161\u00ed \u010d\u00e1sti.<\/p>\n<p>Obvykle to d\u011bl\u00e1me pomoc\u00ed r\u016fzn\u00fdch druh\u016f strom\u016f. P\u0159\u00edkladem m\u016f\u017ee b\u00fdt velk\u00e1 krabice s materi\u00e1ly ve va\u0161\u00ed sk\u0159\u00edni, ve kter\u00e9 se nach\u00e1zej\u00ed men\u0161\u00ed krabice s materi\u00e1ly rozd\u011blen\u00e9 podle r\u016fzn\u00fdch t\u00e9mat. Pokud pot\u0159ebujete materi\u00e1ly, ur\u010dit\u011b budete hledat v krabici pops\u00e1n\u00e9 jako \u201eMateri\u00e1ly\u201c, a ne v t\u00e9, na kter\u00e9 je naps\u00e1no \u201eSla\u0161\u0165\u201c.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/423fac47c748980b18af434644af4dae.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nDruh\u00fd p\u0159\u00edstup spo\u010d\u00edv\u00e1 v okam\u017eit\u00e9m vymezen\u00ed po\u017eadovan\u00e9ho prvku nebo skupiny prvk\u016f. D\u011bl\u00e1me to v hash map\u00e1ch nebo v inverzn\u00edch indexech. Pou\u017eit\u00ed hash map je velmi podobn\u00e9 p\u0159edchoz\u00edmu p\u0159\u00edkladu, jen m\u00edsto jedn\u00e9 krabice s krabicemi m\u00e1te ve sk\u0159\u00edni hromadu mal\u00fdch krabic s kone\u010dn\u00fdmi p\u0159edm\u011bty.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/088fed0a2a0feea4a23edbf0ca654805.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nT\u0159et\u00ed p\u0159\u00edstup spo\u010d\u00edv\u00e1 v odstran\u011bn\u00ed pot\u0159eby hled\u00e1n\u00ed. To d\u011bl\u00e1me pomoc\u00ed Bloom filtr\u016f nebo cuckoo filtr\u016f. Prvn\u00ed poskytuj\u00ed odpov\u011b\u010f okam\u017eit\u011b, \u010d\u00edm\u017e v\u00e1s zbavuj\u00ed pot\u0159eby hled\u00e1n\u00ed.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/493bc4f20baacc0a5dc0faf15cc46285.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nPosledn\u00ed p\u0159\u00edstup spo\u010d\u00edv\u00e1 v pln\u00e9m vyu\u017eit\u00ed v\u0161ech mo\u017enost\u00ed, kter\u00e9 n\u00e1m modern\u00ed hardware nab\u00edz\u00ed. To d\u011bl\u00e1me v bitmapov\u00fdch indexech. Ano, p\u0159i jejich pou\u017e\u00edv\u00e1n\u00ed je ob\u010das nutn\u00e9 proj\u00edt cel\u00fd index, ale \u010din\u00edme to supers efektivn\u011b.<\/p>\n<p>Jak jsem ji\u017e \u0159ekl, t\u00e9ma datab\u00e1zov\u00fdch index\u016f je rozs\u00e1hl\u00e9 a pln\u00e9 kompromis\u016f. To znamen\u00e1, \u017ee n\u011bkdy m\u016f\u017eeme pou\u017e\u00edt n\u011bkolik p\u0159\u00edstup\u016f sou\u010dasn\u011b: pokud pot\u0159ebujeme je\u0161t\u011b v\u00edce urychlit vyhled\u00e1v\u00e1n\u00ed nebo pokud je nutn\u00e9 pokr\u00fdt v\u0161echny mo\u017en\u00e9 typy hled\u00e1n\u00ed.<\/p>\n<p>Dnes v\u00e1m pov\u00edm o nejm\u00e9n\u011b zn\u00e1m\u00e9m p\u0159\u00edstupu z uveden\u00fdch \u2013 o bitmapov\u00fdch indexech.<\/p>\n<h2>Kdo jsem, abych o tom mluvil?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/42a9d17a507c392bc202254a92dfaf41.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nPracuji jako vedouc\u00ed t\u00fdmu v Badoo (mo\u017en\u00e1 l\u00e9pe zn\u00e1te n\u00e1\u0161 jin\u00fd produkt \u2013 Bumble). M\u00e1me ji\u017e v\u00edce ne\u017e 400 milion\u016f u\u017eivatel\u016f po cel\u00e9m sv\u011bt\u011b a mnoho funkc\u00ed, kter\u00e9 se zab\u00fdvaj\u00ed t\u00edm, \u017ee pro n\u011b hledaj\u00ed nejlep\u0161\u00ed partnera. D\u011bl\u00e1me to pomoc\u00ed vlastn\u00edch slu\u017eeb, kter\u00e9 vyu\u017e\u00edvaj\u00ed mimo jin\u00e9 i bitmapov\u00e9 indexy.<\/p>\n<h2>Co je vlastn\u011b bitmapov\u00fd index?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/14f20f3697a20c02f6b3510dc7f0ae4d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nBitmap indexy, jak ji\u017e nazna\u010duje n\u00e1zev, pou\u017e\u00edvaj\u00ed bitmapy nebo bitov\u00e9 sady k implementaci vyhled\u00e1vac\u00edho indexu. Z pta\u010d\u00ed perspektivy se tento index skl\u00e1d\u00e1 z jednoho nebo n\u011bkolika bitmap\u016f, kter\u00e9 p\u0159edstavuj\u00ed ur\u010dit\u00e9 entity (nap\u0159\u00edklad lidi) a jejich vlastnosti nebo parametry (v\u011bk, barva o\u010d\u00ed atd.), a z algoritmu, kter\u00fd pou\u017e\u00edv\u00e1 bitov\u00e9 operace (AND, OR, NOT) k zodpov\u011bzen\u00ed vyhled\u00e1vac\u00edho dotazu.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/f815720330a51b1f0798e45d23160d3b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n\u0158\u00edk\u00e1 se n\u00e1m, \u017ee bitmap indexy jsou nejvhodn\u011bj\u0161\u00ed a velmi v\u00fdkonn\u00e9 pro p\u0159\u00edpady, kdy existuje vyhled\u00e1v\u00e1n\u00ed, kter\u00e9 kombinuje dotazy p\u0159es n\u011bkolik sloupc\u016f s n\u00edzkou kardinalitou (p\u0159edstavte si \u201ebarvu o\u010d\u00ed\u201c nebo \u201erodinn\u00fd stav\u201c oproti n\u011b\u010demu jako \u201evzd\u00e1lenost od centra m\u011bsta\u201c). Ale pozd\u011bji uk\u00e1\u017eu, \u017ee funguj\u00ed v\u00fdborn\u011b i u sloupc\u016f s vysokou kardinalitou.<\/p>\n<p>Zva\u017eme nejjednodu\u0161\u0161\u00ed p\u0159\u00edklad bitmap indexu.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/33fe23476e0931c10345d7175b83d68b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nP\u0159edstavte si, \u017ee m\u00e1me seznam moskevsk\u00fdch restaurac\u00ed s bin\u00e1rn\u00edmi vlastnostmi, jako jsou tyto:<\/p>\n<ul>\n<li>nedaleko metra (near metro);\n<\/li>\n<li>m\u00e1 soukrom\u00e9 parkovi\u0161t\u011b (has private parking);\n<\/li>\n<li>m\u00e1 terasu (has terrace);\n<\/li>\n<li>akceptuje rezervace (accepts reservations);\n<\/li>\n<li>je p\u0159\u00e1telsk\u00e9 k vegetari\u00e1n\u016fm (vegan friendly);\n<\/li>\n<li>drah\u00e9 (expensive).\n<\/li>\n<\/ul>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/fcbad539ea12f79a9d06966ce308637e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPoj\u010fme ka\u017ed\u00e9 restauraci p\u0159i\u0159adit po\u0159adov\u00e9 \u010d\u00edslo po\u010d\u00ednaje 0 a vy\u010dlenit pam\u011b\u0165 pro 6 bitmap\u016f (jeden pro ka\u017edou vlastnost). Pot\u00e9 tyto bitmapy vypln\u00edme v z\u00e1vislosti na tom, zda restaurace m\u00e1 danou vlastnost nebo ne. Pokud restaurace 4 m\u00e1 terasu, bude bit \u010d. 4 v bitmap\u011b \u201em\u00e1 terasu\u201c nastaven na 1 (pokud terasa nen\u00ed, tak na 0).<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/3709c426617d4364f392ee6b68f92b00.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTe\u010f m\u00e1me nejjednodu\u0161\u0161\u00ed bitmap index, jak\u00fd je mo\u017en\u00fd, a m\u016f\u017eeme ho pou\u017e\u00edt k odpov\u011bd\u00edm na dotazy jako:<\/p>\n<ul>\n<li>\u201eUka\u017e mi restaurace vhodn\u00e9 pro vegetari\u00e1ny\u201c;\n<\/li>\n<li>\u201eUka\u017e mi levn\u00e9 restaurace s terasou, kde lze rezervovat st\u016fl.\u201c\n<\/li>\n<\/ul>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" 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: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/0fd0b7fe9f7b7039022ad5c79fe873bc.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nJak? Poj\u010fme se pod\u00edvat. Prvn\u00ed dotaz je velmi jednoduch\u00fd. V\u0161echno, co pot\u0159ebujeme, je vz\u00edt bitmapu \u201eje p\u0159\u00e1telsk\u00e9 k vegetari\u00e1n\u016fm\u201c a p\u0159ev\u00e9st ji na seznam restaurac\u00ed, jejich\u017e bity jsou nastaveny.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" 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: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/9cc175bae55c16018fdf5ff95517a61a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nDruh\u00fd dotaz je o n\u011bco slo\u017eit\u011bj\u0161\u00ed. Mus\u00edme pou\u017e\u00edt bitovou operaci NOT na bitmapu \u201edrah\u00fdch\u201c, abychom z\u00edskali seznam levn\u00fdch restaurac\u00ed, pot\u00e9 je ANDovat s bitmapou \u201erezervace stolu dostupn\u00e1\u201c a v\u00fdsledek ANDovat s bitmapou \u201em\u00e1 verandu\u201c. V\u00fdsledn\u00e1 bitmapa bude obsahovat seznam za\u0159\u00edzen\u00ed, kter\u00e1 spl\u0148uj\u00ed v\u0161echna na\u0161e krit\u00e9ria. V tomto p\u0159\u00edkladu je to pouze restaurace \u201eJunost\u201c.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" 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: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/126b50e0f622b6e36c461cd74e708c38.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTady je hodn\u011b teorie, ale nebojte se, velmi brzy uvid\u00edme k\u00f3d.<\/p>\n<h2>Kde se pou\u017e\u00edvaj\u00ed bitmapov\u00e9 indexy?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/406132236c71a4f66ae79957b6e633b3.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPokud si \u201egoogl\u00edte\u201c bitmapov\u00e9 indexy, 90 % odpov\u011bd\u00ed bude tak \u010di onak spojeno s Oracle DB. Ale ostatn\u00ed DBMS tak\u00e9 jist\u011b podporuj\u00ed tuto skv\u011blou funkci, \u017ee? <\/p>\n<p>Projdeme si seznam hlavn\u00edch podez\u0159el\u00fdch.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/d18d66451a8a26b0ddf121f8ec0204cd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nMySQL je\u0161t\u011b nepodporuje bitmapov\u00e9 indexy, ale existuje n\u00e1vrh na p\u0159id\u00e1n\u00ed t\u00e9to 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\u00edv\u00e1 jednoduch\u00e9 bitmapy a bitov\u00e9 operace pro kombinaci v\u00fdsledk\u016f vyhled\u00e1v\u00e1n\u00ed z n\u011bkolika jin\u00fdch index\u016f.<\/p>\n<p>Tarantool m\u00e1 bitset indexy, podporuje jednoduch\u00e9 vyhled\u00e1v\u00e1n\u00ed podle nich.<\/p>\n<p>Redis m\u00e1 jednoduch\u00e9 bitov\u00e9 pole<noindex><a rel=\"nofollow\" href=\"https:\/\/redis.io\/commands\/bitfield\"> (https:\/\/redis.io\/commands\/bitfield<\/a><\/noindex>) bez mo\u017enosti vyhled\u00e1v\u00e1n\u00ed podle nich.<\/p>\n<p>MongoDB je\u0161t\u011b nepodporuje bitmapov\u00e9 indexy, ale tak\u00e9 existuje n\u00e1vrh na p\u0159id\u00e1n\u00ed t\u00e9to 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\u00edv\u00e1 bitmapy uvnit\u0159<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: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/232d335963603d6e6dec98839fc9f486.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<\/p>\n<ul>\n<li>Ale v na\u0161em dom\u011b se objevil nov\u00fd soused: Pilosa. Je to nov\u00e1 nerela\u010dn\u00ed datab\u00e1ze napsan\u00e1 v Go. Obsahuje pouze bitmapov\u00e9 indexy a v\u0161e zakl\u00e1d\u00e1 na nich. O n\u00ed si pov\u00edme trochu pozd\u011bji.\n<\/li>\n<\/ul>\n<h2>Implementace v Go<\/h2>\n<p>\nAle pro\u010d jsou bitmapov\u00e9 indexy tak vz\u00e1cn\u011b pou\u017e\u00edv\u00e1ny? Ne\u017e na tuto ot\u00e1zku odpov\u00edm, cht\u011bl bych v\u00e1m uk\u00e1zat implementaci velmi jednoduch\u00e9ho bitmapov\u00e9ho indexu v Go.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/ae7f4c1a4a740fe709b05dfaee27ac9b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nBitmapy jsou v podstat\u011b reprezentov\u00e1ny jako kusy dat. V Go si pro to ud\u011blejme pou\u017eit\u00ed slice\u016f byt\u016f.<\/p>\n<p>M\u00e1me jednu bitmapu pro jednu charakteristiku restaurace, a ka\u017ed\u00fd bit v bitmap\u011b \u0159\u00edk\u00e1, zda dan\u00e1 restaurace toto vlastnost m\u00e1 nebo nem\u00e1.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/1ab628ee15887d6b3c6c99855aa610c8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nBudeme pot\u0159ebovat dv\u011b pomocn\u00e9 funkce. Jedna se bude pou\u017e\u00edvat k napln\u011bn\u00ed na\u0161ich bitmap n\u00e1hodn\u00fdmi daty. N\u00e1hodn\u00fdmi, ale s ur\u010ditou pravd\u011bpodobnost\u00ed, \u017ee restaurace m\u00e1 ka\u017edou vlastnost. Nap\u0159\u00edklad si mysl\u00edm, \u017ee v Moskv\u011b je velmi m\u00e1lo restaurac\u00ed, kde nelze rezervovat st\u016fl, a m\u00e1m pocit, \u017ee p\u0159ibli\u017en\u011b 20 % podnik\u016f je vhodn\u00fdch pro vegetari\u00e1ny.<\/p>\n<p>Druh\u00e1 funkce p\u0159evede bitmapu na seznam restaurac\u00ed.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" 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: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/498cf7a33611d99b90197d4ee82e2834.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAbychom mohli odpov\u011bd\u011bt na dotaz \u201eZobraz mi levn\u00e9 restaurace, kter\u00e9 maj\u00ed verandu a kde lze rezervovat st\u016fl\u201c, budeme pot\u0159ebovat dv\u011b bitov\u00e9 operace: NOT a AND.<\/p>\n<p>M\u016f\u017eeme n\u00e1\u0161 k\u00f3d trochu zjednodu\u0161it pou\u017eit\u00edm slo\u017eit\u011bj\u0161\u00ed operace AND NOT.<\/p>\n<p>M\u00e1me funkce pro ka\u017edou z t\u011bchto operac\u00ed. Ob\u011b proch\u00e1zej\u00ed \u0159ezem, berou odpov\u00eddaj\u00edc\u00ed prvky z ka\u017ed\u00e9ho a kombinuj\u00ed je bitovou operac\u00ed a ukl\u00e1daj\u00ed v\u00fdsledek do v\u00fdsledn\u00e9ho \u0159ezu.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/ec5652a34f0370dfb03df199f341f153.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nA te\u010f m\u016f\u017eeme pou\u017e\u00edt na\u0161e bitmapy a funkce pro odpov\u011b\u010f na vyhled\u00e1vac\u00ed dotaz.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/cf9500ccfe75995a6008191c16729689.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nV\u00fdkon nen\u00ed tak vysok\u00fd, i kdy\u017e jsou funkce velmi jednoduch\u00e9 a u\u0161et\u0159ili jsme zna\u010dn\u00e9 mno\u017estv\u00ed prost\u0159edk\u016f t\u00edm, \u017ee jsme p\u0159i ka\u017ed\u00e9m vol\u00e1n\u00ed funkce nevraceli nov\u00fd v\u00fdsledn\u00fd \u0159ez.<\/p>\n<p>Po trochu profilov\u00e1n\u00ed s pprof jsem si v\u0161iml, \u017ee kompil\u00e1tor Go vynechal jednu velmi jednoduchou, ale velmi d\u016fle\u017eitou optimalizaci: inlining funkc\u00ed.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/9092f5ba3940d0a4f3fbfa90b364d716.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPokud jde o to, kompil\u00e1tor Go se hrozn\u011b boj\u00ed cykl\u016f, kter\u00e9 proch\u00e1zej\u00ed \u0159ezem, a kategoricky odm\u00edt\u00e1 inline funkce, kter\u00e9 obsahuj\u00ed takov\u00e9 cykly.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/d1bddd62b61b367dd1f680f223fa0ce7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAle j\u00e1 se neboj\u00edm a m\u016f\u017eu oklamat kompil\u00e1tor pou\u017eit\u00edm goto m\u00edsto cyklu, jako ve star\u00fdch dobr\u00fdch \u010dasech.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" 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: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/1ca31d12dc90931b674c6a86a4ea23bd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nA jak vid\u00edte, nyn\u00ed kompil\u00e1tor s radost\u00ed inline na\u0161i funkci! V d\u016fsledku toho se n\u00e1m poda\u0159\u00ed u\u0161et\u0159it asi 2 mikrosekundy. Nen\u00ed to \u0161patn\u00e9!<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/bdd6735d16082573e600bffe2cdd5662.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nDruhou \u00fazkou hrdlo nen\u00ed obt\u00ed\u017en\u00e9 vid\u011bt, pokud se d\u016fkladn\u011b pod\u00edv\u00e1te na assemblerov\u00fd v\u00fdstup. Kompil\u00e1tor p\u0159idal kontrolu na hranice \u0159ezu p\u0159\u00edmo dovnit\u0159 na\u0161eho nejv\u00edce pou\u017e\u00edvan\u00e9ho cyklu. To proto, \u017ee Go je bezpe\u010dn\u00fd jazyk, kompil\u00e1tor se ob\u00e1v\u00e1, \u017ee moje t\u0159i argumenty (t\u0159i \u0159ezy) maj\u00ed r\u016fznou velikost. Proto by teoreticky mohlo doj\u00edt k takzvan\u00e9mu p\u0159ete\u010den\u00ed bufferu.<\/p>\n<p>Uklidn\u011bme kompil\u00e1tor t\u00edm, \u017ee mu uk\u00e1\u017eeme, \u017ee v\u0161echny slice maj\u00ed stejnou velikost. Toho m\u016f\u017eeme dos\u00e1hnout t\u00edm, \u017ee na za\u010d\u00e1tek na\u0161\u00ed funkce p\u0159id\u00e1me jednoduchou kontrolu.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/59b4ce687a11dd653e9f12fc3130d89a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nKdy\u017e to uvid\u00ed, kompil\u00e1tor ochotn\u011b p\u0159esko\u010d\u00ed kontrolu a my t\u00edm u\u0161et\u0159\u00edme dal\u0161\u00edch 500 nanosekund.<\/p>\n<h2>Velk\u00e9 d\u00e1vky<\/h2>\n<p>\nDob\u0159e, poda\u0159ilo se n\u00e1m vyt\u00e1hnout n\u011bjak\u00fd v\u00fdkon z na\u0161\u00ed jednoduch\u00e9 implementace, ale toto je ve skute\u010dnosti mnohem hor\u0161\u00ed v\u00fdsledek, ne\u017e co je mo\u017en\u00e9 s aktu\u00e1ln\u00edm hardwarem.<\/p>\n<p>V\u0161e, co d\u011bl\u00e1me, jsou z\u00e1kladn\u00ed bitov\u00e9 operace a na\u0161e procesory je prov\u00e1d\u011bj\u00ed velmi efektivn\u011b. Bohu\u017eel ale na\u0161emu procesoru dod\u00e1v\u00e1me velmi mal\u00e9 kousky pr\u00e1ce. Na\u0161e funkce prov\u00e1d\u011bj\u00ed operace po bytech. M\u016f\u017eeme velmi snadno upravit n\u00e1\u0161 k\u00f3d tak, aby pracoval s 8-\u010dlenn\u00fdmi kusy, pomoc\u00ed slices UInt64.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/8d1b60ba4b7046c836601631cadd0b6a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nJak vid\u00edte, tato mal\u00e1 zm\u011bna zrychlila na\u0161i aplikaci osmkr\u00e1t d\u00edky zv\u00fd\u0161en\u00ed d\u00e1vky osmkr\u00e1t. Zisk je mo\u017en\u00e9 \u0159\u00edci line\u00e1rn\u00ed.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/0fc663412d04dd38b927de5c8776f69d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<h2>Implementace v assembleru<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/b3ef133167b89da983356b1c7389aecd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAle to nen\u00ed konec. Na\u0161e procesory mohou pracovat s kousky o velikosti 16, 32 a dokonce i 64 byte. Tyto `\u0161irok\u00e9` operace se naz\u00fdvaj\u00ed single instruction multiple data (SIMD; jedna instrukce, mnoho dat) a proces transformace k\u00f3du t\u00edmto zp\u016fsobem, aby pou\u017e\u00edval takov\u00e9 operace, se naz\u00fdv\u00e1 vektorizace.<\/p>\n<p>Bohu\u017eel, Go kompil\u00e1tor nen\u00ed pr\u00e1v\u011b hv\u011bzda ve vektorizaci. V sou\u010dasnosti je jedin\u00fd zp\u016fsob, jak vektorizovat k\u00f3d v Go, vz\u00edt a ru\u010dn\u011b vlo\u017eit data operac\u00ed pomoc\u00ed assembleru Go.<\/p>\n<p><img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/91278be45df67e1f9572d68fab7ebad1.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nAssembler Go je zvl\u00e1\u0161tn\u00ed zv\u00ed\u0159e. Ur\u010dit\u011b v\u00edte, \u017ee assembler je n\u011bco, co je siln\u011b v\u00e1zan\u00e9 na architekturu po\u010d\u00edta\u010de, pro kter\u00fd p\u00ed\u0161ete, ale v Go tomu tak nen\u00ed. Assembler Go je v\u00edce podobn\u00fd IRL (intermediate representation language) nebo mezijazyku: je t\u00e9m\u011b\u0159 platformov\u011b nez\u00e1visl\u00fd. Rob Pike m\u011bl skv\u011bl\u00fd <noindex><a rel=\"nofollow\" href=\"https:\/\/www.youtube.com\/watch?v=KINIAgRpkDA\">p\u0159edn\u00e1\u0161kou<\/a><\/noindex> p\u0159edn\u00e1\u0161ku na toto t\u00e9ma p\u0159ed n\u011bkolika lety na GopherCon v Denveru.<\/p>\n<p>Krom\u011b toho Go pou\u017e\u00edv\u00e1 neobvykl\u00fd form\u00e1t Plan 9, kter\u00fd se li\u0161\u00ed od uzn\u00e1van\u00fdch form\u00e1t\u016f AT&amp;T a Intel.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/526f75eb18edfc2f851f2725e9d6f69e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nS jistotou lze \u0159\u00edci, \u017ee psan\u00ed assembleru Go ru\u010dn\u011b nen\u00ed zrovna z\u00e1bavn\u00e1 \u010dinnost.<\/p>\n<p>Ale na\u0161t\u011bst\u00ed ji\u017e existuj\u00ed dva vysoce\u00farov\u0148ov\u00e9 n\u00e1stroje, kter\u00e9 n\u00e1m pom\u00e1haj\u00ed p\u0159i psan\u00ed Go assembleru: PeachPy a avo. Ob\u011b utility generuj\u00ed Go assembler z vy\u0161\u0161\u00edho k\u00f3du napsan\u00e9ho v Pythonu a Go.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/b8a7aa2c585b805e9b1f2ada186b84e8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTyto utility zjednodu\u0161uj\u00ed v\u011bci jako je alokace registr\u016f (v\u00fdb\u011br procesorov\u00e9ho registru), psan\u00ed smy\u010dek a celkov\u011b usnad\u0148uj\u00ed vstup do sv\u011bta assemblerov\u00e9ho programov\u00e1n\u00ed v Go.<\/p>\n<p>Budeme pou\u017e\u00edvat avo, tak\u017ee na\u0161e programy budou t\u00e9m\u011b\u0159 b\u011b\u017en\u00fdmi programy v Go.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/128e4adef14e5f2cf00fb5b6302ef58e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTakto vypad\u00e1 ten nejjednodu\u0161\u0161\u00ed p\u0159\u00edklad programu v avo. M\u00e1me funkci main(), kter\u00e1 definuje uvnit\u0159 sebe funkci Add(), jej\u00edm\u017e smyslem je se\u010d\u00edst dv\u011b \u010d\u00edsla. Zde jsou pomocn\u00e9 funkce pro z\u00edsk\u00e1n\u00ed parametr\u016f podle jm\u00e9na a pro z\u00edsk\u00e1n\u00ed jednoho z voln\u00fdch a vhodn\u00fdch procesorov\u00fdch registr\u016f. Ka\u017ed\u00e1 procesorov\u00e1 operace m\u00e1 odpov\u00eddaj\u00edc\u00ed funkci v avo, jak ukazuje ADDQ. A nakonec vid\u00edme pomocnou funkci pro ulo\u017een\u00ed v\u00fdsledn\u00e9 hodnoty.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/01ccaa6aa6d394ef598ea2dbc9257d87.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nZavol\u00e1n\u00edm go generate spust\u00edme program v avo a nakonec budou vygenerov\u00e1ny dva soubory:<\/p>\n<ul>\n<li>add.s s v\u00fdsledn\u00fdm k\u00f3dem v Go-assembleru;\n<\/li>\n<li>stub.go s hlavi\u010dkami funkc\u00ed pro propojen\u00ed dvou sv\u011bt\u016f: Go a assembleru.\n<\/li>\n<\/ul>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/72a9443776ecf45eef6fb97a4e08acba.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nNyn\u00ed, kdy\u017e jsme vid\u011bli, co a jak d\u011bl\u00e1 avo, pod\u00edvejme se na na\u0161e funkce. Implementoval jsem jak skal\u00e1rn\u00ed, tak vektorov\u00e9 (SIMD) verze funkc\u00ed.<\/p>\n<p>Nejprve se pod\u00edvejme na skal\u00e1rn\u00ed verze.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/ec31dbb8b97b9d7c1012a120fa18cdaf.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nStejn\u011b jako v p\u0159edchoz\u00edm p\u0159\u00edkladu, \u017e\u00e1d\u00e1me o poskytov\u00e1n\u00ed voln\u00e9ho a spr\u00e1vn\u00e9ho registru obecn\u00e9ho pou\u017eit\u00ed, nemus\u00edme po\u010d\u00edtat posuny a velikosti argument\u016f. To v\u0161echno avo d\u011bl\u00e1 za n\u00e1s.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/88085e927dd943ea0f808a28fb3ccf9b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nD\u0159\u00edve jsme pou\u017e\u00edvali labely a goto (nebo skoky) pro zlep\u0161en\u00ed v\u00fdkonu a abychom oklamali kompil\u00e1tor Go, ale nyn\u00ed to d\u011bl\u00e1me od za\u010d\u00e1tku. Jde o to, \u017ee smy\u010dky jsou vysoce\u00farov\u0148ov\u00fd pojem. V assembleru m\u00e1me pouze labely a skoky.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/9a4181248eb279d89c1445a820b06649.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nZbytek k\u00f3du by m\u011bl b\u00fdt ji\u017e zn\u00e1m\u00fd a srozumiteln\u00fd. Emulujeme smy\u010dku pomoc\u00ed label\u016f a skok\u016f, vezmeme mal\u00fd kousek dat z na\u0161ich dvou \u0159ez\u016f, slou\u010d\u00edme je bitovou operac\u00ed (AND NOT v tomto p\u0159\u00edpad\u011b) a pot\u00e9 ulo\u017e\u00edme v\u00fdsledek do v\u00fdsledn\u00e9ho \u0159ezu. To je v\u0161echno.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/19275ead27f63092fc6596bed38a8d03.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTakto vypad\u00e1 fin\u00e1ln\u00ed k\u00f3d v assembleru. Nemuseli jsme po\u010d\u00edtat posuny a velikosti (vyzna\u010deno zelen\u011b) ani sledovat pou\u017e\u00edvan\u00e9 registry (vyzna\u010deno \u010derven\u011b).<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/ed68528a6f852634a5b536670c6315f0.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPokud porovn\u00e1me v\u00fdkon implementace v assembleru s v\u00fdkonem nejlep\u0161\u00ed implementace v Go, vid\u00edme, \u017ee jsou si rovny. A to je o\u010dek\u00e1van\u00e9. Nic zvl\u00e1\u0161tn\u00edho jsme ned\u011blali \u2013 pouze jsme reprodukovali to, co by d\u011blal kompil\u00e1tor Go.<\/p>\n<p>Bohu\u017eel nedok\u00e1\u017eeme donutit kompil\u00e1tor, aby naimplementoval na\u0161e funkce napsan\u00e9 v assembleru. Go-kompil\u00e1tor tuto mo\u017enost v sou\u010dasnosti nem\u00e1, p\u0159esto\u017ee \u017e\u00e1dost o jej\u00ed p\u0159id\u00e1n\u00ed existuje u\u017e docela dlouho.<\/p>\n<p>A pr\u00e1v\u011b proto nelze z\u00edskat \u017e\u00e1dn\u00e9 v\u00fdhody z mal\u00fdch funkc\u00ed v assembleru. Mus\u00edme bu\u010f ps\u00e1t velk\u00e9 funkce, nebo pou\u017e\u00edt nov\u00fd bal\u00ed\u010dek math\/bits, nebo se vyhnout assembleru.<\/p>\n<p>Te\u010f se pod\u00edvejme na vektorov\u00e9 verze na\u0161ich funkc\u00ed.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/7f67c3cc855908fb47c7900d6e5d7f54.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPro tento p\u0159\u00edklad jsem se rozhodl pou\u017e\u00edt AVX2, a proto budeme pou\u017e\u00edvat operace pracuj\u00edc\u00ed se 32-bajtov\u00fdmi bloky. Struktura k\u00f3du je velmi podobn\u00e1 skal\u00e1rn\u00ed variant\u011b: na\u010d\u00edt\u00e1n\u00ed parametr\u016f, \u017e\u00e1dost o uvoln\u011bn\u00fd spole\u010dn\u00fd registr atd.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/021e0424a0d733ec7db9edeb98ce1f65.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nJednou z novinek je, \u017ee \u0161ir\u0161\u00ed vektorov\u00e9 operace pou\u017e\u00edvaj\u00ed speci\u00e1ln\u00ed \u0161irok\u00e9 registry. V p\u0159\u00edpad\u011b 32-bajtov\u00fdch blok\u016f jsou to registry s prefixem Y. Proto v k\u00f3du vid\u00edte funkci YMM(). Kdybych pou\u017eil AVX-512 s 64-bitov\u00fdmi bloky, pak by prefix byl Z.<\/p>\n<p>Druh\u00e1 novinka se t\u00fdk\u00e1 toho, \u017ee jsem se rozhodl pou\u017e\u00edt optimalizaci zvanou rozbalov\u00e1n\u00ed cyklu, tj. prov\u00e9st osm operac\u00ed cyklu ru\u010dn\u011b, ne\u017e sko\u010d\u00edm na za\u010d\u00e1tek cyklu. Tato optimalizace sni\u017euje po\u010det branch\u016f (v\u011btven\u00ed) v k\u00f3du a je omezena po\u010dtem voln\u00fdch registr\u016f, kter\u00e9 jsou k dispozici.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/f54631d9e8c69f6f70ecace3133ae1e8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nA co v\u00fdkon? Je skv\u011bl\u00fd! Dos\u00e1hli jsme zrychlen\u00ed p\u0159ibli\u017en\u011b sedmkr\u00e1t oproti nejlep\u0161\u00ed variant\u011b v Go. P\u016fsobiv\u00e9, \u017ee?<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/d7e85c933eecb243cfb49225b4d92c6c.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAle i tuto implementaci by bylo mo\u017en\u00e9 potenci\u00e1ln\u011b zrychlit vyu\u017eit\u00edm AVX-512, p\u0159edna\u010d\u00edt\u00e1n\u00edm nebo JIT (just-in-time compiler) pro pl\u00e1nova\u010d dotaz\u016f. To u\u017e ale ur\u010dit\u011b pat\u0159\u00ed do samostatn\u00e9ho skl\u00e1d\u00e1n\u00ed.<\/p>\n<h2>Probl\u00e9my bitmapov\u00fdch index\u016f<\/h2>\n<p>\nTe\u010f, kdy\u017e jsme u\u017e prozkoumali jednoduchou implementaci bitmapov\u00e9ho indexu v Go a mnohem v\u00fdkonn\u011bj\u0161\u00ed verzi v assembleru, poj\u010fme kone\u010dn\u011b mluvit o tom, pro\u010d se bitmapov\u00e9 indexy pou\u017e\u00edvaj\u00ed tak z\u0159\u00eddka.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/83d36a5c92ba90fd680fe8afb6cfc11f.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nVe star\u00fdch v\u011bdeck\u00fdch prac\u00edch se zmi\u0148uj\u00ed t\u0159i probl\u00e9my bitmapov\u00fdch index\u016f, ale nov\u011bj\u0161\u00ed v\u011bdeck\u00e9 pr\u00e1ce a j\u00e1 tvrd\u00edme, \u017ee jsou ji\u017e neaktu\u00e1ln\u00ed. Nebudeme se do ka\u017ed\u00e9ho z t\u011bchto probl\u00e9m\u016f pono\u0159ovat do hloubky, ale povrchn\u011b je zv\u00e1\u017e\u00edme.<\/p>\n<h2>Probl\u00e9m vysok\u00e9 kardin\u00e1lnosti<\/h2>\n<p>\nTak\u017ee n\u00e1m \u0159\u00edkaj\u00ed, \u017ee bitmapov\u00e9 indexy jsou vhodn\u00e9 pouze pro pole s n\u00edzkou kardin\u00e1lnost\u00ed, tedy takov\u00e1, kter\u00e1 maj\u00ed m\u00e1lo hodnot (nap\u0159\u00edklad pohlav\u00ed nebo barva o\u010d\u00ed), a d\u016fvodem je, \u017ee b\u011b\u017en\u00e9 zobrazen\u00ed takov\u00fdch pol\u00ed (jeden bit na hodnotu) v p\u0159\u00edpad\u011b vysok\u00e9 kardin\u00e1lnosti zabere p\u0159\u00edli\u0161 mnoho m\u00edsta a nav\u00edc budou tyto bitmapov\u00e9 indexy slab\u011b (z\u0159\u00eddka) zapln\u011bny.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" 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: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/44ab4bc7c25d14fe2f53caf5d9da399d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nN\u011bkdy m\u016f\u017eeme pou\u017e\u00edt jin\u00e9 zobrazen\u00ed, nap\u0159\u00edklad standardn\u00ed, kter\u00e9 pou\u017e\u00edv\u00e1me pro reprezentaci \u010d\u00edsel. Ale pr\u00e1v\u011b vznik kompresn\u00edch algoritm\u016f v\u0161echno zm\u011bnil. V posledn\u00edch desetilet\u00edch vymysleli v\u011bdci a v\u00fdzkumn\u00edci \u0159adu kompresn\u00edch algoritm\u016f pro bitmapy. Jejich hlavn\u00ed v\u00fdhodou je, \u017ee nen\u00ed nutn\u00e9 dekomprimovat bitmapy pro prov\u00e1d\u011bn\u00ed bitov\u00fdch operac\u00ed \u2014 m\u016f\u017eeme prov\u00e1d\u011bt bitov\u00e9 operace p\u0159\u00edmo na komprimovan\u00fdch bitmap\u00e1ch.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/ecb54fbf15aa11271bbbab01ecbda880.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nV posledn\u00ed dob\u011b se objevuj\u00ed tak\u00e9 hybridn\u00ed p\u0159\u00edstupy, jako nap\u0159\u00edklad roaring bitmapy. Ty pou\u017e\u00edvaj\u00ed sou\u010dasn\u011b t\u0159i r\u016fzn\u00e1 zobrazen\u00ed pro bitmapy \u2014 vlastn\u011b bitmapy, pole a takzvan\u00e9 bit runs \u2014 a balancuj\u00ed mezi nimi, aby maximalizovaly v\u00fdkon a minimalizovaly spot\u0159ebu pam\u011bti.<\/p>\n<p>M\u016f\u017eete se setkat s roaring bitmapami v nejobl\u00edben\u011bj\u0161\u00edch aplikac\u00edch. Ji\u017e existuje velk\u00e9 mno\u017estv\u00ed implementac\u00ed pro r\u016fzn\u00e9 programovac\u00ed jazyky, v\u010detn\u011b v\u00edce ne\u017e t\u0159ech implementac\u00ed pro Go.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/de2adfebc431ff48c996247b453f02ae.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nDal\u0161\u00ed p\u0159\u00edstup, kter\u00fd n\u00e1m m\u016f\u017ee pomoci vypo\u0159\u00e1dat se s vysokou kardin\u00e1lnost\u00ed, se naz\u00fdv\u00e1 skupinov\u00e1n\u00ed (binning). P\u0159edstavte si, \u017ee m\u00e1te pole, kter\u00e9 p\u0159edstavuje v\u00fd\u0161ku \u010dlov\u011bka. V\u00fd\u0161ka je \u010d\u00edslo s plovouc\u00ed desetinnou \u010d\u00e1rkou, ale my, lid\u00e9, na to takto nep\u0159em\u00fd\u0161l\u00edme. Pro n\u00e1s nen\u00ed rozd\u00edl mezi v\u00fd\u0161kou 185,2 cm a 185,3 cm.<\/p>\n<p>Tedy m\u016f\u017eeme seskupit podobn\u00e9 hodnoty do skupin v rozsahu 1 cm.<\/p>\n<p>A pokud je\u0161t\u011b v\u00edme, \u017ee velmi m\u00e1lo lid\u00ed m\u00e1 v\u00fd\u0161ku pod 50 cm a nad 250 cm, m\u016f\u017eeme v podstat\u011b prom\u011bnit pole s nekone\u010dnou kardin\u00e1lnost\u00ed na pole s kardin\u00e1lnost\u00ed p\u0159ibli\u017en\u011b 200 hodnot.<\/p>\n<p>Samoz\u0159ejm\u011b, pokud bude pot\u0159eba, m\u016f\u017eeme prov\u00e9st dal\u0161\u00ed filtrov\u00e1n\u00ed i pozd\u011bji.<\/p>\n<h2>Probl\u00e9m s velk\u00fdm pr\u016fchodem<\/h2>\n<p>\nDal\u0161\u00ed probl\u00e9m bitmapov\u00fdch index\u016f spo\u010d\u00edv\u00e1 v tom, \u017ee jejich aktualizace m\u016f\u017ee b\u00fdt velmi n\u00e1kladn\u00e1.<\/p>\n<p>Datab\u00e1ze mus\u00ed umo\u017e\u0148ovat aktualizaci dat v okam\u017eiku, kdy potenci\u00e1ln\u011b stovky dal\u0161\u00edch po\u017eadavk\u016f prov\u00e1d\u011bj\u00ed dotazy na tato data. Pot\u0159ebujeme z\u00e1mky, abychom se vyhnuli probl\u00e9m\u016fm s konkuren\u010dn\u00edm p\u0159\u00edstupem k dat\u016fm nebo jin\u00fdm probl\u00e9m\u016fm sd\u00edlen\u00e9ho p\u0159\u00edstupu. A tam, kde je jeden velk\u00fd z\u00e1mek, tam je probl\u00e9m \u2013 \u201elock contention\u201c, kdy se tento z\u00e1mek st\u00e1v\u00e1 \u00fazk\u00fdm m\u00edstem.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/0ae1bf925542d286f8b7b245c160a35e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nTento probl\u00e9m lze vy\u0159e\u0161it nebo obej\u00edt pomoc\u00ed shardingu nebo pou\u017eit\u00ed verzionovan\u00fdch index\u016f.<\/p>\n<p>Sharding je jednoduch\u00e1 a b\u011b\u017en\u011b zn\u00e1m\u00e1 v\u011bc. M\u016f\u017eete shardovat bitmapov\u00fd index stejn\u011b, jako byste shardovali jak\u00e1koli jin\u00e1 data. M\u00edsto jednoho velk\u00e9ho z\u00e1mku dostanete spoustu mal\u00fdch z\u00e1mk\u016f a t\u00edm se zbav\u00edte lock contention.<\/p>\n<p>Druh\u00fd zp\u016fsob, jak vy\u0159e\u0161it probl\u00e9m, spo\u010d\u00edv\u00e1 v pou\u017eit\u00ed verzionovan\u00fdch index\u016f. M\u016f\u017eete m\u00edt jednu kopii indexu, kterou pou\u017e\u00edv\u00e1te pro vyhled\u00e1v\u00e1n\u00ed nebo \u010dten\u00ed, a jednu \u2013 pro z\u00e1pis nebo aktualizaci. A jednou za ur\u010dit\u00e9 obdob\u00ed (nap\u0159\u00edklad ka\u017ed\u00fdch 100 ms nebo 500 ms) je duplikujete a vym\u011bn\u00edte. Tento p\u0159\u00edstup se samoz\u0159ejm\u011b uplat\u0148uje pouze v p\u0159\u00edpadech, kdy va\u0161e aplikace m\u016f\u017ee pracovat s m\u00edrn\u011b opozdil\u00fdm vyhled\u00e1vac\u00edm indexem.<\/p>\n<p>Tyto dva p\u0159\u00edstupy lze pou\u017e\u00edt sou\u010dasn\u011b: m\u016f\u017eete m\u00edt shardovan\u00fd verzionovan\u00fd index.<\/p>\n<h2>Slo\u017eit\u011bj\u0161\u00ed dotazy<\/h2>\n<p>Posledn\u00ed probl\u00e9m bitmapov\u00fdch index\u016f spo\u010d\u00edv\u00e1 v tom, \u017ee, jak n\u00e1m \u0159\u00edkaj\u00ed, nejsou p\u0159\u00edli\u0161 vhodn\u00e9 pro slo\u017eit\u011bj\u0161\u00ed typy dotaz\u016f, nap\u0159\u00edklad dotazy \u201ev rozmez\u00ed\u201c.<\/p>\n<p>A skute\u010dn\u011b, pokud o tom p\u0159em\u00fd\u0161l\u00edme, bitov\u00e9 operace typu AND, OR apod. nejsou p\u0159\u00edli\u0161 vhodn\u00e9 pro dotazy ala \u201eUka\u017ete mi hotely s cenou pokoje od 200 do 300 dolar\u016f za noc\u201c.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/7bc2e129cad46fb5875c2b3018c39ff7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nNaivn\u00edm a velmi nerozumn\u00fdm \u0159e\u0161en\u00edm by bylo vz\u00edt v\u00fdsledky pro ka\u017edou dolarovou hodnotu a slou\u010dit je bitovou operac\u00ed OR.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/b9f8fc7945caa1866f8e0cfa8a04bd98.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nO n\u011bco spr\u00e1vn\u011bj\u0161\u00edm \u0159e\u0161en\u00edm by bylo pou\u017e\u00edvat skupiny. Nap\u0159\u00edklad ve skupin\u00e1ch po 50 dolarech. To by urychlilo n\u00e1\u0161 proces 50kr\u00e1t.<\/p>\n<p>Ale probl\u00e9m je tak\u00e9 snadno \u0159e\u0161iteln\u00fd pou\u017eit\u00edm reprezentace vytvo\u0159en\u00e9 speci\u00e1ln\u011b pro tento typ dotaz\u016f. V odborn\u00fdch prac\u00edch se tomu \u0159\u00edk\u00e1 range-encoded bitmaps.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/644a420628b21f220a7af1ff15c4031f.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nV takov\u00e9 reprezentaci nenastavujeme jen jeden bit pro n\u011bjakou hodnotu (nap\u0159\u00edklad 200), ale nastavujeme tuto hodnotu a v\u0161echno, co je nad n\u00ed. 200 a v\u00fd\u0161e. Tot\u00e9\u017e plat\u00ed pro 300: 300 a v\u00fd\u0161e. A tak d\u00e1le.<\/p>\n<p>Pou\u017eit\u00edm t\u00e9to reprezentace m\u016f\u017eeme odpov\u011bd\u011bt na takov\u00fdto typ vyhled\u00e1vac\u00edho dotazu, projdeme indexem pouze dvakr\u00e1t. Nejprve z\u00edsk\u00e1me seznam hotel\u016f, kde cena pokoje je ni\u017e\u0161\u00ed ne\u017e 300 dolar\u016f, a pot\u00e9 vy\u0159ad\u00edme ty, kde cena pokoje je ni\u017e\u0161\u00ed ne\u017e 199 dolar\u016f. Hotovo.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/cc2bb58d7d7a51495c62ec7da81e2d12.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nBudete se divit, ale dokonce i geo-dotazy jsou mo\u017en\u00e9 za pou\u017eit\u00ed bitmapov\u00fdch index\u016f. Z\u00e1sadn\u00ed je pou\u017e\u00edt geo-representaci, kter\u00e1 obklopuje va\u0161i sou\u0159adnici geometrickou figurou. Nap\u0159\u00edklad S2 od Googlu. Figurku mus\u00ed b\u00fdt mo\u017en\u00e9 p\u0159edstavit ve form\u011b t\u0159\u00ed nebo v\u00edce vz\u00e1jemn\u011b se k\u0159\u00ed\u017e\u00edc\u00edch p\u0159\u00edmek, kter\u00e9 lze o\u010d\u00edslovat. T\u00edmto zp\u016fsobem budeme moci p\u0159ev\u00e9st n\u00e1\u0161 geo-dotaz na n\u011bkolik dotaz\u016f \u201ev rozmez\u00ed\u201c (podle t\u011bchto o\u010d\u00edslovan\u00fdch \u010dar).<\/p>\n<h2>Hotov\u00e1 \u0159e\u0161en\u00ed<\/h2>\n<p>\nDouf\u00e1m, \u017ee jsem v\u00e1s trochu zaujal a \u017ee jste do sv\u00e9ho arzen\u00e1lu p\u0159idali je\u0161t\u011b jeden u\u017eite\u010dn\u00fd n\u00e1stroj. Pokud budete n\u011bkdy pot\u0159ebovat ud\u011blat n\u011bco podobn\u00e9ho, budete v\u011bd\u011bt, kter\u00fdm sm\u011brem se pod\u00edvat.<\/p>\n<p>Nicm\u00e9n\u011b ne ka\u017ed\u00fd m\u00e1 \u010das, trp\u011blivost a zdroje, aby vytvo\u0159il bitmapov\u00e9 indexy od nuly. Zvl\u00e1\u0161\u0165 ty pokro\u010dilej\u0161\u00ed, vyu\u017e\u00edvaj\u00edc\u00ed SIMD nap\u0159\u00edklad.<\/p>\n<p>Na\u0161t\u011bst\u00ed existuje n\u011bkolik p\u0159ipraven\u00fdch \u0159e\u0161en\u00ed, kter\u00e9 v\u00e1m mohou pomoci.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/817b47cb189a758756b602ec9cf319e1.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<h2>Roaring bitmaps<\/h2>\n<p>\nZa prv\u00e9, je tu ta ona knihovna roaring bitmaps, o kter\u00e9 jsem ji\u017e hovo\u0159il. Obsahuje v\u0161echny pot\u0159ebn\u00e9 kontejnery a bitov\u00e9 operace, kter\u00e9 budete pot\u0159ebovat k vytvo\u0159en\u00ed plnohodnotn\u00e9ho bitmapov\u00e9ho indexu.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/57f61a51485c174666b52dc2063fabe8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nBohu\u017eel v sou\u010dasnosti \u017e\u00e1dn\u00e1 z Go implementac\u00ed nevyu\u017e\u00edv\u00e1 SIMD, co\u017e znamen\u00e1, \u017ee Go implementace jsou m\u00e9n\u011b v\u00fdkonn\u00e9 ne\u017e implementace na C nap\u0159\u00edklad.<\/p>\n<h2>Pilosa<\/h2>\n<p>\nDal\u0161\u00ed produkt, kter\u00fd v\u00e1m m\u016f\u017ee pomoci, je datab\u00e1zov\u00fd syst\u00e9m Pilosa, kter\u00fd v podstat\u011b pracuje pouze s bitmapov\u00fdmi indexy. Je to relativn\u011b nov\u00e9 \u0159e\u0161en\u00ed, ale rychle si z\u00edsk\u00e1v\u00e1 srdce u\u017eivatel\u016f.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/d3870a979e1e73d093fe5d5e9bb71cd8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPilosa uvnit\u0159 sebe vyu\u017e\u00edv\u00e1 roaring bitmaps a d\u00e1v\u00e1 v\u00e1m mo\u017enost je pou\u017e\u00edt, zjednodu\u0161uje a vysv\u011btluje v\u0161echny ty v\u011bci, o kter\u00fdch jsem mluvil v\u00fd\u0161e: agregaci, range-encoded bitmaps, pojem pole atd.<\/p>\n<p>Rychle se pod\u00edvejme na p\u0159\u00edklad pou\u017eit\u00ed Pilosa k odpov\u011bdi na ot\u00e1zku, kterou u\u017e zn\u00e1te.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/dfee7abfd653cc19d9aa8b64c64f3e4e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nP\u0159\u00edklad je velmi podobn\u00fd tomu, co jste vid\u011bli d\u0159\u00edve. Vytv\u00e1\u0159\u00edme klienta pro server Pilosa, vytv\u00e1\u0159\u00edme index a pot\u0159ebn\u00e1 pole, pot\u00e9 zapl\u0148ujeme na\u0161e pole n\u00e1hodn\u00fdmi daty s pravd\u011bpodobnostmi a nakonec prov\u00e1d\u00edme zn\u00e1m\u00fd dotaz.<\/p>\n<p>Pot\u00e9 pou\u017e\u00edv\u00e1me NOT na pole \u201eexpensive\u201c, n\u00e1sledn\u011b propoj\u00edme v\u00fdsledek (nebo AND) s polem \u201eterrace\u201c a s polem \u201ereservations\u201c. A nakonec z\u00edsk\u00e1v\u00e1me z\u00e1v\u011bre\u010dn\u00fd v\u00fdsledek.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/8d66c6d68019c2297b6c15b700f06a3a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nOpravdu douf\u00e1m, \u017ee v dohledn\u00e9 dob\u011b se v datab\u00e1z\u00edch jako MySQL a PostgreSQL tak\u00e9 objev\u00ed tento nov\u00fd typ index\u016f \u2014 bitmapov\u00e9 indexy.<br \/>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/7a8e33d576c7fb6376a173ee038b4206.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<h2>Z\u00e1v\u011br<\/h2>\n<p>\n<img decoding=\"async\" alt=\"Bitmapov\u00e9 indexy v Go: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed\" src=\"\/wp-content\/uploads\/2019\/05\/c62caa9ad6f2d96056c80326f4fa9a0d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPokud jste je\u0161t\u011b neusnuli, d\u011bkuji. Musel jsem se ve zhruba dotknout mnoha t\u00e9mat z d\u016fvodu \u010dasov\u00e9ho omezen\u00ed, ale douf\u00e1m, \u017ee byl m\u016fj p\u0159\u00edsp\u011bvek u\u017eite\u010dn\u00fd a mo\u017en\u00e1 i motivuj\u00edc\u00ed.<\/p>\n<p>O bitmapov\u00fdch indexech je dobr\u00e9 m\u00edt p\u0159ehled, i kdy\u017e je aktu\u00e1ln\u011b nepot\u0159ebujete. A\u0165 jsou dal\u0161\u00edm n\u00e1strojem ve va\u0161\u00ed v\u00fdbav\u011b.<\/p>\n<p>Prozkoumali jsme r\u016fzn\u00e9 triky ke zv\u00fd\u0161en\u00ed v\u00fdkonu pro Go a v\u011bci, s nimi\u017e si kompil\u00e1tor Go zat\u00edm p\u0159\u00edli\u0161 dob\u0159e neporad\u00ed. A to je rozhodn\u011b n\u011bco, co by m\u011bl zn\u00e1t ka\u017ed\u00fd program\u00e1tor v Go.<\/p>\n<p>To je v\u0161e, co jsem cht\u011bl \u0159\u00edct. D\u011bkuji!<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.3 - 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\/cs\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti\" \/>\n\t\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.3\" \/>\n\t\t<meta property=\"og:locale\" content=\"cs_CZ\" \/>\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\/cs\/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: vyhled\u00e1v\u00e1n\u00ed neuv\u011b\u0159itelnou rychlost\u00ed | ProHoster","description":"\u00davodn\u00ed slovo P\u0159edstavil jsem.","canonical_url":"https:\/\/prohoster.info\/cs\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"cs_CZ","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\/cs\/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\/cs\/wp-json\/wp\/v2\/posts\/33793","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/comments?post=33793"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/posts\/33793\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/media\/25469"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/media?parent=33793"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/categories?post=33793"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/cs\/wp-json\/wp\/v2\/tags?post=33793"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}