Composite Indexes, the “Include” Keyword, and How They Work

In SQL Server (and most other relational databases), a "Composite Index" is an index with multiple keys. Let's say we have this query that gets run a lot, and we want to create a covering index for this query to speed it up;

SELECT a, b FROM MyTable WHERE c = @val1 AND d = @val2

These are all possible composite indexes that would cover this query;

CREATE INDEX ix1 ON MyTable (c, d, a, b)
CREATE INDEX ix2 ON MyTable (c, d) INCLUDE (a, b)
CREATE INDEX ix3 ON MyTable (d) INCLUDE (a, b, c)
CREATE INDEX ix4 ON MyTable (c) INCLUDE (a, b, d)

But apparently, they don't perform equally. According to Erlan Sommarskog (Microsoft MVP), the first two are faster than the 3rd and 4th, and the 4th is faster than the 3rd.

He goes on to explain;

> ix2 is the "best" index, because a and b will not take up space in the higher levels of the index tree. Also, if a or b are updated, in ix2 there can be no page splits or similar as the index tree is unaffected.

However, I am having a hard time grasping what exactly is going on. I do have the general knowledge on b-tree indexes and how they work, but I don't understand the logic behind composite keys. For example;

CREATE INDEX ix1 ON MyTable (c, d, a, b)

Does the order of the columns here matter? If so, why? Also;

CREATE INDEX ix2 ON MyTable (c, d) INCLUDE (a, b)

What is the difference between this composite key and the one above? I don't understand what difference "INCLUDE" makes.

Note: I know there are a lot of posts on Composite Keys, but I believe my last two questions are specific enough to not be a duplicate.

CREATE INDEX ix1 ON MyTable (c, d, a, b)

> Does the order of the columns here matter? If so, why? Also;

Yes, order is very important while creating index, because each column is (from left) next level of deepness in index, so to determine the compilator to use this index you need always seek for c which is the "opener" of this set.

CREATE INDEX ix2 ON MyTable (c, d) INCLUDE (a, b)

> What is the difference between this composite key and the one above? I don't understand what difference "INCLUDE" makes.

But keep in mind that for each level of the index it starts to be less efficient, so if you know that > 80% of your queries will only seek by c & d and not a & b, but you will need that information in your SELECT (nor in WHERE) you should INCLUDE them, as part of the leaf at the last level of the index.

There are better explanations than mine so feel free to look at them:

https://stackoverflow.com/questions/5108651/include-equivalent-in-oracle -> INCLUDE
https://stackoverflow.com/questions/2292662/how-important-is-the-order-of-columns-in-indexes -> ORDER in INDEX set

> Does the order of the columns here matter?

Considering only the query in your question with 2 equality predicates, the order of the composite index key columns doesn't matter as long as both are the leftmost key columns of the composite index. Any of the covering indexes below will optimize this query:

CREATE INDEX ix1 ON MyTable (c, d, a, b);
CREATE INDEX ix2 ON MyTable (c, d) INCLUDE (a, b);
CREATE INDEX ix3 ON MyTable (d, c, a, b);
CREATE INDEX ix4 ON MyTable (d, c, b, a);
CREATE INDEX ix5 ON MyTable (d, c) INCLUDE (a, b);

That said, the stats histogram contains only the leftmost index key column so the general guidance is to specify the most selective column first to improve row count estimates and execution plan quality. This consideration is more important for non-trivial queries where the optimizer has many choices and row count estimates are an important factor in choosing the best plan.

Another consideration for key order, which may conflict with the above general guidance, is when the index supports different queries and only some of the key columns are specified (e.g. SELECT a, b FROM MyTable WHERE d = @val2;). In that case, it would be better to specify d as the leftmost column regardless of selectivity in order to allow a single index to optimize multiple queries instead of creating a separate index to optimize the second query.

> What is the difference between this composite key and the one above? I
> don't understand what difference "INCLUDE" makes.

Included columns are not key columns. Key columns are maintained in logical order at every level throughout the b-tree whereas included columns are present only in the b-tree leaf nodes and not ordered. Consequently, the specified order of included columns does not matter. The only purpose of included columns is to help cover queries without adding them as key columns and incurring the associated overhead.