Resolvendo gargalos com partições e índices SQL

Publicados: 2022-03-11

Na primeira lição do SQL Indexes Explained, aprendemos que as consultas SELECT são mais rápidas quando os dados já estão ordenados por valores de colunas específicas.

Na segunda lição, aprendemos a estrutura básica dos índices de árvore B e como usá-los para reduzir o volume de dados que acessamos durante a execução de uma consulta. Também descobrimos como implementar consultas que unem várias tabelas e como os índices podem acelerar essas consultas.

Também destacamos dois cenários em que o uso de índices em SQL é útil. Quando os índices estão cobrindo índices, contendo todas as colunas da consulta – das condições WHERE , JOIN e da lista SELECT – evitamos ler a tabela correspondente inteiramente. Como alternativa, os índices podem ajudar quando reduzem o número de blocos de dados acessados a uma pequena fração do tamanho da tabela.

Caso contrário, é mais eficiente varrer toda a tabela do que ler um índice e pular aleatoriamente para as linhas da tabela correspondentes.

Consultas de intervalo SQL

As consultas que podem aproveitar os índices normalmente incluem condições que reduzem significativamente o intervalo de valores possíveis que uma ou mais colunas podem assumir. As consultas de intervalo restringem os dados com base em condições como "o valor da coluna A deve estar entre X e Y".

Um bom exemplo disso é a consulta do Exercício 4 da segunda lição:

 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;

Aqui temos dois intervalos. O primeiro é o intervalo de datas, o período entre 13 de agosto de 2020 e 14 de agosto de 2020. O segundo é o menor intervalo numérico possível. A condição é equivalente a r.HotelID BETWEEN 3 AND 3 .

Exercício 1: Períodos (consultas de intervalo de data e hora)

Vamos adicionar uma coluna chamada CheckInTime à tabela Reservations . Você pode ver dados de amostra nesta planilha. Observe que há um único índice cobrindo CheckInTime e ClientId .

Escreva uma consulta que retorne os nomes dos clientes que fizeram check-in em 15 de agosto de 2020.

Desenvolvedores SQL inexperientes geralmente escrevem a seguinte consulta:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE TO_DATE(r.CheckInTime, 'YYYY-MM-DD') = '2020-08-15';

Eles assumem que a execução da consulta ficaria assim:

 Get first row from IX_CheckInTime_ClientID where TO_DATE(CheckInTime, 'YYYY-MM-DD') = '2020-08-15' While found and TO_DATE(CheckInTime, 'YYYY-MM-DD') = '2020-08-15' Fetch Clients.* where ClientID = IX_CheckInTime_ClientID.ClientID Write down Clients.ClientName Get next row from IX_CheckInTime_ClientID

O problema é que nem um único RDBMS no momento da redação deste artigo é capaz de gerar tal plano de execução. Eles veem TO_DATE (sintaxe Oracle) como uma função que transforma o valor da coluna CheckInTime em algo não indexado. Então, os planos de execução que eles tendem a gerar são assim:

 For each row from IX_CheckInTime_ClientID If TO_DATE(CheckInTime, 'YYYY-MM-DD') = '2020-08-15' then Fetch Clients.* where ClientID = IX_CheckInTime_ClientID.ClientID Write down Clients.ClientName

Executar isso seria mais rápido do que ler todas as linhas da tabela Reservations porque a linha do índice é mais estreita que a linha da tabela. Uma linha menor significa que menos blocos precisariam ser acessados do disco.

No entanto, sabemos que o primeiro plano de execução seria muito mais eficiente. Para persuadir nosso RDBMS a usar essa abordagem, precisamos reescrever a consulta:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.CheckInTime >= TO_DATE('2020-08-15 00:00:00', 'YYYY-MM-DD HH:MI:SS') AND r.CheckInTime < TO_DATE('2020-08-16 00:00:00', 'YYYY-MM-DD HH:MI:SS');

Esta é uma consulta de intervalo adequada, que todo bom RDBMS entende. Nosso RDBMS descobre que queremos dados da tabela Reservations onde o valor de CheckInTime — não algo derivado dele — pertence ao intervalo bem definido. O plano de execução que ele gera seria mais parecido com:

 Get first row from IX_CheckInTime_ClientID where CheckInTime >= '2020-08-15 00:00:00' While found and CheckInTime < '2020-08-16 00:00:00' Fetch Clients.* where ClientID = IX_CheckInTime_ClientID.ClientID Write down Clients.ClientName Get next row from IX_CheckInTime_ClientID

Isso é o que realmente queremos: alavancar não apenas o índice em si, mas também o fato de ele ser classificado.

Exercício 2: `LIKE` com um curinga no início

Desta vez, nosso detetive chega ao hotel com informações vagas sobre o suspeito: apenas que o sobrenome termina com “-filho”. O detetive quer os nomes e sobrenomes de todos esses convidados:

 SELECT FirstName, LastName FROM Clients WHERE LastName LIKE '%son';

Para a tabela Clients e um índice em LastName , usaremos esta planilha. Anote os resultados que a consulta retornaria. Pense em diferentes abordagens que você pode aplicar.

Abordagem de digitalização de tabela

A estratégia mais simples é ler todos os dados da tabela e anotar os nomes dos convidados quando o sobrenome terminar com “-son”:

 For each row from Clients If LastName like '%son' then write down FirstName, LastName

Aqui, teríamos que ler a tabela inteira sequencialmente.

Usando um índice

Vamos tentar aproveitar o índice na coluna LastName . Vá para a planilha IX_LastName, use-a para encontrar todos os clientes que satisfaçam o critério fornecido e anote seus nomes.

Acontece que você tem que ler todo o índice para encontrar todos os Andersons, Robinsons e Thompsons da tabela. Isso é melhor do que usar uma varredura de tabela? Além de ler o índice inteiro, você também tinha que encontrar, para cada entrada correspondente, a linha correspondente da tabela usando o valor rowAddress e, em seguida, anotar o FirstName a partir daí:

 For each row from IX_LastName If LastName like '%son' then Fetch Clients.* where RowAddress = IX_LastName.RowAddress Write down FirstName, LastName

Para nós, foi mais simples e rápido ler a tabela sequencialmente. Para nosso RDBMS, dependeria da porcentagem de linhas que satisfazem os critérios. Se houver apenas um punhado de Andersons, Robinsons e Thompsons em uma tabela grande, um RDBMS leria menos blocos de dados de entradas de índice muito mais restritas, mesmo que tivesse que ler alguns blocos da tabela quando uma correspondência fosse encontrada. Caso contrário, a verificação da tabela leva menos tempo.

Ordenar os dados no índice não fornece nenhuma ajuda com essa consulta. O tamanho menor da linha do índice pode ser útil, mas apenas algumas vezes.

Exercício 3: `LIKE` com um curinga no final

Da próxima vez que nosso detetive vier, precisamos encontrar todos os clientes cujos sobrenomes comecem com “Rob-”.

 SELECT FirstName, LastName FROM Clients WHERE LastName LIKE 'Rob%';

Tente extrair os dados correspondentes à consulta da mesma planilha.

Se você usou a abordagem de verificação de tabela, perdeu a oportunidade de aproveitar ao máximo o índice IX_LastName . É muito mais rápido localizar a primeira entrada do índice começando com “Rob-” (Roberts), ler as linhas subsequentes (Robertses e Robinsons) e parar quando o LastName não corresponder mais ao critério:

 Get first row from IX_LastName where LastName <= 'Rob' While found and LastName < 'Roc' Fetch Clients.* where rowAddress = IX_LastName.rowAddress Write down FirstName, LastName Get next from IX_LastName

Nesse caso, após a pesquisa da árvore B para a primeira entrada, lemos apenas as entradas que satisfazem o critério. Paramos de ler assim que lemos um nome que não corresponde ao critério.

Resolvendo problemas de dimensionamento da árvore B

Normalmente, quando implantamos um novo banco de dados, há algumas tabelas de pesquisa preenchidas e tabelas transacionais vazias. O sistema funciona sem problemas desde o início, especialmente se respeitarmos as boas práticas de design de banco de dados normalizando tabelas; criar chaves primárias, estrangeiras e exclusivas; e suporte a chaves estrangeiras com índices correspondentes.

Após alguns meses ou anos, quando o volume de dados aumentou significativamente a complexidade do sistema e do banco de dados, começamos a notar a degradação do desempenho. Surgem opiniões sobre por que o sistema está desacelerando e o que fazer a respeito.

A opinião popular é muitas vezes que o tamanho do banco de dados é o principal culpado. A solução parece ser remover os dados históricos que não precisamos diariamente e colocá-los em um banco de dados separado para relatórios e análises.

Vamos explorar a suposição principal primeiro.

Consultas de intervalo SQL: o tempo de execução depende do tamanho da tabela?

Considere uma consulta de intervalo típica de uma única tabela:

 SELECT Column1, …, ColumnN FROM Table WHERE Column BETWEEN X AND Y;

Supondo que haja um índice em Column , o plano de execução ideal é:

 Get first row from IX_Column where Column between X and Y While found and Column <= Y Fetch Table.* where rowAddress = IX_Column.rowAddress Write down Column1, …, ColumnN Get next row from IX_Column

Vamos contar os blocos que um RDBMS terá que ler para retornar esses dados.

A parte Get first row é implementada pela pesquisa de árvore B que apresentamos na segunda lição. O número de blocos que ele precisa ler é igual à profundidade da árvore B. Depois disso, lemos os itens subsequentes do nível folha do índice.

Com consultas OLTP, normalmente todos os resultados serão encontrados em um bloco de índice (às vezes dois, mas raramente mais). Além disso, para cada entrada do índice, temos acesso a um bloco na tabela para encontrar a linha correspondente com base em seu endereço. Algumas linhas da tabela podem estar dentro do mesmo bloco de tabela que já carregamos, mas para simplificar a estimativa, vamos supor que carregamos um novo bloco toda vez.

Então a fórmula é:

B = D + 1 + R

B é o número total de blocos lidos, D é a profundidade da árvore B e R é o número de linhas retornadas pela consulta.

O único parâmetro que depende do número de linhas na tabela é D, a profundidade da árvore B.

Para simplificar os cálculos e fazer uma observação, suponha que 1.000 entradas de índice caibam em um bloco. D = 1, desde que haja menos de 1.000 linhas na tabela. Para tabelas que contêm transações comerciais, esse pode ser o caso no primeiro dia útil após a implantação do sistema. Em breve, a profundidade da árvore B aumentará. Enquanto houver menos de 1 milhão de linhas na tabela, o índice consistirá em dois níveis.

Se nos incomodamos com os tempos de resposta lentos do banco de dados e culpamos o volume de dados por isso, observe que as tabelas de transações geralmente têm meros milhões de linhas. Como apenas 1 milhão de linhas se ajustam a um índice de árvore B de dois níveis, a profundidade deve ser de pelo menos três. A profundidade não aumentará para quatro, a menos que haja mais de 1 bilhão de linhas na tabela. Agora temos uma estimativa mais precisa:

B = 4 + R

Se R for pequeno, reduzir a profundidade da árvore B de volta para dois aceleraria significativamente a consulta. Quando pesquisamos por um valor de chave primária ou exclusiva, o sistema lerá quatro blocos em vez de cinco, o que representa uma melhoria de 20%. Se a consulta retornar mais linhas, a melhoria pode não ser perceptível. O problema é que, para muitos aplicativos, talvez não possamos dar suporte às operações de negócios necessárias mantendo menos de 1 milhão de transações no banco de dados.

Portanto, a conclusão parece ser que o tamanho da tabela não importa; em outras palavras, mover dados históricos é uma perda de tempo e recursos.

Mas não tão rápido: vamos aprender mais sobre a estrutura de um índice de árvore B e como as alterações de dados o afetam.

Detalhes de implementação do índice B-tree

Em nossa cobertura de índices de árvore B na segunda lição, vimos que todos os níveis de uma árvore balanceada são (fisicamente) ordenados por valores de coluna-chave. No entanto, quando queremos inserir, atualizar ou excluir um item, muitas vezes temos que mover uma grande quantidade de dados para preservar a ordem.

Digamos que estamos inserindo no meio de um bloco que está cheio. Temos que dividir o bloco, reorganizar os dados e às vezes até atualizar dados em outro nível de árvore B apontando para o atual.

Para tornar esses casos mais eficientes, cada item de índice contém ponteiros para as linhas anterior e seguinte, tornando-o um link duplo. Para inserir em geral, isso significa apenas escrever os novos itens o mais próximo possível do anterior e corrigir os ponteiros.

Quando também precisamos dividir um bloco, devemos escrever um novo item no nível anterior da árvore B. Esta é apenas uma questão de corrigir mais alguns ponteiros - não há necessidade de reescrever grandes porções da árvore. Após uma divisão, ambos os blocos de dados ficam aproximadamente pela metade. Dependendo de onde há espaço livre no disco, os blocos “vizinhos” podem estar fisicamente bem distantes.

Após algum tempo, a fragmentação do índice aumenta e a lentidão na execução da consulta se torna perceptível. Com um RDBMS executando consultas da maneira como as descrevemos, a suposição da ordem e proximidade dos itens torna-se cada vez menos correta, levando a muito mais leituras. Na pior das hipóteses, com todos os blocos de dados meio vazios, o sistema precisa ler o dobro de blocos.

Manutenção do Índice B-tree

A cura para isso é a desfragmentação do índice (ou “reindexação”). Cada RDBMS fornece um recurso para recriar um índice inteiro; após a reindexação, os índices são novamente ordenados fisicamente.

A reindexação é uma operação bastante rápida, embora leia e grave um grande volume de dados. Os RDBMSs modernos normalmente oferecem dois modos de reindexação, com o mais rápido exigindo que as tabelas sejam bloqueadas durante o processamento. De qualquer forma, é preferível reindexar fora do horário de pico. Caso contrário, o processamento pode diminuir o desempenho do banco de dados.

Excluindo dados históricos

Quando temos tabelas com bilhões ou mesmo centenas de milhões de linhas, pode não ser viável concluir uma operação de reindexação fora do horário de pico.

Para evitar essa situação, mover dados históricos de um banco de dados OLTP pode ser a solução. No entanto, se simplesmente excluirmos as linhas mais antigas que um limite específico, tornaremos os índices ainda mais fragmentados e precisaremos reindexá-los com ainda mais frequência.

Particionamento SQL para o resgate?

Existe uma forma de evitar a fragmentação causada pela remoção de dados históricos, mantendo apenas as transações “ativas” no banco de dados de produção. A ideia que todos os principais RDBMSs implementam é dividir uma tabela em pedaços menores (chamados de partições ) e fornecer a capacidade de adicioná-los, removê-los e até alterná-los entre tabelas (por exemplo, de uma tabela ativa para uma histórica com o mesmo estrutura).

Vamos dar uma olhada na tabela Reservations conforme particionada nesta planilha. A tabela é dividida por mês, com nomes de partição mapeados para períodos de data e outras planilhas. Para ver como uma consulta em uma tabela particionada é executada, faremos alguns exercícios.

Exercício 4: Consulta de partição em SQL

Na planilha vinculada acima, tente extrair os dados solicitados pela consulta a seguir, sem usar nenhum índice:

 SELECT HotelID, ReservationID, ClientID, DateFrom, DateTo FROM Reservations WHERE DateFrom BETWEEN TO_DATE('2021-03-01','YYYY-MM-DD') AND TO_DATE('2021-03-03');

Você provavelmente descobriu que primeiro precisa examinar a planilha de mapeamento de partição e encontrar a partição que contém as reservas de março de 2021. Depois disso, você abriu a partição correspondente, leu os dados sequencialmente e filtrou as linhas que não satisfizeram a doença.

Embora simples, você provavelmente não gostou de manter tão poucas linhas depois de ler tantas. Ler a partição de março era melhor do que ler toda a tabela de reservas, mas ainda não era o ideal. E os índices?

Índices Globais

RDBMSs nos permitem criar um índice global para cobrir todas as partições de uma tabela particionada. Mas não há diferença entre como os índices globais e regulares funcionam: os índices globais não reconhecem partições. Assim, as consultas CRUD usando um índice global não envolvem o mapa de partição para sua tabela.

Só precisamos atualizar o mapa de partição quando descartamos uma partição inteira. Em seguida, temos que remover todas as linhas do índice que apontam para a partição removida. Isso significa que todo o índice global precisa ser reconstruído.

Uma janela de interrupção permanece necessária porque os índices não podem ser usados até que os itens obsoletos sejam removidos. Se pudermos descartar partições regularmente, limitando o número de partições ativas, a operação de reindexação poderá se encaixar na janela de interrupção. Portanto, o uso de partições ajuda com o problema original, reduzindo o tempo necessário para tarefas de manutenção, incluindo a manutenção de índices globais.

Mas e se ainda não pudermos arcar com a interrupção?

Índices Particionados Globalmente

Essa estratégia resolve esse problema: simplesmente particionamos o índice da mesma forma que particionamos a tabela. Nas planilhas às quais a planilha de partição está vinculada, cada partição contém sua parte da tabela Reservations e uma folha de índice chamada IX_DateFrom, ambas particionadas por DateFrom .

Para executar a consulta do Exercício 4, um RDBMS examinaria primeiro um mapa de partições de índice e identificaria quais partições contêm datas do intervalo. (No nosso caso, é apenas uma partição de índice.) Depois disso, ele usaria pesquisas de árvore B, percorreria o nível folha e, finalmente, acessaria a tabela usando o endereço de linha correspondente.

Quando descartamos uma partição de uma tabela, basta descartar a partição correspondente do índice. Não é necessário tempo de inatividade.

Índices locais

A principal desvantagem dos índices particionados globalmente é que precisamos cuidar de descartar a tabela e a partição de índice correspondente. Há apenas um pequeno custo extra associado à leitura e manutenção do próprio mapa de partições de índice.

Os índices locais envolvem uma abordagem semelhante, mas ligeiramente diferente. Em vez de particionar um único índice global, criamos um índice local dentro de cada partição de tabela. Ao fazer isso, os índices locais compartilham a principal vantagem dos índices particionados globalmente — ou seja, sem tempo de inatividade — enquanto evitam suas desvantagens.

Parece uma solução perfeita. Mas antes de comemorarmos, vamos investigar o possível plano de execução de algumas consultas.

Exercício 5: Índice Particionado Localmente

Tente executar a consulta novamente, desta vez usando o índice particionado localmente em DateFrom .

Você provavelmente usou este plano de execução:

 For all partitions where [StartDateFrom, StartDateTo) intersects ['2021-03-01', '2021-03-03'] Get first row from IX_DateFrom where DateFrom between '2021-03-01' and '2021-03-03' While found and DateFrom < '2021-03-04' Fetch Reservations.* where RowAddress = IX_DateFrom.RowAddress Write down HotelID, ReservationID, ClientID, DateFrom, DateTo Get next row from IX_DateFrom

Temos sorte que todas as datas pertencem a uma única partição, então tivemos que percorrer apenas um índice local. Se o período fosse de seis meses, teríamos que ler seis índices locais.

Exercício 6: Em contraste

Sua tarefa é usar o mapa de partição Reservas novamente, desta vez para fazer uma lista de períodos em que o Cliente 124 visitou o Hotel 1:

 SELECT DateFrom, DateTo FROM Reservations WHERE ClientID = 124 AND HotelID = 1;

Aqui podemos ver a principal desvantagem dos índices locais. Tivemos que ler a folha de índice local IX_HotelID_CientID de cada partição da tabela Reservations :

 For all partitions Get first row from IX_HotelID_ClientID where ClientID = 124 and HotelID = 1 While found and ClientID = 124 and HotelID = 1 Fetch Reservations.* where RowAddress = IX_HotelID_ClientID.RowAddress Write down DateFrom, DateTo Get next row from IX_HotelID_ClientID

Essa execução claramente leria mais blocos e levaria mais tempo do que se a tabela não fosse particionada.

Portanto, embora tenhamos encontrado uma maneira de manter a integridade de nossos índices durante o período fora de pico, a estratégia também tornou algumas de nossas consultas mais lentas.

Se nosso modelo de negócio nos permite manter um pequeno número de partições ou pelo menos as consultas mais frequentes contiverem critérios que permitam ao RDBMS ler apenas uma ou duas partições, essa solução pode ser o que precisamos. Caso contrário, é melhor evitar o particionamento e trabalhar para melhorar o modelo de dados, índices e consultas — e aprimorar o servidor de banco de dados.

Índices em SQL: o que aprender a seguir

Este é o fim de nossa jornada. Em SQL Indexes Explained, concentrei-me na implementação de índice que é comum a todos os RDBMSs modernos. Também me concentrei em tópicos nos quais os desenvolvedores de aplicativos estão interessados, em detrimento de tópicos que normalmente dizem respeito aos administradores de banco de dados. Este último faria bem em pesquisar o impacto do fator de preenchimento na fragmentação do índice, mas as pessoas em ambas as funções provavelmente acharão útil ler mais sobre:

Cache de dados e índices
Estruturas de índice não-árvore B, como índices hash, GiST, bitmap e columnstore
Índices clusterizados (conhecidos como tabelas organizadas por índice no Oracle)
Índices funcionais
Índices parciais

A abordagem de particionamento que discutimos é o particionamento de intervalo . É o tipo de particionamento mais usado, mas existem outros, como particionamento de hash e particionamento de lista. Além disso, alguns RDBMSs oferecem a opção de vários níveis de particionamento.

Por fim, os desenvolvedores de SQL fariam bem em explorar outros tópicos importantes sobre a execução de consultas RDBMS — primeiro, análise de consultas, depois compilação, armazenamento em cache e reutilização do plano de execução baseado em custo.

Para os quatro RDMBSs com os quais tenho experiência, recomendo estes recursos como próximos passos:

Oráculo

Visão geral do otimizador
Índices e tabelas organizadas por índice
Gerenciando índices
Visão geral das partições
Guia de particionamento
Pergunte ao Tom

PostgreSQL

Processamento de consultas
Índices no PostgreSQL
Índices no PostgreSQL (documentação oficial)
Gerenciamento de buffer
Particionamento de Tabela
Guia de particionamento

Microsoft SQL Server

Arquitetura de processamento de consultas
Índices
Tabelas e índices particionados

MySQL/MariaDB

Entendendo o Plano de Execução de Consulta
Otimização e Índices
Particionamento - Noções básicas
Particionamento - Documentação
Documentação do MariaDB: Otimização de consultas e índices