Yet another SQL Server enthusiast

2014-04-01

Join Elimination: reasons which prevent this optimization

Filed under: Uncategorized — ---- @ 12:29 AM

Intro

SQL Server Query optimizer can automatically remove joins between parent and child tables if  the query’s result  remains unchanged. This is optimization is called foreign key join elimination.

Bellow example creates two tables with a simple foreign key defined on a mandatory column:

Code Snippet
CREATE DATABASE FKJoinElimination;
GO
USE FKJoinElimination;
GO

CREATE TABLE dbo.Customer (
    CustomerID INT PRIMARY KEY,
    FirstName NVARCHAR(50) NOT NULL,
    LastName NVARCHAR(50) NOT NULL
);
GO

CREATE TABLE dbo.SalesOrder (
    SalesOrder INT PRIMARY KEY,
    OrderDate DATE NOT NULL,
    CustomerID INT NOT NULL
        CONSTRAINT FK_SalesOrder_CustomerID
        REFERENCES dbo.Customer(CustomerID),
    TotalAmount NUMERIC(18,2) NOT NULL
);
GO

For the following query

Code Snippet
SELECT    COUNT(*)
FROM    dbo.SalesOrder so INNER JOIN dbo.Customer c ON so.CustomerID = c.CustomerID
GO

SQL Server generates an execution plan (SSMS: Query > Display estimated execution plan)  which includes a single data access operator (Clustered Index Scan on child table dbo.SalesOrder):

Foreign.key.join.elimination.test1

In above example, Query Optimizer automatically removes the JOIN between parent table dbo.Customer and child table dbo.SalesOrder and, also, it removes data access operator on parent table dbo.Customer:

Foreign.key.join.elimination.test1.2

This optimization is possible, mainly, because the foreign key constraint is defined on a single mandatory column and this constraint is trusted.

Reasons

I think it worth mentioning those reasons which prevent Query Optimized to apply this optimization:

  1. When join’s type is INNER JOIN:
    1. FK column allows NULLs. If join’s type is INNER this optimization is possible if FK column is mandatory (NOT NULL).
    2. FK constraint includes multiple columns. If join’s type is INNER this optimization is possible if FK’s constraint is defined on a single column.
    3. FK constraint isn’t trusted but is enabled and isn’t marked [NOT FOR REPLICATION]. This optimization is possible if FK constraint is trusted.
    4. FK constraint isn’t trusted because is disabled and/or is marked [NOT FOR REPLICATION]. This optimization is possible if FK constraint is trusted (FK constraint is enabled and isn’t marked [NOT FOR REPLICATION]).
    5. tempdb.
  2. When join’s type is OUTER JOIN. For simplicity, I will consider only the LEFT JOIN: dbo.ChildTable LEFT [OUTER] JOIN dbo.ParentTable ON …:
    1. There is no unique constraint / primary key constraint / unique index on parent table defined on join’s columns.

Example for 1.3

Code Snippet
– Test #2: what happens if FK constraint isn't enabled properly?
– I disable the FK constraint.
ALTER TABLE dbo.SalesOrder
NOCHECK CONSTRAINT FK_SalesOrder_CustomerID;
GO

SELECT fk.is_disabled, fk.is_not_for_replication, fk.is_not_trusted FROM sys.foreign_keys fk
WHERE fk.name = N'FK_SalesOrder_CustomerID';
GO
/*
is_disabled is_not_for_replication is_not_trusted
———– ———————- ————–
1           0                      1
*/

SELECT    COUNT(*)
FROM    dbo.SalesOrder so INNER JOIN dbo.Customer c ON so.CustomerID = c.CustomerID
GO

– Test #2 Disabling and enabling FK constraint.
– What happens if FK constraint is enabled but is not trusted and is not marked [NOT FOR REPLICATION]?
– FK constraint is enabled and optimization is allowed
SELECT fk.is_disabled, fk.is_not_for_replication, fk.is_not_trusted FROM sys.foreign_keys fk
WHERE fk.name = N'FK_SalesOrder_CustomerID';
GO
/*
is_disabled is_not_for_replication is_not_trusted
———– ———————- ————–
0           0                      0
*/

– We disable the FK constraint
ALTER TABLE dbo.SalesOrder
NOCHECK CONSTRAINT FK_SalesOrder_CustomerID;
GO

– Now, the FK constraint is disabled and becomes not trusted. Optimization is not possible.
SELECT fk.is_disabled, fk.is_not_for_replication, fk.is_not_trusted FROM sys.foreign_keys fk
WHERE fk.name = N'FK_SalesOrder_CustomerID';
GO
/*
is_disabled is_not_for_replication is_not_trusted
———– ———————- ————–
1           0                      1
*/
SELECT    COUNT(*)
FROM    dbo.SalesOrder so INNER JOIN dbo.Customer c ON so.CustomerID = c.CustomerID
GO

The execution plans includes data access operator for both tables:

Foreign.key.join.elimination.test2

Code Snippet
– I enable the FK constraint without data validation. FK constraint remains not trusted. Optimization is not possible.
ALTER TABLE dbo.SalesOrder
CHECK CONSTRAINT FK_SalesOrder_CustomerID;
GO

SELECT fk.is_disabled, fk.is_not_for_replication, fk.is_not_trusted FROM sys.foreign_keys fk
WHERE fk.name = N'FK_SalesOrder_CustomerID';
GO
/*
is_disabled is_not_for_replication is_not_trusted
———– ———————- ————–
0           0                      1
*/

SELECT    COUNT(*)
FROM    dbo.SalesOrder so INNER JOIN dbo.Customer c ON so.CustomerID = c.CustomerID
GO

The execution plan is the same:

Foreign.key.join.elimination.test2

Code Snippet
– Solution: I enabled (CHECK) FK constraint with data validation (WITH CHECK). Thus, FK constraint becomes trusted.
ALTER TABLE dbo.SalesOrder
WITH CHECK CHECK CONSTRAINT FK_SalesOrder_CustomerID;
GO

SELECT fk.is_disabled, fk.is_not_for_replication, fk.is_not_trusted FROM sys.foreign_keys fk
WHERE fk.name = N'FK_SalesOrder_CustomerID';
GO
/*
is_disabled is_not_for_replication is_not_trusted
———– ———————- ————–
0           0                      0
*/

SELECT    COUNT(*)
FROM    dbo.SalesOrder so INNER JOIN dbo.Customer c ON so.CustomerID = c.CustomerID
GO

And the execution plan shows only one data access operator:

Foreign.key.join.elimination.test1

Script

To check what FK constraints allows FK join elimination optimization I wrote this script:

Code Snippet
SELECT    fk.name, fk.is_disabled, fk.is_not_for_replication, fk.is_not_trusted, ca.ColumnCount, ca.NullableColumnCount,
        CASE WHEN fk.is_not_trusted = 0 AND ca.ColumnCount = 1 AND ca.NullableColumnCount = 0 AND DB_NAME() <> 'tempdb' THEN 1 ELSE 0 END AS FK_JoinEliminationIsPossible
FROM    sys.foreign_keys fk
INNER JOIN (
        SELECT    fkcol.constraint_object_id,
                COUNT(*) AS ColumnCount,
                SUM(CONVERT(TINYINT, col.is_nullable)) AS NullableColumnCount
        FROM    sys.foreign_key_columns fkcol
        INNER JOIN sys.columns col ON fkcol.parent_object_id = col.object_id AND fkcol.parent_column_id = col.column_id
        GROUP BY fkcol.constraint_object_id
) ca ON fk.object_id = ca.constraint_object_id
–WHERE fk.name = N'FK_SalesOrder_CustomerID'
GO

About these ads

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Rubric Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: