{"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\/pt\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti","title":{"rendered":"\u00cdndices Bitmap em Go: busca em alta velocidade","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"<p><img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/86ef928e6741022b2c0e5885a031408a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<\/p>\n<h2>Palavra de abertura<\/h2>\n<p>\nEu fiz esta apresenta\u00e7\u00e3o em ingl\u00eas na confer\u00eancia GopherCon Russia 2019 em Moscovo e em russo \u2014 no meetup em Nizhny Novgorod. A palestra fala sobre o \u00edndice bitmap \u2014 menos comum que o B-tree, mas igualmente interessante. Estou compartilhando <noindex><a rel=\"nofollow\" href=\"https:\/\/youtu.be\/WvlUH6MjUuI?list=PL3xVZC4USRNSO_kb2lh_J_no6C-KJ7Phg\">a grava\u00e7\u00e3o<\/a><\/noindex> da apresenta\u00e7\u00e3o na confer\u00eancia em ingl\u00eas e a transcri\u00e7\u00e3o em texto em russo.<\/p>\n<p>Vamos examinar como funciona o \u00edndice bitmap, quando ele \u00e9 melhor, quando \u00e9 pior do que outros \u00edndices e em quais casos \u00e9 significativamente mais r\u00e1pido; veremos em quais SGBDs populares j\u00e1 existem \u00edndices bitmap; tentaremos escrever o nosso em Go. E como 'sobremesa', usaremos bibliotecas prontas para criar nosso banco de dados especializado super r\u00e1pido.<\/p>\n<p>Espero sinceramente que meu trabalho seja \u00fatil e interessante para voc\u00eas. Vamos l\u00e1!<br \/>\n<noindex><a rel=\"nofollow\" name=\"habracut\"><\/a><\/noindex><\/p>\n<h2>Introdu\u00e7\u00e3o<\/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=\"Por que no hosting comum a administra\u00e7\u00e3o do PrestaShop \u00e9 lenta, e no seu n\u00e3o \u00e9?\" 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>Ol\u00e1 a todos! Agora s\u00e3o seis da tarde, todos estamos super cansados. Um momento maravilhoso para falar sobre a chata teoria dos \u00edndices de bancos de dados, n\u00e9? N\u00e3o se preocupem, vou ter algumas linhas de c\u00f3digo aqui e ali. \ud83d\ude42<\/p>\n<p>Brincadeiras \u00e0 parte, a apresenta\u00e7\u00e3o est\u00e1 repleta de informa\u00e7\u00f5es e temos pouco tempo. Ent\u00e3o, vamos come\u00e7ar.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/e778e13727700f0335a4b5558a0d8db3.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nHoje eu vou falar sobre o seguinte:<\/p>\n<ul>\n<li>o que s\u00e3o \u00edndices;\n<\/li>\n<li>o que \u00e9 um \u00edndice bitmap;\n<\/li>\n<li>onde ele \u00e9 usado e onde ele N\u00c3O \u00e9 usado e por qu\u00ea;\n<\/li>\n<li>uma implementa\u00e7\u00e3o simples em Go e um pouco de luta com o compilador;\n<\/li>\n<li>uma implementa\u00e7\u00e3o um pouco menos simples, mas muito mais eficiente em Go-assembly;\n<\/li>\n<li>os 'problemas' dos \u00edndices bitmap;\n<\/li>\n<li>implementa\u00e7\u00f5es existentes.\n<\/li>\n<\/ul>\n<h2>Ent\u00e3o, o que s\u00e3o \u00edndices?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/b80e5b990c44814afe9150a9a82351fd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nUm \u00edndice \u00e9 uma estrutura de dados separada que mantemos e atualizamos al\u00e9m dos dados principais. Ele \u00e9 usado para acelerar a busca. Sem \u00edndices, a busca exigiria uma varredura completa dos dados (processo chamado de full scan), e esse processo tem complexidade algor\u00edtmica linear. Mas os bancos de dados costumam conter uma enorme quantidade de dados e a complexidade linear \u00e9 demasiado lenta. Idealmente, gostar\u00edamos de obter uma complexidade logar\u00edtmica ou constante.<\/p>\n<p>Este \u00e9 um tema enorme e complexo, repleto de sutilezas e compromissos, mas, ap\u00f3s anos de desenvolvimento e pesquisa de v\u00e1rios bancos de dados, estou preparado para afirmar que existem apenas algumas abordagens amplamente utilizadas para a cria\u00e7\u00e3o de \u00edndices de bancos de dados.<\/p>\n<p><img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/08a74dbb365035cd99bc94d72644a1b7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nA primeira abordagem consiste em reduzir hierarquicamente o espa\u00e7o de busca, dividindo a \u00e1rea de pesquisa em partes menores.<\/p>\n<p>Normalmente, fazemos isso usando diferentes tipos de \u00e1rvores. Um exemplo pode ser uma grande caixa com materiais em seu arm\u00e1rio, que cont\u00e9m caixas menores com materiais organizados por diferentes temas. Se voc\u00ea precisa de materiais, certamente ir\u00e1 procurar na caixa marcada \"Materiais\", e n\u00e3o na que diz \"Biscoitos\", certo?<\/p>\n<p><img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/423fac47c748980b18af434644af4dae.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nA segunda abordagem consiste em destacar imediatamente o elemento ou grupo de elementos desejados. Fazemos isso em hash maps ou em \u00edndices invertidos. O uso de hash maps \u00e9 muito semelhante ao exemplo anterior, exceto que, em vez de uma caixa com caixas, voc\u00ea tem no seu arm\u00e1rio uma pilha de pequenas caixas com itens finais.<\/p>\n<p><img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/088fed0a2a0feea4a23edbf0ca654805.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nA terceira abordagem \u00e9 eliminar a necessidade de busca. Fazemos isso com filtros Bloom ou filtros cuckoo. Os primeiros fornecem respostas instantaneamente, livrando voc\u00ea da necessidade de realizar uma busca.<\/p>\n<p><img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/493bc4f20baacc0a5dc0faf15cc46285.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nA \u00faltima abordagem consiste em aproveitar ao m\u00e1ximo todo o poder que a tecnologia moderna nos oferece. \u00c9 exatamente isso que fazemos em \u00edndices bitmap. Sim, ao us\u00e1-los, \u00e0s vezes precisamos percorrer todo o \u00edndice, mas fazemos isso de forma super eficiente.<\/p>\n<p>Como eu j\u00e1 disse, o tema dos \u00edndices de banco de dados \u00e9 amplo e repleto de compromissos. Isso significa que, \u00e0s vezes, podemos usar v\u00e1rias abordagens ao mesmo tempo: se precisarmos acelerar ainda mais a busca ou se for necess\u00e1rio cobrir todos os tipos poss\u00edveis de pesquisa.<\/p>\n<p>Hoje, falarei sobre a abordagem menos conhecida das mencionadas \u2014 os \u00edndices bitmap.<\/p>\n<h2>Quem sou eu para falar sobre este assunto?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/42a9d17a507c392bc202254a92dfaf41.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nEu trabalho como l\u00edder de equipe na Badoo (talvez voc\u00ea conhe\u00e7a melhor nosso outro produto \u2014 Bumble). Temos mais de 400 milh\u00f5es de usu\u00e1rios em todo o mundo e muitas funcionalidades que se dedicam a encontrar a melhor combina\u00e7\u00e3o para eles. Fazemos isso com servi\u00e7os personalizados, que utilizam, inclusive, \u00edndices bitmap.<\/p>\n<h2>Ent\u00e3o, o que \u00e9 um \u00edndice bitmap?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/14f20f3697a20c02f6b3510dc7f0ae4d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nOs \u00edndices bitmap, como o pr\u00f3prio nome sugere, utilizam bitmaps ou bitsets para implementar um \u00edndice de pesquisa. De uma perspectiva geral, esse \u00edndice consiste em um ou mais desses bitmaps, representando entidades (como pessoas) e suas propriedades ou par\u00e2metros (idade, cor dos olhos, etc.), al\u00e9m de um algoritmo que usa opera\u00e7\u00f5es bit a bit (AND, OR, NOT) para responder a consultas de busca.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/f815720330a51b1f0798e45d23160d3b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nDizem que os \u00edndices bitmap s\u00e3o mais adequados e extremamente eficazes para casos em que h\u00e1 busca que combina consultas em v\u00e1rias colunas com baixa cardinalidade (imagine 'cor dos olhos' ou 'estado civil' em compara\u00e7\u00e3o a algo como 'dist\u00e2ncia do centro da cidade'). Mas mais adiante, vou mostrar que eles funcionam muito bem tamb\u00e9m com colunas de alta cardinalidade.<\/p>\n<p>Vamos considerar um exemplo simples de um \u00edndice bitmap.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/33fe23476e0931c10345d7175b83d68b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nImagine que temos uma lista de restaurantes em Moscovo com propriedades bin\u00e1rias como estas:<\/p>\n<ul>\n<li>perto do metr\u00f4 (near metro);\n<\/li>\n<li>tem estacionamento privativo (has private parking);\n<\/li>\n<li>tem varanda (has terrace);\n<\/li>\n<li>aceita reservas (accepts reservations);\n<\/li>\n<li>\u00e9 adequado para vegetarianos (vegan friendly);\n<\/li>\n<li>caro (expensive).\n<\/li>\n<\/ul>\n<p>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/fcbad539ea12f79a9d06966ce308637e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nVamos atribuir a cada restaurante um n\u00famero sequencial come\u00e7ando de 0 e alocar mem\u00f3ria para 6 bitmaps (um para cada caracter\u00edstica). Em seguida, preencheremos esses bitmaps dependendo se o restaurante possui ou n\u00e3o a referida propriedade. Se o restaurante 4 tiver uma varanda, o bit n\u00ba 4 no bitmap 'tem varanda' ser\u00e1 definido como 1 (se n\u00e3o houver varanda, ser\u00e1 0).<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/3709c426617d4364f392ee6b68f92b00.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAgora temos o \u00edndice bitmap mais simples poss\u00edvel, e podemos us\u00e1-lo para responder a consultas como:<\/p>\n<ul>\n<li>\"Mostre-me os restaurantes adequados para vegetarianos\";\n<\/li>\n<li>\"Mostre-me restaurantes baratos com varanda, onde posso reservar uma mesa\".\n<\/li>\n<\/ul>\n<p><img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/90acb0f890686bd52c3db1fc667f0b0b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/0fd0b7fe9f7b7039022ad5c79fe873bc.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nComo? Vamos ver. A primeira consulta \u00e9 muito simples. Tudo que precisamos fazer \u00e9 pegar o bitmap \"\u00e9 adequado para vegetarianos\" e transform\u00e1-lo em uma lista de restaurantes cujos bits est\u00e3o definidos.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/ef4a5cfd658ff4ef8bc0c638c4522d11.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/9cc175bae55c16018fdf5ff95517a61a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nA segunda consulta \u00e9 um pouco mais complicada. Precisamos usar a opera\u00e7\u00e3o bitwise NOT no bitmap \"caro\" para obter uma lista de restaurantes baratos, em seguida, realizar um AND com o bitmap \"reserva dispon\u00edvel\" e depois fazer um AND do resultado com o bitmap \"tem varanda\". O bitmap resultante conter\u00e1 uma lista de estabelecimentos que atendem a todos os nossos crit\u00e9rios. Neste exemplo, \u00e9 apenas o restaurante \"Joventude\".<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/f1cdda0cbf7f15278553899cf876c17e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/126b50e0f622b6e36c461cd74e708c38.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAqui h\u00e1 muita teoria, mas n\u00e3o se preocupe, veremos o c\u00f3digo muito em breve.<\/p>\n<h2>Onde s\u00e3o utilizados \u00edndices bitmap?<\/h2>\n<p>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/406132236c71a4f66ae79957b6e633b3.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nSe voc\u00ea \"googlar\" \u00edndices bitmap, 90% das respostas estar\u00e3o de alguma forma relacionadas ao Oracle DB. Mas outros SGBDs tamb\u00e9m devem suportar algo t\u00e3o legal, certo? Nem tanto. <\/p>\n<p>Vamos passar pela lista dos principais suspeitos.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/d18d66451a8a26b0ddf121f8ec0204cd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nO MySQL ainda n\u00e3o suporta \u00edndices bitmap, mas h\u00e1 uma proposta para adicionar esse recurso (<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>O PostgreSQL n\u00e3o suporta \u00edndices bitmap, mas utiliza bitmaps simples e opera\u00e7\u00f5es bitwise para combinar os resultados de pesquisas em outros \u00edndices.<\/p>\n<p>O Tarantool tem \u00edndices de conjuntos de bits e suporta pesquisa simples neles.<\/p>\n<p>O Redis possui campos bitwise simples<noindex><a rel=\"nofollow\" href=\"https:\/\/redis.io\/commands\/bitfield\"> (https:\/\/redis.io\/commands\/bitfield<\/a><\/noindex>) sem possibilidade de pesquisa neles.<\/p>\n<p>O MongoDB ainda n\u00e3o suporta \u00edndices bitmap, mas tamb\u00e9m h\u00e1 uma proposta para adicionar esse recurso <noindex><a rel=\"nofollow\" href=\"https:\/\/jira.mongodb.org\/browse\/SERVER-1723\">https:\/\/jira.mongodb.org\/browse\/SERVER-1723<\/a><\/noindex><\/p>\n<p>O Elasticsearch utiliza bitmaps internamente<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=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/232d335963603d6e6dec98839fc9f486.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<\/p>\n<ul>\n<li>Mas em nossa casa apareceu um novo vizinho: Pilosa. \u00c9 um novo banco de dados n\u00e3o relacional, escrito em Go. Ele cont\u00e9m apenas \u00edndices bitmap e baseia tudo neles. Vamos falar sobre isso um pouco mais tarde.\n<\/li>\n<\/ul>\n<h2>Implementa\u00e7\u00e3o em Go<\/h2>\n<p>\nMas por que os \u00edndices bitmap s\u00e3o t\u00e3o raramente utilizados? Antes de responder a essa pergunta, gostaria de demonstrar a voc\u00eas a implementa\u00e7\u00e3o de um \u00edndice bitmap muito simples em Go.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/ae7f4c1a4a740fe709b05dfaee27ac9b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nOs bitmaps, na ess\u00eancia, s\u00e3o representados apenas como peda\u00e7os de dados. Em Go, vamos usar slices de bytes para isso.<\/p>\n<p>Temos um bitmap para cada caracter\u00edstica do restaurante, e cada bit no bitmap indica se o restaurante espec\u00edfico possui essa caracter\u00edstica ou n\u00e3o.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/1ab628ee15887d6b3c6c99855aa610c8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPrecisamos de duas fun\u00e7\u00f5es auxiliares. Uma ser\u00e1 usada para preencher nossos bitmaps com dados aleat\u00f3rios. Aleat\u00f3rios, mas com uma certa probabilidade de que o restaurante possua cada propriedade. Por exemplo, eu considero que em Moscovo h\u00e1 muito poucos restaurantes onde n\u00e3o \u00e9 poss\u00edvel reservar uma mesa, e me parece que cerca de 20% dos estabelecimentos s\u00e3o adequados para vegetarianos.<\/p>\n<p>A segunda fun\u00e7\u00e3o converter\u00e1 o bitmap em uma lista de restaurantes.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/ab9c87a0ba63750116e2e7968f842a9a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/498cf7a33611d99b90197d4ee82e2834.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPara responder \u00e0 consulta \"Mostre-me restaurantes baratos que tenham varanda e onde seja poss\u00edvel reservar uma mesa\", precisaremos de duas opera\u00e7\u00f5es bit a bit: NOT e AND.<\/p>\n<p>Podemos simplificar um pouco nosso c\u00f3digo utilizando uma opera\u00e7\u00e3o mais complexa: AND NOT.<\/p>\n<p>Temos fun\u00e7\u00f5es para cada uma dessas opera\u00e7\u00f5es. Ambas percorrem os slices, pegam os elementos correspondentes de cada um, combinam-nos com a opera\u00e7\u00e3o bit a bit e colocam o resultado no slice de resultado.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/ec5652a34f0370dfb03df199f341f153.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nE agora podemos utilizar nossos bitmaps e fun\u00e7\u00f5es para responder \u00e0 consulta de busca.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/cf9500ccfe75995a6008191c16729689.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nO desempenho n\u00e3o \u00e9 t\u00e3o alto, mesmo que as fun\u00e7\u00f5es sejam muito simples e economizamos bastante por n\u00e3o retornar um novo slice de resultado a cada chamada da fun\u00e7\u00e3o.<\/p>\n<p>Depois de fazer um profiling com pprof, notei que o compilador Go ignorou uma otimiza\u00e7\u00e3o muito simples, mas extremamente importante: inlining de fun\u00e7\u00f5es.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/9092f5ba3940d0a4f3fbfa90b364d716.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nO fato \u00e9 que o compilador Go tem muito medo de loops que percorrem slices, e se recusa categoricamente a fazer inlining de fun\u00e7\u00f5es que cont\u00eam tais loops.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/d1bddd62b61b367dd1f680f223fa0ce7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nMas eu n\u00e3o tenho esse medo e posso enganar o compilador usando goto em vez de um loop, como nos velhos tempos.<\/p>\n<p><img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/5b1c3cb26b923972686047910ecd1c31.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/1ca31d12dc90931b674c6a86a4ea23bd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nE, como podem ver, agora o compilador se alegra em fazer o inlining da nossa fun\u00e7\u00e3o! No final, conseguimos economizar cerca de 2 microssegundos. N\u00e3o \u00e9 mau!<\/p>\n<p><img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/bdd6735d16082573e600bffe2cdd5662.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nO segundo gargalo \u00e9 f\u00e1cil de identificar se olharmos atentamente a sa\u00edda do assembly. O compilador adicionou uma verifica\u00e7\u00e3o de limites do slice diretamente dentro do nosso loop mais quente. O fato \u00e9 que Go \u00e9 uma linguagem segura, e o compilador teme que meus tr\u00eas argumentos (tr\u00eas slices) tenham tamanhos diferentes. Pois ent\u00e3o haveria uma possibilidade te\u00f3rica de ocorrer um overflow de buffer.<\/p>\n<p>Vamos acalmar o compilador, mostrando que todos os slices t\u00eam o mesmo tamanho. Podemos fazer isso adicionando uma simples verifica\u00e7\u00e3o no in\u00edcio da nossa fun\u00e7\u00e3o.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/59b4ce687a11dd653e9f12fc3130d89a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nVendo isso, o compilador felizmente ignora a verifica\u00e7\u00e3o, e economizamos mais 500 nanossegundos.<\/p>\n<h2>Grandes lotes<\/h2>\n<p>\nOk, conseguimos extrair um pouco de desempenho da nossa implementa\u00e7\u00e3o simples, mas esse resultado \u00e9, na verdade, muito pior do que o que \u00e9 poss\u00edvel com o hardware atual.<\/p>\n<p>Tudo o que fazemos s\u00e3o opera\u00e7\u00f5es b\u00e1sicas com bits, e nossos processadores as executam de forma muito eficiente. Mas, infelizmente, estamos \"alimentando\" nosso processador com peda\u00e7os muito pequenos de trabalho. Nossas fun\u00e7\u00f5es executam opera\u00e7\u00f5es byte a byte. Podemos facilmente otimizar nosso c\u00f3digo para trabalhar com peda\u00e7os de 8 bytes, usando slices UInt64.<\/p>\n<p><img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/8d1b60ba4b7046c836601631cadd0b6a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nComo voc\u00ea pode ver, essa pequena mudan\u00e7a acelerou nosso programa em oito vezes, aumentando o lote tamb\u00e9m em oito vezes. O ganho pode ser considerado linear.<\/p>\n<p><img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/0fc663412d04dd38b927de5c8776f69d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<h2>Implementa\u00e7\u00e3o em Assembly<\/h2>\n<p>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/b3ef133167b89da983356b1c7389aecd.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nMas isso n\u00e3o \u00e9 o fim. Nossos processadores podem trabalhar com peda\u00e7os de 16, 32 e at\u00e9 64 bytes. Essas opera\u00e7\u00f5es \"largas\" s\u00e3o chamadas de single instruction multiple data (SIMD; uma instru\u00e7\u00e3o, muitos dados), e o processo de transformar c\u00f3digo para que utilize essas opera\u00e7\u00f5es \u00e9 chamado de vetoriza\u00e7\u00e3o.<\/p>\n<p>Infelizmente, o compilador Go n\u00e3o \u00e9 exatamente um modelo em vetoriza\u00e7\u00e3o. At\u00e9 o momento, a \u00fanica forma de vetorizar c\u00f3digo em Go \u00e9 intervir manualmente nas opera\u00e7\u00f5es usando assembly Go.<\/p>\n<p><img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/91278be45df67e1f9572d68fab7ebad1.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nAssembly Go \u00e9 uma coisa estranha. Voc\u00ea provavelmente sabe que o assembly \u00e9 algo muito ligado \u00e0 arquitetura do computador para o qual voc\u00ea est\u00e1 escrevendo, mas em Go isso n\u00e3o \u00e9 o caso. Assembly Go \u00e9 mais parecido com uma IRL (linguagem de representa\u00e7\u00e3o intermedi\u00e1ria): \u00e9 praticamente independente de plataforma. Rob Pike fez uma excelente <noindex><a rel=\"nofollow\" href=\"https:\/\/www.youtube.com\/watch?v=KINIAgRpkDA\">palestra<\/a><\/noindex> sobre este tema alguns anos atr\u00e1s no GopherCon em Denver.<\/p>\n<p>Al\u00e9m disso, Go utiliza um formato incomum, o Plan 9, que difere dos formatos reconhecidos AT&amp;T e Intel.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/526f75eb18edfc2f851f2725e9d6f69e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPode-se afirmar com confian\u00e7a que escrever assembly Go manualmente n\u00e3o \u00e9 a tarefa mais divertida.<\/p>\n<p>Mas, felizmente, j\u00e1 existem duas ferramentas de alto n\u00edvel que nos ajudam a escrever assembly Go: PeachPy e avo. Ambas as ferramentas geram assembly Go a partir de c\u00f3digo de n\u00edvel mais alto escrito em Python e Go, respectivamente.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/b8a7aa2c585b805e9b1f2ada186b84e8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nEssas utilit\u00e1rios simplificam quest\u00f5es como aloca\u00e7\u00e3o de registradores (escolha do registrador do processador), escrita de loops e, no geral, facilitam a entrada no mundo da programa\u00e7\u00e3o em assembly no Go.<\/p>\n<p>Usaremos o avo, de modo que nossos programas ser\u00e3o quase programas comuns em Go.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/128e4adef14e5f2cf00fb5b6302ef58e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nEsta \u00e9 a apar\u00eancia do exemplo mais simples de um programa avo. Temos a fun\u00e7\u00e3o main(), que define internamente a fun\u00e7\u00e3o Add(), cuja finalidade \u00e9 somar dois n\u00fameros. Existem fun\u00e7\u00f5es auxiliares para obter par\u00e2metros pelo nome e para obter um dos registradores de processador livres e adequados. Cada opera\u00e7\u00e3o de processador tem uma fun\u00e7\u00e3o correspondente no avo, como pode ser visto pelo ADDQ. Finalmente, vemos uma fun\u00e7\u00e3o auxiliar para armazenar o valor resultante.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/01ccaa6aa6d394ef598ea2dbc9257d87.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAo chamar go generate, executaremos o programa no avo e, no final, dois arquivos ser\u00e3o gerados:<\/p>\n<ul>\n<li>add.s com o c\u00f3digo resultante em assembly Go;\n<\/li>\n<li>stub.go com as declara\u00e7\u00f5es de fun\u00e7\u00f5es para conectar os dois mundos: Go e assembly.\n<\/li>\n<\/ul>\n<p>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/72a9443776ecf45eef6fb97a4e08acba.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAgora que vimos o que o avo faz e como ele funciona, vamos olhar nossas fun\u00e7\u00f5es. Eu implementei vers\u00f5es escalar e vetorial (SIMD) das fun\u00e7\u00f5es.<\/p>\n<p>Primeiro, vamos olhar para as vers\u00f5es escalares.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/ec31dbb8b97b9d7c1012a120fa18cdaf.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nComo no exemplo anterior, pedimos um registrador de uso geral livre e correto, n\u00e3o precisamos calcular deslocamentos ou tamanhos para os argumentos. Tudo isso o avo faz por n\u00f3s.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/88085e927dd943ea0f808a28fb3ccf9b.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nAnteriormente, utilizamos r\u00f3tulos e goto (ou saltos) para aumentar o desempenho e enganar o compilador Go, mas agora fazemos isso desde o in\u00edcio. O fato \u00e9 que loops s\u00e3o um conceito de n\u00edvel mais alto. Em assembly, s\u00f3 temos r\u00f3tulos e saltos.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/9a4181248eb279d89c1445a820b06649.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nO c\u00f3digo restante deve j\u00e1 ser familiar e compreens\u00edvel. Estamos emulando o loop com r\u00f3tulos e saltos, pegando uma pequena parte de dados de nossas duas listas, combinando-os com uma opera\u00e7\u00e3o bit a bit (AND NOT, neste caso) e, em seguida, colocando o resultado na lista resultante. Isso \u00e9 tudo.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/19275ead27f63092fc6596bed38a8d03.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nEste \u00e9 o aspecto do c\u00f3digo final em assembly. N\u00e3o precisamos calcular deslocamentos e tamanhos (destacado em verde) ou monitorar os registradores utilizados (destacado em vermelho).<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/ed68528a6f852634a5b536670c6315f0.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nSe compararmos o desempenho da implementa\u00e7\u00e3o em assembler com o desempenho da melhor implementa\u00e7\u00e3o em Go, veremos que \u00e9 igual. E isso \u00e9 esperado. Afinal, n\u00e3o fizemos nada de especial \u2014 apenas reproduzimos o que o compilador Go faria.<\/p>\n<p>Infelizmente, n\u00e3o podemos fazer com que o compilador inlined nossas fun\u00e7\u00f5es escritas em assembler. O compilador Go atualmente n\u00e3o possui essa capacidade, embora haja um pedido para adicion\u00e1-la h\u00e1 bastante tempo.<\/p>\n<p>\u00c9 por isso que n\u00e3o \u00e9 poss\u00edvel obter quaisquer vantagens de fun\u00e7\u00f5es pequenas em assembler. Precisamos ou escrever fun\u00e7\u00f5es grandes, ou usar o novo pacote math\/bits, ou evitar o assembler.<\/p>\n<p>Agora vamos dar uma olhada nas vers\u00f5es vetoriais de nossas fun\u00e7\u00f5es.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/7f67c3cc855908fb47c7900d6e5d7f54.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPara este exemplo, decidi aplicar AVX2, portanto, usaremos opera\u00e7\u00f5es que trabalham com blocos de 32 bytes. A estrutura do c\u00f3digo \u00e9 muito semelhante \u00e0 vers\u00e3o escalar: carregamento de par\u00e2metros, solicita\u00e7\u00e3o de um registro geral livre, etc.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/021e0424a0d733ec7db9edeb98ce1f65.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nUma das inova\u00e7\u00f5es est\u00e1 relacionada ao fato de que opera\u00e7\u00f5es vetoriais mais amplas usam registradores especiais. No caso de blocos de 32 bytes, s\u00e3o registradores com o prefixo Y. \u00c9 por isso que voc\u00ea v\u00ea a fun\u00e7\u00e3o YMM() no c\u00f3digo. Se eu tivesse usado AVX-512 com blocos de 64 bits, o prefixo seria Z.<\/p>\n<p>A segunda inova\u00e7\u00e3o est\u00e1 relacionada ao fato de que decidi usar uma otimiza\u00e7\u00e3o chamada desenrolamento de la\u00e7o (loop unrolling), ou seja, realizar oito opera\u00e7\u00f5es do la\u00e7o manualmente antes de pular de volta ao in\u00edcio do la\u00e7o. Essa otimiza\u00e7\u00e3o reduz o n\u00famero de bifurca\u00e7\u00f5es no c\u00f3digo e \u00e9 limitada pelo n\u00famero de registradores livres dispon\u00edveis.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/f54631d9e8c69f6f70ecace3133ae1e8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nE quanto ao desempenho? \u00c9 maravilhoso! N\u00f3s conseguimos uma acelera\u00e7\u00e3o de cerca de sete vezes em compara\u00e7\u00e3o com a melhor solu\u00e7\u00e3o em Go. Impressionante, n\u00e3o \u00e9?<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/d7e85c933eecb243cfb49225b4d92c6c.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nMas mesmo essa implementa\u00e7\u00e3o poderia ser potencialmente acelerada, aproveitando AVX-512, prefetching ou JIT (just-in-time compiler) para o planejador de consultas. Mas isso, sem d\u00favida, \u00e9 um tema para uma apresenta\u00e7\u00e3o separada.<\/p>\n<h2>Problemas dos \u00edndices bitmap<\/h2>\n<p>\nAgora que j\u00e1 analisamos a implementa\u00e7\u00e3o simples de um \u00edndice bitmap em Go e uma muito mais eficiente em assembler, vamos finalmente falar sobre o porqu\u00ea de os \u00edndices bitmap serem t\u00e3o raramente utilizados.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/83d36a5c92ba90fd680fe8afb6cfc11f.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nEm trabalhos cient\u00edficos antigos, tr\u00eas problemas dos \u00edndices bitmap s\u00e3o mencionados, mas pesquisas mais recentes e eu afirmamos que eles j\u00e1 n\u00e3o s\u00e3o relevantes. N\u00e3o vamos nos aprofundar em cada uma dessas quest\u00f5es, mas vamos analis\u00e1-las superficialmente.<\/p>\n<h2>O problema da alta cardinalidade<\/h2>\n<p>\nAssim, nos dizem que os \u00edndices bitmap s\u00e3o adequados apenas para campos com baixa cardinalidade, ou seja, aqueles que possuem poucos valores (por exemplo, g\u00eanero ou cor dos olhos), e a raz\u00e3o \u00e9 que a representa\u00e7\u00e3o comum desses campos (um bit por valor) em caso de alta cardinalidade ocupar\u00e1 muito espa\u00e7o e, al\u00e9m disso, esses \u00edndices bitmap estar\u00e3o pouco (raramente) preenchidos.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/0787efc4d2cb4ea4d404ca7888b33697.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/44ab4bc7c25d14fe2f53caf5d9da399d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n\u00c0s vezes, podemos usar outra representa\u00e7\u00e3o, como a padr\u00e3o que utilizamos para representar n\u00fameros. Mas foi exatamente o surgimento de algoritmos de compress\u00e3o que mudou tudo. Nas \u00faltimas d\u00e9cadas, cientistas e pesquisadores inventaram uma grande quantidade de algoritmos de compress\u00e3o para bitmaps. Sua principal vantagem \u00e9 que n\u00e3o \u00e9 necess\u00e1rio descomprimir bitmaps para realizar opera\u00e7\u00f5es de bits \u2014 podemos fazer opera\u00e7\u00f5es de bits diretamente sobre bitmaps comprimidos.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/ecb54fbf15aa11271bbbab01ecbda880.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nRecentemente, tamb\u00e9m come\u00e7aram a surgir abordagens h\u00edbridas, como os bitmaps roaring. Eles utilizam simultaneamente tr\u00eas representa\u00e7\u00f5es diferentes para bitmaps \u2014 os pr\u00f3prios bitmaps, arrays e os chamados bit runs \u2014 e equilibram entre elas para maximizar o desempenho e minimizar o consumo de mem\u00f3ria.<\/p>\n<p>Voc\u00ea pode encontrar bitmaps roaring nas aplica\u00e7\u00f5es mais populares. J\u00e1 existe uma enorme quantidade de implementa\u00e7\u00f5es para diversas linguagens de programa\u00e7\u00e3o, incluindo mais de tr\u00eas implementa\u00e7\u00f5es para Go.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/de2adfebc431ff48c996247b453f02ae.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nOutra abordagem que pode nos ajudar a lidar com alta cardinalidade \u00e9 chamada de agrupamento (binning). Imagine que voc\u00ea tem um campo que representa a altura de uma pessoa. A altura \u00e9 um n\u00famero de ponto flutuante, mas n\u00f3s, humanos, n\u00e3o pensamos nisso dessa maneira. Para n\u00f3s, n\u00e3o h\u00e1 diferen\u00e7a entre uma altura de 185,2 cm e 185,3 cm.<\/p>\n<p>Portanto, podemos agrupar valores semelhantes em grupos dentro de 1 cm.<\/p>\n<p>E se ainda soubermos que muito poucas pessoas t\u00eam altura abaixo de 50 cm ou acima de 250 cm, podemos, essencialmente, transformar um campo de cardinalidade infinita em um campo com cardinalidade de aproximadamente 200 valores.<\/p>\n<p>Claro, se necess\u00e1rio, podemos fazer uma filtragem adicional depois.<\/p>\n<h2>O problema da alta largura de banda<\/h2>\n<p>\nO pr\u00f3ximo problema dos \u00edndices bitmap \u00e9 que sua atualiza\u00e7\u00e3o pode ser muito cara.<\/p>\n<p>Os bancos de dados devem permitir a atualiza\u00e7\u00e3o dos dados no momento em que potencialmente centenas de outras solicita\u00e7\u00f5es est\u00e3o buscando esses dados. Precisamos de bloqueios para evitar problemas de acesso simult\u00e2neo aos dados ou outros problemas de compartilhamento. E onde h\u00e1 um grande bloqueio, h\u00e1 um problema - a conten\u00e7\u00e3o do bloqueio, quando esse bloqueio se torna um gargalo.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/0ae1bf925542d286f8b7b245c160a35e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nEsse problema pode ser resolvido ou contornado usando sharding ou \u00edndices versionados.<\/p>\n<p>Sharding \u00e9 algo simples e bem conhecido. Voc\u00ea pode shardizar um \u00edndice bitmap da mesma forma que shardizaria qualquer outro dado. Em vez de um grande bloqueio, voc\u00ea ter\u00e1 muitos pequenos bloqueios e, assim, eliminar\u00e1 a conten\u00e7\u00e3o do bloqueio.<\/p>\n<p>Uma segunda forma de resolver o problema \u00e9 usar \u00edndices versionados. Voc\u00ea pode ter uma c\u00f3pia do \u00edndice que usa para busca ou leitura, e outra para grava\u00e7\u00e3o ou atualiza\u00e7\u00e3o. E a cada intervalo de tempo (por exemplo, a cada 100 ms ou 500 ms), voc\u00ea duplica e troca-os de lugar. Claro, essa abordagem \u00e9 aplic\u00e1vel apenas em casos onde seu aplicativo pode funcionar com um \u00edndice de busca um pouco defasado.<\/p>\n<p>Essas duas abordagens podem ser usadas simultaneamente: voc\u00ea pode ter um \u00edndice versionado shardizado.<\/p>\n<h2>Consultas mais complexas<\/h2>\n<p>O \u00faltimo problema dos \u00edndices bitmap \u00e9 que, como nos dizem, eles n\u00e3o s\u00e3o adequados para tipos de consultas mais complexas, como consultas 'por intervalo'.<\/p>\n<p>De fato, se pensarmos bem, opera\u00e7\u00f5es bit a bit como AND, OR, etc., n\u00e3o s\u00e3o muito adequadas para consultas do tipo 'mostre-me os hot\u00e9is com pre\u00e7os de quartos entre 200 e 300 d\u00f3lares por noite'.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/7bc2e129cad46fb5875c2b3018c39ff7.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nUma solu\u00e7\u00e3o ing\u00eanua e muito irracional seria pegar os resultados para cada valor em d\u00f3lar e combin\u00e1-los com a opera\u00e7\u00e3o bit a bit OR.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/b9f8fc7945caa1866f8e0cfa8a04bd98.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nUma solu\u00e7\u00e3o um pouco mais adequada seria usar agrupamento. Por exemplo, em grupos de 50 d\u00f3lares. Isso aceleraria nosso processo em 50 vezes.<\/p>\n<p>Mas o problema \u00e9 facilmente resolvido pelo uso de uma representa\u00e7\u00e3o criada especificamente para esse tipo de consulta. Em trabalhos acad\u00eamicos, \u00e9 chamada de bitmaps codificados por intervalo.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/644a420628b21f220a7af1ff15c4031f.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nNessa representa\u00e7\u00e3o, n\u00e3o estamos apenas definindo um bit para um certo valor (por exemplo, 200), mas estabelecemos esse valor e tudo acima. 200 e acima. O mesmo se aplica a 300: 300 e acima. E assim por diante.<\/p>\n<p>Usando essa representa\u00e7\u00e3o, podemos responder a esse tipo de consulta de busca, percorrendo o \u00edndice apenas duas vezes. Primeiro, obtemos uma lista de hot\u00e9is onde o pre\u00e7o do quarto \u00e9 menor que 300 d\u00f3lares, e depois retiramos aqueles onde o pre\u00e7o do quarto \u00e9 menor que 199 d\u00f3lares. Pronto.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/cc2bb58d7d7a51495c62ec7da81e2d12.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nVoc\u00ea ficar\u00e1 surpreso, mas at\u00e9 mesmo consultas geogr\u00e1ficas podem ser feitas usando \u00edndices bitmap. O truque \u00e9 usar uma representa\u00e7\u00e3o geogr\u00e1fica que cercar\u00e1 sua coordenada com uma figura geom\u00e9trica. Por exemplo, S2 do Google. A figura deve ser represent\u00e1vel por tr\u00eas ou mais linhas cruzadas que podem ser numeradas. Assim, poderemos transformar nossa consulta geogr\u00e1fica em v\u00e1rias consultas 'por intervalo' (por essas linhas numeradas).<\/p>\n<h2>Solu\u00e7\u00f5es prontas<\/h2>\n<p>\nEspero ter despertado seu interesse e que voc\u00ea tenha um novo instrumento \u00fatil em seu arsenal. Se algum dia voc\u00ea precisar fazer algo semelhante, saber\u00e1 em que dire\u00e7\u00e3o olhar.<\/p>\n<p>No entanto, nem todos t\u00eam tempo, paci\u00eancia e recursos para criar \u00edndices bitmap do zero. Especialmente os mais avan\u00e7ados, usando SIMD, por exemplo.<\/p>\n<p>Felizmente, existem algumas solu\u00e7\u00f5es prontas que podem ajudar voc\u00ea.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/817b47cb189a758756b602ec9cf319e1.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<h2>Bitmaps roaring<\/h2>\n<p>\nEm primeiro lugar, existe a biblioteca de bitmaps roaring, sobre a qual j\u00e1 falei. Ela cont\u00e9m todos os cont\u00eaineres e opera\u00e7\u00f5es bit a bit necess\u00e1rios para que voc\u00ea possa criar um \u00edndice bitmap completo.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/57f61a51485c174666b52dc2063fabe8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nInfelizmente, no momento, nenhuma das implementa\u00e7\u00f5es em Go utiliza SIMD, o que significa que as implementa\u00e7\u00f5es em Go s\u00e3o menos eficientes do que as implementa\u00e7\u00f5es em C, por exemplo.<\/p>\n<h2>Pilosa<\/h2>\n<p>\nOutro produto que pode ajudar voc\u00ea \u00e9 o banco de dados Pilosa, que possui, essencialmente, apenas \u00edndices bitmap. Esta \u00e9 uma solu\u00e7\u00e3o relativamente nova, mas est\u00e1 conquistando cora\u00e7\u00f5es rapidamente.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/d3870a979e1e73d093fe5d5e9bb71cd8.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nPilosa utiliza bitmaps roaring internamente e permite que voc\u00ea os utilize, simplificando e explicando todas as coisas que mencionei acima: agrupamento, bitmaps codificados em intervalo, o conceito de campo, etc.<\/p>\n<p>Vamos dar uma r\u00e1pida olhada em um exemplo de uso do Pilosa para responder a uma pergunta que voc\u00ea j\u00e1 conhece.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/dfee7abfd653cc19d9aa8b64c64f3e4e.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nO exemplo \u00e9 muito semelhante ao que voc\u00ea viu antes. Criamos um cliente para o servidor Pilosa, criamos um \u00edndice e os campos necess\u00e1rios, em seguida, preenchemos nossos campos com dados aleat\u00f3rios com probabilidades e, finalmente, executamos uma consulta familiar.<\/p>\n<p>Depois disso, usamos NOT no campo 'expensive', em seguida, cruzamos o resultado (ou AND) com o campo 'terrace' e com o campo 'reservations'. E finalmente, obtemos o resultado final.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/8d66c6d68019c2297b6c15b700f06a3a.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nEu realmente espero que em um futuro pr\u00f3ximo bancos de dados como MySQL e PostgreSQL tamb\u00e9m adotem esse novo tipo de \u00edndices \u2014 \u00edndices bitmap.<br \/>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/7a8e33d576c7fb6376a173ee038b4206.jpeg\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<h2>Conclus\u00e3o<\/h2>\n<p>\n<img decoding=\"async\" alt=\"\u00cdndices Bitmap em Go: busca em alta velocidade\" src=\"\/wp-content\/uploads\/2019\/05\/c62caa9ad6f2d96056c80326f4fa9a0d.jpeg\" style=\"display:block;margin: 0 auto;\" \/><br \/>\nSe voc\u00ea ainda n\u00e3o est\u00e1 dormindo, obrigado. Tive que tocar em muitos t\u00f3picos rapidamente devido ao tempo limitado, mas espero que a palestra tenha sido \u00fatil e, talvez, at\u00e9 motivadora.<\/p>\n<p>\u00c9 bom saber sobre \u00edndices bitmap, mesmo que voc\u00ea n\u00e3o precise deles agora. Que eles sejam mais uma ferramenta na sua caixa de ferramentas.<\/p>\n<p>N\u00f3s exploramos v\u00e1rios truques para aumentar o desempenho no Go e as coisas com as quais o compilador Go ainda n\u00e3o se sai muito bem. Isso definitivamente \u00e9 \u00fatil saber para qualquer programador em Go.<\/p>\n<p>Isso \u00e9 tudo o que eu queria compartilhar. Obrigado!<br \/>\n<br \/>Fonte: <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\/pt\/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=\"pt_PT\" \/>\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\/pt\/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\udd47\u00cdndices bitmap em Go: busca em alta velocidade | ProHoster","description":"Introdu\u00e7\u00e3o: eu fiz uma apresenta\u00e7\u00e3o.","canonical_url":"https:\/\/prohoster.info\/pt\/blog\/administrirovanie\/bitmap-indeksy-v-go-poisk-na-dikoj-skorosti","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"pt_PT","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\/pt\/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\/pt\/wp-json\/wp\/v2\/posts\/33793","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/comments?post=33793"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/posts\/33793\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/media\/25469"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/media?parent=33793"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/categories?post=33793"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/tags?post=33793"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}