Índices SQL explicados, pt. 2

Na primeira lição do SQL Indexes Explained , aprendemos a usar a classificação para acelerar a recuperação de dados. Embora nossa execução de consulta seja mais rápida depois que as linhas são classificadas, a classificação envolve ler cada linha pelo menos uma vez e movê-las. Isso torna o método mais lento e menos eficiente do que simplesmente ler a tabela inteira sequencialmente.

A conclusão lógica parece ser que devemos manter cópias ordenadas – que chamaremos oficialmente de índices SQL , prefixados com IX_ – de uma determinada tabela. Os algoritmos de recuperação do primeiro artigo seriam então aplicáveis ​​e não precisaríamos ordenar a tabela antes de começar.

O índice como uma cópia ordenada da tabela

Vamos dar uma olhada na implementação literal dessa ideia, novamente usando o Planilhas Google. Nossa planilha de Reservas se torna uma coleção de cinco planilhas contendo os mesmos dados. Cada folha é classificada de acordo com diferentes conjuntos de colunas.

Os exercícios aqui pretendem ser menos exigentes do que no artigo anterior do tutorial de índice SQL — eles podem ser feitos mais por sensação do que por cronômetro e contagem de linhas. Alguns exercícios parecerão muito semelhantes, mas desta vez, estamos explorando:

1. Como recuperar dados com mais eficiência ao usar índices separados em vez de tabelas primárias classificadas
2. Como manter a ordem em cada índice e tabela ao modificar dados

O tutorial anterior se concentrou em leituras, mas em muitas dinâmicas comuns de dados do mundo real - incluindo nossas reservas de hotel - temos que levar em conta os efeitos da indexação no desempenho de gravação, tanto para inserir novos dados quanto para atualizar dados existentes.

Exercício Preliminar: Cancelar uma Reserva

Para ter uma ideia do desempenho do índice SQL usando a estratégia de tabela classificada, sua tarefa é excluir uma reserva para o Cliente 12, a partir de 22 de agosto de 2020, no Hotel 4. Lembre-se de que você deve remover uma linha de todas as cópias de a tabela e manter a classificação correta.

Feito? Deve ficar claro que a ideia de manter várias cópias classificadas da tabela não é tão boa quanto parecia. Se ainda tiver dúvidas, também pode tentar reinserir a reserva que acabou de eliminar ou alterar a data de uma reserva existente.

Embora as cópias classificadas da tabela permitam uma recuperação mais rápida, como aprendemos agora, a modificação de dados é um pesadelo. Sempre que precisarmos adicionar, excluir ou atualizar uma linha existente, teremos que recuperar todas as cópias da tabela, encontrar uma linha e/ou o local onde ela deve ser adicionada ou movida e, finalmente, mover blocos de dados.

Índices SQL usando endereços de linha

Esta planilha contém índices que usam uma abordagem diferente. As linhas de índice ainda são classificadas de acordo com critérios específicos, mas não mantemos todas as outras informações na linha de índice. Em vez disso, mantemos apenas o “endereço da linha”, o endereço da linha na planilha Reservas – representando a própria tabela – na coluna H.

Todas as implementações de RDBMS usam um recurso de nível de sistema operacional para localizar rapidamente o bloco no disco usando um endereço físico. Os endereços de linha geralmente consistem em um endereço de bloco mais a posição da linha dentro do bloco.

Vamos fazer alguns exercícios para aprender como esse design de índice funciona.

Exercício 1: Todas as Reservas de um Cliente

Assim como no primeiro artigo, você vai simular a execução da seguinte consulta SQL:

 SELECT * FROM Reservations WHERE ClientID = 12;

Novamente, existem duas abordagens razoáveis. A primeira é simplesmente ler todas as linhas da tabela Reservas e buscar apenas as linhas que correspondem aos critérios:

 For each row from Reservations If Reservations.ClientID = 12 then write down Reservations.*

A segunda abordagem envolve a leitura de dados da planilha IX_ClientID e, para qualquer item que corresponda aos critérios, encontrar uma linha na tabela Reservation com base no valor rowAddress:

 Get first row from IX_ClientID where ClientID = 12 While IX_ClientID.ClientID = 12 Fetch Reservations.* where rowAddress = IX_ClientID.rowAddress Write down Reservations.* Get next row from IX_ClientID

Aqui, a expressão Get first row from é implementada por um loop semelhante aos vistos no artigo anterior:

 Repeat Fetch next row from IX_ClientID Until ClientID >= 12

Você pode encontrar uma linha com um determinado rowAddress deslizando para baixo até encontrar uma linha ou usando um filtro na coluna rowAddress.

Se houvesse apenas um punhado de reservas a serem retornadas, a abordagem usando o índice seria melhor. No entanto, com centenas — ou às vezes apenas dezenas — de linhas a serem retornadas, simplesmente usar a tabela Reservas diretamente pode ser mais rápido.

O volume de leituras depende do valor de ClientID. Para o maior valor, você deve ler todo o índice, enquanto para o menor valor, ele está no início do índice. O valor médio é metade do número de linhas.

Voltaremos a essa parte mais tarde e apresentaremos uma solução eficiente. Por enquanto, vamos nos concentrar na parte depois de encontrar a primeira linha que corresponde aos nossos critérios.

Exercício 2: O número de reservas a partir de uma determinada data

A tarefa é contar o número de check-ins no dia 16 de agosto de 2020, usando o novo design do índice.

 SELECT COUNT (*) FROM Reservations WHERE DateFrom = TO_DATE('2020-08-16','YYYY-MM-DD');

A abordagem de usar o índice apropriado para contagem é superior a uma varredura de tabela, independentemente do número de linhas envolvidas. A razão é que não precisamos acessar a tabela Reservas – temos todas as informações de que precisamos no próprio índice:

 Count := 0 Get first row from IX_DateFrom where DateFrom >= '2020-08-16' While found and DateFrom < '2020-08-17' Count := Count + 1 Get next row from IX_DateFrom Write down Count

O algoritmo é basicamente o mesmo que usa tabelas ordenadas. No entanto, a linha do índice é muito menor que a linha da tabela, portanto, nosso RDBMS teria que ler menos blocos de dados do disco.

Exercício 3: Investigação Criminal (Lista de Hóspedes Dado o Hotel e o Período)

Vamos preparar uma lista dos hóspedes que chegaram ao Hotel 3 nos dias 13 e 14 de agosto de 2020.

 SELECT ClientID FROM Reservations WHERE DateFrom BETWEEN ( TO_DATE('2020-08-13','YYYY-MM-DD') AND TO_DATE('2020-08-14','YYYY-MM-DD') ) AND HotelID = 3;

Podemos ler todas as linhas da tabela Reservas ou usar um dos índices disponíveis. Depois de fazer o mesmo exercício com uma tabela ordenada de acordo com critérios específicos, descobrimos que o índice IX_HotelID_DateFrom é o mais eficiente.

 Get first row from IX_HotelID_DateFrom where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and DateFrom < '2020-08-15' and IX_HotelID_DateFrom.HotelID = 3 Fetch Reservations.* where rowAddress = IX_HotelID_DateFrom.rowAddress Write down Reservations.ClientID Get next row from IX_HotelID_DateFrom

Podemos projetar um índice ainda mais eficiente?

Acessamos a tabela por causa do valor ClientID , a única informação que precisamos para a lista de convidados que estamos relatando. Se incluirmos esse valor no índice SQL, não precisaremos acessar a tabela. Tente preparar uma lista lendo apenas de um índice, IX_HotelID_DateFrom_ClientID :

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Write down ClientID Get next row from IX_HotelID_DateFrom_ClientID

Quando o índice contém todas as informações necessárias para a execução da consulta, dizemos que o índice cobre a consulta.

Exercício 4: Lista de nomes de convidados em vez de IDs

Uma lista de identidades de convidados seria inútil para um policial investigando um crime. Precisamos fornecer nomes:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND r.HotelID = 3;

Para fornecer uma lista, além dos dados da tabela Reservations , também precisamos de uma tabela Clients contendo informações dos hóspedes, que podem ser encontradas nesta planilha do Google.

Este exercício é semelhante ao anterior, assim como a abordagem.

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Clients.ClientName Get next row from IX_HotelID_DateFrom_ClientID

A expressão Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID pode ser implementada por varredura de tabela ou usando nosso índice. Se usarmos uma varredura de tabela, para cada ClientID do loop While , teríamos que ler em média a metade das linhas da tabela Clients :

 -- Get row from Clients using table scan Repeat Fetch next row from Clients Until ClientID = IX_HotelID_DateFrom_ClientID.ClientID or not found If found Write down ClientName

A implementação de índice que consideramos até agora – vamos chamá-la de implementação de índice “plana” – não seria muito útil. Teríamos que ler o mesmo número de linhas (embora linhas menores) do índice e, em seguida, pular para a linha em Clients usando RowAddress :

 -- Get row from Clients using flat index Repeat Fetch next row from Clients_PK_Flat Until ClientID >= IX_HotelID_DateFrom_ClientID.ClientID If found Fetch Clients.* where rowAddress = Clients_PK_Flat.rowAddress Write down ClientName

Observação: aqui, PK se refere a “chave primária”, um termo que exploraremos mais adiante na série.

Existe uma maneira de fazer isso sem ter que ler tantas linhas? Sim - é exatamente para isso que servem os índices de árvore B.

Índices de Árvore Balanceada (Árvore B)

Vamos dividir as linhas de Clients_PK_Flat em blocos de quatro linhas e criar uma lista contendo o valor do último ClientID do bloco e o endereço do início do bloco (coluna IndexRowAddress ). A estrutura de dados de índice de banco de dados resultante - você pode encontrar na planilha Clients_PK_2Levels. Experimente como a nova estrutura o ajuda a encontrar um cliente com ClientID de 28. O algoritmo deve ficar assim:

 Fetch Level2.* Loop Leaf_address := Level3Address Exit when ClientID >= 28 Fetch next row from Level2 Fetch Level3.* where Level3Address = Leaf_address -- 3-21 Loop Client_address := RowAddress Exit when ClientID >= 28 Fetch next row from Level 3 Fetch Clients.* where rowAddress = Client_address -- 42 Write down Clients.*

Você provavelmente descobriu que podemos adicionar outro nível. O nível 1 consiste em quatro linhas, como você pode ver na guia IX_Clients_PK. Para encontrar o nome do convidado com um ClientID de 28, você deve ler três blocos (nós) de dados - um por nível - da estrutura de chave primária e, finalmente, pular para a linha Clientes com endereço 42.

A estrutura desse índice SQL é chamada de árvore balanceada. A árvore é balanceada quando o caminho do nó raiz para cada nó no nível da folha tem o mesmo comprimento, a chamada profundidade da árvore B. No nosso caso, a profundidade é três.

A partir de agora, consideraremos que cada índice tem uma estrutura de árvore B, mesmo que nossas planilhas contenham apenas entradas em nível de folha. Os fatos mais importantes a saber sobre a árvore B são:

• A estrutura do índice B-tree é o índice mais comumente usado por todos os principais RDBMSs no mercado.
• Todos os níveis de uma árvore balanceada são ordenados por valores de coluna chave.
• Os dados são lidos do disco em blocos.
• Um nó de árvore B contém um ou mais blocos.
• O fator mais importante que afeta o desempenho da consulta é o número de blocos lidos do disco.
• O número de itens em cada novo nível de árvore B, começando pela raiz e terminando no nível folha, aumenta exponencialmente.

Exercício 5: Investigação Criminal, Parte II

Agora, o inspetor de polícia está procurando uma lista de nomes de hóspedes correspondentes, datas de chegada e nomes de hotéis de todos os hotéis da cidade A.

 SELECT h.HotelName, r.DateFrom as CheckInDate, c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID JOIN Hotels h ON r.HotelID = h.HotelID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND h.City = 'A';

Abordagem 1

Se usarmos o índice IX_DateFrom_HotelID_ClientID , então para cada linha do intervalo de datas, teríamos que acessar a tabela Hotels e verificar se o hotel é da cidade A. Se for, teríamos que acessar a tabela Clients também para leia o nome do cliente.

 For each row from IX_DateFrom_HotelID_ClientID where DateFrom between '2020-08-13' and '2020-08-14' For each row from Hotels where HotelID = IX_DateFrom_HotelID_ClientID.HotelID If Hotels.City = 'A' then Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Abordagem 2

Usar IX_HotelID_DateFrom_ClientID nos dá um plano de execução mais eficiente.

 For each row from Hotels where City = 'A' For each row from IX_HotelID_DateFrom_ClientID where HotelID = Hotels.HotelID and DateFrom between '2020-08-13' and '2020-08-14' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Na tabela Hotels , encontramos todos os hotéis da cidade A. Conhecendo o ID desses hotéis, podemos ler os itens subsequentes do índice IX_HotelID_DateFrom_ClientID . Dessa forma, após encontrar a primeira linha no nível da folha da árvore B para cada hotel e data, não lemos as reservas de hotéis fora da cidade A.

Aqui, podemos ver que quando temos um índice de banco de dados apropriado para nossos objetivos, uma junção adicional pode realmente tornar uma consulta mais rápida.

A estrutura da árvore B e como ela é atualizada sempre que uma linha é inserida, atualizada ou excluída será abordada com mais detalhes quando explicar a motivação para o particionamento e seu impacto. A questão é que podemos considerar essa operação rápida sempre que usarmos um índice.

A consulta de índice em SQL: os detalhes fazem toda a diferença

Quando se trata de índices e bancos de dados, trabalhar no nível da linguagem SQL oculta até certo ponto os detalhes da implementação. Esses exercícios destinam-se a ajudá-lo a ter uma ideia de como os planos de execução funcionam ao usar diferentes índices SQL. Depois de ler o artigo, espero que você consiga adivinhar o melhor plano de execução com base nos índices disponíveis e nos índices de design que tornariam uma consulta o mais rápida e eficiente possível.

Na próxima parte desta série, usaremos e expandiremos as habilidades recém-adquiridas para investigar e entender as melhores práticas e antipadrões mais comuns no uso de índices em SQL. Tenho uma lista de boas e melhores práticas que quero abordar na próxima parte, mas para tornar o próximo artigo mais relevante para suas necessidades e experiência, sinta-se à vontade para postar suas próprias perguntas que gostaria de ver respondidas .

Na parte final de SQL Indexes Explained , também aprenderemos sobre particionamento de tabela e índice, as motivações certas e erradas para usá-lo e seu impacto no desempenho da consulta e na manutenção do banco de dados.