Search Key

If an index is a map from values to record locations, then the search key defines what those values are. The search key is not merely a column you happen to index—it is the organizing principle of the entire index structure. Everything about how the index behaves, what queries it accelerates, and how much space it consumes derives from the search key choice.

Choosing search keys is one of the most impactful decisions a database professional makes. A well-chosen search key turns a 10-minute query into a 10-millisecond query. A poorly chosen search key wastes disk space, slows writes, and provides no query benefit. Understanding search keys deeply—not just what they are, but how they interact with data characteristics and query patterns—is essential for effective database design.

A search key is the attribute or combination of attributes whose values are used to look up records in an index. More formally:

A search key K for an index I on relation R is an ordered list of attributes (A₁, A₂, ..., Aₙ) from R such that each entry in I contains a value from the domain of K paired with references to records in R having that value.

Critical Clarification: Search Key vs. Primary Key

This is a common source of confusion. The term "search key" has a specific technical meaning in indexing that is distinct from the concept of a primary key:

• Primary Key: A constraint on the table that enforces uniqueness and not-null. A table has exactly one primary key.

• Search Key: Any attribute(s) used to organize an index. A table can have many indexes with different search keys. The search key need not be unique—indexes can have duplicate key values.

A simple search key consists of a single attribute. This is the most straightforward form of indexing and is appropriate when queries filter on a single column.

Example:

Consider an employees table with columns (emp_id, name, department, salary, hire_date). An index on department uses department as its search key. The index might look like:

Engineering → {rec_1, rec_4, rec_7, rec_12}
Finance → {rec_2, rec_8}
HR → {rec_3, rec_6, rec_11}
Marketing → {rec_5, rec_9, rec_10}

Each distinct department value maps to the set of records belonging to that department.

Characteristics of Simple Search Keys:

1. Natural Ordering: Most index structures (B+-trees) impose an ordering on key values. For simple keys, this is straightforward—numeric keys are ordered numerically, string keys are ordered lexicographically.

2. Selectivity: A simple key's selectivity—the average fraction of records matching a given key value—is determined by the attribute's cardinality (number of distinct values) and value distribution.

3. Storage Efficiency: Index entries are compact—each contains one value from the indexed column plus a pointer. For a 4-byte integer key with 8-byte pointers, each entry is 12 bytes.

Query Matching:

A simple search key index is useful for queries with predicates on that column:

-- Uses the department index effectively
SELECT * FROM employees WHERE department = 'Engineering';

-- Can use the department index for range queries (in B+-trees)
SELECT * FROM employees WHERE department BETWEEN 'A' AND 'F';

-- Cannot use the department index (predicate on different column)
SELECT * FROM employees WHERE salary > 100000;

A composite (compound) search key consists of multiple attributes in a defined order. This powerful technique allows a single index to efficiently serve queries filtering on combinations of columns.

Example:

An index on (department, hire_date) creates a two-level ordering:

1. First, entries are sorted by department
2. Within each department, entries are sorted by hire_date

(Engineering, 2020-01-15) → rec_7
(Engineering, 2021-03-22) → rec_1
(Engineering, 2022-08-10) → rec_12
(Finance, 2019-07-01) → rec_2
(Finance, 2022-02-28) → rec_8
(HR, 2018-11-30) → rec_3
...

This structure is ideal for queries like:

-- Uses both columns: very efficient
SELECT * FROM employees 
WHERE department = 'Engineering' AND hire_date > '2021-01-01';

Composite Key Ordering:

The order of attributes in a composite key is critical and cannot be changed after index creation. Consider an index on (A, B) versus (B, A):

Both indexes store the same information but support different query patterns efficiently. This is why understanding workload characteristics is essential before creating composite indexes.

Guidelines for Composite Key Column Order:

1. Place equality-predicate columns first: Columns that appear in = conditions should come before columns that appear in >, <, or BETWEEN conditions.

2. Higher selectivity first: When multiple columns have equality predicates, placing more selective columns first can reduce the search space faster.

3. Match query patterns: Analyze your workload. If most queries filter on A and sometimes on A, B, but never on B alone, order (A, B) is correct.

4. Consider sorting needs: If queries often ORDER BY multiple columns, a composite index in that order can provide sorted results without a separate sort operation.

The data type of the search key profoundly affects index structure, storage requirements, and query performance. Each data type brings unique characteristics that must be understood for effective index design.

Numeric Types (INTEGER, BIGINT, DECIMAL):

Numeric keys are ideal for indexing:

• Compact storage: 4 bytes for INT, 8 for BIGINT
• Fast comparison: Single CPU instruction for equality/ordering
• Predictable distribution: Often naturally sequential (auto-increment IDs)
• No collation complexity: Universal ordering semantics

String Types (VARCHAR, TEXT):

String keys introduce complexity:

• Variable length: Storage depends on actual values
• Collation-dependent ordering: 'a' < 'B' in some collations, 'B' < 'a' in others
• Prefix complexity: 'apple' and 'application' share a prefix—index must store differentiating suffixes
• Case sensitivity: May need separate indexes for case-sensitive and case-insensitive searches

Date/Time Types (DATE, TIMESTAMP, DATETIME):

Temporal keys have special characteristics:

• Natural range queries: Time data is inherently ordered
• Clustering opportunity: Recent data is often accessed together (temporal locality)
• Precision matters: TIMESTAMP with milliseconds vs. DATE affects cardinality
• Time zone complexity: Storage format affects comparison semantics

UUIDs and GUIDs:

Random identifiers create specific challenges:

• No locality: Random UUIDs scatter insertions across the entire index
• Large size: 16 bytes per key vs. 4 bytes for integer
• Poor cache utilization: Random access patterns defeat caching strategies
• Alternative: UUID v7 and ULID provide time-ordered UUIDs with better indexing behavior

Two related but distinct concepts determine how effective a search key will be: cardinality (a property of the data) and selectivity (a property of queries against that data).

Cardinality:

Cardinality is the number of distinct values in the search key column(s). For a table with N rows:

• Maximum cardinality = N: Every row has a unique value (unique key)
• Minimum cardinality = 1: Every row has the same value (useless for indexing)

Examples:

• employee_id in employees table: Cardinality = N (unique per row)
• country in customers table: Cardinality = ~200 (number of countries)
• is_active boolean column: Cardinality = 2 (true/false)

Selectivity:

Selectivity measures how many rows match a particular predicate value. It is typically expressed as a fraction:

Selectivity = (Number of rows matching the predicate) / (Total rows)

Low selectivity (bad for indexing): Many rows match

• WHERE is_active = true on a table where 95% are active → selectivity = 0.95
• Index provides little benefit over full scan

High selectivity (good for indexing): Few rows match

• WHERE employee_id = 12345 → selectivity = 1/N ≈ 0
• Index dramatically reduces I/O

The Relationship:

High cardinality often (but not always) implies high selectivity. A column with 1 million distinct values is likely to have high selectivity for equality predicates. However, skewed distributions can break this:

• Column has 1 million distinct values (high cardinality)
• But one value appears in 50% of rows
• Queries for that common value have low selectivity despite high cardinality

In ordered indexes (B+-trees and similar structures), the search key defines the sort order of index entries. This ordering is not merely an implementation detail—it has profound implications for query processing.

The Ordering Guarantee:

An index on search key K guarantees that entries are stored in sorted order by K. This enables:

1. Binary search for equality: O(log n) lookup time
2. Range queries: Find start point, scan sequentially
3. Sorted output: Index scan produces results in K order
4. MIN/MAX operations: Directly accessible at index extremities

Example Impact:

-- With index on (department, hire_date):

-- This query gets sorted results 'for free'
SELECT * FROM employees 
WHERE department = 'Engineering'
ORDER BY hire_date;
-- Execution: Index scan, no sorting needed

-- This query requires sorting
SELECT * FROM employees 
WHERE department = 'Engineering'
ORDER BY salary;
-- Execution: Index scan + sort operation (salary not in index)

Ascending vs. Descending Order:

Most databases allow specifying sort direction for each column in a composite index:

CREATE INDEX idx_orders ON orders (customer_id ASC, order_date DESC);

This creates an index where:

• Within each customer, orders are sorted newest-first
• Perfectly matches queries like: ORDER BY customer_id ASC, order_date DESC
• Cannot efficiently satisfy: ORDER BY customer_id DESC, order_date DESC (mixed direction mismatch on customer_id)

Sort Order Compatibility Matrix:

For index (A ASC, B DESC):

Selecting the right search key(s) for an index is as much art as science. It requires understanding the data, the queries, and the trade-offs. Here is a systematic approach:

Step 1: Analyze Query Workload

Before creating any index, collect and analyze query patterns:

• What columns appear in WHERE clauses?
• What columns appear in JOIN conditions?
• What columns appear in ORDER BY clauses?
• What columns appear in GROUP BY clauses?
• What is the frequency of each query pattern?

Step 2: Identify Candidate Keys

For each query pattern, identify which columns would form an effective search key:

• Equality predicates → Candidate for index key
• Range predicates → Candidate for index key (but position matters)
• Join columns → Candidate for index on join attribute
• Sort columns → Candidate if sorting cost is high

Step 3: Evaluate Data Characteristics

For each candidate key, evaluate:

• Cardinality: How many distinct values?
• Distribution: Are values uniformly distributed or skewed?
• Null percentage: How many nulls? (Affects index size and usability)
• Correlation: Are candidate columns correlated? (Affects composite key design)

Step 4: Consider Write Impact

Each index adds write overhead. Consider:

• How often is the indexed column updated?
• What is the read/write ratio for this table?
• Can we consolidate multiple indexes into one composite?

Step 5: Prototype and Measure

Create the index and measure actual performance:

• Is the index being used? (Check EXPLAIN plans)
• What is the improvement in query time?
• What is the impact on write operations?
• Does the optimizer's behavior match expectations?