SQL Server Hekaton (XTP) in-memory Tables: Range Indexes and Row Chains 2

Hash and Range indexes both involve row chains, if you haven’t already read my post on Understanding the row chains of Hash Indexes I’d suggest you do before continuing with this post which essentially is a continuation of it and assumes you know the basics of row chains already.

A range index is implemented using the new Bw-Tree aka the Buzz Word-Tree, if you read the academic paper (and I highly recommend you do!) you’ll understand why they call it “buzz word” lol.

There are two components to in-memory table data access, you first access through an index structure i.e. Hash or Range, you then have the data rows themselves. In the case of the Hash index the hash bucket gives you the pointer to the first data row which gets you to the data rows, and for the Range index, the leaf level of the Bw-Tree gives you the pointer to the first data row in the row chain – just like hash buckets, rows with the same indexed value are grouped together to form the row chain.

The diagram below shows how the various components hang together on a table with two single column Range indexes defined, one on Col3 which is fairly unique and one on Col5 which low cardinality with only two values 0 or 1 across the 11 rows in the table.

rangeindex-rowchain

Step #1 – Range Index Nodes and Index Leaf

The Range Index Nodes creates an ordered structure allowing for efficient range scans, for example a range expression of Col3 > 25 – logically it works like the B-Tree you know and “love” in the existing product on non-clustered and clustered indexes on SQL tables. Like traditional non-clustered indexes, there is a B-Tree for each separate index.

Step #2 – Leaf level of Index with pointer to row data

Just like its B-Tree (non-clustered index) cousin, the leaf level of the Bw-Tree (Range Index) points to the actual data; there is a very big difference though – for the B-Tree there exists a pointer per row in the table, so if you have a million row table and only 1 unique value in the indexed column the leaf still contains 1 million pointers – one for every row, conversely the Bw-Tree (Range index) contains a pointer per unique indexed value which can dramatically change the amount of storage used – a big plus because it’s an in-memory table! I’ll cover off the complexities of the Bw-Tree in a separate post, but here I’ll give you a simple example to ponder.

Example – compare standard SQL table with in-memory table

The SQL table has a clustered index on the Primary Key, the in-memory table as a Hash index; in addition each table has a non-clustered index (a range index in the case of the in-memory).

We will insert 1 million rows, the first sample inserts a million rows where the same value is used throughout the table on the column where upon the non-clustered index exists, the second sample uses an incremental and unique value for each row in the table thus comparing what difference if any may exist given different cardinality of the index column (note: it’s not just cardinality, the order the unique values are inserted matters because that affects how the Bw-Tree is built – like I said earlier, I’ll cover that in a separate post specifically on the Bw-Tree).

Test for on-storage:

--	SQL (on-disk)
create table range_onstorage (
	id	int not null 
		constraint pk_bigtable_onstorage primary key clustered,
	keycol  char(100) collate Latin1_General_BIN2 not null ,
		index nc_keycol1 nonclustered( keycol ),
		index nc_keycol2 nonclustered( keycol ),
		index nc_keycol3 nonclustered( keycol ),
 
	spacer	char(11) not null default( 'pad out row')
	);

#1 insert 1 million rows into a normal SQL table where the table has 3 non-clustered indexes all on the same column, that column has 1 unique value (the value is duplicated across all 1 million rows).

set nocount on;
 
declare @i int = 1;
 
while @i <= 1000000
begin
	insert range_onstorage ( id, keycol ) values( @i, '0' )
 
	set @i = @i + 1
 
end

#2 insert 1 million rows into a normal SQL table where the table has 3 non-clustered indexes all on the same column, that column is unique, the values are inserted in order so to help the B-Tree and minimise the impact un-ordered inserts create.

set nocount on;
 
declare @i int = 1;
 
while @i <= 1000000
begin
	insert range_onstorage ( id, keycol ) 
                values( @i, right( replicate( '0', 100 ) 
                          + cast( @i as varchar(10) ), 100 ) )
 
	set @i = @i + 1
 
end

Results:

rangeindex-instest-singlevalue

The table above shows space usage for the multiple non-clustered indexes all on the same column where all 1 million rows have the same value, it highlights that a row exists in the non-clustered index for every row in the table.

rangeindex-instest-multivalue

The table above shows space usage for the multiple non-clustered indexes all on the same column, but, each value for that indexed column is unique, to reduce the affect of fragmentation the inserts were ordered. You can clearly see that it makes no difference if the index column contains unique values or not.

Test for in-memory:

create table range_inmem (
	id	int not null 
		constraint pk_bigtable_inmem primary key nonclustered hash with ( bucket_count = 1048576  ),
	keycol  char(100) collate Latin1_General_BIN2 not null ,
		index nc_keycol1 nonclustered( keycol ),
		index nc_keycol2 nonclustered( keycol ),
		index nc_keycol3 nonclustered( keycol ),
 
	spacer	char(11) not null default( 'pad out row')
 
	)  WITH ( MEMORY_OPTIMIZED=ON, 
			  DURABILITY=SCHEMA_ONLY
			   );

#1 insert 1 million rows into a in-memory table where the table has a non-clustered Range index on a column that has 1 unique value (the value is duplicated across all 1 million rows).

set nocount on;
 
declare @i int = 1;
 
while @i <= 1000000
begin
	insert range_inmem ( id, keycol ) values( @i, '0' )
 
	set @i = @i + 1
 
end

#2 insert 1 million rows into a in-memory table where the table has a non-clustered Range index on a column that is unique, the values are inserted in order so to help the B-Tree and minimise the impact un-ordered inserts create.

set nocount on;
 
declare @i int = isnull( ( select max( id ) from range_inmem ), 0 ) + 1;
 
while @i <= 1000000
begin
	insert range_inmem ( id, keycol ) 
                 values( @i, right( replicate( '0', 100 ) 
                        + cast( @i as varchar(10) ), 100 ) )
 
	set @i = @i + 1
 
end

Results:

rangeindex-instest-inmem

The table above shows the difference between single value for all rows on the index column compared with it being unique with an ordered insert to reduce the affect on the Bw-Tree. Some explanations on what the table is telling us:

Table Used Diff KB (average bytes per row) – you can see that for each index we add the table size increases by an average of 8 bytes per row – that’s the index pointer on the row header, you get one index pointer in the row header per index on the table.

The difference between the range index with a single value for each of the million rows and the range index where rows are unique is clear to see, unlike the traditional SQL based non-clustered index, you do not get a row pointer per row in the index structure, you get a pointer per unique value in the index structure which points to the row chain (see diagram at the start of this post).

It makes no difference if the in-memory table is durable or not, well in terms of space, in terms of my laptop the Garbage Collection and logging couldn’t keep up so I ran out of space in the resource pool :) so had to run the test in two batches for SCHEMA_AND_DATA.

Step #3 – Row Chain

Nothing to be said! It’s the row chain :) – just like I explained in my hash index article on row chains – it works the same way now we are in the row structure. Rows with the same index value are grouped into a row chain, the most recently added or modified row is the first row in the row chain.

That concludes this post, there is more to this than meets the eye, but, I hope I’ve given you a basic idea of how the range and hash row chain hang together, once you’ve got the row chain concept the MVCC and garbage collection starts to flow and is more easily understood – I’ll cover those topics in another post to come.