Indexing

An index is a second copy of one or more columns, kept in sorted order, pointing back at the rows they came from. Looking a value up in it costs a few page reads instead of a walk over the table, and it costs something on every write that touches the indexed columns.

CREATE INDEX IX_Orders_CustomerId ON Orders(CustomerId);
CREATE UNIQUE INDEX IX_Users_Email ON Users(Email);

A primary key gets an index without being asked. Everything else is yours to decide.

The kinds available

Composite, over several columns, where order decides what it can answer:

CREATE INDEX IX_Users_Name ON Users(LastName, FirstName);

This serves a query on LastName alone, or on both columns. A query on FirstName alone cannot use it, because the index is sorted by LastName first and the second column is only ordered within each value of the first. Put the column you filter on most often, or the one that narrows the result hardest, on the left.

Covering, carrying extra columns so a query can be answered without going back to the table:

CREATE INDEX IX_Orders_Customer ON Orders(CustomerId) INCLUDE (Total, Status);

SELECT CustomerId, Total, Status FROM Orders WHERE CustomerId = 123 then reads the index and stops there. The included columns make the index larger and make writes that touch them more expensive.

Descending, when the sort order matters:

CREATE INDEX IX_Orders_Recent ON Orders(CreatedAt DESC);

Expression, over the result of a call rather than the raw column:

CREATE INDEX IX_Users_EmailLower ON Users(LOWER(Email));

This one needs care, and the rule is exact: a predicate that wraps a column in a call is not a question about the column. WHERE LOWER(Email) = 'x' can use an index on LOWER(Email) and cannot use an index on Email, because seeking 'x' among the raw values would find the wrong rows. The predicate has to be written the same way the index was.

Partial, over a subset of the rows:

CREATE INDEX IX_Orders_Pending ON Orders(CustomerId) WHERE Status = 'pending';

The index is smaller and cheaper to maintain, and it holds only the rows matching its filter. Note what the planner does with it, below.

When the planner uses an index

Two behaviours are worth knowing before you design around them.

The primary key index is not consulted. A lookup by primary key goes straight to the row, so the planner skips that index rather than choosing it.

Partial indexes are never selected. Deciding whether a query's predicates imply an index's filter is real work, and it is not done today: a filtered index is passed over before cost is considered. It is still built, still maintained on every write that touches its table, and still enforces uniqueness if it is unique.

Until that is implemented, a partial index is a cost with no benefit. A full index on the same column is the answer. The engine's own note adds that such an index can be reached with an explicit hint; nobody has verified that, so do not plan around it.

Deciding between an index and a scan

The planner compares an estimated cost for each. An equality predicate on a unique index is one row and wins easily. A range is the hard case, since the answer depends on what fraction of the table falls inside it.

That fraction is measured rather than assumed. The estimator asks the index for its smallest and largest key and interpolates the bound between them, working on the encoded key bytes rather than on typed values, which is why a text column gets an estimate as readily as an integer one. It costs two descents and no bookkeeping, and it caches its answer for the duration of one planning pass.

Interpolating assumes the values are spread evenly, and often they are not. The estimate is then wrong by the shape of the data rather than by a constant, which is a different order of wrong from the flat 20% guess it replaced: on a thousand rows holding 1 to 1000, that guess was 200 times too high for Value > 999 and five times too low for Value > 0.

Two cases still fall back to the flat guess. A predicate comparing against something other than a literal, as in WHERE a > b, gives the estimator nothing to place. And a range over an index whose bounds cannot be read cheaply gets no answer rather than an expensive one, which is deliberate: a wrong estimate picks a slower plan, while an expensive estimate is paid by every query.

Practical advice

Index the columns you filter and join on, not every column. Each index is maintained on every insert, update and delete touching its columns, and a table carrying several of them writes noticeably slower.

Skip indexes on small tables. Scanning a few hundred rows is quick, and the index costs more to keep than it saves.

Index your foreign keys. A join over an unindexed foreign key is the most common cause of a query that was fast in development and is not in production. Note that a foreign key constraint does not create an index; you write it yourself.

Check what the planner actually did rather than assuming:

EXPLAIN SELECT * FROM Orders WHERE CustomerId = 123;

The index layer is replaceable

Indexes are created through ISecondaryIndexFactory, which is a provider like every other layer. The factory that ships builds each index as a key-value store of its own, so an index uses the same storage engine the table does.

public interface ISecondaryIndexFactory
{
    ISecondaryIndex CreateIndex(string name, bool isUnique);
    string ProviderKey { get; }
}

The shipped factory registers under kvstore and takes a function that produces a store per index, which is why an index inherits whatever storage engine the database was built with rather than being tied to one.

This is the seam to use for an index kind the engine does not have: full-text, spatial, vector. You implement ISecondaryIndex for the structure and ISecondaryIndexFactory to hand them out, and the rest of the engine maintains them on every write without knowing what they are. See architecture for registering one.

Where to go next

• Architecture, the index factory as a replaceable layer
• Benchmarks, what a seek and a range scan cost
• Limitations, the edges of query planning
• WitSQL reference, CREATE INDEX in full