SQL & Databases Indexing and Query Optimization Syllabus

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.

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.

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.

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.

In a PostgreSQL EXPLAIN plan, what do the two cost numbers in 'cost=0.00..25.00' mean?

The first number is the estimated startup cost (work before the first row can be returned), and the second is the estimated total cost to return all rows. Costs are in arbitrary units where 1.0 traditionally equals one sequential page fetch (seq_page_cost).

When reading EXPLAIN ANALYZE, what is the biggest red flag to look for?

A large discrepancy between estimated rows and actual rows (e.g. estimated 10, actual 1,000,000). Bad row estimates cascade into poor plan choices (wrong join algorithm/order). Also watch for unexpected sequential scans on large tables, high 'loops' counts on nested loops, and rows removed by filter.

What is a sequential (full table) scan and when is it actually the optimal choice?

A sequential scan reads every row/page of a table in storage order, cost $O(n)$. It is optimal when the query returns a large fraction of the table (roughly above 5-20%), because sequential I/O is cheaper per row than the random I/O of many index lookups, or when the table is tiny.

Contrast an index seek (index scan with condition) versus an index scan / index-only scan.

An index seek/scan uses the index B-tree to jump to qualifying rows via the sort order, then usually fetches full rows from the table (random I/O). An index-only scan answers the query entirely from a covering index with no table access. A full index scan reads the whole index (useful when the index covers and is smaller than the table).

What is a bitmap index scan in PostgreSQL and when is it used?

A bitmap index scan builds an in-memory bitmap of matching row locations from one or more indexes, optionally combining multiple indexes with AND/OR, then fetches the rows in physical (heap) order via a bitmap heap scan. It's chosen for a medium selectivity result — too many rows for individual random index lookups but too few for a full seq scan — because sorting accesses by heap page reduces random I/O.

Name the three classic join algorithms and their typical cost characteristics.

Nested Loop Join: for each outer row, probe inner (best when outer is small and inner is indexed), cost ~$O(n \times m)$ or $O(n \log m)$ with an index. Hash Join: build a hash table on the smaller input, probe with the larger (best for large, unsorted, equality joins), cost ~$O(n + m)$. Merge Join: sort both inputs then merge in one pass (best when inputs are already sorted), cost ~$O(n \log n + m \log m)$ or $O(n+m)$ if pre-sorted.

When does the optimizer prefer a nested loop join over a hash join?

When the outer (driving) input is small and there is an index on the inner table's join column, so each of the few outer rows triggers a cheap indexed lookup. Nested loops become disastrous when both inputs are large, giving quadratic behavior; hash join is preferred there.

Why can a hash join only be used for equijoins, but a merge join and nested loop can handle other conditions?

A hash join partitions rows by a hash of the join key and can only match rows that hash equal, so it requires an equality (=) join condition. Merge join relies on sorted order and works for equality (and some range/inequality) conditions; nested loop can evaluate any arbitrary join predicate since it directly tests each pair.

What is a query optimizer, and is SQL's typical optimizer rule-based or cost-based?

The query optimizer is the component that transforms a declarative SQL query into an efficient physical execution plan by exploring alternatives (join orders, access methods, algorithms). Modern optimizers (PostgreSQL, SQL Server, Oracle) are cost-based: they estimate a numeric cost for candidate plans using statistics and pick the cheapest, rather than following fixed syntactic rules.

What inputs does a cost model use to estimate the cost of a plan?

Table/index statistics (row counts, distinct values, histograms, null fraction, correlation), estimated selectivity of predicates, and per-operation cost parameters — e.g. PostgreSQL's seq_page_cost, random_page_cost, cpu_tuple_cost, cpu_index_tuple_cost, cpu_operator_cost. Cost roughly models I/O pages plus CPU tuple/operator work.

Why is join-order optimization computationally hard, and how do optimizers cope?

The number of possible join orders grows combinatorially — with $n$ tables there are on the order of $n!$ orderings — making exhaustive search infeasible for many tables. Optimizers cope with dynamic programming (System-R style, exact but exponential in the worst case) for few tables and switch to heuristics like genetic/greedy algorithms (PostgreSQL's GEQO) beyond a threshold (default 12 tables).

What are table statistics and what does ANALYZE do?

Statistics are metadata the optimizer uses to estimate row counts: total rows, number of distinct values, most-common-values list, histograms of value distribution, null fraction, and physical/logical correlation. ANALYZE (PostgreSQL) / UPDATE STATISTICS (SQL Server) samples the table to (re)compute these. Stale statistics after bulk changes lead to bad estimates and bad plans.

What is cardinality estimation and why is it critical?

Cardinality estimation predicts how many rows each operation will produce (e.g. how many rows satisfy a WHERE, or a join). It's critical because every downstream cost and algorithm choice depends on it; underestimates lead to nested loops that explode, overestimates lead to unnecessary hash builds/sorts. It is often cited as the single biggest source of optimizer error.

How is the selectivity of an equality predicate 'col = x' estimated from statistics, assuming a uniform distribution?

For a uniformly-distributed column, selectivity $\approx \frac{1}{n_{distinct}}$, so estimated rows $\approx \frac{N}{n_{distinct}}$ where $N$ is total rows and $n_{distinct}$ is the number of distinct values. If a most-common-values (MCV) histogram exists, the stored frequency of $x$ is used instead of the uniform assumption.

Under the independence assumption, how does the optimizer combine selectivities of two ANDed predicates, and why is this a common error source?

It multiplies them: $S_{A \wedge B} = S_A \times S_B$, assuming the columns are statistically independent. This underestimates rows when columns are correlated (e.g. city and country), causing gross cardinality errors. Fix: create multivariate/extended statistics (PostgreSQL CREATE STATISTICS) to capture the correlation.

What is the difference between a most-common-values (MCV) list and a histogram in column statistics?

The MCV list stores the specific most frequent values and their exact frequencies, used to estimate selectivity for those common values precisely. The histogram divides the remaining (non-MCV) values into equal-frequency (equi-depth) buckets to estimate selectivity of ranges and less-common equality values. Together they model skewed distributions.

What tools/approaches identify slow queries in a production database?

Server-side statement statistics (PostgreSQL pg_stat_statements aggregating total/mean/max time and calls per normalized query), slow query logs (log_min_duration_statement, MySQL slow_query_log), the active-session view (pg_stat_activity) for currently running queries, and APM/monitoring tools. Then EXPLAIN ANALYZE the offenders.

When prioritizing which slow query to optimize, why is total time often more important than per-execution time?

Total impact = mean execution time $\times$ call frequency. A query taking 50 ms but run 1,000,000 times/hour consumes far more resources than a 5-second query run twice/hour. pg_stat_statements' total_exec_time column captures this cumulative load, so optimizing high-total-time queries yields the biggest system-wide gains.

List common query anti-patterns that prevent index use or hurt performance.

Wrapping indexed columns in functions (non-sargable); leading-wildcard LIKE '%x%'; SELECT * (defeats covering indexes, extra I/O); implicit type mismatches forcing casts; OR conditions across different columns; large offset pagination (OFFSET 100000); N+1 query patterns; and correlated subqueries that run per outer row.

Why is OFFSET-based pagination (LIMIT ... OFFSET large_number) slow, and what is the fix?

OFFSET still reads and discards all preceding rows, so cost grows linearly with the offset — deep pages get progressively slower. Fix: keyset / cursor (seek) pagination, e.g. WHERE id > :last_seen_id ORDER BY id LIMIT n, which uses the index to jump straight to the next page in constant time regardless of depth.

What is the N+1 query problem and how is it resolved?

N+1 occurs when code runs 1 query to fetch N parent rows, then 1 additional query per parent to fetch children — totaling N+1 round trips. Resolved by fetching in a single query with a JOIN or by batching child fetches with WHERE parent_id IN (...), turning N+1 into 1 or 2 queries.

Give an example of query rewriting: replacing a correlated subquery. Why does it help?

Rewrite a correlated EXISTS/scalar subquery that executes once per outer row into a JOIN or a single aggregated/derived table. E.g. replace SELECT ... WHERE x IN (SELECT ... correlated) with a JOIN to a grouped subquery. It helps because the optimizer can then use set-based hash/merge joins instead of repeated per-row execution.

How can rewriting an OR predicate improve index usage?

A predicate like WHERE a = 1 OR b = 2 often prevents a single index seek. Rewriting it as UNION (or UNION ALL) of two separate queries — one filtering a=1, one filtering b=2 — lets each branch use its own index. Similarly, WHERE col IN (list) is usually better than a chain of OR equalities.

Why can UNION ALL be preferable to UNION, and when must you keep UNION?

UNION removes duplicate rows, which forces an extra sort or hash de-duplication pass over the combined result — costly. UNION ALL simply concatenates results with no dedup, so it's faster and should be used whenever you know the branches produce no overlapping duplicates (or duplicates are acceptable). Keep UNION only when duplicate elimination is semantically required.

What is connection pooling and what problem does it solve?

A connection pool maintains a set of reusable, already-established database connections that application requests borrow and return, instead of opening/closing a new connection per request. It solves the high cost of connection setup (TCP + auth + backend process/thread spawn) and caps concurrent connections to protect the database. In PostgreSQL, tools like PgBouncer are common because each connection is a separate backend process.

Contrast query result caching with a buffer/page cache, and note a key caching hazard.

A buffer/page cache (e.g. PostgreSQL shared_buffers, OS page cache) keeps recently-read data pages in RAM to avoid disk I/O, managed by the database automatically. Query result caching (e.g. an application/Redis layer) stores the final results of expensive queries keyed by their parameters. Key hazard: cache invalidation — cached results can become stale when underlying data changes, so you need TTLs or explicit invalidation on writes.