Internal Structure

Clustered columnstore indexes use the same storage format as nonclustered columnstore indexes, storing columnstore data in row groups. However, they have two additional elements to support data modifications. The first is delete bitmap, which indicates what rows were deleted from a table. The second structure is delta store, which includes newly inserted rows. Both delta store and delete bitmap use the B-Tree format to store data.

Figure 35-1 illustrates the structure of a clustered columnstore index in a table that has two partitions. Each partition can have a single delete bitmap and multiple delta stores. This structure makes each partition self-contained and independent from other partitions, which allows you to perform a partition switch on tables that have clustered columnstore indexes defined.

It is worth noting that delete bitmaps and delta stores are created on-demand. For example, a delete bitmap would not be created unless some of the rows in the row groups were deleted.

Every time you delete a row that is stored in a row group (not in a delta store), SQL Server adds information about the deleted row to the delete bitmap. Nothing happens to the original row. It is still stored in a row group. However, SQL Server checks the delete bitmap during query execution, excluding deleted rows from the processing.

As already mentioned, when you insert data into a columnstore index, it goes into a delta store, which uses a B-Tree format. Updating a row that is stored in a row group does not change the row data either. Such an update triggers the deletion of a row, which is, in fact, insertion to a delete bitmap, and insertion of a new version of a row to a delta store. However, any data modifications of the rows in a delta store are done the same way as in regular B-Tree indexes by updating and deleting actual rows there. You will see one such example later in this chapter.

Each delta store can be either in open or closed state. Open delta stores accept new rows and allow modifications and deletions of data. SQL Server closes a delta store when it reaches 1,048,576 rows, which is the maximum number of rows that can be stored in a row group. Another SQL Server process, called tuple mover, runs every five minutes and converts closed delta stores to row groups that store data in a column-based storage format.

Alternatively, you can force the conversion of closed delta stores to row groups by reorganizing an index with the ALTER INDEX REORGANIZE command. While both approaches achieve the same goal of converting closed delta stores to row groups, their implementation is slightly different. Tuple mover is a single-threaded process that works in the background, preserving system resources. Alternatively, index reorganizing runs in parallel using multiple threads. That approach can significantly decrease conversion time at a cost of extra CPU load and memory usage.

Neither tuple mover nor index reorganizing prevent other sessions from inserting new data into a table. New data will be inserted into different and open delta stores. However, deletions and data modifications would be blocked for the duration of the operation. In some cases, you may consider forcing index reorganization manually to reduce execution and, therefore, locking time.

You can examine the state of row groups and delta stores with the sys.column_store_row_groups view. Figure 35-2 illustrates the output of this view, which returns the combined information of all columnstore index objects. Rows in OPEN or CLOSED state correspond to delta stores. Rows in COMPRESSED state correspond to row groups with data in a column-based storage format. Finally, the deleted_rows column provides statistics about deleted rows stored in a delete bitmap.

As you can see, the second row in a view output from Figure 35-2 shows the closed delta store that has yet to be picked up by the tuple mover process. The situation will change after the tuple mover process converts the closed delta store to a row group on its next scheduled run. Figure 35-3 shows the output from a view after this occurs. It is worth noting that the row_group_id of the converted row group changed. Tuple mover created a new row group, dropping the closed delta store afterwards.

Data Load

Two different types of data load can insert data into a columnstore index. The first type is bulk insert, which is used by the BULK INSERT operator, bcp utility, and other applications that utilize the bulk insert API. The second type, called trickle inserts, are regular INSERT operations that do not use the bulk insert API.

Bulk insert operations provide the number of rows in the batch as part of the API call. SQL Server inserts data into newly created row groups if that size exceeds a threshold of about 100,000 rows. Depending on the size of the batch, one or more row groups can be created and some rows may be stored in delta store.

Table 35-1 illustrates how data from the different batches are distributed between row groups and delta stores.

SQL Server loads columnstore data to memory on a per-segment basis and, as you remember, segments represent data for a single column in a row group. It is more efficient to load and process a smaller number of fully populated segments as compared to a large number of partially populated segments. An excessive number of partially populated row groups negatively affect SQL Server performance. I will provide an example of this later in the chapter.

If you bulk load data to a table with a clustered columnstore index, you will achieve the best results by choosing a batch size that is close to 1,048,576 rows. This will guarantee that every batch produces a fully populated row group, reduces the total number of row groups in a table, and improves query performance. Do not exceed that number, however, because the batch would not fit into a single row group.

Batch size is less important for non-bulk operations. Trickle inserts go directly to a delta store. In some cases, SQL Server can still create row groups on the fly in a similar manner to bulk insert when the size of the insert batch is close to or exceeds 1,048,576 rows. You should not rely on that behavior, however.

Delta Store and Delete Bitmap

Let’s analyze the structure of delta stores and delete bitmaps and look at the format of their rows. As a first step, let’s create a table, populate it with data, and define a clustered column store index there. Finally, we will look at segments and row groups with the sys.column_store_segments and sys.column_store_row_groups views.

Listing 35-1 shows the code that does just that. I am using MAXDOP=1 option during the index creation stage to minimize the number of partially-populated row groups in the index.

Listing 35-1.  Delta store and Delete bitmap: Test table creation

create table dbo.CCI
(
        Col1 int  not null,
        Col2 varchar(4000) not null,
);
 
;with N1(C) as (select 0 union all select 0) -- 2 rows
,N2(C) as (select 0 from N1 as T1 cross join N1 as T2) -- 4 rows
,N3(C) as (select 0 from N2 as T1 cross join N2 as T2) -- 16 rows
,N4(C) as (select 0 from N3 as T1 cross join N3 as T2) -- 256 rows
,N5(C) as (select 0 from N4 as T1 cross join N4 as T2) -- 65,536 rows
,N6(C) as -- 1,048,592 rows
(
        select 0 from N5 as T1 cross join N3 as T2
        union all
        select 0 from N3
)
,IDs(ID) as (select row_number() over (order by (select NULL)) from N6)
insert into dbo.CCI(Col1,Col2)
        select ID, 'aaa'
        from IDS
go
 
create clustered columnstore index IDX_CS_CLUST on dbo.CCI
with (maxdop=1)
go
 
select g.state_description, g.row_group_id, s.column_id
        ,s.row_count, s.min_data_id, s.max_data_id, g.deleted_rows
from
        sys.column_store_segments s join sys.partitions p on
                s.partition_id = p.partition_id
        join sys.column_store_row_groups g on
                p.object_id = g.object_id and
                s.segment_id = g.row_group_id
where
        p.object_id = object_id(N'dbo.CCI')
order by
        g.row_group_id, s.column_id;

Figure 35-4 shows the output from sys.column_store_segments and sys.column_store_row_groups views. The columnstore index has two row groups and does not have delta store nor delete bitmap. You can see Col1 values that are stored in both row groups in min_data_id and max_data_id columns for the rows that have column_id=1.

In the next step, shown in Listing 35-2, we will perform some data modifications in the table. The first statement inserts two new rows into the table. The second statement deletes three rows, including one of the rows that we just inserted. Finally, we will update another newly inserted row.

Listing 35-2.  Delta store and Delete bitmap: Data modifications

insert into dbo.CCI(Col1,Col2)
values
        (2000000,REPLICATE('c',4000)),
        (2000001,REPLICATE('d',4000));
 
delete from dbo.CCI
where Col1 in
        (
        100             -- Row group 0
        ,16150          -- Row group 1
        ,2000000        -- Newly inserted row (Delta Store)
        );
 
update dbo.CCI
set Col2 = REPLICATE('z',4000)
where Col1 = 2000001;   -- Newly inserted row (Delta Store)

Now it is time to find the data pages that are used by delta store and delete bitmap. We will use the undocumented sys.dm_db_database_page_allocations system function, as shown in Listing 35-3.

Listing 35-3.  Delta store and Delete bitmap: Analyzing page allocations

select object_id, index_id, partition_id
        ,allocation_unit_type_desc as [Type]
        ,is_allocated,is_iam_page,page_type,page_type_desc
        ,allocated_page_file_id as [FileId]
        ,allocated_page_page_id as [PageId]
from sys.dm_db_database_page_allocations
        (db_id(), object_id('dbo.CCI'),NULL, NULL, 'DETAILED')

You can see the output of the query in Figure 35-5. As you know, SQL Server stores columnstore segments in LOB_DATA allocation units. Delta store and delete bitmap are using IN_ROW_DATA allocation.

Let's look at the data pages using another undocumented command, DBCC PAGE, with the code shown in Listing 35-4. Obviously, the database, file, and page IDs would be different in your environment.

Listing 35-4.  Delta store and Delete bitmap: Analyzing page data

-- Redirecting output to console
dbcc traceon(3604)
 
-- Analyzing content of a page
dbcc page
(
        9        -- Database Id
        ,1       -- FileId
        ,306     -- PageId
        ,3       -- Output style
)

Archival Compression

Archival compressionis another feature introduced in SQL Server 2014. It can be applied on a table or on an individual partition by specifying a DATA_COMPRESSION=COLUMNSTORE_ARCHIVE columnstore index property, and it reduces storage space even further. It uses the Xpress 8 compression library, which is an internal Microsoft implementation of the LZ77 algorithm. This compression works directly with binary data without any knowledge of the underlying SQL Server data structures.

Archival compression works transparently with other SQL Server features. Columnstore data is compressed at the time it is saved on disk and decompressed before it is loaded into memory.

Let’s compare the results of different compression methods. I created four different tables with the same schema, as shown in Listing 35-5. The first two tables are heaps with no nonclustered indexes defined. The first table was uncompressed and the second one was compressed with page compression. The third and fourth tables had clustered columnstore indexes compressed with COLUMNSTORE and COLUMNSTORE_ARCHIVE compression methods respectively. Each table had almost 62 million rows generated based on the dbo.FactResellerSales table from the AdventureWorksDW2012 database.

Listing 35-5.  Schema of test tables

create table dbo.FactSalesBig
(
        ProductKey int not null,
        OrderDateKey int not null,
        DueDateKey int not null,
        ShipDateKey int not null,
        CustomerKey int not null,
        PromotionKey int not null,
        CurrencyKey int not null,
        SalesTerritoryKey int not null,
        SalesOrderNumber nvarchar(20) not null,
        SalesOrderLineNumber tinyint not null,
        RevisionNumber tinyint not null,
        OrderQuantity smallint not null,
        UnitPrice money not null,
        ExtendedAmount money not null,
        UnitPriceDiscountPct float not null,
        DiscountAmount float not null,
        ProductStandardCost money not null,
        TotalProductCost money not null,
        SalesAmount money not null,
        TaxAmt money not null,
        Freight money not null,
        CarrierTrackingNumber nvarchar(25) null,
        CustomerPONumber nvarchar(25) null,
        OrderDate datetime null,
        DueDate datetime null,
        ShipDate datetime null
)

Table 35-2 compares the on-disk size of all four tables.

Obviously, different table schema and data lead to different compression results; however, in most cases, you will achieve significantly greater space saving when archival compression is implemented.

Archival compression introduces additional CPU overhead at the compression and decompression stages. Let’s run a query that performs a MAX() aggregation on 20 columns in a table. The result of the query is meaningless; however, it forces SQL Server to read data from 20 different column segments in each row group in the table. Listing 35-6 shows the query.

Listing 35-6.  Test query

-- Clear buffer pool forcing SQL Server to read data from disk
dbcc dropcleanbuffers
go
 
select
        max(ProductKey),max(OrderDateKey),max(DueDateKey)
        ,max(ShipDateKey),max(CustomerKey),max(PromotionKey)
        ,max(CurrencyKey),max(SalesTerritoryKey),max(SalesOrderLineNumber)
        ,max(RevisionNumber),max(OrderQuantity),max(UnitPrice)
        ,max(ExtendedAmount),max(UnitPriceDiscountPct),max(DiscountAmount)
        ,max(ProductStandardCost),max(TotalProductCost),max(SalesAmount)
        ,max(TaxAmt),max(Freight)
from dbo.FactSalesBig

Table 35-3 illustrates the execution time of the query against the tables with different columnstore compression methods. Even though the data compressed using archival compression uses significantly less space on disk, it takes longer for the query to complete due to the decompression overhead involved. Obviously, the results would vary based on the CPU and I/O performance of the system.

Archival compression is a great choice for static, rarely accessed, data. It is common for Data Warehouses to retain data for a long time, even though historical data is rarely accessed. You may wish to consider applying archival compression on partitions that store historical data and benefit from the disk space saving it achieves.

Excessive Number of Partially Populated Row Groups

For this test, I created two tables of a similar structure to the table shown in Listing 35-5, and I bulk imported almost 62 million rows with the bcp utility using 1,000,000 rows batches and 102,500 rows batches respectively.

Figure 35-8 illustrates the row groups in both tables after the import.

Table 35-4 illustrates the execution time and number of I/O operations for the query from Listing 35-6 running against both tables. As you can see, the query against a table with partially populated row groups took a considerably longer time to execute.

It is worth noting that the performance of batch inserts was also affected by smaller batch sizes. In the case of 1,000,000-row batches, my system was able to insert about 103,500 rows per second, contrary to 94,300 rows per second in the case of the 102,500-row batches.

Large Delta Stores

For the next step, let’s look at how large delta stores affect the performance of queries. SQL Server needs to scan these delta stores during query execution.

For this test, I inserted 1,000,000 rows in small batches into the delta store of the first table from the previous test (the table that had row groups fully populated). After that, I rebuilt the columnstore index, comparing the execution time of the test query before and after the index rebuild.

The index rebuild process moved all data from the delta store to row groups. You can see the status of row groups and the delta store before (on the left side) and after (on the right side) the index rebuild in Figure 35-9.

Table 35-5 illustrates the execution times of the test query in both scenarios, and it shows the overhead introduced by the large delta store scan during query execution.

Large Delete Bitmap

Finally, let’s see how delete bitmaps affect query performance. For that test, I deleted almost 30,000,000 rows from a table.

You can see the row groups’ information in Figure 35-10.

The test query needs to validate that rows have not been deleted during query execution. Similar to the previous test, this adds considerable overhead. Table 35-6 shows the execution time of the test query, comparing it to the execution time of the query before the data deletion.

Index Maintenance Options

You can address all of these performance issues by rebuilding the columnstore index, which you can trigger with the ALTER INDEX REBUILD command. The index rebuild forces SQL Server to remove deleted rows physically from the index and to merge the delta stores’ and row groups’ data. All column segments are recreated with row groups fully populated.

Similar to index creation, the index rebuild process is very resource intensive. Moreover, it prevents any data modifications in the table by holding shared (S) table lock. However, other sessions can still read data from a table while the rebuild is running.

One of the methods used to mitigate the overhead of index rebuild is table/index partitioning. You can rebuild indexes on a partition-basis and only perform it for partitions that have volatile data. Old facts table data in most Data Warehouse solutions is relatively static, and ETL processes usually load new data only. Partitioning by date in this scenario localizes modifications within the scope of one or very few partitions. This can help you dramatically reduce the overhead of an index rebuild.

As we already discussed, columnstore indexes support an index reorganize process, which you can trigger with the ALTER INDEX REORGANIZE command. The term index reorganize is a bit vague here; you can think of it as a tuple mover process running on-demand. The only action performed by index reorganization is compressing and moving data from closed delta stores to row groups. Deleted bitmap and open delta stores stay intact.

In contrast to a single-threaded tuple mover process, the ALTER INDEX REORGANIZE operation uses all available system resources while it is running. This can significantly speed up the execution process and reduce the time that other sessions cannot modify or delete data in a table. It is worth noting again that insert processes are not blocked during that time.

A columnstore indexes maintenance strategy should depend on the volatility of the data and the ETL processes implemented in the system. You should rebuild indexes when a table has a considerable amount of deleted rows and/or a large number of partially populated row groups.

It is also advantageous to rebuild partition(s) that have a large number of rows in open delta stores after the ETL process has completed, especially if the ETL process does not use a bulk insert API.