{"id":3706,"date":"2014-04-17T15:30:40","date_gmt":"2014-04-17T13:30:40","guid":{"rendered":"https:\/\/www.dbi-services.com\/blog\/in-memory-tables-bw-tree-and-storage\/"},"modified":"2014-04-17T15:30:40","modified_gmt":"2014-04-17T13:30:40","slug":"in-memory-tables-bw-tree-and-storage","status":"publish","type":"post","link":"https:\/\/www.dbi-services.com\/blog\/in-memory-tables-bw-tree-and-storage\/","title":{"rendered":"SQL Server 2014: In-Memory tables, Bw-Tree, and storage"},"content":{"rendered":"

SQL Server 2014 introduces hash indexes with in-memory optimized tables. I described some of their aspects in a previous blog post<\/a>.\u00a0 These indexes are very efficient with lookup search operations but have some limitations with operations like range scans, inequality predicates or scan order operations. These limitations are linked to hash index design that stores rows in the index in a random order. Fortunately, nonclustered indexes for in-memory optimized tables (aka range indexes or Bw-Tree) solve this issue and, like hash indexes, involve a data row chain at their own structure in the leaf level.
\nIn this blog post I would like to share with you an interesting consideration about the Bw-Tree storage. Like a traditional b-tree index structure, accessing in-memory table data rows themselves requires first to go through the Bw-Tree structure prior to retrieve the corresponding row data in the chain. At the leaf level of the Bw-Tree we have different pointers to the first concerned data in the row chain. Pages in the index are linked together by logical pointers (called page identifiers or PID). This PID is then translated to a physical address or a flash offset of a page in memory or to a stable media storage. The Bw-Tree layer interacts with the cache layer that abstracts physical page by using a mapping table that maps logical pages to physical pages. Beside, others non-leaf pages in the Bw-Tree structure use the same mechanism. Here a simplified schema for retrieving the data through the Bw-Tree structure :<\/p>\n

Bw-Tree –> Mapping Table –> Physical Page<\/p>\n

Abstracting the physical layer has some advantages. Indeed, changing the physical location of a page requires only to change to corresponding mapping to the mapping table. The Bw-Tree path will not be affected by this change because each page is logical with their own PID.<\/p>\n

Now let\u2019s demonstrate an interesting behaviour of Bw-Tree (range indexes) with several extreme tests. We create an in-memory optimized table named hekaton_table with the following definition:<\/p>\n

CREATE TABLE dbo.hekaton_table<\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
(<\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 id INT NOT NULL PRIMARY KEY NONCLUSERED HASH WITH ( BUCKET_COUNT = 1048576 ),<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 col1 CHAR(100) COLLATE French_BIN2 NOT NULL,<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 INDEX idx_hekaton_table_col1 NONCLUSTERED ( col1 )<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
)<\/span><\/div>\n
WITH<\/span><\/div>\n
(<\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 MEMORY_OPTIMIZED = ON,<\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 DURABILITY = SCHEMA_AND_DATA<\/span><\/span><\/span><\/span><\/div>\n
)<\/span><\/div>\n

 <\/p>\n

This table contains a hash index as a primary key on the id column and a nonclustered range index idx_hekaton_table_col1 that concerns the col1 column. We will use the DMVs sys.dm_db_xtp_nonclustered_index_stats<\/em>, sys.dm_db_xtp_memory_consumers<\/em> and sys.dm_db_xtp_xtp_memory_stats<\/em> during the test.<\/p>\n

The first DMV sys.dm_db_xtp_nonclustered_index_stats<\/em> includes statistics about operations on nonclustered indexes in memory-optimized tables.<\/p>\n

select<\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 o.name as table_name,<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 i.name as index_name,<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 nis.internal_pages,<\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 nis.delta_pages,<\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 nis.leaf_pages<\/span><\/span><\/span><\/span><\/div>\n
from sys.dm_db_xtp_nonclustered_index_stats as nis<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 join sys.objects as o<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 on o.object_id = nis.object_id<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 join sys.indexes as i<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 on i.object_id = nis.object_id<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 and i.index_id = nis.index_id<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
where i.name = ‘idx_hekaton_table_col1’;<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n

 <\/p>\n

\"billet_6_-_sys_dm_db_xtp_nonclustered_index_stats\"<\/p>\n

The second DMV sys.dm_db_xtp_memory_consumers<\/em> provides useful information about the memory consumers. We are concerned by the Range index heap consumer for this example.<\/p>\n

select<\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 o.name as table_name,<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 i.name as index_name,<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 xmc.memory_consumer_desc,<\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 xmc.allocated_bytes \/ 1024 as allocated_kb,<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 xmc.used_bytes<\/span><\/span><\/span><\/span><\/div>\n
from sys.dm_db_xtp_memory_consumers as xmc <\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 join sys.indexes as i<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 on xmc.object_id = i.object_id<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 and xmc.index_id = i.index_id<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
where i.name = ‘idx_hekaton_table_col1’; <\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n

 <\/p>\n

\"billet_6_-_sys_dm_db_xtp_nonclustered_index_stats_2\"<\/p>\n

The third DMV sys.dm_db_xtp_table_memory_stats<\/em> provides information about the size of an in-memory table into the memory.<\/p>\n

select<\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 memory_used_by_table_kb,<\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 memory_used_by_indexes_kb<\/span><\/div>\n
from sys.dm_db_xtp_table_memory_stats<\/span><\/span><\/span><\/span><\/div>\n
where [object_id] = object_id(‘hekaton_table’)<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n

 <\/p>\n

For the first test we will introduce 200K rows of data in the col1 column with a high cardinality. All rows will have a distinct value.<\/p>\n

declare @i int = 1;<\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0<\/span><\/div>\n
while @i 200000<\/span><\/span><\/span><\/span><\/div>\n
begin<\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 insert dbo.hekaton_table values (@i, ‘t_’ + cast(@i as varchar(10)));<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 set @i += 1;<\/span><\/span><\/span><\/span><\/span><\/div>\n
end<\/span><\/div>\n

 <\/p>\n

Then we take a look to result of the all DMVs:<\/p>\n