Skip to content

Leftmost-prefix principle

The leftmost-prefix principle is a rule in database indexing that dictates how queries utilize multi-column (composite) indexes.^[600-developer-mysql.md] It states that an index can only be used by a query if the query filters or accesses the columns starting from the leftmost column of the index definition and proceeding sequentially to the right without skipping the first column.^[600-developer-mysql.md]

Mechanics

When a database creates a composite index, it creates a sorted data structure (typically a B+ Tree) based on the leftmost column first.^[600-developer-mysql.md] For this reason, the index is most efficient when the WHERE clause or ORDER BY clause specifies the leading column.^[600-developer-mysql.md]

If a query attempts to filter by a column that is the second or third item in the index without specifying the first column, the database generally cannot perform an index range scan on that index.^[600-developer-mysql.md] However, if the leading columns are specified, the database can use the index for the matching prefix, and then access the subsequent columns within that sorted subset.^[600-developer-mysql.md]

This principle applies to matching conditions (=, IN) as well as range operations (>, <, BETWEEN).^[600-developer-mysql.md] Once a range query is encountered on a column within the index, columns to its right in the index definition may not be efficiently used for sorting or filtering.^[600-developer-mysql.md]

Practical Example

Consider a composite index created on columns (column_a, column_b, column_c).

  • Fully utilized: WHERE column_a = 1 AND column_b = 2
  • Partially utilized: WHERE column_a = 1 (The database can jump to the section of the index where column_a is 1).
  • Not utilized: WHERE column_b = 2 (Since column_a is missing, the database cannot use the sort order of this index).
  • Prefix utilized: WHERE column_a > 10 AND column_b > 5 (The database can use the index to find column_a > 10, but column_b filtering may be less efficient due to the range on column_a).
  • [[Composite Index]]
  • [[Database Indexing]]
  • [[Query Optimization]]
  • [[B+ Tree]]

Sources

^[600-developer-mysql.md]