Query Optimization and Execution Plans Questions

Direct answer. Approximate techniques (most commonly HyperLogLog for distinct counts, and similar probabilistic sketches for other aggregates) trade a small, quantifiable, and tunable error rate for a dramatic reduction in the memory and computation an exact count would require, which is the right trade when the business decision the number feeds doesn't actually hinge on exact precision.

Structured elaboration. An exact DISTINCT count over a massive dataset generally has to track every unique value seen, memory or disk cost scaling with the number of distinct values, which becomes genuinely expensive at high cardinality and high volume. A probabilistic cardinality sketch instead maintains a small, fixed-size summary (independent of how many distinct values there actually are) that can estimate the true distinct count within a known, tunable error bound, commonly around 1-2% for HyperLogLog at practical configurations, in exchange for that summary using a small constant amount of memory rather than growing with the data.

Worked example. A "distinct visitors this month" metric computed nightly for an internal dashboard, where a 1-2% error is invisible to anyone reading the number and completely irrelevant to any decision it informs, is a strong candidate for an approximate technique; a count feeding a legal or financial reconciliation process, where every unit matters and the number needs to tie out exactly against an external source, is not, regardless of how expensive the exact computation is.

Trade-offs and pitfalls. Presenting this trade-off honestly to a stakeholder means being explicit about both the error bound and what it does and doesn't affect: the sketch is well-calibrated (the true value falls within the stated bound with known probability), but stakeholders who are used to seeing exact numbers may reasonably want that distinction called out clearly rather than silently swapped in, especially the first time a number they're used to being exact stops matching a manually-computed spot check by a small amount. A good practice is to label approximate metrics as approximate in the dashboard or report itself, not just in an internal engineering doc, so the distinction is visible to whoever's making decisions with the number.

Complexity

An exact distinct count costs memory proportional to the number of distinct values (in the worst case, proportional to the row count); a cardinality sketch costs a small, FIXED amount of memory regardless of how many distinct values exist, which is the entire source of its scalability advantage.

Edge cases

Extremely low-cardinality columns (very few distinct values) get little practical benefit from a probabilistic sketch, since an exact count there is already cheap; the technique earns its keep specifically at high cardinality and high data volume, where the exact approach's cost genuinely becomes a problem.

Direct answer. A merge join needs both inputs to already be sorted on the join key (either because an index provides that order for free, or because the optimizer decided an explicit sort was worth paying for), and it wins over a hash join specifically when that sortedness is cheap to obtain and the two inputs are both large, since it then needs no in-memory hash table at all, just a single linear walk through both sorted streams.

Structured elaboration. Given two inputs sorted on the join key, a merge join advances through both in lockstep, comparing the current key from each side and advancing whichever is behind, producing matches as it goes; this is a single linear pass with essentially no extra memory needed beyond tracking the current position in each input, which makes it very cheap once the sortedness is already available. A hash join instead builds an in-memory hash table from one side (a real memory cost, and a potential spill-to-disk cost if that side is large) and probes it with the other; it doesn't need either input sorted, which is exactly why it's the more common default for two large, unsorted inputs.

Merge join suffers when the required sortedness ISN'T already available and has to be produced with an explicit sort step, since sorting a large input from scratch can be as expensive as (or more expensive than) simply building a hash table would have been, at which point the merge join's own advantage evaporates and a hash join becomes the better choice. To prepare data to make a merge join a live, attractive option, ensure both sides have an index on the join key (so the sort comes "free" from index order) or that the join key is already the table's natural clustering order, rather than relying on an explicit, expensive sort step to manufacture that order on the fly.

Worked example. Joining two large fact tables that are BOTH naturally maintained in sorted order on the join key (say, both clustered or indexed on the same surrogate key by construction) is close to the ideal case for a merge join: the sortedness is free, and the join itself becomes a cheap linear pass with no hash table memory pressure at all, which can beat an equivalent hash join, especially under tight memory constraints where a large hash table would otherwise risk spilling.

Trade-offs and pitfalls. Don't assume a merge join is "the sophisticated choice" and therefore always preferable; it only wins when sortedness is genuinely cheap, and forcing one via a hint on two unsorted large inputs, paying for an explicit sort neither input naturally had, is very often worse than just letting the optimizer's default hash join choice stand.

Direct answer. Nested loop is cheapest when the outer side is small and the inner side has a cheap way to be probed (typically an index); hash join is the workhorse for large, unsorted inputs where one side comfortably fits in memory to build a hash table from; sort-merge join wins when both inputs are already sorted (or cheaply sortable) on the join key, since it can then walk both in a single linear pass with no random lookups and no hash table at all.

Structured elaboration. Nested loop's cost is roughly (outer rows) times (cost per inner probe); it degrades badly the moment the outer side is larger than expected, since every extra outer row multiplies the total work. Hash join's cost is roughly (build side rows, to construct the hash table) plus (probe side rows, each a cheap in-memory lookup); its main risk is memory: if the build side is bigger than the memory budget allotted, the hash table spills to disk in partitions, which is far slower than an in-memory hash join but still usually better than a nested loop over the same volumes. Sort-merge needs both inputs sorted; if an index already provides that order, the "sort" part is free and the join itself is a fast linear merge, but if neither input is sorted and both are large, the up-front sort cost can make this the worst of the three options.

Worked example. Joining a 50-million-row fact table to a 200-row lookup table: a nested loop with an index on the fact table's join key (probing the fact table once per lookup row) does roughly 200 cheap index probes, which is far cheaper than building a hash table from 50 million rows. Flip the sizes, joining two roughly-equal, unsorted multi-million-row tables, and a hash join (build from the smaller of the two, probe with the larger) beats a nested loop by orders of magnitude, since nested loop would need tens of millions of probes instead of one hash table build plus one linear probe pass.

Trade-offs and pitfalls. None of the three algorithms is universally best; the right one is a function of the relative sizes of the two inputs, whether either side is already sorted or indexed on the join key, and how much memory is available for a hash table. A senior red flag is seeing a nested loop join over two large, unindexed inputs (that's the shape most likely to be a genuine planner mistake, usually traced back to a cardinality misestimate) versus seeing it over one genuinely small input joined to a large indexed one (that's usually correct and fast).

Direct answer. Query system catalogs and usage-tracking views for both index usage counts (to spot ones that are never or rarely scanned) and index definitions (to spot ones that are subsets or exact duplicates of other indexes); before actually dropping anything, confirm across a representative time window and check for uses outside plain SELECT queries, like enforcing a uniqueness constraint, that usage stats alone won't show.

Structured elaboration. Most relational databases expose a system view or catalog that reports, per index, how many times it's been scanned since statistics were last reset; an index with a usage count of zero (or near-zero) over a long enough observation window, on a table that otherwise sees real traffic, is a strong candidate for being unused. For redundancy, compare index DEFINITIONS directly: an index on (user_id) is functionally redundant if another index on (user_id, order_date) already exists, since any query that could use the narrower index can use the leading portion of the wider one just as well; two indexes with the exact same column set in the same order are pure duplicates.

The evidence bar before actually dropping an index should be higher than "usage count looks low right now." Observe over a window long enough to cover your real traffic patterns (including infrequent batch jobs or month-end reports that only run periodically), and separately verify the index isn't silently required for something usage stats won't show, most commonly enforcing a UNIQUE or primary-key constraint, or being the specific index a foreign-key relationship depends on for efficient cascade operations.

-- illustrative shape (exact catalog names vary by engine):
-- 1) find indexes with (near) zero scans over the observation window
SELECT index_name, scans FROM pg_stat_user_indexes WHERE scans < 10;
-- 2) find indexes whose column list is a strict subset of another index's
--    on the same table, in the same leading order

Trade-offs and pitfalls. Dropping an index that turns out to matter (even rarely) can cause a sudden, hard-to-diagnose regression the next time that infrequent query or batch job runs; a safer rollout pattern is to disable (rather than immediately drop) a candidate index where the engine supports that, monitor for any regression over a full business cycle, and only drop it permanently once you're confident nothing depends on it.

Complexity

This is a metadata-driven audit, not a per-row scan of the table itself, so it's cheap to run repeatedly regardless of table size; the expensive part is the calendar time needed to observe a representative traffic window, not the query cost.

Edge cases

An index that backs a UNIQUE or FOREIGN KEY constraint will often show up as "unused" in scan-count views even though it's structurally required; always cross-check the constraint catalog before treating a low-scan index as a safe drop.

Direct answer. A bitmap index scan builds an in-memory bitmap of matching row locations from one or more indexes, then visits the table using that combined bitmap in physical storage order rather than in index order, which lets the planner efficiently combine multiple indexes for one query and avoid the random-access pattern a plain index scan would otherwise pay for at moderate selectivity.

Structured elaboration. A plain index scan visits matching rows in the INDEX's order, which for a moderately selective predicate (not tiny, not huge) can mean visiting the underlying table in scattered, random physical order, one lookup per match. A bitmap scan instead first builds a bitmap marking which table pages (or exact rows, depending on how lossy the bitmap is) contain a match, without immediately visiting the table at all, then does a single pass over the table in PHYSICAL order, checking only the pages the bitmap flagged. This turns what would have been scattered random access into a more sequential, sorted-by-physical-location access pattern, which tends to win specifically in the middle ground of selectivity, too many matches for a plain index scan's random-access pattern to stay cheap, too few for a full sequential scan to be the better choice.

The other place this shines is combining multiple indexes for one query: bitmaps from two different single-column indexes can be combined (via a boolean AND or OR) in memory before ever touching the table, letting the planner efficiently satisfy a multi-column predicate even without a single composite index covering all the relevant columns.

Worked example. A query filtering on two separately-indexed columns with moderate selectivity each, where no composite index covering both exists, can use a bitmap scan on each individual index, AND the two resulting bitmaps together in memory, and then visit only the table pages that satisfy BOTH conditions in one physical-order pass, rather than either falling back to a full table scan or being unable to use both indexes together at all.

Trade-offs and pitfalls. A bitmap can become "lossy" (tracking pages rather than exact rows) once it would otherwise consume too much memory to track every individual matching row precisely, at which point the table visit has to re-check every row on a flagged page against the actual predicate, adding back a small amount of the cost the bitmap was trying to avoid; this is still typically much cheaper than the alternative, but worth knowing about if you're trying to understand exactly why a bitmap scan's actual time doesn't match a naive "just count the matching rows" estimate.