SQL Server 2014 Range Index Vs Hash Index

SQL Server 2014 Ctp2 rende disponibile oltre alle In-Memory table con Hash Index anche le In-Memory Table dotate di Range Index.
La struttura di un Hash Index è assimilabile a questa

Il suo funzionamento è spiegato molto bene a questo link.

Una delle limitazioni che abbiamo con l'utilizzo di In-Memory table con indici Hash, ne ho parlato in questo post, è che per ciascun indice, dobbiamo necessariamente conoscere la cardinalità dei dati per poter definire la dimensione del Bucket_Count. In altre parole dobbiamo conoscere a priori quante righe conterrà la tabella...
Un altro limite degli Hash index è che non consentono accessi in Seek alla tabella per ricerche basate su range di valori. Ciò significa che in questi casi l'engine implementa una Scan della tabella intera.

Qualora non si conosca la cardinalità dei dati o si debbano effettuare ricerche basate su range di valori conviene utilizzare i Range index.

Questa tipologia di oggetti ha una struttura a Bw-Tree (Buzz Word Tree).














La struttura ricorda i B-Tree a cui siamo abituati, ma non lasciamoci trarre in inganno, sono differenti ed il loro funzionamento è ben spiegato a questo link.
La struttura del BW-Tree, così come quella degli Hash index è totalmente in memoria RAM, il che da ad entrambi tipi un incredibile vantaggio in termini di performance rispetto alle tabelle tradizionali.

Per creare In-Memory Table basate su Hash e/o Range Index qui trovate tutte le info.

Proviamo a creare 2 In-Memory table

USE MASTER
GO

CREATE DATABASE Hekaton_Test      
 ON PRIMARY(NAME = [PRIMARY],         
   FILENAME = 'C:\Program Files\Microsoft SQL Server\MSSQL12.MSSQLSERVER\MSSQL\DATA\Hekaton_Test\Hekaton_DiskBasedTable.mdf')    
,FILEGROUP [Hekaton_InMemory_FG] CONTAINS MEMORY_OPTIMIZED_DATA          
 (NAME = [Hekaton_InMemory_Dir],
  FILENAME = 'C:\Program Files\Microsoft SQL Server\MSSQL12.MSSQLSERVER\MSSQL\DATA\Hekaton_Test\In_Memory_Table') 
LOG ON (name = [Hekaton_log], FILENAME='C:\Program Files\Microsoft SQL Server\MSSQL12.MSSQLSERVER\MSSQL\DATA\Hekaton_Test\Hekaton_Test_log.ldf')   
Go

USE Hekaton_Test
GO

--In-Mem with Hash Index
CREATE TABLE Hash_MemoryTable 
( 
 id INT NOT NULL PRIMARY KEY NONCLUSTERED HASH WITH(BUCKET_COUNT = 65536)  
 ,Nome VARCHAR(25) COLLATE Latin1_General_100_BIN2 not null
 ,Cognome VARCHAR(50) COLLATE Latin1_General_100_BIN2 not null
 ,Indirizzo VARCHAR(50) COLLATE Latin1_General_100_BIN2 
 INDEX inMemoryIdx NONCLUSTERED HASH (Cognome,Nome) WITH(BUCKET_COUNT = 35000)  
)WITH 
 (
  MEMORY_OPTIMIZED = ON
  ,DURABILITY = SCHEMA_AND_DATA
 );  
GO

--In-Mem with Range Index
CREATE TABLE Range_MemoryTable 
( 
 id INT NOT NULL PRIMARY KEY NONCLUSTERED
 ,Nome VARCHAR(25) COLLATE Latin1_General_100_BIN2 not null
 ,Cognome VARCHAR(50) COLLATE Latin1_General_100_BIN2 not null
 ,Indirizzo VARCHAR(50) COLLATE Latin1_General_100_BIN2 
 INDEX inMemoryIdx NONCLUSTERED(Cognome,Nome)  
)WITH 
 (
  MEMORY_OPTIMIZED = ON
  ,DURABILITY = SCHEMA_AND_DATA
 );  
GO

--Popolo entrambe le 5tabelle con 65536 Record
;WITH Cte AS(SELECT 1 Riga UNION ALL SELECT 1) 
 ,Cte4 as (SELECT A.Riga FROM Cte A, Cte B) 
 ,Cte16 as (SELECT A.Riga FROM Cte4 A, Cte4 B) 
 ,Cte256 as (SELECT A.Riga FROM Cte16 A, Cte16 B) 
 ,Cte65536 as (SELECT A.Riga FROM Cte256 A, Cte256 B) 
 ,Results as (SELECT ROW_NUMBER()OVER(ORDER BY A.Riga) Riga FROM Cte65536 A,Cte65536 B) 
INSERT INTO Hash_MemoryTable(id, Nome, Cognome, Indirizzo) 
SELECT Riga 
  , 'Nome ' + Cast(Riga as char(8))  
  , 'Cognome ' + Cast(Riga as char(8))      
  , 'Indirizzo ' + Cast(Riga as char(8))  
FROM Results WHERE Riga <= 65536
GO

;WITH Cte AS(SELECT 1 Riga UNION ALL SELECT 1) 
 ,Cte4 as (SELECT A.Riga FROM Cte A, Cte B) 
 ,Cte16 as (SELECT A.Riga FROM Cte4 A, Cte4 B) 
 ,Cte256 as (SELECT A.Riga FROM Cte16 A, Cte16 B) 
 ,Cte65536 as (SELECT A.Riga FROM Cte256 A, Cte256 B) 
 ,Results as (SELECT ROW_NUMBER()OVER(ORDER BY A.Riga) Riga FROM Cte65536 A,Cte65536 B) 
INSERT INTO Range_MemoryTable(id, Nome, Cognome, Indirizzo)  
SELECT Riga 
  , 'Nome ' + Cast(Riga as char(8))  
  , 'Cognome ' + Cast(Riga as char(8))      
  , 'Indirizzo ' + Cast(Riga as char(8))  
FROM Results WHERE Riga <= 65536
GO

 

In entrambe le tabelle il campo id è Primary Key e nella Hash_MemoryTable è associato ad un indice Hash mentre nella Range_MemoryTable è creato come Range. Inoltre, su entrambe le tabelle è presente un indice sulle colonne Cognome e Nome.

Come si comportano le due tabelle in caso di ricerca puntuale ?

--Seek diretta
SELECT * FROM Hash_MemoryTable WHERE id = 65000
Go
SELECT * FROM Range_MemoryTable WHERE id = 65000
Go

Il piano d'esecuzione per le query è il medesimo.

Pur non essendo dei contatori particolarmente significativi guardiamo i "Query cost (Relative to the batch)" che  danno l'idea del peso di ciascuna query nel batch...

Il piano d'esecuzione per la ricerca nella Hash_MemoryTable è estremamente performante nelle ricerche puntuali. Questo perché l'indice Hash, che di fatto è un array di puntatori, contiene l'indirizzo della riga. La query filtra direttamente sulla colonna di PK Id = 65000, quindi sul valore 65000 viene applicata una funzione di hash che restituisce il bucket contenente l'indirizzo della riga nell'array.

La query sulla Range_MemoryTable, a parità di piano d'esecuzione, è meno performante dato che l'accesso alla riga selezionata è fatto seguendo l'indice Bw-Tree.

Cosa accade invece se modifico le condizioni di ricerca?

SELECT * FROM Hash_MemoryTable WHERE id >= 65000
Go
SELECT * FROM Range_MemoryTable WHERE id >= 65000
Go

I piani d'esecuzione in questo caso sono differenti...

La ricerca su Hash_MemoryTable è decisamente la più pesante, per sua natura la struttura di un Hash index non consente l'uso del Seek in questi tipi di ricerche.
Il Range index, invece, utilizza un Seek risultando molto più performante.
Dopotutto è un Bw-Tree, quindi le ricerche di questo tipo sono il suo pane....

Quale tipo indice dunque è il migliore ?
Bhe... Dipende da cosa dobbiamo fare....
Per ricerche dirette l'Hash Index è la soluzione più performante.
Per ricerche su range di valori il Range Index è quello che fa per noi.

Dato che le In-Memory table possono avere fino ad un max di 8 Index possiamo creare delle strutture ibride che sfruttino sia gli indici Hash che i Range.
Sulle colonne che saranno accedute in modo diretto (Where id = 65000) potrei creare un indice Hash, per le colonne su cui effettuo ricerche di tipo range (Where id >= 65000) posso creare un Range Index.

Un vantaggio comune ad entrambi i tipi di indici, dato che puntano alla riga nella sua interezza, è che l'engine non ha più la necessità di effettuare Key o Rid lookup.

Creo una tabella tradizionale e la popolo con le solite 65536 righe

CREATE TABLE DiskTable  
( 
 id INT NOT NULL PRIMARY KEY CLUSTERED
 ,Nome VARCHAR(25) COLLATE Latin1_General_100_BIN2 not null
 ,Cognome VARCHAR(50) COLLATE Latin1_General_100_BIN2 not null
 ,Indirizzo VARCHAR(50) COLLATE Latin1_General_100_BIN2 
 INDEX DiskIdx NONCLUSTERED (Cognome,Nome) 
)
GO

;WITH Cte AS(SELECT 1 Riga UNION ALL SELECT 1) 
 ,Cte4 as (SELECT A.Riga FROM Cte A, Cte B) 
 ,Cte16 as (SELECT A.Riga FROM Cte4 A, Cte4 B) 
 ,Cte256 as (SELECT A.Riga FROM Cte16 A, Cte16 B) 
 ,Cte65536 as (SELECT A.Riga FROM Cte256 A, Cte256 B) 
 ,Results as (SELECT ROW_NUMBER()OVER(ORDER BY A.Riga) Riga FROM Cte65536 A,Cte65536 B) 
INSERT INTO DiskTable(id, Nome, Cognome, Indirizzo)  
SELECT Riga 
  , 'Nome ' + Cast(Riga as char(8))  
  , 'Cognome ' + Cast(Riga as char(8))      
  , 'Indirizzo ' + Cast(Riga as char(8))  
FROM Results WHERE Riga <= 65536
GO

Come vedete la tabella ha la medesima struttura delle In-Memory create precedentemente e le stesse colonne indicizzate.
Ovviamente in termini di performance è molto più lenta delle In-Memory table ma non solo, ha un'ulteriore handicap che è la struttura dei B-Tree tradizionali.
Le datapages che compongono un index non clustered cosa contengono ?
Contengono i valori delle colonne su cui ho creato l'indice ed eventualmente:

1. Se la tabella è dotata di chiave clustered il valore della chiave clustered stessa per la riga
2. Se la tabella è in Heap lo Heap Rid della riga

Cosa accade quindi se la query richiede altre colonne oltre a quelle contenute nell'indice ?

Prendiamo queste Select che richiedono tutte le colonne che compongono la tabella.

SELECT * FROM DiskTable WHERE Cognome = 'Cognome 65000' And Nome = 'Nome 65000'
GO
SELECT * FROM Hash_MemoryTable WHERE Cognome = 'Cognome 65000' And Nome = 'Nome 65000'
GO
SELECT * FROM Range_MemoryTable WHERE Cognome = 'Cognome 65000' And Nome = 'Nome 65000'
GO

Questi sono i piani d'esecuzione generati dall'engine

Accade che l'engine è costretto ad implementare un Key LookUp se la tabella è clustered oppure un RID LookUp se la tabella è Heap per reperire anche i valori delle colonne non presenti nell'indice.
Questi surplus di lavoro, sono comunque accessi ad altre strutture, diminuiscono le performance aumentando le risorse in uso ed i tempi di attesa.
Le select sulle In-Memory table non richiedono l'operatore di Key Lookup dato che gli indici, sia Hash che Range (seppur nel leaf level), hanno sempre disponibile il puntatore all'intera riga. La select sulla DiskTable invece è costretta ad utilizzare un Key LookUp per reperire le colonne richieste.

Ciao

Luca