Feb
20
2013

Startup Expression Predicates

When we write T-SQL statements, what we're really doing is describing what data to return. It's then up to the internals of SQL Server to best decide how to most efficiently return the data we asked for.

Sometimes, there's extra information we know about, but that SQL Server doesn't (automatically). Letting SQL Server in on this seemingly redundant information can change how efficiently the data is accessed and returned.

In this post, we'll walk through a simple parent/child example that exploits a partially denormalized table schema to improve join performance to the child tables. The performance improvement comes through SQL Server producing query plans that contain Startup Expression Predicates, which effectively prevents certain parts of the query plan from executing in some cases.

 

Test Setup

The first thing we need to do is set up the tables. We'll need a ProductTypes table, a parent table (Products) and two child tables (ItemProducts and ServiceProducts).

CREATE TABLE [dbo].[ProductTypes]
(
	Id tinyint NOT NULL PRIMARY KEY,
	Description varchar(50) NOT NULL
);

CREATE TABLE [dbo].[Products]
(
	Id int NOT NULL PRIMARY KEY,
	ProductTypeId tinyint NOT NULL
		FOREIGN KEY REFERENCES [dbo].[ProductTypes](Id),
);

CREATE TABLE [dbo].[ItemProducts]
(
	ProductId int NOT NULL PRIMARY KEY
		FOREIGN KEY REFERENCES [dbo].[Products](Id),

	ItemColumn int NOT NULL
);

CREATE TABLE [dbo].[ServiceProducts]
(
	ProductId int NOT NULL PRIMARY KEY
		FOREIGN KEY REFERENCES [dbo].[Products](Id),

	ServiceColumn int NOT NULL
);

In this type of design, there will only ever be a single row in one of the child tables for each row in the parent table. This is typically handled by some form of business logic (stored procedures or views) and enforced by constraints, but I want to keep this example simple, so I'm only mentioning this for the sake of completeness, and what the data is going to "look" like.

Okay, let's add some test data so we can run some queries:

INSERT INTO [dbo].[ProductTypes](Id, Description)
	VALUES
		(1, 'Item'),
		(2, 'Service');
		
INSERT INTO [dbo].[Products](Id, ProductTypeId)
	VALUES
		(1, 1),
		(2, 2);
		
INSERT INTO [dbo].[ItemProducts](ProductId, ItemColumn)
	VALUES (1, 50);
	
INSERT INTO [dbo].[ServiceProducts](ProductId, ServiceColumn)
	VALUES (2, 40);

Now we have rows representing one ItemProduct, and one ServiceProduct.

 

Querying the Data

First let's start by looking at a typical query that might be run against these tables:

SELECT
	p.Id AS ProductId,
	p.ProductTypeId,
	COALESCE(ip.ItemColumn, sp.ServiceColumn) AS OtherColumn
	FROM [dbo].[Products] p
	LEFT OUTER JOIN [dbo].[ItemProducts] ip WITH(FORCESEEK) ON
		ip.ProductId = p.Id
	LEFT OUTER JOIN [dbo].[ServiceProducts] sp WITH(FORCESEEK) ON
		sp.ProductId = p.Id;

(Note: the hints are not standard, but are needed for demonstration purposes; I got a nested loops/table scan plan by default. See the final section of this post for some extra discussion.)

Since each product row will only exist in one of the child tables, we have to use LEFT joins to get any results. The query plan looks like this (click for full size):

We can see that for each row in the Products table, SQL Server must join to both child tables in case there are rows there. Legitimately there could be, as the only thing preventing that is our business logic. SQL Server doesn't understand that, so it has no choice but to ensure correctness and do the extra work.

Here's where the magic comes in. We know that for a given ProductTypeId, rows will only exist in one of the child tables. If SQL Server knew that, then it would only have to join to one child table for each row in Products.

Let's try this query:

SELECT
	p.Id AS ProductId,
	p.ProductTypeId,
	COALESCE(ip.ItemColumn, sp.ServiceColumn) AS OtherColumn
	FROM [dbo].[Products] p
	LEFT OUTER JOIN [dbo].[ItemProducts] ip WITH(FORCESEEK) ON
		(ip.ProductId = p.Id) AND
		(p.ProductTypeId = 1) /*****/
	LEFT OUTER JOIN [dbo].[ServiceProducts] sp WITH(FORCESEEK) ON
		(sp.ProductId = p.Id) AND
		(p.ProductTypeId = 2) /*****/

Now we're telling SQL Server something about our business logic. Let's see if this improves the execution plan:

 

That's better. SQL Server has added two Filter operators -- one for each child table -- that reject rows that don't satisfy the Startup Expression Predicate (in other words, the extra business logic we told SQL Server). This results in only a single seek against the proper child table for each row in the Products table. This could provide a big performance boost: for the number of child tables (m) and the number of parent rows (n), this approach will always execute only n seeks (thus making the number of seeks independent of the number of child tables), instead of m*n as the first approach does. This does of course come at the penalty of storage to denormalize enough information (ProductTypeId in this case) to drive the process, but usually that's not going to be a huge hit (most likely 1 byte per row in the parent table).

As a bonus, here's a different approach to writing the same query. This form may be more appropriate for some things, depending on what you're trying to do:

SELECT
	p.Id AS ProductId,
	p.ProductTypeId,
	a.OtherColumn
	FROM [dbo].[Products] p
	CROSS APPLY
	(
		SELECT
			ItemColumn AS OtherColumn
			FROM [dbo].[ItemProducts] ip
			WHERE
				(ip.ProductId = p.Id) AND
				(p.ProductTypeId = 1) /*****/
				
		UNION ALL
		
		SELECT
			ServiceColumn
			FROM [dbo].[ServiceProducts] sp
			WHERE
				(sp.ProductId = p.Id) AND
				(p.ProductTypeId = 2) /*****/
	) a;

And here is the resulting query plan that contains the Startup Expression Predicate Filter operators:

 

Conclusion

Sometimes giving SQL Server more information than you might think is necessary can help to improve the query plans that are generated. Certainly in cases like this parent/child example, we were able to exploit a denormalized ProductTypeId column to drive the index seeks to the child tables, and make the query scale much better. The result in this case was that the total number of seeks against the child tables became independent of the number of child tables, while still retaining the original query logic. Look for opportunities like this in your queries to give SQL Server extra hints about your table schema -- you can be rewarded with more scalable queries.

 

More?

As I was playing around with these examples, in particular the second query, I found it interesting that for some reason if the plan used a scan operator as the lower input of the nested loops join (such as I got by not using the FORCESEEK hints), there were no startup expression predicates to be found (nor Filter operators). Instead, the predicate end up on the nested loops operator itself, with each child table scanned for every upper input row. This is somewhat puzzling, as I can't think of a reason why the lower input couldn't be protected by a startup expression in that scenario as well. (Note: I only tested on a 2008 R2 RTM instance.)

Comments are closed