Otimizando Consultas Com Índices em Bases de Dados
por Bruno Rasteiro, Engenheiro de Dados na Big Data.
Introdução
A necessidade de armazenar informação não é novidade para a espécie humana. Temos registros de compra e venda que datam desde antes de cristo [1]. Com o passar do tempo, as civilizações foram se desenvolvendo e junto delas o volume de registros e informações produzidas pelas mesmas. Ao final dos anos 70, com o surgimento dos computadores pessoais e sua difusão no meio comercial, passamos a armazenar muito dado digitalmente. Neste contexto, surgiram os bancos de dados relacionais como uma forma de salvar e recuperar dados com consistência e velocidade.
Neste post vamos focar na velocidade e em entender brevemente como um banco relacional consegue fazer uma busca em meio a milhões de linhas e retornar o resultado em poucos segundos usando suas estruturas de indexação. Em seguida, veremos um exemplo prático da atuação de um índice na base de dados.
Redução do tempo de busca
Em bancos de dados armazenamos os dados em tabelas que podem conter milhões ou bilhões de linhas. Se toda vez que formos fazer uma busca na tabela tivermos que procurar em todas as linhas, o tempo de busca irá crescer na mesma proporção que a quantidade de linhas da tabela. Isso não é um cenário agradável, pois se pensarmos, por exemplo, nas transações realizadas por uma rede varejista, podemos ter facilmente milhões de linhas por semana ou até por dia. Nesse contexto surge o índice, uma estrutura de dados que torna a busca mais eficiente e faz com que o tempo de procura cresça a uma taxa inferior à da quantidade de linhas. Para fazer tal feito, os índices aumentam o custo de armazenamento e o tempo de escrita na tabela.
O funcionamento de um índice dentro de um banco de dados é parecido com o de um índice em um livro. Imagine que você abre um livro de história, por exemplo, e queira ler sobre a Segunda Guerra Mundial, o índice torna sua busca muito mais rápida e efetiva, pois não é necessário percorrer todas as folhas até encontrar o tópico desejado, você só precisa procurar no índice e depois abrir no número da página correta. Se o livro contém 1000 páginas e o índice 5, você reduziu o espaço de busca 200 vezes. Incrível, não é?
Para reduzir o espaço de busca, o índice é feito da cópia de uma ou mais colunas da tabela e é armazenado em uma estrutura que possibilita isso. Uma das estruturas mais comuns utilizadas em bancos de dados é a Árvore B ou variações dela [2]. A grande vantagem da árvore é que ela permite fazer busca em tempo logarítmico, ou seja, com uma complexidade O(log(n)). Dependendo da sua familiaridade com computação e algoritmos isso pode parecer técnico demais. Na prática é mais simples: se em uma tabela de N linhas faríamos uma busca sequencial com N operações, usando uma árvore o número de operações é reduzido para log(N). Para um número grande de linhas, por exemplo N=100.000.000 a árvore reduz esse número para log(N) = 8. Isso tem um impacto enorme no tempo de busca, pois assim como no exemplo do livro nosso espaço de busca foi reduzido drasticamente.
Redução das operações no disco
Outro aspecto importante da Árvore B é que ela foi projetada para funcionar bem em discos rígidos. Para entender isso, precisamos diferenciar os tipos de memória de um computador. Elas são divididas em duas categorias, a principal e a secundária.
Na memória principal encontra-se a cache do processador e a memória RAM, essas são memórias de rápido acesso, porém com capacidades de armazenamentos limitadas a poucos megas e gigas respectivamente. Além disso, são voláteis, seus dados não persistem quando o computador é desligado.
A memória secundária consiste do disco rígido, seu armazenamento não é volátil e sua capacidade é da ordem de terabytes. Essas características tornam o disco o dispositivo certo para ser habitado por um banco de dados. O problema é que o acesso aos dados é muito lento em relação à memória primária, principalmente devido às operações mecânicas do disco, ou seja, a movimentação do disco e da agulha de leitura. A Árvore-B aproveita dessa informação e se preocupa para armazenar os dados de maneira a minimizar o número de movimentos da agulha.
Indexando múltiplas colunas
Em muitos cenários, estamos interessados em fazer consultas na base dados considerando mais de uma coluna. Por exemplo, podemos querer buscar em uma base de transações todas as vendas em Outubro de 2019 de um determinado produto. Se esse tipo de consulta for frequente na aplicação um índice com as duas colunas (no exemplo, data e produto) pode agilizar muito a busca.
Como já dito, índices são estruturas de dados compostas por uma ou mais colunas da tabela armazenadas de forma ordenada e em árvore. Dito isso, percebemos que a ordem das colunas tem impacto nas possibilidades de uso do índice. Isso ocorre porque só é possível tirar proveito dessa estrutura caso você esteja buscando por todas as colunas (eficiência máxima) ou pelas colunas mais à esquerda (eficiência parcial). A lista abaixo ilustra as tuplas de colunas usadas para a criação do índice e as tuplas possíveis de busca com ele:
- (c1, c2) → (c1, c2), (c1)
- (c1, c2, c3) → (c1, c2, c3), (c1, c2), (c1)
Índices na prática
Agora que já temos uma noção sobre o funcionamento dos índices, vamos ver exemplos práticos do quão poderosos eles são. Os testes realizados neste tutorial foram feitos em um banco PostgreSQL, a tabela utilizada possui 20 milhões de linhas e contém dados transacionais fictícios. As colunas são: cod_cliente, cod_produto, cod_vendedor, quantidade, preco e data.
A tabela abaixo mostra os índices que foram criados, o tempo de execução, o tamanho e a proporção do espaço em megabytes ocupado pelo índice em relação a tabela.
Realizamos cinco consultas na tabela antes e depois da criação dos índices, a tabela abaixo mostra os resultados. Perceba que o ganho de performance com o índice não é uniforme, isso varia de acordo com a consulta. Porém, é interessante observar que no pior dos casos o índice foi duas vezes mais rápido e no melhor 59.
Conclusão
Índices são extremamente úteis e essenciais para o funcionamento adequado de muitos sistemas. Nos exemplos da seção prática pudemos ter uma noção do quão poderosa essa estrutura pode ser, e o mais interessante desse fato é que a diferença entre uma consulta com e sem o índice tende a ficar maior conforme a tabela fica maior. Assim, quanto mais linhas sua tabela possuir, mais rápido seu índice irá desempenhar em relação a uma consulta sem ele.
Entretanto, utilizar-se dessas estruturas tem seu custo associado, o crescimento do espaço em disco. No exemplo deste tutorial, houve um aumento de 137% no espaço total ocupado pela tabela após a criação dos índices. Dessa forma é importante nos questionarmos antes de criar um índice se o ganho de performance compensa o custo de armazenamento associado.
