SQL Indexing & Query Optimization Techniques Flashcards

Question 1

B-Tree Index

Accepted Answer

A self-balancing search tree structure that maintains sorted data to enable logarithmic time complexity ($O(\log n)$) for searches, sequential access, insertions, and deletions. It is the default index type in most relational database management systems (RDBMS).

Question 2

Clustered Index vs. Non-Clustered Index

Accepted Answer

**Clustered Index**: Determines the physical storage order of data inside the table. A table can have only *one* clustered index (usually the Primary Key).

**Non-Clustered Index**: A separate structure containing sorted keys and pointers (Row IDs or clustered keys) back to the actual data rows. A table can have multiple non-clustered indexes.

Question 3

Composite Index & Leftmost Prefix Rule

Accepted Answer

An index created on multiple columns (e.g., `(A, B, C)`). It follows the **Leftmost Prefix Rule**, meaning queries can utilize the index if filtering by `A`, `(A, B)`, or `(A, B, C)`, but *not* by `B` or `C` alone without `A`.

Question 4

Covering Index

Accepted Answer

An index that contains all the columns requested by a query (in `SELECT`, `WHERE`, `JOIN`, and `ORDER BY` clauses). Because all required data resides inside the index itself, the database avoids costly physical table lookups (key lookups).

Question 5

Include Columns (`INCLUDE` clause)

Accepted Answer

A mechanism to add non-key payload columns to the leaf nodes of a non-clustered index without increasing the size of the B-tree search keys.

Example:
```sql
CREATE INDEX idx_user_status 
ON users (status) 
INCLUDE (email, name);
```

Question 6

Query Execution Plan

Accepted Answer

A sequence of operations generated by the database optimizer detailing how a query will be executed. It reveals operational steps such as Index Seeks, Table Scans, Join algorithms, and sorting costs.

Question 7

`EXPLAIN` vs. `EXPLAIN ANALYZE`

Accepted Answer

- **`EXPLAIN`**: Generates and displays the estimated execution plan based on table statistics without running the query.
- **`EXPLAIN ANALYZE`**: Actually executes the query, returning execution times, actual row counts, memory usage, and structural plan details.

Question 8

Table Scan vs. Index Scan vs. Index Seek

Accepted Answer

- **Table Scan**: Reads every data page in the entire table ($O(n)$).
- **Index Scan**: Reads through all leaf pages of an index ($O(n)$).
- **Index Seek**: Uses the B-tree structure to jump directly to specific matching rows ($O(\log n)$).

Question 9

Nested Loop Join

Accepted Answer

A join algorithm where the database iterates through an outer loop table and searches for matching rows in an inner table for each iteration. Most efficient when the outer dataset is small and the inner dataset is indexed on the join key.

Question 10

Hash Join

Accepted Answer

A join algorithm that builds an in-memory hash table from the smaller input and probes it with rows from the larger input. Ideal for joining large, unindexed datasets.

Question 11

Merge Join (Sort-Merge Join)

Accepted Answer

A join algorithm that reads two input datasets sorted on the join key sequentially and merges matching rows ($O(n + m)$). Extremely fast when inputs are already sorted via an index.

Question 12

SARGable Queries (Search Argument Able)

Accepted Answer

A query is **SARGable** if the engine can leverage an index seek to evaluate predicates. Wrapping indexed columns in functions (e.g., `WHERE YEAR(created_at) = 2023`) makes queries **non-SARGable**, forcing full scans.

Question 13

Anti-Pattern: Function on Indexed Column

Accepted Answer

**Bad (Non-SARGable)**:
```sql
SELECT * FROM orders WHERE UPPER(status) = 'PENDING';
```

**Good (SARGable)**:
```sql
SELECT * FROM orders WHERE status = 'PENDING'; -- assuming canonical storage
```

Question 14

Anti-Pattern: Leading Wildcards in `LIKE`

Accepted Answer

Queries containing `LIKE '%value'` cannot perform an Index Seek because the prefix is unknown, causing a full table or index scan. `LIKE 'value%'` allows an Index Seek.

Question 15

Implicit Data Type Conversion Anti-Pattern

Accepted Answer

Occurs when a query compares an indexed column to a parameter of a different data type (e.g., comparing a `VARCHAR` column to an integer literal `123`). The database implicitly wraps the column in a conversion function, invalidating index seeking.

Question 16

Subquery Optimization: `EXISTS` vs. `IN`

Accepted Answer

`EXISTS` short-circuits as soon as a single matching row is found, returning a boolean. `IN` gathers all values from the subquery into memory first. While modern optimizers often rewrite `IN` to semi-joins, `EXISTS` is generally safer for large subquery result sets.

Question 17

Database Statistics

Accepted Answer

Metadata stored by the database regarding table size, row counts, and data distribution (histograms). The Query Optimizer relies on up-to-date statistics to estimate cost and select optimal execution strategies.

Question 18

Partial / Filtered Index

Accepted Answer

An index that includes only a subset of table rows using a `WHERE` condition.

Example:
```sql
CREATE INDEX idx_unprocessed_orders 
ON orders (created_at) 
WHERE status = 'UNPROCESSED';
```
Reduces index storage and speeds up targeted queries.

Question 19

Index Fragmentation & Maintenance

Accepted Answer

Over time, frequent `INSERT`, `UPDATE`, and `DELETE` queries lead to fragmented pages and logical ordering mismatches. Maintenance involves running `REBUILD` or `REORGANIZE` commands to restore sequential I/O layout.

Question 20

Interpreting `EXPLAIN ANALYZE` Output Example

Accepted Answer

Example PostgreSQL output:
```sql
Index Scan using idx_users_email on users (cost=0.28..8.30 rows=1 width=32) (actual time=0.015..0.017 rows=1 loops=1)
```
- `cost=0.28..8.30`: Estimated startup and total cost units.
- `rows=1`: Expected vs. actual returned row count.
- `actual time`: Execution time in milliseconds.

SQL Indexing & Query Optimization Techniques

Card Preview

Related Flashcard Sets

German B1 - Intermediate Vocabulary & Grammar

Classical Mechanics - Newton's Laws & Conservation Principles

CFA Level 1 - Equity & Fixed Income Investments

Stanford CS106A - Python Programming Methodology