Hash Indexes – Uma implementação no SQL Server – Parte I

Boa Noite Pessoal,

Hoje vou pagar uma das promessas antigas de postagem aqui no blog. A primeira vez que comentei sobre o assunto hash indexes foi no community zone de 2008 para alguns profissionais, que assim como eu, trabalham com o SQL Server, participam de eventos relacionado a esse produto, ajudam comunidades e respondem as perguntas nos principais fóruns. Na época esse assunto despertou uma certa curiosidade, já que os termos ligados a índices no SQL Server sempre rodeam a famosa B-TREE quer seja em implementações clusterizadas ou não clusterizadas. Estou certo de que aqueles que ficaram curiosos não esperaram para ver o artigo que nunca saiu, mas acho a implementação baseada em hash muito útil e estou certo que outros poderão se beneficiar para algumas situações de negócio pouco comuns mas que cedo ou tarde acontecem. Como o artigo é consideravelmente grande, o spaces não permitirá que eu o poste de uma só vez, forçando-me dividí-lo em duas partes. Nessa primeira parte falarei apenas das bases teóricas para entender o funcionamento de índices baseados em Hash e alguns scripts necessários para o devido entendimento. Na segunda parte do artigo, a ser publicada futuramente, demonstrarei uma aplicação prática com variações de volume e a mensuração de desempenho entre os índices tradicionais, um índice baseado em hash e outras soluções pertinentes. Embora o SQL Server 2008 tenha sido utilizado, boa parte dos artigos é aplicável às versões anteriores desde que feita as devidas adaptações.

Uma situação de negócio

Imagine que você seja o responsável por elaborar um modelo de dados que representa um sistema de pagamentos de títulos. Nesse sistema de pagamentos teremos as seguintes características:

  • O título possui um código de barras com 44 posições sempre fixas (ex: 23892000000000000001042065252722910301128000)
  • O título possui um valor em moeda corrente
  • O título pode ser pago com um valor a menor
  • O título pode ser pago com atraso
  • O título pode ser pago em outra moeda

O código de barras do título é único e geralmente carrega intrisicamente diversos detalhes do título em questão. Embora o título normalmente seja pago uma única vez e dentro da data de vencimento (quando há) e na mesma moeda em que foi emitido essa não é um regra que se aplique em 100% dos casos.

Há bancos que permitem o pagamento de títulos em duplicidades (é um absurdo mais existem), há títulos que podem ser pagos após o vencimento e existem aqueles que permitem a digitação do valor o que pode fazer com que sejam pagos no valor integral ou um valor a menor (típico de cartões de crédito) e talvez um brasileiro no exterior possa pagar um título brasileiro em moeda estrangeira (com as devidas conversões).

Assim sendo, dadas essas possibilidades, manter em uma única tabela de títulos os dados referentes a pagamento pode não ser interessante. Na proposta para o modelo, considerei duas tabelas conforme demonstrado abaixo:

O código do boleto com 44 posições é um identificador único e poderia assumir o papel de chave primária. No entanto, ele possui 44 posições e repassá-lo como FK para uma tabela de pagamentos é aumentar significativamente a largura do registro e conseqüentemente o tamanho da tabela e dos índices existentes. Por isso a utilização de uma chave artificial para tornar o registro menor (um INT possui 4 bytes) economiza espaço e proporciona desempenho (quanto menor for o registro mais rápida será sua recuperação).

Colunas textuais geralmente estão presentes em tabelas pequenas e possuem uma busca não exata sendo típicas de predicados usando o operador LIKE que normalmente ignoram a utilização de índices. Não há problema em usar um operador LIKE contra uma tabela relativamente pequena, assim como não há problema em usá-lo para tabelas muito grandes, desde que na cláusula WHERE haja algum outro predicado que seja mais seletivo e efetivo que o LIKE.

Uma coluna que representa o código de barra (embora textual) normalmente é resultado de situações um pouco mais atípicas. Esse tipo de coluna é utilizada para buscas exatas e utilizam o operador de igualdade para que se encontre o título que tem exatamente aquele código de barra. Para situações de igualdade, os índices tradicionais baseados em B-TREE (Clustered e NonClustered) são bem eficientes.

O problema com índices baseados em B-TREE é que eles contém em sua composição uma ou mais colunas chave acompanhadas de ponteiros e quanto maior for a coluna chave, maior será o tamanho do índice e por conseqüência mais lenta será a navegação por esse índice e recuperação dos dados. Indexar uma coluna textual como um UF, CPF ou um CNPJ pode ser aceitável, mas um coluna textual com muitos caractéres pode ser desastroso.

Em nosso exemplo, a coluna de código do boleto ocupa 44 bytes por registro enquanto as demais colunas juntas ocupam juntas ocupam 11 bytes por registro (desconsiderados os controles internos de quantidade de colunas, nulabilidade, offset, etc). A coluna código do boleto é responsável por 80% do espaço do registro e indexá-la irá produzir um índice tão grande quanto praticamente a própria tabela incorrendo em muito espaço e pouca eficiência.

O tal do HASH

O termo HASH significa espalhar ou embaralhar e é utilizado em diversas situações no mundo da tecnologia de informação (embora existam situações do uso de hash na antiguidade). Uma implementação bem conhecida do uso do hash é para criptografia de dados (em especial o "inquebrável" hash MD5). O objetivo do hash é normalmente aplicar um algoritmo (função de hash ) sobre um determinado dado e retornar um valor normalmente menor do o dado original. Quando uma função de hash é aplicada sobre um determinado dado ela deve produzir sempre o mesmo valor (ou seja é determinística), mas é possível que dados diferentes submetidos a uma função de hash retornem o mesmo valor. Vejamos um exemplo de uma função de hash bem típica do dia a dia nos concursos públicos e vestibulares. A lista abaixo foi obtida na internet e representa a lista de aprovados no processo seletivo de graduação em direito na FGV de São Paulo na fase 2. A lista foi retirada do link http://educaterra.terra.com.br/vestibular/aprovados_direito.pdf (apenas os nomes):

Nome Balcão
Alexandre Rebêlo Ferreira A – C
Amanda Cunha e Mello Smith Martins A – C
Ana Paula Chican e Oliveira A – C
Andre Gomes Montilha A – C
Antônio Augusto Pereira dos Santos A – C
Beatriz Sampaio Barros A – C
Cindy Scofano Takahashi A – C
Diana Barlem dos Santos D – F
Erik Fontenele Nybo D – F
Estêvão Nascimento Orcini D – F
Felipe Nutti Giannattasio D – F
Felipe Tucunduva Van Den Berch Van Heemstede D – F
Francisco Ribeiro de Magalhães Neto D – F
Gabriel Henrique Montera Lucilio G – I
Gabriel Landi Fazzio G – I
Gabriel Oura Chiang G – I
Gustavo Abrahamsson Marcondes Pereira G – I
Henrique Tetsuaki Matsura Misawa G – I
Isabella Bancovsky Becker G – I
Isabelle Glezer G – I
Jayme Polachini Neto J – L
Joao Guimaraes Cozac J – L
Joao Gustavo De Rezende Lima J – L
João Luis Monteiro Piassi J – L
Joao Vicente Lapa de Carvalho J – L
Julia Aoki Chao J – L
Laura Costa Gibin J – L
Livia Bragança Claudio J – L
Lucas de Araujo Gomes de Castro J – L
Maira Machado Frota Pinheiro M – N
Marcela Gaspar Pedrazzoli M – N
Marcela Mattiuzzo M – N
Marcela Rissato Ferreira M – N
Mariana Marangoni de Paulo M – N
Mariana Ribeiro Cardoso M – N
Mariel Linda Safdie M – N
Nathalia Arcencio de Marchi Dos Santos M – N
Olivia Do Amaral Mesquita O – R
Paulo Eduardo de Lima Pacheco O – R
Pedro Gallas Prellwitz O – R
Pedro Henrique Wieck Gonçalves O – R
Pedro Ivo Gil Zanetti O – R
Rafael Campedelli Andrade O – R

Supondo que os aprovados tenham de ir a um balcão específico para matricular-se, e supondo que existam seis balcões (AC, DF, GI, JL, MN e OR), para que o aprovado saiba em qual balcão ele deve procurar atendimento, basta ele verificar a primeira letra do nome e comparar com o intervalo de letras entre a letra inferior e a letra superior de cada balcão existente. Um aprovado com o nome Pedro deveria procurar o balcão (O – R), pois, esse balcão atenderá a todos os aprovados cuja primeira letra do nome esteja entre O e R. A conversão de um nome para localizar um balcão específico é uma função de hash . O menor dos nomes da lista possui 15 caractéres, o maior possui 44 caractéres e a média é de 25 caractéres. Já a identificação baseada em hash possui apenas dois caractéres (considerando apenas as letras inferior e superior). Pode-se perceber que cada aprovado só poderá dirigir-se a um único balcão, mas um balcão poderá atender mais de uma pessoa.

O uso do hash têm várias aplicações em banco de dados. O hash está presente em algoritmos de junção baseados em hash (hash joins). A própria criptografia de dados e compactação também são aplicações de hash. O Analysis Services utiliza uma função de hash para agrupamento automático de membros formando um hierarquia. Funções de hash podem ser aplicadas sobre uma determinada coluna e mapear o registro para um determinado bloco de dados. Existem várias variações do uso de hash para esse mapeamento (hash simples, linear, extensível, particionado, etc).

Tanto no exemplo real quanto em diversas outras aplicações, uma função de hash é ótima quando mapeia poucas entradas para um determinado resultado ou faz o mapeamento de forma a distribuir os resultados com equivalência. O uso do hash no exemplo da lista de aprovados é adequado, pois, mapeia os candidatos aos balcões mantendo uma quantidade entre seis e nove candidatos. Se fosse utilizado apenas dois intervalos (AM e NZ), haveria 36 aprovados no primeiro intervalo e apenas 7 no segundo intervalo deixando-os bem desbalanceados.

CHECKSUM e BINARY_CHECKSUM – Duas funções de hash nativas no SQL Server

CHECKSUM significa checagem e possui diversas utilizações. No protocólo TCP/IP por exemplo, quando dados são quebrados em pacotes e enviados via rede, ao término do envio dos pacotes é feita uma checagem para verificar se algum pacote foi alterado. Essa checagem se dá por uma combinação através do cabeçalho dos pacotes, ou seja, se algo foi violado, a checagem inicial irá dar um valor da checagem final.

O SQL Server também utiliza mecanismos de CHECKSUM para verificar a integridade de suas páginas de dados. Nesse caso, cada byte da página é combinado com o byte subseqüente produzindo um valor. No momento em que a página é escrita, o valor obtido da combinação entre os bytes da página é gravado no cabeçalho da página. Quando a página for lida novamente, o SQL Server irá combinar os bytes novamente para obter o valor e comparar com o valor armazenado no cabeçalho da página. Se houver uma diferença entre esses valores, a checagem terá falhado e a página será marcada como corrompida. Se o valor calculado for igual ao armazenado no cabeçalho da página então a página será considerada íntegra. Um raciocínio semelhante é aplicado ao backup quando a opção CHECKSUM é utilizada junto ao comando BACKUP DATABASE.

Além das aplicações citadas, o SQL Server dispõe de uma função chamada CHECKSUM. Essa função é utilizada para computar um valor inteiro independente do parâmetro passado. Ex: SELECT CHECKSUM(‘Um parâmetro de entrada’)

Após aplicar a função CheckSum sobre a string "Um parâmetro de entrada", podemos perceber que o retorno da função foi -1752065197. Isso significa que a string sofreu uma transformação e retornou um valor inteiro. É interessante notar que uma string como "Um parâmetro de entrada" possui 23 caractéres e isso significa 23 bytes. O valor após a utilização do CHECKSUM foi um inteiro e valores inteiros ocupam 4 bytes. Se o mapeamento de uma string de 23 bytes resulta em um inteiro de 4 bytes é natural que diferentes valores resultem em um mesmo CHECKSUM já que não é possível um valor exclusivo para cada parâmetro. Podemos evidenciar isso através dos comandos SELECT abaixo:

  • SELECT CHECKSUM(‘ABC’), CHECKSUM(‘abc’) retornam 1132495864
  • SELECT CHECKSUM(1), CHECKSUM(0x01) retornam 1

Há uma variação da função CHECKSUM conhecida como BINARY_CHECKSUM que poderia resolver esse problema. A função abaixo não incorre no mesmo valor. Ex:

  • SELECT BINARY_CHECKSUM(‘ABC’), BINARY_CHECKSUM(‘abc’) retornam respectivamente 17763 e 26435

Ainda assim, a função BINARY_CHECKSUM também não irá gerar um valor exclusivo já que similar ao CHECKSUM também retorna um inteiro. É possível que valores diferentes gerem o mesmo valor através da função BINARY_CHECKSUM. Ex:

  • SELECT BINARY_CHECKSUM(‘2q’), BINARY_CHECKSUM(‘3a’) retornam 849

Se fizermos uma analogia à descrição do hash, as funções CHECKSUM e BINARY_CHECKSUM são um tipo de funções de hash. Elas recebem um parâmetro de entrada e retornam um valor e esse valor é menor que o parâmetro original. De forma análoga à aplicação de funções de hash na aplicabilidade de mapeamentos, as funções CHECKSUM e BINARY_CHECKSUM também funcionam como uma mapa, na qual o parâmetro original é mapeado para o retorno da função.

Colunas calculadas, indexação e funções de hash

Uma das funcionalidades disponíveis a partir do SQL Server 2000 é a possibilidade de criar colunas calculadas e indexá-las. Essa funcionalidade permite estratégias de indexação bem interessantes. É possível indexar o resultado de uma função e utilizá-lo como critério de busca ao invés de utilizar conversões em uma cláusula WHERE (o que normalmente desperdiça o potencial de recuperação de um índice). Os artigos "Index Seek em um Where com função ? Como ?" e "Otimizando Performance Com Colunas Computadas" são bem interessantes para compreender como o uso de colunas calculadas em combinação com a indexação podem prover desempenho.

Através do uso das colunas calculadas, pode-se criar uma coluna calculada que seja o resultado de uma função de hash como a checksum. O exemplo abaixo demonstra como fazer isso:

— Criação da tabela de títulos
CREATE TABLE Titulos (
    TituloID INT,
    TituloCodigo CHAR(44) NOT NULL,
    TituloValor SMALLMONEY NOT NULL,
    TituloDataVencimento DATE NOT NULL,
    TituloCodigoHash As CHECKSUM(TituloCodigo)
    CONSTRAINT PK_Titulo PRIMARY KEY CLUSTERED (TituloID))

— Criação do Índice baseado na função de hash
CREATE INDEX IX_TituloCodigo ON Titulos (TituloCodigo)
CREATE INDEX IX_TituloCodigoHash ON Titulos (TituloCodigoHash)

Consultas através de índices baseados em hash

Agora que a coluna existe e que os índices foram criados, é necessário popular a tabela de títulos para que o uso do índice hash possa ser evidenciado. O script abaixo populará 10 milhões de linhas nessa tabela de forma aleatória. Não vou entrar nos detalhes de como o script faz essa carga, mas ao final haverá 10 milhões de títulos carregados (aproximadamente umas duas horas).

— Desabilita os índices para acelerar a carga
ALTER INDEX IX_TituloCodigo ON Titulos DISABLE
ALTER INDEX IX_TituloCodigoHash ON Titulos DISABLE

— Declara uma variável e a inicializa
DECLARE @i INT = 1

— Declara demais variáveis necessárias
DECLARE @TituloCodigo CHAR(44), @TituloValor SMALLMONEY, @TituloDataVencimento DATE

WHILE @i <= 10000000
BEGIN

    SET @TituloCodigo =
        CAST(((ABS(CHECKSUM(NEWID())) % 89999999999) + 10000000000) As CHAR(11)) +
        CAST(((ABS(CHECKSUM(NEWID())) % 89999999999) + 10000000000) As CHAR(11)) +
        CAST(((ABS(CHECKSUM(NEWID())) % 89999999999) + 10000000000) As CHAR(11)) +
        CAST(((ABS(CHECKSUM(NEWID())) % 89999999999) + 10000000000) As CHAR(11))

    SET @TituloValor =
        CAST((ABS(CHECKSUM(NEWID())) / 800000.00) As DECIMAL(10,2))

    SET @TituloDataVencimento =
        CAST((DATEADD(D,ABS(CHECKSUM(NEWID())) % 120,GETDATE())) As DATE)

    INSERT INTO Titulos (TituloID, TituloCodigo, TituloValor, TituloDataVencimento)
    VALUES (@i, @TituloCodigo, @TituloValor, @TituloDataVencimento)

    SET @i += 1

END

— Reabilita os Índices
ALTER INDEX IX_TituloCodigo ON Titulos REBUILD
ALTER INDEX IX_TituloCodigoHash ON Titulos REBUILD

Após a inserção de 10 milhões de registros de forma aleatória, é necessário inserir um registro conhecido para que as pesquisas possam ser realizadas.

— Insere um título conhecido
INSERT INTO Titulos (TituloID, TituloCodigo, TituloValor, TituloDataVencimento)
VALUES (10000001,‘23892000000000000001042065252722910301128000’,300,‘20091101’)

A consulta abaixo irá pesquisar o título recém inserido com base no seu código que normalmente será o elemento conhecido. Para verificar o desempenho, utilizarei as estatísticas de IO, tempo e o plano de execução.

— Ativa as estatísticas de IO e tempo
SET STATISTICS IO ON
SET STATISTICS TIME ON

— Pesquisa o título com o código 23892000000000000001042065252722910301128000
SELECT
    TituloID, TituloCodigo, TituloValor, TituloDataVencimento
FROM Titulos
WHERE TituloCodigo = ‘23892000000000000001042065252722910301128000’

As estatísticas de tempo e IO são detalhadas abaixo:

SQL Server parse and compile time:
   CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 0 ms.
SQL Server parse and compile time:
   CPU time = 0 ms, elapsed time = 135 ms.
SQL Server parse and compile time:
   CPU time = 0 ms, elapsed time = 0 ms.

(1 row(s) affected)
Table ‘Titulos’. Scan count 1, logical reads 7, physical reads 5, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

(1 row(s) affected)

SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 69 ms.
SQL Server parse and compile time:
   CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 0 ms.

O plano de execução, como era de se esperar, fez uma pesquisa no índice nonclustered (IX_TituloCodigo) para encontrar o código do título e posteriormente acessar as demais colunas:

Agora vejamos a consulta reescrita para utilizar o índice com base na função de hash.

— Ativa as estatísticas de IO e tempo
SET STATISTICS IO ON
SET STATISTICS TIME ON

— Pesquisa o título com o código 23892000000000000001042065252722910301128000
SELECT
    TituloID, TituloCodigo, TituloValor, TituloDataVencimento
FROM Titulos
WHERE TituloCodigoHash = CHECKSUM(‘23892000000000000001042065252722910301128000’)

As medidas de desempenho em tempo e IO foram:

SQL Server parse and compile time:
   CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 0 ms.
SQL Server parse and compile time:
   CPU time = 16 ms, elapsed time = 60 ms.

(1 row(s) affected)
Table ‘Titulos’. Scan count 1, logical reads 6, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

(1 row(s) affected)

SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 1 ms.
SQL Server parse and compile time:
   CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 0 ms.

O plano de execução é idêntico, a exceção de que o índice baseado na coluna hash  foi utilizado para fazer a pesquisa (seek):

O primeiro plano leu 7 páginas em memória (logical reads) enquanto o segundo leu 6 páginas que representa uma página a menos (vou desconsiderar as leituras físicas, pois, quando a segunda consulta foi executada, as páginas já estavam em memória). Em termos de velocidade, é até covardia comparar 120ms contra 2ms. Ainda que a medida de tempo seja imprecisa quando representa frações muito pequenas, a execução consecutiva dessas consultas (com variações de parâmetros) mostrará que a segunda é com certeza mais rápida. É de se esperar, pois, há pelo menos uma página a menos para ser lida.

A segunda consulta (embora mais eficiente) não está correta. O uso da função CHECKSUM pode fazer com que títulos diferentes obtenham o mesmo valor de CHECKSUM e isso pode fazer com que a busca por um determinado título através dessa função de hash retorne mais de um resultado já que embora o código do título seja único, não necessariamente o resultado da função de hash trará valores únicos. A consulta abaixo mostra que existem repetições para um mesmo valor de hash (minha consulta retornou 11717 registros).

— Encontra os códigos de hash duplicados
SELECT TituloCodigoHash, COUNT(*) FROM Titulos
GROUP BY titulocodigohash
HAVING COUNT(*) > 1

Para evitar que isso aconteça, é necessário adaptar a segunda consulta de forma que após o uso do índice hash, ela filtre o título correto.

— Pesquisa o título com o código 23892000000000000001042065252722910301128000
SELECT
    TituloID, TituloCodigo, TituloValor, TituloDataVencimento
FROM Titulos
WHERE TituloCodigoHash = CHECKSUM(‘23892000000000000001042065252722910301128000’)
AND TituloCodigo = ‘23892000000000000001042065252722910301128000’

Nesse caso a consulta está correta e o otimizador pode escolher tanto o índice normal quando o índice baseado em hash. Embora o índice baseado em hash e o índice sobre a coluna TituloCodigo tenham praticamente o mesmo desempenho, curiosamente o SQL Server escolheu o índice sobre a coluna TituloCodigo ao invés do índice baseado em hash conforme a figura abaixo:

De fato, como há os dois predicados (o baseado em hash e o baseado em código) e o desempenho é semelhante, não é uma escolha ruim optar pelo índice tradicional. Não acho que a escolha do otimizador esteja errada, mas a consulta abaixo mostra o tamanho dos índices:

— Mostra o espaço ocupado
SELECT
    Object_Name(p.Object_Id) As Tabela,
    I.Name As Indice, Total_Pages As Paginas,
    Total_Pages * 8 / 1024.00 As TamanhoMB
FROM sys.Partitions As P
INNER JOIN sys.Allocation_Units As A ON P.Hobt_Id = A.Container_Id
INNER JOIN sys.Indexes As I ON P.object_id = I.object_id AND P.index_id = I.index_id
WHERE p.Object_Id = Object_Id(‘Titulos’)

O resultado da consulta é expresso conforme tabela abaixo:

Tabela Índice Páginas Tamanho (MB)
Titulos PK_Titulo 79673 622.44
Titulos IX_TituloCodigo 63755 498.08
Titulos IX_TituloCodigoHash 17365 135.66

O índice IX_TituloCodigo representa 498MB de espaço contra 136MB do índice IX_TituloCodigoHash. Se o índice IX_TituloCodigo fosse eliminado, o desempenho das consultas ainda se manteria o mesmo, e haveria um espaço de 498MB liberados. Pode não parecer muito, mas vale a pena lembrar que 498MB representa 80% do tamanho total da tabela (622MB). Se a tabela tivesse por exemplo 2TB, esse índice iria representar 1,6TB e isso é bem considerável. Sobre esse ponto de vista, o índice IX_TituloCodigoHash é certamente muito mais indicado, pois, representa 22% do tamanho da tabela (algo bem inferior a 80%). À medida que o número de caractéres for aumentando, o uso do índice sobre a coluna de título tornar-se-á cada vez mais oneroso do ponto de vista de espaço e manutenção e com o tempo o próprio otimizador poderá descartá-lo.

Se os planos têm desempenho semelhante, ocupar 80% do tamanho da tabela parece ser um completo desperdício e de fato é. Se há como fazer a pesquisa através do índice hash e liberar o espaço certamente essa é a escolha certa.

— Retira o Índice NonClustered IX_TituloCodigo
DROP INDEX Titulos.IX_TituloCodigo

— Pesquisa o título com o código 23892000000000000001042065252722910301128000
SELECT
    TituloID, TituloCodigo, TituloValor, TituloDataVencimento
FROM Titulos
WHERE TituloCodigoHash = CHECKSUM(‘23892000000000000001042065252722910301128000’)
AND TituloCodigo = ‘23892000000000000001042065252722910301128000’

A consulta possui excelentes tempos de execução.

SQL Server parse and compile time:
   CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 0 ms.
SQL Server parse and compile time:
   CPU time = 0 ms, elapsed time = 3 ms.

(1 row(s) affected)
Table ‘Titulos’. Scan count 1, logical reads 6, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

(1 row(s) affected)

SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 2 ms.
SQL Server parse and compile time:
   CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 0 ms.

Embora o plano de execução seja visualmente parecido com o plano anterior, há um detalhe a mais para efetuar o filtro e remover os registros que tem o mesmo CHECKSUM, mas não possuem o valor do título correto. Após o índice hash ter sido utilizado (Index Seek), as entradas da tabela já foram recuperadas (Key Lookup). O CHECKSUM pode não recuperar exatamente um único registro já que é passível de título com códigos diferentes possuírem o mesmo valor de CHECKSUM. O predicado adicional para filtrar a ocorrência correta não representa perda de desempenho, pois, o índice hash já fez boa parte dos filtros.

Quando não utilizar índices baseados em Hash

O uso de hash indexes representa uma solução de busca alternativa com base em uma correspondência única. Sua principal vantagem é que o tempo de pesquisa é semelhante ao uso de índices baseados em btree, mas com um espaço de armazenamento e manutenção muito superior. Em contrapartida, soluções de índices baseadas em funções de hash são excelentes para pesquisas de identificação única. Esse mecanismo não poderia ser utilizado para pesquisar um range de títulos que definidos entre 23892000000000000001042065252722910301128000 e 34152000000000000001042065252722910301128000 por exemplo. A idéia de economia de espaço também só é válida se o parâmetro de entrada (no caso o código do título) tiver um comprimento muito grande em relação ao resultado da função de hash. Não seria muito vantajoso por exemplo utilizar uma função de hash se o tamanho do código título fosse algo entre 6 ou 10 caractéres.

Na parte II desse artigo, a ser publicada futuramente, apresentarei alguns testes comparativos mais interessantes abordando a utilização de hash indexes.

[ ]s,

Gustavo

5 Respostas para “Hash Indexes – Uma implementação no SQL Server – Parte I

  1. Olá Gustavo,Como sempre, são aulas dados, e quem não acompanha seus artigos não sabe o que estão perdendo, muito bom mesmo.Maiar tenho uma dúvida, você falou que a função CHECKSUM iria gerar hashs duplicados, e para evitar erros de duplicidades na consulta você utilizou o operador AND, visto que temos dois índex, um no campo TituloCodigo e outro no campo TituloCodigoHash, onde vimos na última tabela que os tamanhos dos índex, na qual para mim é uma grande diferença em comparação um com o outro, seu exemplo de 2TB é plausível, mas minha dúvida é, como ficaria o desempenho da consulta caso retirasse o índex do campo TituloCodigo? Mudaria alguma coisa já que o mesmo não estaria indexado? Pois na consulta utilizo os dois campos indexados, ou seja, ganharia espaço com a eliminação do índex no campo TituloCodigo, mas o desempenho como ficaria? Mudaria alguma coisa?Heberton Melo

  2. Ótima matéria meu amigo !!!!. Como você disse isso se aplica sim a outras versões do sql server.Em 2002 eu QUAAAAASE consegui colocar essa idéia num projeto em SQL 2000 ainda, mas infelizmente não deu certo. Infelizmente com hash keys eu só fiz testes..testes..testes…., mas nunca consegui mandar pra produção. Mas é isso aí Dr…pouca gente conhece esse conceito e tu conseguiu, como sempre, explicar de uma maneira qq um entenda.Abraços carinha!!!!

  3. Olá Heberton,A idéia é realmente levar os conceitos ao maior número possível de pessoas. Se o índice sobre o campo TituloCodigo for retirado, a consulta não terá outra escolha senão usar o índice hash. Mesmo que o índice hash possa retornar dois ou três registros (é difícil ter tantas coincidências), filtrar um entre esses registros é uma atividade desprezível em termos de desempenho.Para evitar outras pessoas com a mesma dúvida, adicionei essa explicação ao artigo.[ ]s,Gustavo

  4. Oi Laerte,Eu também fiz muitos testes, mas em produção mesmo só em um único cliente e isso foi a muito tempo também. É um conceito bem interessante e embora útil, eu nunca encontrei em nenhum livro.Abs,

  5. Olá Gustavo,Perfeito, compreendi, embora pouco tempo estudando e trabalhando com SQL Server nunca tinha ouvido falar sobre esse conceito abordado por você.Ficou muito boa mesma a matéria.Heberton Melo

Deixe uma resposta

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 )

Imagem do Twitter

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

Foto do Facebook

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

Foto do Google+

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

Conectando a %s