SQL Indexes

The Search Problem: Finding Information Quickly

• Scenario: Imagine searching for a specific word or topic in a 1000-page textbook.
• Without an index: You'd have to scan every page sequentially – very time-consuming.
• With an index: You look up the term in the index at the back, get the page number(s), and jump directly there – much faster.
• Connection: Database queries face a similar challenge when retrieving specific data from large tables.

Database Query Performance

• We execute SELECT statements to retrieve data from potentially very large tables.
• Problem: Without optimization, querying large tables (millions/billions of rows) can be extremely slow, impacting application responsiveness.
• Question: How do database management systems (DBMS) speed up this data retrieval process?
• A Key Solution: Database Indexes.

Today's Learning Objectives

• By the end of this lecture, you will be able to:
• Define what a database index is and its purpose.
• Explain why indexes improve query performance.
• Identify common index types in PostgreSQL (B-Tree, Hash, GIN, GiST, BRIN).
• Understand the basic SQL syntax for creating and dropping indexes.
• Analyze the trade-offs associated with using indexes.
• Briefly explain how the query planner uses indexes (using EXPLAIN).

What is a Database Index?

• Definition: A separate, specialized data structure (often a tree or hash map) associated with a table or view.
• Stores a subset of the table's data (the indexed column(s)) in a structured/sorted manner.
• Contains pointers back to the corresponding full rows in the main table (heap).
• Purpose: To speed up data retrieval operations (primarily SELECT queries) by providing faster lookup paths.

Index Analogies

• Think of indexes like familiar real-world examples:
• Book Index: Quickly find pages containing specific keywords.
• Library Card Catalog: Locate books by title, author, or subject without searching every shelf.
• Phone Book Index: Find a person's number by their last name without reading every entry.
• All these allow direct access to information, bypassing a full sequential scan.

Querying Without an Index: Full Table Scan

• Consider a large users table and the query:

SELECT user_id, email

FROM users

WHERE registration_date = '2023-10-26';

• Problem: If there's no index on registration_date, the database has no optimized way to find matching rows.
• Process (Full Table Scan / Sequential Scan in PostgreSQL):
• The database must read the first row, check the date.
• Read the second row, check the date.
• ...continue for every single row in the table.

The Inefficiency of Full Table Scans

• High I/O Cost: Reading every row from disk (or memory) is input/output intensive. Disk I/O is typically the slowest part of database operations.
• Scalability Issues: Performance degrades linearly (or worse) as the table size increases.
• Unacceptable Latency: For tables with millions or billions of rows, a full table scan can take minutes or even hours, making applications unresponsive.

Querying With an Index: Index Scan / Lookup

• Now, assume an index exists on registration_date.
• Query:

SELECT user_id, email

FROM users

WHERE registration_date = '2023-10-26';

• Process (Using the Index):
1. The database efficiently searches the index structure (e.g., a B-Tree) for the value '2023-10-26'.
2. The index entry provides the direct address(es) of the matching row(s) in the main table.
3. The database uses these addresses to fetch only the required rows directly.

Why Use Indexes? Key Benefits

• Faster Data Retrieval: Significantly speeds up SELECT queries, especially those involving:
• WHERE clauses (filtering rows).
• JOIN conditions (matching rows between tables).
• ORDER BY clauses (sorting results).
• MIN() / MAX() aggregate functions.
• Reduced I/O Operations: Avoids reading unnecessary data blocks from disk.
• Improved Application Performance: Faster queries lead to more responsive applications and better user experience.

How Indexes Work: The Core Idea

• Core Idea: Store the indexed column value(s) along with a pointer to the original row in a structure designed for efficient searching.
• Instead of scanning N table rows, the database searches the smaller, optimized index structure.
• The most common index structure used by default in PostgreSQL (and many other relational databases) is the B-Tree.

The B-Tree Index: PostgreSQL's Default

• B-Tree: A self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time complexity (O(log n)).
• Balanced: The tree automatically adjusts its structure during insertions/deletions to ensure the distance from the root node to any leaf node remains roughly the same. This guarantees consistently efficient search performance.
• Think of it as a multi-level index, like chapters, sections, and paragraphs in a book.

B-Tree Structure

• Nodes: The tree is composed of nodes (pages/blocks).
• Root Node: The top-level entry point.
• Internal Nodes: Contain separator keys and pointers to child nodes. These guide the search. (e.g., "Keys < 50 go left, Keys >= 50 go right").
• Leaf Nodes: Contain the actual indexed values (e.g., specific registration_date values) and pointers (TIDs/CTIDs in PostgreSQL) to the physical location of the corresponding rows in the main table (heap). Leaf nodes are typically linked sequentially.

Searching a B-Tree

• Process: To find a specific value (e.g., registration_date = '2023-10-26'):
1. Start at the Root Node.
2. Compare the search value with keys in the node to determine which child node to follow.
3. Descend down the tree, repeating the comparison at each Internal Node.
4. Reach a Leaf Node containing the indexed value (or the range where it would be).
5. Retrieve the associated TID(s) and fetch the actual table row(s).
• Efficiency: This traversal is very fast due to the balanced structure – logarithmic complexity (O(log n)). Finding one item among a billion takes roughly twice as many steps as finding one among a million.

B-Tree Strengths

• B-Trees are the default index type in PostgreSQL because they are highly versatile and efficient for many common query types:
• Equality: = (e.g., WHERE user_id = 123)
• Range Queries: <, >, <=, >=, BETWEEN (e.g., WHERE price BETWEEN 10 AND 50)
• Sorting: ORDER BY indexed_column (data is already sorted in leaf nodes)
• Pattern Matching (Prefix): LIKE 'prefix%' (e.g., WHERE email LIKE 'test@%')
• Minimum/Maximum: MIN(indexed_column), MAX(indexed_column) (easily found at the start/end of the leaf node chain)

Beyond B-Trees: Index Types in PostgreSQL

• PostgreSQL offers multiple index access methods, specified using the USING clause in CREATE INDEX.
• Different index types are optimized for different data types and query patterns.
• Choosing the right index type is crucial for maximizing query performance.
• We will cover the most common types: B-Tree, Hash, GIN, GiST, and BRIN.

Index Type: B-Tree

• Method: USING btree (or omit USING, as it's the default).
• Structure: Balanced tree.
• Best For: General-purpose indexing. Handles equality (=), range queries (<, >, BETWEEN), ORDER BY, LIKE 'prefix%', MIN/MAX.
• Use Case: The standard choice for most scalar data types (integers, text, dates, etc.) when dealing with typical comparison operators.

Index Type: Hash

• Method: USING hash
• Structure: Uses an on-disk hash table. Each bucket points to rows with that hash value.
• Supported Operation: Only equality (=). Cannot efficiently handle range queries or sorting.
• Performance: Theoretically faster than B-Tree for pure equality lookups (O(1) average case, assuming good hash distribution).
• Use Case: Primarily for scenarios demanding the absolute fastest equality lookups where no other operations (range, sort) are needed on the indexed column. B-Tree often remains the practical choice.

Index Type: GIN �(Generalized Inverted Index)

• Method: USING gin
• Structure: An "inverted index". Suitable for indexing composite values (values containing multiple components, like elements in an array or keys in JSON). It maps individual components back to the rows they appear in.
• Best For: Checking if a specific item exists within a composite value.
• Use Cases:
• Searching elements within arrays
• Querying keys/values within JSONB
• Full-text search

Index Type: GiST (Generalized Search Tree)

• Method: USING gist
• Structure: A template framework for building various balanced tree structures beyond simple B-Trees. More complex internally.
• Best For: Indexing complex data types and implementing non-standard search predicates (like overlap, containment, nearest neighbor).
• Use Cases:
• Geospatial data: Finding overlapping polygons, points within a radius.
• Full-text search (can also be used, though GIN is often preferred).
• Some types of range types and geometric primitives.

Index Type: BRIN (Block Range Index)

• Method: USING brin
• Structure: Stores summary information (e.g., min/max values) for ranges of physical table blocks ("block ranges"). Does not index individual rows directly.
• Effectiveness Condition: Highly effective only when the indexed column's values have a strong physical correlation with the row storage order (e.g., an INSERT-only table with an auto-incrementing ID or an event timestamp).
• Use Case: Querying very large, naturally ordered tables to quickly skip large numbers of irrelevant blocks. Less useful for precise lookups.

Other Indexing Concepts (1/4): �Multi-Column Indexes

• Index multiple columns together:

​

​

• Order Matters: An index on (col1, col2) is different from (col2, col1).
• Use Case: Speeds up queries that filter, sort, or group by the leading columns of the index. A query filtering only on city will not effectively use the (country, city) index, but one filtering on country or country and city can.

Other Indexing Concepts (2/4): �Unique Indexes

• Enforces a uniqueness constraint on the indexed column(s). Prevents duplicate values.
• Provides the performance benefits of an index and guarantees data integrity.
• Created via:

CREATE UNIQUE INDEX idx_users_email ON users (email);

-- Or often implicitly via constraints:

ALTER TABLE users ADD CONSTRAINT users_email_unique UNIQUE (email); -- Uses a unique index behind the scenes

Other Indexing Concepts (3/4): Partial Indexes

• Index only a subset of table rows that satisfy a WHERE clause.

CREATE INDEX idx_orders_pending

ON orders (order_id)

WHERE status = 'pending';

• Benefits:
• Smaller index size.
• Reduced index maintenance overhead.
• Use Case: Target specific, frequent queries that operate on a predictable subset of data (e.g., indexing only active users, open orders).

Other Indexing Concepts (4/4): Expression Indexes

• Index the result of a function or expression applied to one or more columns. Also known as Functional Indexes.

-- Index case-insensitive email lookups

CREATE INDEX idx_users_email_lower

ON users (lower(email));

• Use Case: Speed up queries that frequently use functions in the WHERE clause. The query must use the exact same expression.

-- This query CAN use the index:

SELECT * FROM users WHERE lower(email) = 'test@example.com';

Index Management: Creating Indexes

• The fundamental command to create an index:

CREATE INDEX [index_name]

ON table_name [ USING method ] ( column1 [, column2, ...] )

[ WHERE predicate ]; -- For Partial Indexes

• index_name: Choose a descriptive name (e.g., idx_tablename_columnname).
• table_name: The table to index.
• USING method: Optional. Specifies index type (e.g., btree, hash, gin, gist, brin). Defaults to btree.
• (column1, ...): The column(s) or expression(s) to index.
• WHERE predicate: Optional. For creating partial indexes.

Creating Indexes: Examples

• Standard B-Tree Index (Default):

CREATE INDEX idx_users_email ON users (email);

-- Equivalent to: CREATE INDEX idx_users_email ON users USING btree (email);

• GIN Index (for Array Column):

-- Assuming 'tags' is an array type column (e.g., TEXT[])

CREATE INDEX idx_posts_tags ON posts USING GIN (tags);

• Partial Index (B-Tree):

CREATE INDEX idx_orders_pending ON orders (order_id)

WHERE status = 'pending';

Index Management: Dropping Indexes

• To remove an existing index:

DROP INDEX [IF EXISTS] index_name;

• index_name: The name of the index to remove.
• IF EXISTS: Optional clause to prevent an error if the index doesn't exist.
• Example:

DROP INDEX idx_users_email;

• Dropping an index removes the index structure and frees the associated disk space. The table data remains untouched.

Index Management: Viewing Existing Indexes

• How to see which indexes exist on a table:
• 1. Using PSQL: The \d command describes a table, including its indexes.

\d users

• (Output will show table columns, constraints, and associated indexes at the bottom)
• 2. Querying System Catalogs: PostgreSQL stores metadata in system tables/views.

SELECT indexname, indexdef

FROM pg_indexes

WHERE tablename = 'users';

Index Usage: The Query Planner

• You create indexes, but the database decides when to use them.
• Query Planner (or Optimizer): A core component of the DBMS.
• Role: Analyzes an SQL query and determines the most efficient execution plan to retrieve the requested data.
• Decision Factors: Considers available indexes, table statistics (size, data distribution), query structure, costs of different access paths (full scan vs. index scan), etc.
• Goal: Minimize the estimated total cost (usually related to I/O and CPU time). An index will only be used if the planner estimates it will be faster than a full table scan.

Verifying Index Usage: �The EXPLAIN Command

• How do you know if the planner is using your index? Use EXPLAIN.
• Prepend EXPLAIN to your SELECT, INSERT, UPDATE, or DELETE statement. It doesn't execute the query, but shows the planned execution strategy.
• Syntax:

EXPLAIN [ANALYZE] SELECT columns

FROM table_name

WHERE condition;

• ANALYZE (optional): Executes the query and shows actual timings and row counts alongside the plan estimates. Use with caution on production systems or long-running queries.

EXPLAIN Output: Seq Scan vs. Index Scan

• Scenario 1: No suitable index or index deemed too costly

​

EXPLAIN SELECT * FROM users WHERE registration_date = '2023-10-26’;

​

• Sample Output (Simplified):

​

QUERY PLAN

-------------------------------------------------------------

Seq Scan on users (cost=0.00..5000.00 rows=10 width=120)

Filter: (registration_date = '2023-10-26'::date)

​

(Seq Scan = Sequential Scan = Full Table Scan)

EXPLAIN Output: Seq Scan vs. Index Scan

• Scenario 2: Index on registration_date exists and is used
• Sample Output (Simplified - may vary):

​

QUERY PLAN

--------------------------------------------------------------------------

Index Scan using idx_users_reg_date on users (cost=0.40..8.42 rows=10 width=120)

Index Cond: (registration_date = '2023-10-26'::date)

-- OR sometimes:

Bitmap Heap Scan on users (cost=4.50..100.50 rows=10 width=120)

Recheck Cond: (registration_date = '2023-10-26'::date)

-> Bitmap Index Scan on idx_users_reg_date (cost=0.00..4.49 rows=10 width=0)

Index Cond: (registration_date = '2023-10-26'::date)

​

• (Index Scan or Bitmap Index Scan/Bitmap Heap Scan indicates the index is being used.)

The Costs of Indexing: No Free Lunch

• While indexes significantly speed up data retrieval (SELECT), they introduce overheads.
• Indexes are not "free" – they come with trade-offs that must be considered.
• Key costs include:
• Write Performance Penalty
• Disk Storage Space Consumption
• Maintenance Overhead

Trade-off 1: Write Performance Penalty

• Operations that modify data become slower:
• INSERT: New entries must be added to the table and to each relevant index.
• UPDATE: If an indexed column is updated, the index entry must be updated (often involving deleting the old entry and inserting a new one).
• DELETE: Entries must be removed from the table and from each index.
• Impact: Each index adds extra work to write operations. Having too many indexes on a table can severely degrade INSERT, UPDATE, and DELETE performance, especially on write-heavy workloads.

Trade-off 2: Storage Space

• Indexes are physical data structures stored on disk (or in memory).
• They consume storage space, separate from the table data itself.
• The size of an index depends on:
• The index type (e.g., BRIN is small, B-Tree is moderate, GIN can be large).
• The width of the indexed column(s).
• The number of rows in the table.
• On very large tables, indexes can consume a significant amount of disk space.

Trade-off 3: Maintenance Overhead

• Indexes require ongoing maintenance to remain efficient.
• Fragmentation: Over time, as data is inserted, updated, and deleted, indexes can become fragmented or "bloated," potentially reducing their effectiveness.
• Database Administration: Standard database maintenance tasks help keep indexes healthy:
• REINDEX: Rebuilds an index from scratch, removing bloat and restoring optimal structure (can be resource-intensive).

Indexing Strategy: Key Considerations

• Index columns frequently used in:
• WHERE clauses (for filtering)
• JOIN conditions (ON clauses)
• ORDER BY clauses (for sorting)
• Prioritize indexing on large tables where full scans are particularly expensive.
• Avoid indexing:
• Columns that are rarely or never queried.
• Columns with very low cardinality (few distinct values, e.g., a boolean is_active flag or a gender column with 2-3 values). A standard B-Tree index is often ineffective here; a full table scan might be faster.
• Balance: Carefully weigh the SELECT performance gains against the write performance costs and storage implications. Don't just index everything!

Lecture Summary: SQL Indexes

• Crucial Performance Tools: Indexes are essential for efficient data retrieval in databases.
• Mechanism: Provide optimized lookup paths (e.g., B-Trees) to quickly locate rows, avoiding costly full table scans (Sequential Scans).
• PostgreSQL Index Types: Offers various types (B-Tree, Hash, GIN, GiST, BRIN) tailored for different data types and query patterns.
• Trade-offs: Indexes accelerate SELECT queries but slow down write operations (INSERT, UPDATE, DELETE) and consume disk space.
• Verification: Use the EXPLAIN command to analyze the query plan and confirm if indexes are being used effectively.