Document

1.2 - Como o SGBD processa uma operação SELECT/WHERE utilizando um índice

Quando o índice existe, seja ele criado temporariamente ou já preexistente, o SGBD utiliza esses índices para dividir o conjunto total de registros em subconjuntos menores (usando o algoritmo b-tree), fazendo assim menos testes lógicos. Ao final, o SGBD irá retornar para o usuário o resultado do último subconjunto criado.

Exemplo: Vamos supor a mesma operação anterior, SELECT * FROM FUNCIONARIOS WHERE Idade > 18 AND Salario > 1.000, com a tabela de funcionários possuindo 10.000 registros:

Com índices, o SGBD irá processar as condições da consulta WHERE uma a uma, da mais externa à mais interna. Dessa forma, primeiramente será processada a operação “Salario > 1.000”.
O SGBD então analisa o índice de salários, utilizando o algoritmo de b-tree para localizar o ponto exato onde está o registro que separa aqueles cujo salário é maior que 10.000, daqueles cujo salário é menor ou igual a 10.000. Já aprendemos que para esse processamento, serão executados no máximo Log2 10.000, ou seja, 13 operações. Após um máximo de 13 operações, o SGBD criará em memória um subconjunto de ID’s que satisfazem a condição. Vamos supor que após esse processamento, o SGBD identifique que 2.000 registros satisfaçam à condição. Então em memória teremos um subconjunto de 2.000 ID’s da tabela de funcionários (e não mais os 10.000 IDs originais).
O próximo passo é processar o segundo filtro, “Idade > 18”; para tal, o SGBD utilizará agora o índice de Idade. A partir do conjunto de 2.000 IDs que ele tem em memória, resultado do filtro anterior, o SGBD irá processar o algoritmo b-tree no índice de Idade para localizar qual é o ponto de corte para a operação desejada. Novamente, aplicando a fórmula Log2 2.000, há um máximo de 10 operações para que o SGBD identifique os registros desejados. A partir desse ponto, o SGBD cria outro subconjunto de IDs apenas com os resultados verdadeiros. Vamos supor que ao aplicar esse segundo filtro, o SGBD tenha reduzido o subconjunto de IDs para apenas 800 registros.
Agora que o SGBD já sabe quais registros satisfazem às duas condições de filtros aplicadas, ele irá fazer uma consulta ao disco para identificar todos os dados (SELECT * FROM FUNCIONARIOS...) dos 800 funcionários que satisfazem os critérios da pesquisa (Salario > 1.000 e Idade > 18).

Observe que o número máximo de testes lógicos executados foi de apenas 23 operações, contra 10.000 operações do modelo anterior (sem uso de índices), e que o acesso a disco leu apenas 800 registros, contra 10.000 do modo anterior. Dessa forma, fica claro que o uso de índices é extremamente benéfico para aumentar a performance das consultas SQL.