Índices (InterBase e Firebird)

Alexey Kovyazin, última atualização 07-Set-2005

O conceito adotado como base dos índices é simples e visual e é uma das bases mais importantes do design de bancos de dados. Com base nos índices, muitos objetos básicos do banco de dados são fundamentados e, além disso, o uso correto dos índices é a chave para a melhoria da produtividade de aplicações de bancos de dados. No entanto, o que é um índice? Índice é um ponteiro ordenado dos registros na tabela. Ponteiro significa que o índice contém valores de um ou vários campos na tabela e os endereços das páginas de dados onde esses valores estão localizados (para detalhes sobre páginas de dados, veja o capítulo “Estrutura do banco de dados InterBase”) (parte 4). Em outras palavras, o índice consiste em pares de valores “valor do campo” - “localização física deste campo”.

Assim, pelo valor do campo (ou campos), incluído no índice, usando o índice podemos encontrar rapidamente o lugar na tabela onde o registro que contém esse valor está alocado. Ordenado significa que os valores dos campos armazenados no índice estão ordenados. Muitas vezes o índice é comparado com um catálogo de biblioteca, no qual todos os livros são registrados em fichas e ordenados de alguma forma: de acordo com o alfabeto ou temas, e em cada ficha contém a informação de onde exatamente o livro em questão está alocado no acervo.

Por que precisamos de índices?

A única coisa que os índices promovem é a aceleração da recuperação de registros pelo seu campo indexado (indexado - significa incluído no índice). A função principal dos índices é fornecer recuperação rápida de registros na tabela. Qualquer uso de índice se resume a isso.

Como essa função de recuperação é realizada? Na entrada desta função temos o valor do campo indexado (ou vários campos). Como resultado da recuperação, devemos receber o registro completo, no qual o campo indexado tem um valor predefinido. Primeiro no índice (mais precisamente, no array ordenado de valores do campo indexado) o valor necessário é pesquisado, então o endereço da página de dados é obtido onde o registro necessário está localizado, o servidor vai até essa página e lê o registro encontrado. Parece um tanto inconveniente, no entanto, a busca usando índice é muitas vezes mais rápida do que a enumeração sequencial de todos os valores da tabela.

Se continuarmos a analogia entre índice e catálogo de biblioteca, veremos que a recuperação de registros usando índice é muito semelhante à busca de livros usando ficha. Quando encontramos um livro em um catálogo relativamente pequeno (em comparação com todo o acervo da biblioteca), recebemos imediatamente a informação sobre onde exatamente o livro está armazenado e podemos ir direto para lá. Busca sem usar índice pode ser comparada com a enumeração sequencial de todos os livros da biblioteca!

A enumeração de todos os registros na tabela é chamada de direta ou natural. Devemos dizer que, apesar do poder dos computadores modernos, a enumeração natural pode ser muito longa se a tabela contiver um grande número de registros.

Como eles são organizados?

O índice não é uma parte da tabela, é um objeto separado conectado à tabela e a outros objetos do banco de dados. Este é um ponto muito importante da implementação de SGBD que permite separar o armazenamento de informações de sua representação.

O InterBase, como qualquer outro banco de dados relacional, armazena registros em tabelas de forma não ordenada, ou seja, não se importa em como os registros estão fisicamente alocados na tabela. Armazenamento não ordenado significa que dois registros adicionados à tabela um após o outro podem não estar próximos um do outro. Além disso, os dados extraídos da tabela também não têm ordem, exceto aquela que deve ser explicitamente especificada pelo usuário ao fazer uma consulta de recuperação.

No entanto, não podemos passar sem ordenar os dados armazenados: usuários finais de aplicações querem ver os dados em uma ordem definida - por exemplo, sobrenomes de pessoas em ordem alfabética. Os índices resolvem o problema da representação de dados de forma ordenada. Os valores dos campos incluídos no índice são ordenados e representados em uma visão especial, otimizada para buscar os valores necessários (ou seja, isso é essencial para criar sequências ordenadas).

Separar o armazenamento de dados de sua representação dá benefícios adicionais em comparação com a ordenação direta - talvez você precise ordenar a tabela inicial de diferentes maneiras. Então os índices ajudarão você - pode haver até 64 índices para cada tabela!

Se falarmos sobre a implementação de índices no nível físico, eles representam uma árvore binária cujos nós representam pares “valor do campo no índice” - “alocação de dados na tabela”. A recuperação do registro necessário no índice é realizada usando o mecanismo de busca por hash - um dos algoritmos de busca mais rápidos.

Aplicação de índices

Agora, quando está claro o que podemos exigir dos índices, é hora de saber sobre sua função em um banco de dados. Os índices são usados em três casos principais:

Aceleração da execução de consultas. Índices são criados para os campos usados nas condições de busca de consultas SQL.
Suporte à unicidade de valores em campos; uma restrição de chave primária (sobre a qual foi falado no capítulo “Tabelas. Chaves primárias”) exige que na tabela não haja dois valores idênticos dos campos incluídos em uma chave primária. Para atender a essa condição, ao inserir um novo registro você deve buscar o mesmo valor que será inserido. Para a recuperação de registros, uma variedade especial de índice é usada - um índice único (veja abaixo).
Suporte à integridade referencial. Restrições de chave estrangeira (que são consideradas no capítulo “Restrições do banco de dados”) são usadas para verificar se os valores inseridos na tabela necessariamente existem em outra tabela. Ao criar uma chave estrangeira, um índice é automaticamente criado. Esse índice é aplicado para acelerar consultas que usam junção de tabelas, bem como para verificar as condições da chave estrangeira. Cobrimos brevemente todas as aplicações possíveis de índices. Agora consideraremos as peculiaridades de cada caso em mais detalhe e responderemos às perguntas mais frequentes sobre a aplicação de índices.

Acelerando a execução de consultas usando índices

Foi descrito acima que a aplicação de índices pode acelerar muito a execução de consultas. Isso é realmente verdade na maioria dos casos, mas há certas ressalvas. Primeiro, responderemos à pergunta frequente entre aqueles que se familiarizaram com índices. Se os índices aceleram a recuperação de um banco de dados, por que não indexar todos os campos na tabela? Há dois pontos que impedem a indexação geral - espaço em disco e custos ao modificar os dados na tabela. Cada índice criado tem um tamanho igual ao tamanho dos dados no campo indexado, mais o tamanho dos dados da alocação dos registros. Se criarmos índices para cada campo na tabela, seu tamanho total será maior que o tamanho dos dados na tabela! Portanto, a criação de um grande número de índices leva a um enorme gasto de espaço em disco.

O segundo ponto é mais importante. São os custos ao modificar os dados na tabela. Em um SGBD relacional, como você sabe, os registros nas tabelas são não ordenados e, consequentemente, adicionar/excluir registros ocorre sem custos significativos de recursos do servidor. Mesmo se um registro for excluído do meio de um banco de dados, não há movimentação de dados para preencher esse vazio - não é necessário: o servidor simplesmente marcará o lugar vazio e escreverá algo lá quando necessário. Quanto à adição, na maioria dos casos ela é executada no final da tabela. No entanto, embora o servidor não mova os dados principais na tabela ao modificar, os dados armazenados nos índices são reordenados toda vez que registros são adicionados/excluídos! Em outras palavras, o servidor tem que reconstruir o índice ao adicionar um registro no meio da tabela. Certamente, a implementação de índice é de alguma forma destinada a reorganizações frequentes, mas essas operações ainda assim levam tempo e recursos do processador e, quando há um grande número de índices na tabela, a modificação de dados dentro dela pode ser muito mais lenta do que na mesma tabela sem índices!

Essas são duas razões principais que interferem na indexação geral. Além delas, há mais algumas observações que restringem a aplicação de índices. A primeira é a regra dos 20%. Ela diz que se a consulta de recuperação retorna mais de 20% dos registros da tabela, o uso de índice pode desacelerar a recuperação de dados! Certamente, a situação depende de uma consulta concreta e das condições definidas para a recuperação, mas devemos lembrar que 20% dos registros são um limite quando a eficiência do uso de índices se torna duvidosa. A segunda observação não é formulada tão claramente. Ela está conectada ao trabalho do otimizador do InterBase.

O otimizador é uma coleção de mecanismos que desenvolvem o cronograma de execução da consulta. Quando o usuário dá qualquer consulta SQL ao InterBase, ele especifica o que o servidor deve retornar após executar a consulta, mas não define COMO o servidor deve cumprir a consulta. O otimizador, com base na consulta dada, cria o cronograma de sua execução, ou seja, de onde e em que ordem os dados para executar a consulta serão obtidos, quais índices serão usados nisso. Quando o servidor analisa as condições de recuperação (estas são principalmente partes da expressão WHERE, ORDER BY, etc.) para cada campo incluído na condição, o servidor tenta usar o índice. Infelizmente, o algoritmo de criação do cronograma é incompleto e o otimizador frequentemente usa índices que não são muito eficazes para a consulta concreta, por causa do que o tempo de execução pode ser desacelerado essencialmente. Portanto, a criação de índices desnecessários pode levar à criação de cronogramas não otimizados.

Deve ser observado que no clone Yaffil esse problema é resolvido usando algoritmos modernos de criação de cronogramas. O terceiro caso em que o índice não é necessário são campos com um conjunto limitado de valores - por exemplo, o campo que armazena a informação sobre o sexo da pessoa e contém apenas dois valores possíveis - “F” e “M”; não há sentido em indexar esse campo. Então, consideramos as principais restrições à criação de índices. Agora devemos cobrir o problema de quando é necessário usar índices para alcançar melhoria de produtividade. Há 3 casos principais em que um campo deve ser indexado:

Quando esse campo é usado nas condições de recuperação em consultas
Quando junções de tabelas usam esse campo
Quando esse campo é usado na declaração de ordenação ORDER BY Se o campo é aplicado da maneira mencionada acima, criar o índice para ele pode levar à melhoria da produtividade da consulta.

Vamos considerar uma sintaxe de criação de índices. Aqui está um formato completo do comando DDL que permite criar índices:

CREATE [UNIQUE] [ASC[ENDING] | DESC[ENDING]] INDEX index ON table (col [, col …]);

A expressão mínima que cria o índice é a seguinte:

CREATE INDEX my_index ON Table_example(ID)

Neste exemplo, o índice com nome my_index é criado para a tabela Table_example, e o campo ID é o campo indexado. O índice é ascendente, ou seja, os valores nele são ordenados por ascensão, bem como não único, e isso significa que o campo ID pode ter vários valores idênticos. É certamente o exemplo mais simples de índice - o mais comum. Como podemos ver na descrição da sintaxe, o índice pode conter não um, mas vários campos. Tal índice é usado quando consultas são frequentemente executadas e contêm uma combinação de campos indexados nas condições de busca ou ordenação. Por exemplo, se temos uma tabela contendo os campos Sobrenome, Nome, Patronímico, tal índice será aplicado ao fazer a consulta que usa ordenação por Sobrenome, Nome e Patronímico. Em geral, não é necessário especificar as condições para todos os 3 campos aplicados no índice para usar suas vantagens. Se quisermos ordenar o resultado da consulta, o índice será usado no caso em que o primeiro campo na condição de ordenação coincide com o primeiro campo no índice. Por exemplo, nosso índice será aplicado no caso de ordenação por Sobrenome e Nome.

De acordo com a documentação, para otimização da execução de consultas contendo na declaração WHERE uma junção de campos com condição OR, devemos usar não o índice agregado, mas vários índices únicos para todos os campos incluídos na condição OR.

Quanto à questão da ordem de classificação do índice, ela pode ser ascendente ou descendente. Por que precisamos de ordens de classificação diferentes? Obviamente, para classificações diferentes! Se desejamos classificar pessoas pelo sobrenome em ordem ascendente, criamos o índice ascendente (ASC), e se em ordem descendente (de Z a A) - então descendente! Se quisermos ambos, temos que criar ambos os índices.

Suporte à integridade referencial usando índices

Há mais uma opção na definição de índice - UNIQUE. Se a especificarmos, o índice permitirá inserir apenas valores únicos na tabela. Na verdade, é uma base para a implementação de chaves únicas. Chaves únicas são amplamente utilizadas em bancos de dados. Ou seja, a CP é uma chave-índice única, mas nem toda CU é CP. Falamos apenas sobre CP acima. Uma chave primária é o tipo mais comumente usado de chave única. Ao criar uma chave primária para a tabela, um índice único é criado automaticamente. Ele recebe um nome composto por RDB$PRIMARYNNN, onde NNN é um número sequencial único dentro do banco de dados. Assim, duas restrições principais de integridade referencial - uma chave única e uma chave primária - são realizadas usando um índice único. É óbvio que a noção de unicidade é incompatível com a noção de valor indefinido. Em outras palavras, não deve haver nenhum valor do tipo NULL nos campos contidos em índices únicos. Antes de criar um índice único para um campo, é necessário definir a restrição NOT NULL. Se o índice for criado para dados que já existem, então, ao criar, o campo indexado será verificado quanto à presença de valores repetitivos. Se contiver, será proibido criar o índice.

Além das restrições de chave única e chave primária, o mecanismo de índices fundamenta a implementação de mais uma restrição de integridade referencial - uma chave estrangeira. A restrição de chave estrangeira é definida para um ou vários campos de qualquer tabela e impede a inserção de valores nesses campos que não estejam incluídos na chave primária da outra tabela, a tabela pai. Para implementar a chave estrangeira, ou seja, para realizar a verificação de se há um valor na tabela pai, um índice especial é criado automaticamente. Seu nome é RDB$FOREIGNNN, onde NNN é um número sequencial único dentro do banco de dados.

Por que o mecanismo de índices é usado para implementar as restrições de integridade referencial? A questão é que os índices no InterBase estão em uma posição especial e preferencial - diz-se que eles são executados fora do contexto das transações. Esta é uma propriedade muito importante. Falaremos sobre transações mais tarde, no capítulo dedicado a elas. Agora mencionaremos apenas que quando os índices estão fora das transações, isso significa que todos os usuários trabalhando simultaneamente com os dados na mesma tabela têm que observar as restrições de integridade referencial.

Otimização da produtividade do índice

No título desta parte podemos encontrar algum paradoxo - índices, como foi dito acima, servem para acelerar a execução de consultas, e acontece que eles também devem ser otimizados! Mas o que fazer (assim é a vida) - alguém tem que cuidar dos índices. O que acontece com os índices? Por que eles “perdem a forma”? Teremos que dizer mais uma vez que os índices são implementados como uma árvore binária. E quando um novo registro é adicionado (atualizado, excluído - como preferir) à tabela, um novo ramo é adicionado à árvore. Esses ramos são adicionados não ao meio da árvore, mas aos topos de outros ramos. Gradualmente a árvore se torna cada vez mais ramificada (ou desbalanceada), e a busca - menos eficaz. A reconstrução da árvore ou (em alguns casos) o recálculo de estatísticas pode melhorar a situação.

Periodicamente é necessário recriar o índice para restaurar sua produtividade. A recriação do índice acontece nos seguintes casos:

Ao reconstruir o índice usando o comando ALTER INDEX.
Ao excluir e recriar o índice usando os comandos DROP INDEX e CREATE INDEX.
Ao fazer backup e restaurar a partir de uma cópia de backup usando a ferramenta gbak.

Também é possível usar o recálculo de estatísticas. Mas deve-se entender que esta operação não altera o estado do índice, ela apenas informa ao otimizador informações precisas sobre seu estado, permitindo usar este índice corretamente. Em outras palavras, o recálculo de estatísticas não é a “cura” do índice, mas apenas o diagnóstico preciso de seu estado. Vamos considerar todas essas formas de otimização de índice em mais detalhes. O uso do comando ALTER INDEX tem o seguinte formato:

ALTER INDEX nome {ACTIVE | INACTIVE};

Aqui nome é o nome do índice, e ACTIVE e INACTIVE - dois estados do índice para os quais ele pode ser convertido usando o comando ALTER INDEX. O parâmetro ACTIVE significa que o índice está ativo e pode ser aplicado em todas as consultas e procedimentos. Se você definir o índice como INACTIVE, isso resultará na desativação de seu uso. Para reorganizar a árvore, dois comandos devem ser executados sequencialmente:

ALTER INDEX nome INACTIVE; ALTER INDEX nome ACTIVE;

Assim, o índice será reconstruído. O uso de ALTER INDEX tem uma série de restrições: você não pode reconstruir os índices usados em chaves primárias, únicas e estrangeiras; você não pode reconstruir o índice se ele estiver sendo usado por qualquer consulta no momento atual; e também para alterar o índice é necessário ter os direitos de administrador (SYSDBA) ou ser o criador do referido índice.

A recriação do índice usando os comandos DROP INDEX e CREATE INDEX leva à exclusão completa do índice do banco de dados e, em seguida, à sua criação a partir do zero. A sintaxe do comando DROP INDEX é óbvia:

DROP INDEX nome_do_índice;

Após a exclusão, é necessário criar o índice com o mesmo nome e parâmetros usando o comando CREATE INDEX, cuja sintaxe já consideramos. A forma de reconstruir o índice por sua recriação completa tem restrições semelhantes às do uso de ALTER INDEX.

A terceira forma de reconstruir o índice é baseada na propriedade das cópias de backup dos bancos de dados InterBase criadas pelo utilitário gbak. A questão é que, ao fazer backup, os dados incluídos no índice não são salvos em uma cópia de backup, apenas a definição do índice é armazenada. Ao restaurar a partir de uma cópia de backup, o índice é recriado. Se você quiser saber mais sobre o backup, veja o capítulo “Backup e restauração a partir de uma cópia de backup” (parte 4).

A quarta forma de melhorar a produtividade do índice é coletar estatísticas sobre os índices usando o comando SET STATISTICS. A estatística da tabela é um valor dentro do intervalo de 0 a 1, cujo valor depende do número de registros diferentes na tabela. O otimizador do InterBase usa estatísticas para definir a eficiência da aplicação deste ou daquele índice em uma consulta. Quando o número de registros na tabela pode alterar profundamente (por exemplo, devido a um grande número de inserções ou remoções), o recálculo de estatísticas pode melhorar consideravelmente a produtividade. O comando de recálculo de estatísticas é o seguinte:

SET STATISTICS INDEX nome;

Aqui nome é o nome do índice para o qual as estatísticas são recalculadas. O recálculo de estatísticas não reconstrói o índice e, por isso, está livre da maioria das restrições definidas para as formas descritas acima de melhorar a produtividade, exceto que apenas o criador do índice ou o administrador do sistema (o usuário com nome SYSDBA) pode recalcular estatísticas. Estatísticas corretas permitem que o otimizador tome a decisão correta sobre usar ou não qualquer índice.

Consideramos algumas formas de melhorar a produtividade dos índices. Usando os comandos ALTER INDEX e DROP/CREATE INDEX, podemos reconstruir quaisquer índices, exceto os índices de sistema criados automaticamente, destinados a fornecer integridade referencial. Se você quiser reconstruir esses índices, deve usar os comandos de alteração e criação de tabelas - ALTER TABLE e CREATE TABLE, pois esses índices são parte integrante das chaves tabulares.