Composite Indexes

Indexes need not necessarily be just on one column. Consider this table, which denotes different types of relationships between two users:

Now, say we want to query all Friends of User 10. If we simply had an index on the User ID 1 column, then matching that with ID 10 would give us all relationships of User ID 10. Then we would have to do another pass and filter the “FRIEND” relation rows and return those as the result.

This is not the best use of the index, specially if each user has tons of different relationships with different users. Instead, what we can do is have a multi-column index on (USER ID 1, Relation). This basically means that the B-tree index is built on the user and relation together — think concatenating user ID and relation — and having that as the sort key.

Now we look up the index for (10, Friend) which easily gets us to the friends of User 10.

🤔 Quick notes

While creating the composite index, the order of columns does matter. If a composite index is created on columns (A, B, C), the index is efficient for queries that filter on A and B or just on A. However, it might be less effective for queries filtering only on columns B or C.

The size of the composite index is influenced by the order of columns. The more columns included in the index, the larger the index size.

Additional Reading

⁠

shows how a b-tree index structure for a composite index would look like.