Fragmentação de índices – o básico

A fragmentação de índices no SQL Server é assunto antigo e recorrente em notas de blogs, em fóruns e também em grupos de sql server no telegram e no whatsapp.
Eu tinha lá minhas dúvidas e resolvi estudar o assunto, procurando conhecer as entranhas da fragmentação. O resultado é este artigo sobre fragmentação de índices no SQL Server, cuja publicação será dividida em partes.

1. Introdução

Esta é a primeira parte do artigo sobre fragmentação de índices. Introdutória e simples; somente o básico para permitir a compreensão do que é essa fragmentação. Há uma segunda parte, que está quase pronta e então será possível definir a continuação para este artigo.

O artigo não trata de índices e também não explica o que são. Muito menos explica quais vantagens e desvantagens no uso de índice, mas demonstra para índices clustered quando ocorre a fragmentação, tipos de fragmentação, como medir a fragmentação, etc. Talvez um pouco mais.

Nesta parte inicial do artigo vamos apresentar modelo simplificado do que ocorre quando linhas são incluídas, alteradas e apagadas em uma tabela, sem entrar em detalhes de implementação.

2. Modelo simplificado

A estrutura básica de armazenamento interno é denominada de página (page) e é nela que as linhas são armazenadas. Em nosso modelo reduzido vamos considerar que cada página tem capacidade de 100 bytes e que as linhas são inicialmente acrescentadas do início para o final. Além disso, ao final de cada página há um vetor em ordem invertida, denominado row offset array, que aponta para o início de cada linha, dentro da página.

A figura abaixo será utilizada para representar a página, com as posições numeradas de 0 a 99:

p046_figura 2.1

A tabela fictícia, demoFrag, contém duas colunas de preenchimento obrigatório:

p046_figura 2.2

e a coluna Cod é chave primária de índice clustered.

Colunas de texto de tamanho variável (varchar, nvarchar) utilizam 2 bytes adicionais para armazenar o tamanho do texto mas nos exemplos deste capítulo essa característica será ignorada.

2.1. Incluindo linha a linha

2.1.1. Inclusão da primeira linha

O primeiro comando de inclusão de linha é o seguinte:

INSERT into dbo.demoFrag (Cod, Info) 
    values ('10', 'JOÃO ANTUNES DA SILVA');

Após a inclusão a página passa a ter o seguinte conteúdo

p046_figura 2.3

Observe que ao final da linha foi acrescentado 00 no row offset array, que aponta para o primeiro byte da primeira linha armazenada na página.

2.1.2. Inclusão da segunda linha

O segundo comando de inclusão de linha é o seguinte:

INSERT into dbo.demoFrag (Cod, Info) 
    values ('50', 'MARIA ESTELLA ROCHA DA SILVA');

Após a inclusão a página passa a ter o seguinte conteúdo

p046_figura 2.4

Observe que ao final da linha foi acrescentado 23 à esquerda de 00 no row offset array. Como mencionado anteriormente, esse vetor está em ordem invertida, iniciando o preenchimento à direita e crescendo para a esquerda. O primeiro elemento dele, índice 0, contém o valor 00; o segundo elemento dele, índice 1, contém o valor 23.

2.1.3. Inclusão da terceira linha

O terceiro comando de inclusão de linha é o seguinte:

INSERT into dbo.demoFrag (Cod, Info) 
    values ('30', 'EUSÉBIO FARIA DOS SANTOS');

Após a inclusão a página passa a ter o seguinte conteúdo

p046_figura 2.5

Observe que no row offset array foi acrescentado o valor 53 entre os valores 23 e 00; qual o motivo? Como mencionado anteriormente, a coluna Cod é chave primária da tabela e, sendo assim, as linhas devem ficar ordenadas dentro de cada página de modo que a leitura sequencial ordenada retorne as linhas conforme na sequência correta. Na primeira linha incluída a chave foi “10”, na segunda “50”; ou seja, em ordem. Mas a terceira linha incluída a chave foi “30”, que é maior do que “10” mas menor do que “50”. Como manter dentro de cada página as linhas de acordo com a ordem da chave primária? Uma solução seria deslocar a linha “50” n posições para a direita e então inserir a linha “30” entre elas; algo assim:

p046_figura 2.6

Mas isso demandaria processamento adicional. Para evitar tais deslocamentos é que existe o row offset array, com ele indicando a ordem em que devem ser lidas as linhas dentro da página. Ao registrar a posição inicial de cada linha obtém-se de forma automática – e com custo mínimo – a leitura na ordem correta. No nosso exemplo o row offset array está com os seguintes valores:

p046_figura 2.7

Ou seja, as linhas podem ser lidas na ordem correta pela coluna Cod, mesmo que dentro da página não estejam na ordem física. Em resumo, o row offset array garante a ordem lógica das linhas, dentro de cada página.

2.1.4. Inclusão da quarta linha

O quarto comando de inclusão de linha é o seguinte:

INSERT into dbo.demoFrag (Cod, Info) 
    values ('40', 'MARIA APARECIDA AFFONSO PENNA');

São necessários 31 bytes mas na página somente temos 12 bytes disponíveis. O que acontece? Como a nova linha não cabe na página, então:

  1. é alocada uma nova página;
  2. o conteúdo da linha “50” é movido da página 1 para a nova página;
  3. o conteúdo da linha “30” é deslocado para a esquerda, dentro da página 1;
  4. o conteúdo da linha “40” é incluído na página 1.

A situação das páginas após a inclusão da quarta linha é esta:

p046_figura 2.8

e

p046_figura 2.9

Neste caso o que ocorreu foi o page split, quando o conteúdo de uma página é quebrado em duas páginas, de modo a arrumar espaço para que uma nova linha seja incluída na ordem correta.

No processo de incluir a linha “40” na página 1 o SQL Server aproveitou e ordenou fisicamente as linhas; observe que elas estão armazenadas na ordem do valor da coluna Cod, que é a chave primária.

Além disso, observe a presença dos controles “Próxima página” e “Página anterior”. Eles fazem parte de lista duplamente encadeada, cujo objetivo será explicado na continuação deste artigo mas você já deve ter percebido a utilidade.

2.1.5. Inclusão da quinta linha

O quinto comando de inclusão de linha é o seguinte:

INSERT into dbo.demoFrag (Cod, Info) 
    values ('20', 'ABIGAIL FONTES ROCHA');

E agora, essa linha será incluída na página 1 ou na página 2? Pelo valor da coluna Cod ela deve obrigatoriamente ser inserida entre as linhas “10” e “30” da página 1, mesmo que logicamente (lembre-se do row offset array). Entretanto, não há espaço na página 1 mas percebe-se que se o conteúdo da linha “40” for movido para a página 2 haverá espaço para incluir a linha “20” na página 1, ficando as linhas “10”, “20” e “30” na página 1 e as linhas “40” e “50” na página 2. Entretanto, nos testes que fiz ocorreu algo diferente:

  1. uma nova página foi alocada;
  2. o conteúdo das linhas “30” e “40” foi movido da página 1 para a nova página;
  3. o conteúdo da linha “20” foi incluído na página 1.

A representação visual das páginas após a inclusão da quinta linha ficou assim:

p046_figura 2.10

e

p046_figura 2.11

e

p046_figura 2.12

2.2. Apagando linha

Mas o que ocorre quando linhas são apagadas? Devemos considerar duas situações, considerando-se o valor da chave primária: apagamento de linhas esparsas e apagamento em blocos contíguos. Neste item vamos exemplificar o apagamento de uma linha.

Vamos apagar a linha cujo valor da coluna Cod é ’03’, que corresponde a EUSÉBIO FARIA DOS SANTOS. Essa linha está gravada na página 3, slot 0.

Antes de apagar o conteúdo da página de dados estava assim:

p046_figura 2.13

Após rodar o seguinte comando SQL

DELETE dbo.demoFrag where Cod = '30';

o conteúdo da página 3 foi alterado para:

p046_figura 2.14

Para facilitar a compreensão do que ocorre ao apagar uma linha, na figura acima o conteúdo da linha ’03’ que foi apagado está representado por uma sequência de “x” mas na prática ele não é apagado dentro da linha mas somente a informação a respeito da linha “30” é removida do vetor row offset array. Observe que haviam 2 elementos no vetor e após o apagamento da linha passou a existir um único elemento e apontando diretamente para a posição 26.

2.3. Alterando conteúdo de linha

Após certo tempo descobriu-se que o nome JOÃO ANTUNES DA SILVA estava incorreto, não existindo o “DA”. Assim, para corrigir o erro foi rodado o seguinte comando SQL:

UPDATE dbo.demoFrag
  set Info= 'JOÃO ANTUNES SILVA'
  where Cod = '10';

A página em que está gravada a informação é a 1, com o seguinte conteúdo antes da alteração:

p046_figura 2.15

Após alterar o nome, ficou assim:

p046_figura 2.16

Observe que o novo conteúdo da linha “10” foi gravado após o conteúdo da linha “20” e o vetor row offset array atualizado para apontar para a nova posição da linha “10”. Ficou um buraco no início da página.

Ao final o conteúdo das 3 páginas ficou assim:

p046_figura 2.17

O que você acha que ocorreria com a página 2 se a linha “50” fosse apagada?

Como consta no título deste capítulo, foi exibido um modelo simplificado de como as páginas de dados são manuseadas ao longo do ciclo de inclusão, alteração, apagamento. Há várias outras situações que são interessantes de conhecer e que serão tratadas posteriormente.

2.4. E chegamos à fragmentação

Agora que já vimos o modelo simplificado do que ocorre quando há inclusões, alterações e apagamentos podemos entrar no assunto principal deste artigo: fragmentação de índices.

Page split. No item 2.1.4, no momento da inclusão da quarta linha é detectado que a linha é maior do que o espaço disponível na página e também que o valor da coluna Cod, “40”, significa que a linha deve ser incluída entre as linhas “30” e “50”. Para atender a esses requisitos foi necessário quebrar o conteúdo da página 1 em duas páginas, através da alocação de página adicional; este mecanismo é denominado de page split.

Fragmentação interna ocorre quando o espaço de uma página de dados não está utilizado de forma contígua e a partir de sua posição inicial, como se observou ao apagar e alterar linhas dentro de uma página, exemplificados nos itens 2.2 e 2.3. Algumas das causas comuns de fragmentação interna são: apagamentos de linhas que deixam buracos nas páginas; ampliação ou redução no conteúdo de colunas de tamanho variável; dentre outros.

Densidade média das páginas de dados. Ao longo das inclusões de linhas no item 2.1 observou-se que as páginas de dados (nível folha de um índice clustered) nunca estiveram completamente preenchidas. Este espaço não utilizado acarreta em desperdício de espaço físico e também de memória quando as páginas são carregadas no memory buffer pool. Uma forma de medir a eficiência no preenchimento das páginas de dados é o cálculo da densidade média das páginas de dados ou average leaf page density, cujo valor pode ser obtido ao consultar a visão sys.dm_db_index_physical_stats.

Ao analisar os valores de densidade de página é necessário saber qual é o valor configurado para FILLFACTOR do índice.

Fragmentação externa. No item 2.1.5, após a inclusão da quinta linha observou-se que a ordem das páginas de dados não era a mesma da ordem de leitura sequencial pelo índice (index order scan): primeiro lê-se a página 1, a seguir a página 3 e então volta para a página 2. O conteúdo da página 3 está fora da ordem lógica de leitura sequencial, o que ocasiona a fragmentação externa. Entretanto, pode ocorrer que não exista nenhuma página fora de ordem mas ainda assim exista fragmentação, o que será explicado posteriormente na continuação deste artigo.

Atenção: a fragmentação externa somente tem impacto negativo quando se efetua leitura sequencial ordenada pelo nível folha (index order scan) e as páginas não estejam na memória.

Acabou? É só isso?!

Ainda não. A segunda parte do artigo está em
  ⇒  Fragmentação de índices – além do básico

 


PDF

Este artigo também está disponível em arquivo no formato PDF, o que possibilita tanto visualizar online quanto obter cópia (download) para leitura offline e até mesmo impressão. Clique no texto abaixo para obter o artigo completo.

O beabá da fragmentação de índices

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s