The Query Optimizer and Contradiction Detection

Ben Nevarez — Tue, 04 Aug 2009 06:56:00 GMT

One of the many interesting topics I found while working as technical editor of the SQL Server 2008 Internals book was the concept of contradiction detection. So, in this post I will to try to expand on this topic and provide some additional examples.

Contradiction detection is performed by SQL Server during the early steps of the query optimization process. During this process the Query Optimizer tries to find contradictions that can be removed and can make the query perform better. Since these parts of the query are not executed at all, SQL Server saves resources like I/O, locks, memory and CPU, making the query to be executed faster. For example, the Query Optimizer may know that no records can satisfy a predicate even before touching any page of data.

A contradiction may be related to a check constraint, or may be related to the way the query is written, that is, the query itself contains a contradiction. Let us explore both scenarios and analyze the execution plans that are generated on each case.

First, I need to a table with a check constraint. The following code creates a table that stores information about classic rock albums and its check constraint validates that every record entered was released before 1990.

-- create table

create table albums (

name varchar(40),

band varchar(40),

album_year smallint,

constraint check_year check (album_year < 1990))

-- add some records

insert into albums values ('Machine Head', 'Deep Purple', 1972)

insert into albums values ('A Night at the Opera', 'Queen', 1975)

insert into albums values ('British Steel', 'Judas Priest', 1980)

So, if I run a query to list all the records released, let us say before 1980, the execution plan uses a Table Scan operator, which is exactly what I expected for this scenario.

select * from albums

where album_year < 1980

Check Constraint

But what about if somebody tries to request all the records released, for example, after 1995, like in the following query? Does the Query Optimizer know that no records will be returned even before looking at the data on the table?

select * from albums

where album_year > 1995

In this case the Query Optimizer should know that because of the existing check constraint the previous query returns no records. So if I execute this query there is no need for SQL Server to access the data on the table, right? But surprisingly, the resulting execution plan still shows the Table Scan operator. Why?

Actually, there is another optimization called autoparameterization, which is closely related to the trivial plan feature and that overrides contradiction detection. To avoid this optimization I can use some features like query hints, joins, etc. like in the following example

select * from albums

where album_year > 1995

option (maxdop 1)

Once I change the query to use a query hint, the execution plan does not access the table at all, and instead it is just using a Constant Scan operator.

Now, see what happens if I disable the check constraint

-- disable constraint

alter table albums nocheck constraint check_year

This time running the last query uses a Table Scan operator again as the optimizer can not longer use the check constraint.

Finally, there are two choices to enable back the existing check constraint. If I ask SQL Server to enable the constraint and validate the existing data, the constraint will be enabled only if all the data complies with the check constraint definition. If I ask not to validate the existing data, the check constraint will be enabled but only the new records will be validated.

Of course the resulting execution plan of my query will be different depending on the selected choice. If the check constraint is enabled validating the existing data, running the same query again (and including the query hint) will use the Constant Scan operator. But enabling the constraint without validating the existing data will again result in a Table Scan even when no records are returned. Basically, in this last case the query optimizer can not trust the check constraint.

You can test yourself the resulting execution plans of the query after enabling the check constraint with any of these two commands

-- enable constraint validating existing data

alter table albums with check check constraint check_year

-- enable constraint without validating existing data

alter table albums with nocheck check constraint check_year

By the way, you can use the following query to see if a check constraint is not trusted, that is, if it has not been verified for all the records on the table.

select name, is_not_trusted from sys.check_constraints

Contradicting Predicate

The second type of contradiction case is when the query itself contains a contradiction. Take a look at this query

select * from albums

where album_year < 1970 and album_year > 1980

option (maxdop 1)

Same as before the execution plan for this query will use a Table Scan when the query hint is not used even when it is so obvious that there is a contradiction and no records should be returned.

Once I add the query hint, the Table Scan again is gone and only a Constant Scan operator is used.

Search results matching tags 'Query Optimizer', 'Performance', 'Optimization', and 'Check Constraints'

The Query Optimizer and Contradiction Detection