Columnstore Indexes – part 58 (“String Predicate Pushdown”)

Continuation from the previous 57 parts, the whole series can be found at https://www.nikoport.com/columnstore/.

I have previously blogged on the predicate pushdown matter in the post Columnstore Indexes – part 49 (“Data Types & Predicate Pushdown”), and from the published table one could see that the vast majority of the data types are being supported for predicate pushdown in SQL Server 2014.
The most important data type(s) missing the predicate pushdown support is(are) definitely all string ones – (n)char & (n)varchar. In a perfect people would avoid to use character fields for fact tables, but in the real world – well … :)
The missing feature has a major impact on any query involving a character predicate and especially in SQL Server 2016 where the Operational Analytics will allow to create an updatable Nonclustered Columnstore Index over the operational tables, where a lot of string columns to be found.

At Ignite, Microsoft has revealed that it is including String predicate support in SQL Server 2016, and so I decided to take CTP 2.1 for a test drive.

The theory & the basics

With a numeric data type the situation is quite simple, we simply compare the value on the Storage level (one level above SQLOS) and determine if it serves the used predicate or not. With character fields, the situation is a little bit more complex than this – we have a number of ways to search for the content inside our character fields with such operators as ‘LIKE’, for example.

Given this challenge, this is how the Microsoft SQL Server Team decided to implement predicate pushdown for the String data types.
The key aspect of the compression strategy for the string data types in Columnstore Indexes are the Dictionaries. Since the first version of Columnstore Indexes in SQL Server 2012, we always have had 2 types of the dictionaries – the global ones(serves all Segments of a particular column) and the local ones(serve just one single Segment of a particular column).
To determine if the row satisfy the search criteria, we can do string comparison on the dictionary level, and if we are lucky – even a short dictionary string will help us to identify a good number of rows that satisfying our search criteria.

Whenever we execute a search inside some string, the strategy that is being executed on by the Query Optimiser is the following:
1. Search for the applied predicate inside the dictionaries to determine the rows that are satisfying the criteria.
2. Identify the rows that are using the found dictionaries. These rows will be identified as R1.
3. Identify the other rows, that have not been selected with the help of the dictionary. These rows that are not elegible for the dictionary search optimisation will marked as R2.
4. All of the columnstore rows will be returned from the Columnstore Index Scan iterator, where it will simply pass through all identified rows (R1) and will apply the searched predicate filter on the unoptimised R2 rows to filter out the rows applying to the search criteria (R3).
5. The final result returned by the Filter iterator will be the sum of the R1 + R3 rows.

On the diagram on the left, you can see the basic positive (LIKE) process described. For the negative search (NOT LIKE), the logic will be the same, though I believe it would be much more efficient to filter out the not matching rows immediately, because this way we would simply avoid forwarding any of the rows from the Columnstore Index Scan to the filter operator, if they were found in the dictionary already.

You might think – hey, but I do not see any significant IO improvement here, because every row will be read anyway!
Well, its all about the CPU instructions & execution time optimisation here, so we should see a significant win in the terms of the execution time, because a true direct search inside a string is very resource intensive operation, which compared to a dictionary search can come really close to nothing.

The Tests

Using the free database ContosoRetailDW, I am restoring it to my local VM and after dropping the primary key constraint (yeah, all the foreign keys are still in place, because we are rocking SQL Server 2016 – more on this, hopefully in a week).
Notice that I am setting the compatibility level explicitly to 130, because otherwise the new improvements for the queries simply will be deactivated.

USE master;
 
alter database ContosoRetailDW
    set SINGLE_USER WITH ROLLBACK IMMEDIATE;
 
RESTORE DATABASE [ContosoRetailDW] 
    FROM  DISK = N'C:\Install\ContosoRetailDW.bak' WITH  FILE = 1,  
        MOVE N'ContosoRetailDW2.0' TO N'C:\Data\ContosoRetailDW.mdf', 
        MOVE N'ContosoRetailDW2.0_log' TO N'C:\Data\ContosoRetailDW.ldf',  
        NOUNLOAD,  STATS = 5;
 
alter database ContosoRetailDW
    set MULTI_USER;
GO

GO
ALTER DATABASE [ContosoRetailDW] SET COMPATIBILITY_LEVEL = 130
GO
ALTER DATABASE [ContosoRetailDW] MODIFY FILE ( NAME = N'ContosoRetailDW2.0', SIZE = 2000000KB , FILEGROWTH = 128000KB )
GO
ALTER DATABASE [ContosoRetailDW] MODIFY FILE ( NAME = N'ContosoRetailDW2.0_log', SIZE = 400000KB , FILEGROWTH = 256000KB )
GO

ALTER TABLE dbo.[FactOnlineSales] DROP CONSTRAINT [PK_FactOnlineSales_SalesKey];

create clustered columnstore Index PK_FactOnlineSales
	on dbo.FactOnlineSales;

The query I that I will be executing for the test purposes will be the following simple one, which is including 2 string predicates for searching at the FactOnlineSales table, containing ~12.6 Million Rows:

set statistics time, io on
dbcc dropcleanbuffers
dbcc freeproccache

select sum(SalesAmount), sum(SalesAmount) - sum(SalesAmount*prom.DiscountPercent)
	from dbo.FactOnlineSales sales
		inner join dbo.DimPromotion prom
			on sales.PromotionKey = prom.PromotionKey
	where SalesOrderNumber like N'2008%' and
		SalesOrderNumber not like N'%000' 
	option (recompile, maxdop  2);

Here is the relevant part from the execution plan, we can clearly see the Columnstore Index Scan iterator processing the dictionaries and scanning the Segments (I am starting to wish to gain a better visual insight into these type of operations, because Columnstore Indexes become progressively more complex structures with more internal processes that they almost justify their own execution sub-plan existence).

The execution plan does not guarantee us a true predicate pushdown, it is only after we see the sequence of the Columnstore Index Scan and a Filter iterators, that we can check on the properties of the Columnstore Index Scan then determining there if the predicate is being truly listed under the properties.
Yeah, this is definitely not the best way, but right now I honestly do not have any better ideas about how to make it more clear. If you have a good idea, please make sure to raise a Connect Item, because I am confident that everyone would profit from a better visual analysis of the execution plans.

Now let us compare with the execution plan for SQL Server 2014. On the left side you can see the relevant part that I took from SQL Server 2014 – where one could easily notice 2 important parts:
– the absence of the Filter iterator
– the excessive estimated cost for the Columnstore Index Scan
These are the best indications that the Predicate is not being pushed down to the storage level.

That’s interesting, but what about the execution times between different SQL Server versions? They are very significant in my books, even given that we are considering a Non-RTM version of SQL Server 2016 and my other test VM was hooked up with SQL Server 2014 SP1. The total execution time on SQL Server 2016 was 4548 ms with 8499 ms of CPU time burned, while on SQL Server 2014 SP1 it was 6146 ms for the total execution time and 10858 ms for the CPU time.
1.6 Seconds difference in the total time represents around 25% of the difference and for the CPU time it represents 2.7 Seconds. For a small simple query on a rather small table (12.6 million rows) this represents a nice improvement, especially since we do not need to do anything with our existing query.
From what I have seen so far, the better findings in the R1 phase (dictionary search) are, the bigger the difference between SQL Server 2014 & SQL Server 2016 will be.

Segment Elimination

To test the Segment Elimination I suggest to consider a typical query one would face in a lot of projects, where people simply filter on textual columns:

set statistics io on

select max(SalesAmount)
	from dbo.FactOnlineSales
	where SalesOrderNumber >= '2008' and SalesOrderNumber < '2009'

Let's see the textual output with the results, since they are so accessible in SQL Server 2016:

...
Table 'FactOnlineSales'. Segment reads 13, segment skipped 0.
...

What ?!
Why oh why???
Oh wait, this might have to do with the fact that there is a Segment dealignment problem, running the query agains our FactOnlineSales table have shown that we have 100% dealignment. :s

Ok, let's solve the problem in the good old way, by rebuilding the rowstore clustered index and then building the clustered columnstore index with MAXDOP = 1 on it:

	create clustered index PK_FactOnlineSales
		on dbo.FactOnlineSales (SalesOrderNumber desc)
		with (drop_existing = on, maxdop = 1);

	create clustered columnstore index PK_FactOnlineSales
		on dbo.FactOnlineSales 
		with (drop_existing = on, maxdop = 1);

Let's check the segment alignment:

	select segment_id, min_data_id, max_data_id
		from sys.column_store_segments
		where column_id = 8 /* SalesOrderNumber */
		order by segment_id;

Looking at the results I can only feel the cold rising through my vertebral column - there is no alignment at all!
This does not look very much different from SQL Server 2014, this does not allow to do a real Segment Elimination based on the String Predicate, and this means that we have not advanced a full step forward in this direction.

Let's run our test query again:

set statistics io on

select max(SalesAmount)
	from dbo.FactOnlineSales
	where SalesOrderNumber >= '2008' and SalesOrderNumber < '2009'

The results are here:

...
Table 'FactOnlineSales'. Segment reads 13, segment skipped 0.
...

This is definitely not the most correct query in the world, but this is definitely the one type of query that through my entire career I am used to face with. Unfortunately, many developers do not understand the difference in data types and using textual ones in every possible way is the most common thing you will see whenever discovering a new database.

I strongly believe that Microsoft should solve the absence of support for the String Predicate Segment Elimination, this would definitely win a lot of friends from those who are using Columnstore Indexes regularly.

to be continued with Columnstore Indexes – part 59 ("Aggregate Pushdown")