Indexes

What Is an Index?

Imagine you're looking for the word "photosynthesis" in a biology textbook. You could start at page 1 and read every single page until you find it — that's a full table scan. Or you could flip to the back of the book, find "photosynthesis" in the alphabetical index, and jump directly to page 347 — that's an index scan.

A database index works exactly the same way. It's a separate data structure that the database maintains alongside a table. It stores a sorted copy of one or more column values, with pointers to the actual row locations. When you query with a WHERE clause or ORDER BY, the database can use the index to find the right rows in milliseconds instead of scanning every row in the table.

Why Indexes Matter for Performance

The difference between a query with and without an appropriate index can be staggering:

A full table scan reads every row regardless of how many rows match your query. An index scan reads only the relevant rows. On a table with millions of rows, this is the difference between milliseconds and minutes.

B-Tree Index — The Default Index

The vast majority of indexes you'll ever create or use are B-Tree (Balanced Tree) indexes. This is the default when you write CREATE INDEX.

How a B-Tree Works (Conceptually)

Think of it as a sorted binary tree, like a phone directory sorted alphabetically:

                    [M]
                 /       \
            [G]               [T]
           /   \             /   \
        [C]    [J]        [P]    [W]
       / \    / \        / \    / \
     [A][D] [H][K]    [N][R] [U][Z]

• The root and branch nodes store the sorted key values and pointers to child nodes
• The leaf nodes store the actual index key values plus a rowid — a physical pointer to where the row lives in the table
• To find "R", the database traverses just 3 comparisons: Root → T → P → R

A B-Tree index on a million-row table needs only about 20 comparisons to find a value — versus 1,000,000 for a full scan. The tree stays balanced automatically as data changes.

B-Tree Indexes Speed Up:

-- 1. WHERE clause equality
SELECT * FROM employees WHERE employee_id = 107;
-- Index on employee_id → direct lookup

-- 2. WHERE clause range queries
SELECT * FROM employees WHERE salary BETWEEN 50000 AND 80000;
-- Index on salary → scan the sorted range

-- 3. ORDER BY (reads the pre-sorted index)
SELECT first_name, last_name FROM employees ORDER BY last_name;
-- Index on last_name → already sorted, no sort operation needed

-- 4. JOIN conditions
SELECT e.first_name, d.department_name
FROM   employees e
JOIN   departments d ON e.department_id = d.department_id;
-- Index on e.department_id and/or d.department_id speeds up the join

Creating Indexes

Basic CREATE INDEX Syntax

-- Create a B-Tree index on a single column
CREATE INDEX idx_emp_last_name
ON employees (last_name);

-- Create an index on a column frequently used in WHERE and JOIN
CREATE INDEX idx_emp_department_id
ON employees (department_id);

-- Create an index on a column used for sorting
CREATE INDEX idx_emp_hire_date
ON employees (hire_date);

After creating the index, queries that filter, sort, or join on those columns may automatically use it — no query changes needed.

DROP INDEX

-- Remove an index (Oracle)
DROP INDEX idx_emp_last_name;

-- Remove an index (MySQL / PostgreSQL)
DROP INDEX idx_emp_last_name ON employees;

Unique Index

A unique index enforces uniqueness on a column (or combination of columns) — no two rows can have the same value. Creating a PRIMARY KEY or UNIQUE constraint automatically creates a unique index.

-- Explicitly create a unique index (alternative to UNIQUE constraint)
CREATE UNIQUE INDEX idx_emp_email
ON employees (email);

-- Now this INSERT would fail:
INSERT INTO employees (employee_id, email) VALUES (299, 'EXISTING_EMAIL');
-- ORA-00001: unique constraint violated

Composite (Multi-Column) Index

A composite index covers two or more columns. It's like an address book sorted first by last name, then by first name within each last name.

-- Composite index on last_name + first_name
CREATE INDEX idx_emp_name
ON employees (last_name, first_name);

The Left-Prefix Rule — Column Order Matters Enormously

A composite index on (last_name, first_name) can be used when you query:

• WHERE last_name = 'King' ✓ (uses leftmost column)
• WHERE last_name = 'King' AND first_name = 'Robert' ✓ (uses both columns)
• WHERE first_name = 'Robert' ✗ (skips leftmost column — index NOT used)
• WHERE last_name = 'King' AND salary > 50000 — partial use (only last_name portion used)

-- This query CAN use the composite index idx_emp_name (last_name, first_name)
SELECT * FROM employees
WHERE  last_name = 'Abel'               -- uses leftmost column ✓
AND    first_name = 'Ellen';            -- uses second column ✓

-- This query CANNOT use idx_emp_name
SELECT * FROM employees
WHERE  first_name = 'Ellen';            -- skips last_name (leftmost column) ✗
-- The database falls back to a full table scan

Practical Composite Index Example

-- This query is very common: filter by department, sort by salary
SELECT first_name, last_name, salary
FROM   employees
WHERE  department_id = 60
ORDER BY salary DESC;

-- A composite index on (department_id, salary) serves both needs:
CREATE INDEX idx_emp_dept_salary
ON employees (department_id, salary);
-- WHERE department_id = 60 uses the first column
-- ORDER BY salary uses the second column (already sorted within dept 60)

Function-Based Index

A function-based index pre-computes the result of a function on a column and indexes that result. This is necessary when you query using a function on an indexed column.

-- Problem: this query cannot use a regular index on last_name
SELECT * FROM employees
WHERE UPPER(last_name) = 'KING';
-- UPPER() is applied to the column, breaking the index

-- Solution: create a function-based index on UPPER(last_name)
CREATE INDEX idx_emp_last_upper
ON employees (UPPER(last_name));

-- Now this query uses the index:
SELECT * FROM employees
WHERE UPPER(last_name) = 'KING';   -- matches the indexed expression ✓

-- Index on the month of hire_date (for monthly reports)
CREATE INDEX idx_emp_hire_month
ON employees (EXTRACT(MONTH FROM hire_date));

-- Uses the index:
SELECT * FROM employees
WHERE EXTRACT(MONTH FROM hire_date) = 3;   -- March hires

Partial / Filtered Index

A partial index (called a filtered index in SQL Server) indexes only a subset of rows — those matching a specific condition. This makes the index smaller and faster.

-- PostgreSQL: index only active employees (is_deleted = 0)
CREATE INDEX idx_active_employees
ON employees (last_name, first_name)
WHERE is_deleted = 0;

-- Oracle: partial indexes via invisible/filtered approach
-- (Oracle uses function-based or partitioned indexes for similar effect)

-- This query can use the partial index:
SELECT * FROM employees
WHERE  last_name  = 'King'
AND    is_deleted = 0;

Partial indexes are ideal for tables where most queries filter on a specific condition — like active records, unpaid invoices, or open orders.

Bitmap Index (Oracle — Low-Cardinality Columns)

A bitmap index stores a bitmap (a string of 0s and 1s) for each distinct value in a column. They're extremely efficient for columns with very few distinct values — called low-cardinality columns.

-- Good candidates for bitmap indexes:
-- gender: 'M', 'F' (2 values)
-- status: 'ACTIVE', 'INACTIVE', 'PENDING' (3 values)
-- region: 'NORTH', 'SOUTH', 'EAST', 'WEST' (4 values)

-- Oracle bitmap index syntax
CREATE BITMAP INDEX idx_emp_gender
ON employees (gender);

CREATE BITMAP INDEX idx_job_region
ON jobs (region);

How bitmaps work: If a column has the values 'ACTIVE' and 'INACTIVE', Oracle creates two bitmaps:

ACTIVE:   1 0 0 1 1 0 1 0 0 1 ...  (1 = row is ACTIVE)
INACTIVE: 0 1 1 0 0 1 0 1 1 0 ...  (1 = row is INACTIVE)

To find all ACTIVE employees in the NORTH region: bitwise AND the two bitmaps — extremely fast.

When NOT to Use Indexes

Indexes have costs. Here's when to skip them:

How the Query Planner Decides to Use an Index

The database's query planner (also called the optimizer) decides whether to use an index by estimating costs. It considers:

1. Table statistics — How many rows? How spread out are the values?
2. Selectivity — What fraction of rows does the WHERE clause return?
3. Index availability — Is there an index that matches the query?
4. Cost estimate — Is using the index actually faster than a full scan?

The optimizer may ignore your index if it estimates the query will return more than ~10-20% of rows — at that point, a full scan is often faster due to the overhead of following index pointers.

-- The optimizer uses statistics to decide
-- If salary has values from 20K to 200K and you query:
SELECT * FROM employees WHERE salary > 10000;
-- This returns almost all rows → optimizer chooses FULL SCAN

SELECT * FROM employees WHERE salary > 190000;
-- This returns very few rows → optimizer chooses INDEX SCAN

Keeping Statistics Current

-- Oracle: gather statistics so the optimizer makes good decisions
EXEC DBMS_STATS.GATHER_TABLE_STATS('HR', 'EMPLOYEES');

-- Or gather for the entire schema:
EXEC DBMS_STATS.GATHER_SCHEMA_STATS('HR');

-- PostgreSQL:
ANALYZE employees;

Covering Index — Eliminating Table Lookups

A covering index contains all the columns needed to satisfy a query — so the database never needs to touch the actual table at all. This is the fastest possible query execution.

-- Query: find name and salary for employees in department 60
SELECT first_name, last_name, salary
FROM   employees
WHERE  department_id = 60;

-- A covering index includes all columns in SELECT + WHERE:
CREATE INDEX idx_emp_dept_cover
ON employees (department_id, first_name, last_name, salary);
-- department_id → WHERE filter
-- first_name, last_name, salary → SELECT columns

-- The entire query is answered from the index; the table isn't touched

Index on Foreign Keys

Foreign key columns are extremely important to index, yet often forgotten. Without an index on the foreign key:

1. Every DELETE from the parent table requires a full scan of the child table to check for dependent rows
2. Every JOIN between parent and child tables does a full scan

-- employees.department_id references departments.department_id
-- Without an index on employees.department_id:
-- - DELETE FROM departments WHERE department_id = 60
--   requires scanning ALL employees to check for FK violation

-- Create the index:
CREATE INDEX idx_emp_department_id
ON employees (department_id);

-- Now FK checks and JOINs on department_id are fast

EXPLAIN — Verifying Index Usage

The EXPLAIN command shows you the execution plan — how the database intends to run your query. Use it to verify that your indexes are being used.

PostgreSQL EXPLAIN ANALYZE

-- EXPLAIN shows the plan; ANALYZE actually runs it and shows real times
EXPLAIN ANALYZE
SELECT first_name, last_name
FROM   employees
WHERE  last_name = 'King';

-- Sample output:
-- Index Scan using idx_emp_last_name on employees  (cost=0.14..8.16 rows=1 width=18)
--   Index Cond: ((last_name)::text = 'King'::text)
-- Planning Time: 0.5 ms
-- Execution Time: 0.1 ms

Key terms to look for:

Oracle EXPLAIN PLAN

-- Generate the execution plan (doesn't run the query)
EXPLAIN PLAN FOR
SELECT first_name, last_name
FROM   employees
WHERE  last_name = 'King';

-- View the plan:
SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY);

-- Sample output:
-- PLAN_TABLE_OUTPUT
-- -----------------------------------------------------------------
-- Plan hash value: 1234567890
-- -----------------------------------------------------------------
-- | Id | Operation                   | Name              | Rows |
-- -----------------------------------------------------------------
-- |  0 | SELECT STATEMENT            |                   |    1 |
-- |  1 |  TABLE ACCESS BY INDEX ROWID| EMPLOYEES         |    1 |
-- |* 2 |   INDEX RANGE SCAN          | IDX_EMP_LAST_NAME |    1 |
-- -----------------------------------------------------------------

Common Index Mistakes

Mistake 1: Using a Function on an Indexed Column

-- Index on last_name EXISTS, but this query won't use it:
SELECT * FROM employees WHERE UPPER(last_name) = 'KING';
--                                  ^^^^^^
-- The function wrapping the column breaks the index

-- Fix option 1: function-based index
CREATE INDEX idx_emp_last_upper ON employees (UPPER(last_name));

-- Fix option 2: store data consistently (all uppercase) and query without function
SELECT * FROM employees WHERE last_name = 'KING';  -- if data stored as 'KING'

Mistake 2: Implicit Type Conversion

-- employee_id is NUMBER, but you pass a VARCHAR2
SELECT * FROM employees WHERE employee_id = '107';
--                                          ^^^^^ string
-- Oracle implicitly converts: TO_NUMBER('107')
-- This may or may not break the index depending on data type

-- Always match the data type of the column:
SELECT * FROM employees WHERE employee_id = 107;   -- NUMBER literal ✓

Mistake 3: Leading Wildcard in LIKE

-- Index on last_name, but leading wildcard makes it useless:
SELECT * FROM employees WHERE last_name LIKE '%ing';
--                                           ^
-- The % at the start means "any prefix" — can't use a sorted index

-- Trailing wildcard is fine (searches from the left):
SELECT * FROM employees WHERE last_name LIKE 'K%';   -- uses index ✓

-- For full-text search needs, use a full-text index instead

Mistake 4: OR on Different Indexed Columns

-- This may not efficiently use either index:
SELECT * FROM employees
WHERE  last_name = 'King'
OR     first_name = 'Steven';

-- Better: UNION (each branch can use its own index)
SELECT * FROM employees WHERE last_name = 'King'
UNION
SELECT * FROM employees WHERE first_name = 'Steven';

Index Summary

-- Quick reference: common index creation patterns

-- Standard B-Tree (most common)
CREATE INDEX idx_orders_customer ON orders (customer_id);

-- Unique (enforces no duplicates)
CREATE UNIQUE INDEX idx_emp_email ON employees (email);

-- Composite (column order matters — most selective first)
CREATE INDEX idx_orders_date_status ON orders (order_date, status);

-- Function-based (for queries with functions in WHERE)
CREATE INDEX idx_emp_lower_email ON employees (LOWER(email));

-- Covering (includes all SELECT columns to avoid table access)
CREATE INDEX idx_emp_dept_covering
ON employees (department_id, first_name, last_name, salary);

-- Bitmap (Oracle only — for low-cardinality columns in DW)
CREATE BITMAP INDEX idx_emp_status ON employees (status);

Common Errors

Interview Corner

-- Composite (emp_dept_sal) covers:
WHERE department_id = 10                          -- leading column
WHERE department_id = 10 AND salary > 5000        -- both columns
-- NOT efficiently: WHERE salary > 5000 only      -- skip-scan may or may not apply

Related Topics

• Performance — broad query tuning: statistics, hints, execution plan analysis
• Explain Plan — reading TABLE ACCESS FULL vs INDEX RANGE SCAN in execution plans
• DDL Commands — CREATE INDEX, ALTER INDEX REBUILD, index storage options
• Partitioning — local vs global indexes on partitioned tables