Hekaton In-Memory Tables: HASH Indexes 3

The purpose of this post is to help you understand the new HASH indexing in SQL Server 2014 in-memory tables feature (project Hekaton). As ever, it’s actually quite a big topic so I’ll cover aspects in multiple posts (I’ll pop back here and update the links once complete)…

Post 1 – How the Hash Index works
Post 2 – Understanding the Row Chain including Hash collisions
Post 3 – Performance considerations and monitoring
Post 4 – Considerations for sizing and choosing the correct columns for the Hash Index.

Background Reading

Hekaton: SQL Server’s Memory-Optimised OLTP Engine.
http://research.microsoft.com/pubs/193594/Hekaton%20-%20Sigmod2013%20final.pdf

The Bw-Tree: A B-Tree for New Hardware Platforms
http://research.microsoft.com/pubs/178758/bw-tree-icde2013-final.pdf

What’s a Hash?

For a backgrounder to hashing see my post: http://dataidol.com/tonyrogerson/2013/11/25/what-is-hashing-using-modulus-to-partition-data/

Hash Index

The hash gives a position in a one dimensional array of 8 byte memory pointers – aka the “Mapping Table”; the memory pointer links to the data row, if multiple rows hash to the same Mapping Table position then it will point to the start of a row chain which I’ll talk about in my row chain post, note the hash itself is never stored because it’s an array pointer :), the hash range depends on the number of BUCKET_COUNTS you specified on the index creation.

It’s important to realise you can only do equality checks i.e. = or != on hash values, that is because a range scan makes no sense, for example using the SQL Server CHECKSUM function to hash the values ‘A’, ‘B’, ‘C’, ‘D’ gives 114, 121, 122, 106 – notice that the hash value for ‘D’ is less that the hash value for ‘A’ thus making an expression like WHERE pk >= ‘A’ meaningless, because it would be interpreted as WHERE pk_hash >= 114 thus excluding 106 (‘D’).

The hash is generated across all the columns contained in the index (see below), you must also specific all the columns in the hash index on your equality check expression otherwise the index cannot be used.

Example – single column HASH index

PositionInMappingTable = HASH( [data-column] )

Example – composite column HASH index

PositionInMappingTable = HASH( CONCATENATE( [data-column1]+[data-column2]+[data-column3] ))

… and querying WHERE [data-column1] = ‘x’ AND [data-column2] = ‘y’ AND [data-column3] = ‘z’

The hash function is light weight, it needs to be because performance would suffer otherwise. I’ve seen a number of places where it states the hash gives a random position in the hash index – that is impossible, the hash must be deterministic i.e. each call of the hash for the same value will always return the same hash. What they are referring to is the distribution of the hash across the Mapping Table appears random; the hash function is based around a Poisson distribution of the row chain and as such helps make the hash function what we call “even” or “balanced”, that is to say,  you don’t get large clumps of rows in the same hash location thus skewing performance – see charts below….

Hashing - Even / Un-Even

I’ll cover row versioning and more about the row chain in another post.

BUCKET_COUNT

Specifies the size of the Mapping Table, once the table has been created it can’t be changed, when you execute CREATE TABLE the SQL is turned into C and compiled. If you could change BUCKET_COUNT all the existing data would need to be re-hashed because the hash function would return a different range (and value) when executed for the hash key columns.

It’s critical to get your BUCKET_COUNT correct; the Microsoft recommendation is for a BUCKET_COUNT double the number of unique values given for the hash key columns; for example, if you have a 1 million row table, you put a hash key on a column that can only be Y or N then you only have 2 unique values, thus if the value hash is balanced then you will have 2 buckets populated, each bucket pointing to a row chain of 500K rows.

For your convenience I’ve listed the available BUCKET_COUNT above 1000, note, if you choose a BUCKET_COUNT of 5000 for instance, it rounds up to the nearest power of 2 which is 8192. Each bucket is 8 bytes (a 64 bit memory pointer), remember the amount specified below is per hash index and needs to fit entirely in memory along with the data.

1024 – 8 kilobytes
2048 – 16 kilobytes
4096 – 32 kilobytes
8192 – 64 kilobytes
16384 – 128 kilobytes
32768 – 256 kilobytes
65536 – 512 kilobytes
131072 – 1 megabytes
262144 – 2 megabytes
524288 – 4 megabytes
1048576 – 8 megabytes
2097152 – 16 megabytes
4194304 – 32 megabytes
8388608 – 64 megabytes
16777216 – 128 megabytes
33554432 – 256 megabytes
67108864 – 512 megabytes
134217728 – 1,024 megabytes
268435456 – 2,048 megabytes
536870912 – 4,096 megabytes
1073741824 – 8,192 megabytes

BUCKET_COUNT is a trade off between the average row chain size and the amount of memory you have available, the larger the row chain the worse the performance will be (covered in the row chain post I’ll write soon).

Syntax example

The in-memory table must have a primary key, in the example below I’ve made the primary key a hash index, it can also be a range index. All indexes on an in-memory table are non-clustered, by the very nature of how the hash and range indexes work they are “covered” indexes.

create table xtp_table (
	account_id bigint not null,
		primary key 
		NONCLUSTERED 
		HASH( account_id ) WITH ( BUCKET_COUNT = 8192 )
 
	)  WITH ( MEMORY_OPTIMIZED=ON, 
			  DURABILITY=SCHEMA_AND_DATA );