EXPLAIN EXTENDED

From Stack Overflow:

How can I programmatically determine which foreign key are missing indexes?

Concise. Let's try to answer it.

A foreign key involves two tables: a referencing one and a referenced one.

In most databases, some kind of a unique key is required on the referenced table (this may be a PRIMARY KEY or just a UNIQUE constraint). This is by design (when we delete a UNIQUE value, we always delete last instance of this value).

However, indexing the FOREIGN KEY fields in the referencing table is not required. Database can function even without this index. However, this can make deletes from the referenced table slow (to validate the relationship we should perform a full table lookup on the referenced table). It almost always makes sense to index the FOREIGN KEY fields.

For an index on the FOREIGN KEY fields to be of use, its leading key part should consist of all columns that comprise the FOREIGN KEY, in any order. Since FOREIGN KEY checks are always equijoins, not range joins, the order of columns does not matter as long as they are leading in the key.

Consider a constraint: FOREIGN KEY (col1, col2) REFERENCES othertable. Which indexes are good for this foreign key?

So for each foreign key, we should check the following condition: there exists at least one index whose leading part consists of (and only of) all columns that constitute the key.

In SQL Server 2005, the information about indexed columns is stored in sys.index_column. Since indexes can be composite, this is a one-to-many relationship, where index_id and column_id define the index and the column indexed with it, while index_column_id defines column's ordinal position in the index.

For an index to satisfy the foreign key, two conditions should be fulfilled:

1. The number of columns in the index that are also a part of the foreign key should be equal to the maximal index_column_id. This ensures that all columns constitute the leftmost part of the index.
2. The number of columns in the index that are also a part of the foreign key should be equal to the number of columns in the foreign key. This ensures that all foreign key columns are indexed.

And here's the query:

SELECT  fk.name, s.name, o.name,
FROM    sys.foreign_keys fk
JOIN    sys.objects o
ON      o.object_id = fk.parent_object_id
JOIN    sys.schemas s
ON      s.schema_id = o.schema_id
WHERE   EXISTS
(
SELECT  *
FROM    sys.index_columns ic
WHERE   EXISTS
(
SELECT  NULL
FROM    sys.foreign_key_columns fkc
WHERE   fkc.constraint_object_id = fk.object_id
AND fkc.parent_object_id = ic.object_id
AND fkc.parent_column_id = ic.column_id
)
GROUP BY
index_id
HAVING  COUNT(*) = MAX(index_column_id)
AND COUNT(*) =
(
SELECT  COUNT(*)
FROM    sys.foreign_key_columns fkc
WHERE   fkc.constraint_object_id = fk.object_id
)
)

Now, let's create some sample tables and check this query:

Table creation details

CREATE SCHEMA [20090910_foreign]
CREATE TABLE t_primary (
col1 INT NOT NULL,
col2 INT NOT NULL,
CONSTRAINT PK_primary_col1_col2
PRIMARY KEY (col1, col2)
)
CREATE TABLE t_foreign (
id INT NOT NULL,

col11 INT NOT NULL,
col21 INT NOT NULL,
col31 INT NOT NULL,

col12 INT NOT NULL,
col22 INT NOT NULL,
col32 INT NOT NULL,

col13 INT NOT NULL,
col23 INT NOT NULL,

CONSTRAINT FK_foreign_col11_col21
FOREIGN KEY (col11, col21)
REFERENCES t_primary,

CONSTRAINT FK_foreign_col12_col22
FOREIGN KEY (col12, col22)
REFERENCES t_primary,

CONSTRAINT FK_foreign_col13_col23
FOREIGN KEY (col13, col23)
REFERENCES t_primary
)
GO
CREATE INDEX IX_foreign_col21_col11 ON [20090910_foreign].t_foreign (col21, col11)
CREATE INDEX IX_foreign_col32_col12_col22 ON [20090910_foreign].t_foreign (col32, col12, col22)
CREATE INDEX IX_foreign_col13 ON [20090910_foreign].t_foreign (col13)
GO

This script creates a schema with two tables, t_primary and t_foreign. t_primary has a composite PRIMARY KEY, t_foreign has 3 references to that key from different columns.

The first reference is indexed properly (col1, col2), the second one does not consititute the leftmost part of its index (col3, col1, col2), the third one is not indexed on all columns (col1).

Let's run the query:

SELECT  fk.name, s.name, o.name
FROM    sys.foreign_keys fk
JOIN    sys.objects o
ON      o.object_id = fk.parent_object_id
JOIN    sys.schemas s
ON      s.schema_id = o.schema_id
WHERE   s.name = '20090910_foreign'
AND o.name = 't_foreign'
AND EXISTS
(
SELECT  *
FROM    sys.index_columns ic
WHERE   EXISTS
(
SELECT  NULL
FROM    sys.foreign_key_columns fkc
WHERE   fkc.constraint_object_id = fk.object_id
AND fkc.parent_object_id = ic.object_id
AND fkc.parent_column_id = ic.column_id
)
GROUP BY
index_id
HAVING  COUNT(*) = MAX(index_column_id)
AND COUNT(*) =
(
SELECT  COUNT(*)
FROM    sys.foreign_key_columns fkc
WHERE   fkc.constraint_object_id = fk.object_id
)
)

As we can see, the query returned only one foreign key, and this is the one that is indexed properly.