Index #

“The query is slow, try adding an index.” This advice is correct — but only half of it. The unspoken part: a wrongly placed index actually slows the whole system down. Writes become slower because the database must update every index whenever data changes. Storage balloons. The query planner gets confused choosing which index is optimal. And the most annoying part: an index that was painstakingly added turns out to never be used at all because of a small mistake in the query.

Indexes are one of those topics that’s easiest to understand on the surface — “create an index so queries are fast” — but deepest when you trace all the way down to how they work. Understanding indexes correctly means understanding why a query is slow even though an index exists, why adding an index can make the whole system slower, and how to design indexes that actually work for your data access patterns.

How Indexes Work: From Full Scans to Logarithmic Search #

Without an index, the database’s way of finding data is very simple and very expensive: it reads every row from start to finish — called a full table scan — until it finds a row matching the query condition. For a table with a thousand rows, this is still fast. For a table with ten million rows, this can take seconds.

Full table scan — without an index:

  Table users (10,000,000 rows):
  ┌────┬────────────────────────┬──────┐
  │ id │ email                  │ name │
  ├────┼────────────────────────┼──────┤
  │  1 │ [email protected]          │ Andi │  ← read, check, no match
  │  2 │ [email protected]          │ Budi │  ← read, check, no match
  │  3 │ [email protected]          │ Cici │  ← read, check, no match
  │ .. │ ...                    │ ...  │  ← continues to 10 million rows
  │ 7M │ [email protected]        │ Tejo │  ← found at row 7 million
  └────┴────────────────────────┴──────┘

  SELECT * FROM users WHERE email = '[email protected]';
  → The database reads 7,000,000 rows before finding the result
  → Time: O(n) — linear to the number of rows

An index solves this problem the same way a book’s table of contents does: instead of reading page by page, you immediately know which page the topic you’re looking for is on.

With an index on the email column:

  B-Tree index (sorted):              Original table:
  ┌──────────────────┬─────────┐       ┌────┬────────────────────┐
  │ email (sorted)   │ row ptr │       │ id │ email              │
  ├──────────────────┼─────────┤       ├────┼────────────────────┤
  │ [email protected]    │ → id=1  │       │  1 │ [email protected]      │
  │ [email protected]    │ → id=2  │       │  2 │ [email protected]      │
  │ [email protected]    │ → id=3  │       │  7M│ [email protected]    │
  │ ...              │ ...     │       └────┴────────────────────┘
  │ [email protected]  │ → id=7M │
  └──────────────────┴─────────┘

  SELECT * FROM users WHERE email = '[email protected]';
  → The database navigates the B-Tree: O(log n)
  → For 10 million rows: only ~23 steps, not 7 million

The difference between O(n) and O(log n) on large tables isn’t just a speed difference — it’s the difference between a query finishing in milliseconds and a query timing out.

Internal Structure: How B-Trees Work #

Almost all indexes in modern relational databases use the B-Tree structure or its variant B+Tree. Understanding how it works is important for understanding why indexes work for some query types but not others.

A B-Tree is always balanced — the depth from root to every leaf is always the same, no matter how much data there is. This is what guarantees O(log n) complexity for all operations.

B-Tree visualization for an index on the 'email' column:

                    [M]
                   /   \
              [D-G]     [R-T]
             /  |  \   /  |  \
           [A] [E] [H][P] [S] [V]

  Each node stores sorted values.
  Searches always start from the root, descending in the right direction.
  To find '[email protected]': root → right (R-T) → right (V) → not there,
  check [S] → found. Only 3 steps for the entire dataset.

This sorted structure is why B-Tree indexes aren’t only useful for equality searches (=), but also for:

Range queries: WHERE price BETWEEN 100 AND 500 — the database navigates to value 100, then scans right to 500
Prefix matches: WHERE name LIKE 'Ali%' — the database navigates to ‘Ali’, then scans while the prefix still matches
Sorting: ORDER BY created_at — the data is already sorted in the index, no extra sort needed
Min/Max: SELECT MIN(price) — just take the leftmost or rightmost node

What a B-Tree index can’t do efficiently:

WHERE name LIKE '%Ali%' — a leading wildcard can’t leverage the index order
WHERE LOWER(email) = '[email protected]' — a function on the column makes the index unusable
Columns with very low cardinality (boolean, gender) — an index is ineffective because every value matches too many rows

Four Most Important Index Types #

Single Column Index #

An index on one column — the simplest and most common form. Effective for queries that filter, sort, or join on a single column.

-- Creating single column indexes
CREATE INDEX idx_orders_user_id ON orders(user_id);
CREATE INDEX idx_orders_created_at ON orders(created_at);

-- Queries that will leverage these indexes:
SELECT * FROM orders WHERE user_id = 42;
SELECT * FROM orders WHERE created_at >= '2025-01-01' ORDER BY created_at;
SELECT COUNT(*) FROM orders WHERE user_id = 42;

Composite Index #

An index on more than one column. This is the index type most often misused — both in its column order and in assumptions about which queries can leverage it.

The most important rule for composite indexes: column order determines everything. The database can only use a composite index if the query uses those columns from left to right without skipping a column in the middle.

-- Composite index: (user_id, status, created_at)
CREATE INDEX idx_orders_user_status_date ON orders(user_id, status, created_at);

-- Queries that CAN leverage this index:
SELECT * FROM orders WHERE user_id = 42;                          -- ✓ first column
SELECT * FROM orders WHERE user_id = 42 AND status = 'pending';   -- ✓ first two columns
SELECT * FROM orders
WHERE user_id = 42 AND status = 'pending'
  AND created_at >= '2025-01-01';                                  -- ✓ all three columns

-- Queries that CANNOT fully leverage the index:
SELECT * FROM orders WHERE status = 'pending';        -- ✗ skips user_id (first column)
SELECT * FROM orders WHERE created_at >= '2025-01-01'; -- ✗ skips user_id and status

The "leftmost prefix rule" visualization:

  Index: (A, B, C)
  ┌───────────────────────────────────────────────────────────────┐
  │  Query uses A        → index used (column A)                  │
  │  Query uses A, B     → index used (columns A and B)           │
  │  Query uses A, B, C  → index fully used                       │
  │  Query uses B        → index NOT used                         │
  │  Query uses B, C     → index NOT used                         │
  │  Query uses A, C     → index used only for A                  │
  └───────────────────────────────────────────────────────────────┘

Unique Index #

A unique index combines two functions: speeding up lookups while guaranteeing no duplicate values. Every UNIQUE KEY in a table DDL automatically creates a unique index.

-- Unique index on a single column
ALTER TABLE users ADD UNIQUE KEY uk_users_email (email);

-- Composite unique index: a column combination that must be unique
ALTER TABLE order_items ADD UNIQUE KEY uk_order_items_order_product (order_id, product_id);
-- One product can't appear twice in the same order

-- Unique indexes are also used for upserts:
INSERT INTO users (email, name) VALUES ('[email protected]', 'Ali')
ON DUPLICATE KEY UPDATE name = VALUES(name);

Covering Index #

A covering index is an index that already includes all the columns a query needs — whether in WHERE, SELECT, or ORDER BY. When a covering index is used, the database doesn’t need to access the main table at all: all the needed data is already in the index.

This is a very significant optimization because index access is far faster than table access (indexes are smaller, more likely to fit in memory/cache).

-- Query: get the email and name of all active users
SELECT email, name FROM users WHERE is_active = 1;

-- A regular index on is_active:
-- The database uses the index for filtering, but must read the table to get email and name

-- A covering index that includes all columns the query needs:
CREATE INDEX idx_users_active_email_name ON users(is_active, email, name);
-- The database doesn't need to read the table at all — everything is in the index

-- How to verify a covering index is used:
EXPLAIN SELECT email, name FROM users WHERE is_active = 1;
-- Look at the 'Extra' column: if it shows "Using index" → covering index successfully used

Covering indexes are one of the optimizations with the biggest impact on read-heavy queries. If there’s a query run very frequently and it doesn’t have too many columns, consider creating a covering index that includes all the columns that query needs.

The Trade-off That Must Not Be Ignored #

Indexes aren’t free. Every index you create carries a cost that must be paid on every write operation.

Writes Become Slower #

Every INSERT, UPDATE, and DELETE doesn’t just update the table data — it must also update all relevant indexes. The more indexes, the more expensive every write operation.

The impact of indexes on writes:

  Table orders without indexes:
    INSERT → updates 1 structure (table)     → fast

  Table orders with 5 indexes:
    INSERT → updates 6 structures (table + 5 indexes) → slower

  Table orders with 15 indexes:
    INSERT → updates 16 structures → slow, especially for bulk inserts

  Systems with high INSERT rates (logging, event tracking, IoT):
  → Too many indexes can become a serious write bottleneck

This is also why very write-heavy systems — like logging, analytics events, or sensor data — usually use a separate database optimized for writes, not the operational database with many indexes.

Storage Grows #

Indexes are separate data structures stored on disk. For large tables with many indexes, the total index size can exceed the data size itself.

-- How to check index size per table in MySQL
SELECT
    table_name,
    ROUND(data_length / 1024 / 1024, 2) AS data_mb,
    ROUND(index_length / 1024 / 1024, 2) AS index_mb,
    ROUND(index_length / data_length * 100, 1) AS index_ratio_pct
FROM information_schema.tables
WHERE table_schema = 'your_database'
ORDER BY index_length DESC;

-- If index_ratio_pct is far above 100%,
-- that means indexes are bigger than the data → worth evaluating whether all indexes are needed

Low Cardinality Makes Indexes Ineffective #

Cardinality is the number of unique values in a column. Indexes are most effective on high-cardinality columns — many distinct values, so each index value points to few rows. Indexes are almost useless on low-cardinality columns.

Cardinality examples:

  Column 'id' (primary key)        → cardinality = row count (very high)
  Column 'email' (unique)          → cardinality ≈ row count (very high)
  Column 'user_id' in the orders table → cardinality = user count (high)
  Column 'status' (5 unique values) → cardinality = 5 (low)
  Column 'is_active' (boolean)     → cardinality = 2 (very low)
  Column 'gender'                  → cardinality = 3-4 (very low)

  An index on 'is_active':
  → The value TRUE matches 50% of rows
  → The value FALSE matches 50% of rows
  → The database often chooses a full table scan because it's more efficient
    than using an index pointing to millions of rows

-- Check the cardinality of existing indexes
SHOW INDEX FROM orders;
-- The 'Cardinality' column shows the estimated number of unique values
-- The higher → the more effective the index

Traps That Make Indexes Unused #

This is the most important and most often unnoticed part. You’ve created the index, but the query is still slow — because there’s a condition making the database decide not to use the index at all.

Functions on Indexed Columns #

Placing a function on a column in the WHERE clause disables the database’s ability to use an index on that column.

-- ANTI-PATTERN: functions on columns → index unused
SELECT * FROM orders WHERE DATE(created_at) = '2025-06-01';
-- The database can't use the index on created_at
-- because it must evaluate DATE() for every row first

SELECT * FROM users WHERE LOWER(email) = '[email protected]';
-- The index on email is unused because LOWER() changes the value before comparison

SELECT * FROM products WHERE YEAR(released_at) = 2024;
-- Same — YEAR() on the column makes the index useless

-- CORRECT: rewrite the query so the column isn't wrapped in a function
SELECT * FROM orders
WHERE created_at >= '2025-06-01' AND created_at < '2025-06-02';
-- The index on created_at can be used — a range query on the column itself

SELECT * FROM users WHERE email = LOWER('[email protected]');
-- Apply the function to the searched value, not the column
-- The index on email can still be used

SELECT * FROM products WHERE released_at >= '2024-01-01' AND released_at < '2025-01-01';
-- A range query replaces YEAR() — the index on released_at is used

Implicit Type Conversion #

If the data type of the searched value differs from the column type, the database performs automatic conversion — and that conversion can make the index unused.

-- ANTI-PATTERN: type mismatch → implicit conversion → index unused
-- The 'phone' column is VARCHAR
SELECT * FROM users WHERE phone = 628123456789;
-- The database converts the number to a string for every row → full scan

-- CORRECT: use the same type
SELECT * FROM users WHERE phone = '628123456789';
-- No conversion → the index on phone can be used

Leading Wildcards in LIKE #

A wildcard at the start of a string in LIKE makes the database unable to use the B-Tree order to find matches.

-- ANTI-PATTERN: leading wildcard → index unused
SELECT * FROM products WHERE name LIKE '%Sepatu%';
-- The database doesn't know where in the B-Tree to start searching
-- → full table scan

-- CORRECT: trailing wildcard → index can still be used
SELECT * FROM products WHERE name LIKE 'Sepatu%';
-- The database knows: start from values beginning with 'Sepatu' in the B-Tree
-- → index used for prefix matching

-- For substring searches anywhere in the text, use a Full-Text Index:
ALTER TABLE products ADD FULLTEXT INDEX ft_products_name (name);
SELECT * FROM products WHERE MATCH(name) AGAINST('Sepatu' IN BOOLEAN MODE);

OR Conditions Weakening Selectivity #

OR conditions between two different columns often make the query planner unable to use a single index effectively.

-- ANTI-PATTERN: OR across two different columns
SELECT * FROM users WHERE email = '[email protected]' OR phone = '08123456789';
-- The indexes on email and phone can't be used together efficiently
-- The database may choose a full scan

-- CORRECT: split into two queries and combine with UNION
SELECT * FROM users WHERE email = '[email protected]'
UNION
SELECT * FROM users WHERE phone = '08123456789';
-- Each query part can use its own index

How to Read EXPLAIN for Index Diagnosis #

EXPLAIN is the main tool for verifying whether an index is used and how effective it is. You should be comfortable reading it before creating or dropping any index.

-- Run EXPLAIN before the query you want to inspect
EXPLAIN SELECT * FROM orders WHERE user_id = 42 AND status = 'pending';

-- Output to pay attention to:
-- ┌────────────┬────────────┬─────────────────────────┬──────────┬────────────────────────┐
-- │ type       │ key        │ rows                    │ filtered │ Extra                  │
-- ├────────────┼────────────┼─────────────────────────┼──────────┼────────────────────────┤
-- │ ALL        │ NULL       │ 5,000,000               │ 1.00     │ Using where            │
-- │ ref        │ idx_u_s    │ 150                     │ 100.00   │ Using index condition  │
-- │ const      │ PRIMARY    │ 1                       │ 100.00   │                        │
-- └────────────┴────────────┴─────────────────────────┴──────────┴────────────────────────┘

Guide to reading the 'type' column (best to worst):

  const    → primary key or unique key with a single value. Fastest.
  eq_ref   → join using a primary key or unique key. Very efficient.
  ref      → index used but not unique. Efficient for indexed columns.
  range    → index used for ranges (BETWEEN, >, <). Still good.
  index    → full scan of the index (faster than ALL, but still a scan).
  ALL      → full table scan. No index used. ← the one to avoid

Guide to reading the 'Extra' column:

  Using index         → a covering index is used, no table reads. Best.
  Using where         → the database filters rows after reading. Normal.
  Using filesort      → the database needs extra sorting in memory/disk. Consider an ORDER BY index.
  Using temporary     → the database creates a temporary table. Often appears in GROUP BY without an index.
  Using index condition → Index Condition Pushdown — some filtering happens at the index level.

-- For more detailed analysis, use EXPLAIN ANALYZE (MySQL 8.0+)
EXPLAIN ANALYZE SELECT * FROM orders WHERE user_id = 42 AND status = 'pending';
-- Shows actual rows, actual time, and loops — not just estimates

Strategies for Designing the Right Indexes #

Designing correct indexes isn’t about adding as many as possible — it’s about understanding the most frequent and most important query patterns, then creating indexes that serve those patterns as efficiently as possible.

Column priority order in a composite index:

  1. Equality columns (=) first — place them leftmost
  2. Then range columns (>, <, BETWEEN) — place after equality
  3. ORDER BY columns can be part of the index if the order matches

  Example query:
  WHERE user_id = 42 AND status = 'pending' AND created_at >= '2025-01-01'
  ORDER BY created_at

  The right index: (user_id, status, created_at)
  → user_id and status as equality columns (left)
  → created_at as a range column and ORDER BY at once (right)
  → One index serving filtering, ranges, and sorting together

-- How to find slow queries needing indexes
-- Enable the slow query log in MySQL:
SET GLOBAL slow_query_log = 'ON';
SET GLOBAL long_query_time = 1;  -- log queries taking > 1 second
SET GLOBAL slow_query_log_file = '/var/log/mysql/slow.log';

-- Or use the Performance Schema for the queries with the most scanning:
SELECT
    digest_text,
    count_star,
    avg_timer_wait / 1000000000 AS avg_seconds,
    sum_rows_examined / count_star AS avg_rows_examined
FROM performance_schema.events_statements_summary_by_digest
WHERE avg_timer_wait > 1000000000  -- over 1 second
ORDER BY avg_timer_wait DESC
LIMIT 20;
-- Queries with high avg_rows_examined are candidates needing indexes

Managing Existing Indexes #

An index isn’t something you create once and forget. As features grow and query patterns change, some indexes become irrelevant — and unused indexes keep burdening write operations and storage.

-- Finding indexes never used (MySQL 8.0+)
SELECT
    object_schema,
    object_name,
    index_name
FROM performance_schema.table_io_waits_summary_by_index_usage
WHERE index_name IS NOT NULL
  AND count_star = 0
  AND object_schema NOT IN ('mysql', 'performance_schema', 'information_schema')
ORDER BY object_schema, object_name;
-- Indexes with count_star = 0 haven't been used since the server last restarted

-- Dropping unused indexes
DROP INDEX idx_unused ON table_name;

-- Adding a new index in production without blocking the table (MySQL 5.6+)
-- The INPLACE or INSTANT algorithm allows ALTER without a full table lock
ALTER TABLE orders
ADD INDEX idx_orders_status_created (status, created_at),
ALGORITHM=INPLACE, LOCK=NONE;

Before dropping an index based on count_star = 0 data, make sure the server has been running long enough to pass all normal usage cycles (including monthly or quarterly processes). An index unused daily might be critical for a process that runs once a month.

Anti-Patterns to Avoid #

-- ✗ Anti-pattern 1: indexes on low-cardinality columns
CREATE INDEX idx_users_is_active ON users(is_active);
-- is_active only has two values: 0 and 1
-- Each value matches ~50% of rows → the database often ignores this index
-- Storage wasted, writes slower, without real benefit

-- ✓ Solution: use a composite index that adds selectivity
CREATE INDEX idx_users_active_created ON users(is_active, created_at);
-- The is_active + created_at combination is far more selective

────────────────────────────────────────────────────────────────────────────────

-- ✗ Anti-pattern 2: creating a separate index for every column
--    when queries always use them together
CREATE INDEX idx_orders_user_id ON orders(user_id);
CREATE INDEX idx_orders_status ON orders(status);
-- Query: WHERE user_id = 42 AND status = 'pending'
-- The database can only use one index, not both at once

-- ✓ Solution: a composite index for the consistent query pattern
CREATE INDEX idx_orders_user_status ON orders(user_id, status);
-- One more effective index replaces two separate ones

────────────────────────────────────────────────────────────────────────────────

-- ✗ Anti-pattern 3: a composite index with reversed column order
-- Query: WHERE user_id = 42 AND status = 'pending'
CREATE INDEX idx_wrong_order ON orders(status, user_id);
-- Because status has low cardinality (only a few values),
-- this index is less effective than (user_id, status)
-- Plus: queries using only user_id can't leverage this index

-- ✓ Solution: put high-cardinality equality columns on the left
CREATE INDEX idx_correct_order ON orders(user_id, status);

────────────────────────────────────────────────────────────────────────────────

-- ✗ Anti-pattern 4: never verifying whether an index is used
-- Adding an index based on guesswork without EXPLAIN verification
ALTER TABLE orders ADD INDEX idx_guess ON orders(category_id);
-- It might never be used because existing queries don't match

-- ✓ Solution: always run EXPLAIN before and after adding an index
-- Verify: does the 'key' column in EXPLAIN change to the new index?
-- Verify: does the 'rows' column drop significantly?
-- Verify: does the 'type' column change from ALL to ref or range?

────────────────────────────────────────────────────────────────────────────────

-- ✗ Anti-pattern 5: too many indexes on write-heavy tables
-- A logs table with 20 indexes: every INSERT updates 21 structures
-- INSERT throughput drops drastically

-- ✓ Solution: for very write-heavy tables, minimize indexes
-- Only create indexes truly needed for critical operations
-- Consider an architecture separating the write store and read store

Index Review Checklist #

BEFORE CREATING A NEW INDEX:
  □ EXPLAIN already run and shows the query needs an index (type=ALL)
  □ The cardinality of the column to be indexed checked — high enough to be effective
  □ No existing index already serving this query
  □ The write performance trade-off considered
  □ For composite indexes: column order thought through (equality first, ranges later)

VERIFICATION AFTER CREATING AN INDEX:
  □ EXPLAIN after creating the index shows it used (key = index name)
  □ The 'type' column changed from ALL to ref, range, or const
  □ The 'rows' column dropped significantly compared to before
  □ Relevant queries confirmed to not use functions on indexed columns
  □ Data types in WHERE clauses match the column types (no implicit conversion)

TRAPS TO CHECK:
  □ No functions (DATE(), LOWER(), YEAR()) wrapping indexed columns in WHERE
  □ LIKE doesn't use leading wildcards ('%keyword')
  □ WHERE value data types match the schema column types
  □ Composite indexes used from the leftmost column (leftmost prefix rule)

PERIODIC MAINTENANCE:
  □ Never-used indexes identified and evaluated
  □ Total index size per table monitored — not far exceeding data size
  □ Indexes re-evaluated after major query pattern or feature changes
  □ Slow query log active to detect new queries needing indexes

Summary #

Indexes turn searches from O(n) into O(log n) — the difference isn’t just speed, it’s whether a query finishes in milliseconds or times out on large tables.
B-Tree indexes are effective for equality, ranges, prefix LIKE, and ORDER BY — but ineffective for leading wildcards, functions on columns, or very low-cardinality columns.
Every index slows writes — INSERT, UPDATE, DELETE must update all related indexes. A table with many indexes is a table with expensive writes.
Composite indexes follow the leftmost prefix rule — the database can only use the index from the leftmost column sequentially. Column order in a composite index largely determines which queries can leverage it.
Covering indexes eliminate table access — if all columns a query needs are already in the index, the database doesn’t need to read the table at all.
Functions on columns in WHERE kill indexes — DATE(created_at), LOWER(email), YEAR(released_at) all make indexes on those columns unused. Rewrite queries so columns aren’t wrapped in functions.
Low cardinality = ineffective indexes — indexes on boolean or gender columns almost never provide real benefit. The database often chooses a full scan.
EXPLAIN is the mandatory tool — always run EXPLAIN before creating an index and after creating one. Make sure type isn’t ALL and key shows the expected index.
Indexes need maintenance — never-used indexes still burden writes and storage. Audit indexes periodically and drop irrelevant ones.
Design indexes based on real queries — not on feelings or “this column seems important”. Look at the slow query log, use EXPLAIN, then decide.

← Previous: Locking Next: Connection Pooling →