SQL & Databases Indexing and Query Optimization Syllabus

Indexing and Query Optimization syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Indexing and Query Optimization in SQL & Databases, not a summary of it.

1. 1

   Index Fundamentals

   4 topics

   • How Indexes Work
   • Clustered vs Non-Clustered Indexes
   • Composite Indexes and Column Order
   • Covering Indexes and Included Columns
2. 2

   Specialized Index Types

   5 topics

   • Hash Indexes
   • GIN and GiST Indexes
   • Partial and Filtered Indexes
   • Expression and Functional Indexes
   • Full-Text Search Indexes
3. 3

   Query Execution and Planning

   5 topics

   • Reading EXPLAIN / EXPLAIN ANALYZE
   • Scan Types
   • Join Algorithms
   • The Query Optimizer and Cost Model
   • Table Statistics and Cardinality Estimation
4. 4

   Performance Tuning

   5 topics

   • Identifying Slow Queries
   • Avoiding Common Pitfalls
   • Query Rewriting Techniques
   • Connection Pooling and Caching
   • Index Maintenance and Bloat

Indexing and Query Optimization flashcards for SQL & Databases

24 of 50 cards from the Indexing and Query Optimization deck — real questions with worked answers.

1. What is a database index, and what is its fundamental trade-off?

   An index is an auxiliary data structure (usually a B-tree) that stores a sorted copy of one or more column values plus pointers to the corresponding table rows, enabling fast lookups. The trade-off: it speeds up reads (SELECT/WHERE/JOIN/ORDER BY) but slows down writes (INSERT/UPDATE/DELETE) and consumes extra disk space, since every write must also maintain the index.

2. What data structure underlies most default relational indexes, and what is its lookup time complexity?

   A balanced B-tree (specifically a B+ tree in most engines). Lookup, insertion, and deletion are all $O(\log n)$, because the tree stays balanced and its height grows logarithmically with the number of rows.

3. In a B+ tree index, where are the actual data pointers stored, and how does this help range scans?

   All keys (and their row pointers) live in the leaf nodes; internal nodes hold only separator keys for navigation. The leaf nodes are linked in a sorted doubly-linked list, so a range scan finds the start key in $O(\log n)$ then walks the leaf chain sequentially without re-traversing the tree.

4. What is a clustered index and how many can a table have?

   A clustered index determines the physical storage order of the table's rows — the leaf level of the index IS the table data. A table can have at most one clustered index, because rows can only be physically sorted one way.

5. What is a non-clustered (secondary) index and how does it locate a row?

   A non-clustered index is a separate structure whose leaf nodes store the key values plus a pointer to the actual row. That pointer is either a physical row identifier (heap RID) or, when a clustered index exists, the clustered-index key, requiring a second lookup (a 'key lookup' / 'bookmark lookup') to fetch non-indexed columns.

6. In PostgreSQL, how do table storage and indexes differ from SQL Server's clustered-index model?

   PostgreSQL stores tables as unordered heaps — it has no true clustered index. All PostgreSQL indexes are secondary and point into the heap via a tuple identifier (ctid). The CLUSTER command physically reorders a heap by an index once, but the ordering is not maintained afterward.

7. What is a composite (multi-column) index, and why does column order matter?

   A composite index indexes several columns together as an ordered tuple, e.g. $(a, b, c)$. Order matters because the index is sorted by the leftmost column first, then the next, etc. It can efficiently serve queries that filter on a leftmost prefix of the columns but not on non-prefix columns alone.

8. State the leftmost-prefix rule for a composite index on $(a, b, c)$. Which queries can use it?

   An index on $(a,b,c)$ supports predicates on the prefixes: $a$; $a,b$; and $a,b,c$. It cannot efficiently serve a query filtering only on $b$, only on $c$, or on $b,c$ without $a$, because those are not leftmost prefixes of the sort order.

9. For a composite index, how should you generally order columns with respect to equality vs. range predicates?

   Put equality-predicate columns first and the range/inequality column last. Once a range (>, <, BETWEEN) is applied to a column, the columns after it in the index can no longer be used for further seeking, only for filtering, so a trailing range column preserves index usefulness.

10. What is a covering index?

    An index that contains all columns a query needs (in both its SELECT and WHERE clauses), so the query can be answered entirely from the index without accessing the table. This is called an 'index-only scan' and avoids the extra table/heap lookups.

11. What are INCLUDE (included/non-key) columns in a covering index, and how do they differ from key columns?

    INCLUDE columns are stored only in the index's leaf level, not in the internal B-tree nodes. They are not part of the sort key (cannot be seeked or used for ordering) but are available to make an index covering. This keeps the tree smaller than adding them as key columns while still avoiding table lookups.

12. What is a hash index and what operations does it support?

    A hash index stores keys via a hash function into buckets, giving average $O(1)$ lookup for exact-match equality (=) queries. It does NOT support range queries, ordering, or leftmost-prefix matching because hashing destroys sort order.

13. When would a hash index outperform a B-tree, and what is a key limitation in PostgreSQL historically?

    Hash indexes can beat B-trees for pure equality lookups on large, non-ordered keys with $O(1)$ average lookup vs $O(\log n)$. Limitation: they only handle the = operator (no <, >, BETWEEN, ORDER BY, sorting). In PostgreSQL, hash indexes were not crash-safe / WAL-logged until version 10.

14. What is a GIN index and what is it designed for?

    GIN (Generalized Inverted Index) is designed for composite values where a single row maps to many keys — e.g. array elements, JSONB keys, and full-text search lexemes. It stores an inverted mapping from each element to the list of rows containing it, making 'contains' (@>, ?, full-text @@) queries fast.

15. What is a GiST index and how does it differ from GIN?

    GiST (Generalized Search Tree) is a balanced-tree framework for lossy, extensible indexing supporting operators like overlap, nearest-neighbor, and geometric/range containment (used by PostGIS, range types, exclusion constraints). Compared to GIN: GiST is faster to build/update and better for geometric and nearest-neighbor searches, while GIN is faster to search but slower to update, and is preferred for static full-text/array/JSONB data.

16. Give the rule of thumb for choosing GIN vs. GiST for full-text search in PostgreSQL.

    Use GIN when the data is relatively static and search speed matters most (GIN lookups are ~3x faster but the index is larger and slower to build/update). Use GiST when the table has frequent updates/inserts, since GiST is cheaper to maintain, at the cost of slower, sometimes lossy searches that require rechecking.

17. What is a partial (filtered) index and why use one?

    A partial index (PostgreSQL: WHERE clause; SQL Server: 'filtered index') indexes only the subset of rows satisfying a predicate, e.g. CREATE INDEX ... WHERE status = 'active'. Benefits: smaller index, less maintenance overhead, and it can index only the 'interesting' minority of rows (e.g. non-null, or unprocessed records).

18. Give a classic use case where a partial index dramatically saves space.

    Indexing a boolean/status flag with a heavy skew — e.g. a large orders table where only 0.1% of rows have status = 'pending'. A partial index WHERE status='pending' indexes just those few rows, so queries for pending orders are fast while the index stays tiny, versus a full index on millions of mostly-irrelevant rows.

19. What is an expression (functional) index, and what problem does it solve?

    An index built on the result of an expression or function rather than a raw column, e.g. CREATE INDEX ON users (LOWER(email)). It solves the problem that a predicate like WHERE LOWER(email)='x' cannot use a plain index on email; the optimizer can use the functional index only when the query's expression matches the indexed expression exactly.

20. Why does WHERE YEAR(order_date) = 2024 typically fail to use an index on order_date, and how do you fix it?

    Wrapping the column in a function makes the predicate non-sargable — the optimizer can't seek a plain B-tree on order_date because it's indexed by raw value, not by YEAR(). Fixes: (1) rewrite as a range, WHERE order_date >= '2024-01-01' AND order_date < '2025-01-01'; or (2) create an expression index on YEAR(order_date).

21. What does 'sargable' mean?

    Sargable (Search ARGument ABLE) describes a predicate that can use an index seek. A predicate is sargable when the indexed column is isolated on one side of the comparison and not wrapped in a function or expression, e.g. col = 5 is sargable but col + 1 = 6 or FUNC(col) = x generally is not.

22. How does full-text search indexing differ from a normal B-tree LIKE search?

    Full-text search tokenizes text into normalized lexemes (stemming, stop-word removal) and stores an inverted index mapping each lexeme to documents, enabling fast relevance-ranked word/phrase searches. A B-tree can only anchor a leading prefix (LIKE 'abc%'); it cannot efficiently do LIKE '%word%' or linguistic matching, which full-text indexes handle.

23. In PostgreSQL full-text search, what are tsvector and tsquery?

    A tsvector is a preprocessed document: a sorted list of distinct normalized lexemes with their positions. A tsquery is a search query of lexemes combined with boolean operators (& AND, | OR, ! NOT, <-> followed-by). Matching is done with the @@ operator: tsvector @@ tsquery, and is accelerated by a GIN or GiST index on the tsvector.

24. What does the SQL EXPLAIN command produce, and how does EXPLAIN ANALYZE differ?

    EXPLAIN shows the optimizer's chosen execution plan with estimated costs, row counts, and access methods — without running the query. EXPLAIN ANALYZE actually executes the query and adds real runtime measurements (actual time, actual rows, loops, buffers), letting you compare estimates against reality.

See more Indexing and Query Optimization flashcards →

Planning Indexing and Query Optimization for SQL & Databases

Indexing and Query Optimization (SQL & Databases) FAQ