Interview questions
When an ordinary index cannot help
2Indexes and joins assume that a predicate reduces to a point, a range or an exact hash equality. In what ways does that assumption break?
Dimensionality (no one-dimensional order keeps neighbours close), structure (the next record to read depends on the last one, as in a graph), and relevance (there is no ground truth for "best match"). Skew in the data's distribution, and the needs of whoever consumes the result, break it in two further ways.
Read moreThree ways the reduction breaks
4When must an approximate filter avoid false negatives, and when may it err in both directions?
If an exact answer exists (containment, equality), the approximation must be one-sided: no false negatives, followed by an exact check. If there is no ground truth (relevance, similarity), errors may go in both directions.
Read moreWhat the approximation must respectOne-sided versus two-sided approximation
5Why can no multidimensional index keep all close points close together on disk?
No total order preserves proximity in more than one dimension, so every multidimensional index chooses which neighbours to separate. It is a mathematical fact, not a limit of today's engineering.
Read moreWhat the approximation must respect
6When the judge of a correct answer lies outside the system, as with relevance, what replaces correctness?
Reproducibility: versioned datasets, pinned index builds, point-in-time joins and A/B evaluation.
Read moreWhat the approximation must respect
Text search
7Why does LIKE '%kurta%' not use a B-tree index?
A B-tree is sorted by the beginning of the string. A pattern with a leading wildcard has no starting point, so the engine scans every row. An inverted index, which maps each word to the documents containing it, answers it instead.
Read moreThe inverted index
8How can a search engine rank millions of matches cheaply?
The relevance score is a sum of per-term parts, each with a stored maximum. Keeping a heap of the best 10, whole blocks of postings are skipped when they cannot beat the tenth-best score (WAND and block-max skipping).
Read moreDecomposability
9Why does a common word like 'the' make a search query slow?
Its postings list is huge and its maximum score is low and flat, so skipping rarely helps. Because word frequencies follow a Zipf distribution, the cost of a query varies far more with its words than with data volume.
Read moreDecomposabilityThree consequences
10Why do category counts (facets) cost far more than the ten results next to them?
Ranking the top 10 can skip most matches, but a count needs every match. Facets also need a forward copy, from document to value, and they cancel early termination.
Read moreFaceting defeats early termination
11Why does a very short refresh interval slow search down?
Each refresh writes a new small segment, and every query pays a fixed cost per segment, so more segments mean more fixed work for every reader.
Vector search
12Why is brute-force vector search memory-bound?
It performs about 0.5 floating-point operations per byte read. 10 million 768-dimension float32 vectors are about 30 GB, so one scan at 50 GB/s takes about 0.6 s.
13Why is quantization mainly a speed tool for vectors, not a storage tool?
The scan is limited by bytes read, so reading 32 times fewer bytes makes it about 32 times faster. Fitting in RAM is secondary.
14What do IVF, HNSW and PQ each do?
IVF partitions vectors into cells and probes only a few. HNSW navigates a layered graph of neighbours. PQ (product quantization) compresses each vector into a short code. They can be combined.
Read moreThe three ANN families
15Why can two HNSW graphs not be merged the way LSM segments are?
Sorted runs combine by merging, but neighbour graphs and sets of cluster centroids do not. The only way to merge them is to rebuild from the vectors.
Read moreBuild cost, mutability, and why merging does not work
16Why do keyword (BM25) and vector scores need rank fusion?
They are on different scales that are not calibrated against each other. Reciprocal rank fusion combines the ranks instead of the score values.
Read moreHybrid search and rank fusion
17Why is vector search with a filter hardest when the filter keeps 0.1% to 10% of items?
Filtering after the search needs to fetch k ÷ selectivity candidates; filtering first abandons the index and scans what is left. The filter defines a sub-population the index was never fitted to, and a structure fitted to one distribution is only valid for that distribution.
Read moreFiltered ANNWhy the middle resists
Graphs
18Why is a three-hop graph query slow in a relational database?
Each hop is a self-join with an index lookup for every row in the frontier, and the frontier grows as degree^hops.
Read moreTraversal as a query primitive
19What is CSR?
Compressed sparse row: one array of neighbour IDs and one array of offsets, so the neighbours of vertex v are nbrs[off[v]:off[v+1]]. It is columnar layout for graphs, and in practice immutable.
Read moreAdjacency list and CSR
20Why do you store a graph twice?
An adjacency index points one way. Following incoming edges needs a reverse copy, which doubles storage and adds a second write path.
Read moreAdjacency list and CSR
21When does a graph engine beat a join, and when not?
Few starting points and many hops favour traversal. Many starting points and few hops favour a vectorized hash join.
Read moreAdjacency list and CSR
22Why is a power-law graph hard to partition?
There is no good balanced cut to find, so any balanced partition cuts most edges. The fix is a vertex cut: split the edges, replicate the hub vertices and reconcile them.
Read moreDegree skew
23How does Pregel (bulk synchronous parallel) process a graph?
In supersteps: each vertex processes its incoming messages and sends new ones, with a global barrier between rounds. Random access becomes one shuffle per hop.
Read morePregel / BSP: batching by round
24How do PageRank and connected components differ in how predictable their cost is?
PageRank converges geometrically and can be stopped early. Connected components must run until nothing changes, and the number of rounds depends on the graph's diameter.
Read morePageRank and connected components
25Property graph or RDF: what does each trade?
RDF (subject–predicate–object triples) gives maximal normalization and easy merging without agreeing a schema, at the cost of self-joins and several sorted copies of the triples. Property graphs fix structure early and are cheaper to read.
Read moreProperty graph versus RDF
Geospatial
26Why must spatial queries filter by bounding box first, then refine?
Exact intersection of two shapes with m and n vertices costs about m × n, while a box test is four comparisons. Disjoint boxes imply disjoint shapes, so the filter has no false negatives.
27What is the fill ratio of a shape?
The shape's area divided by its bounding box's area. It sets the false-positive rate of the box filter.
28What does an object with extent, such as a polygon, do to partitioning?
You must either copy the object into every cell it touches (and deduplicate on read) or let regions overlap (and search several paths).
Read moreThe boundary problem
29Why use a grid such as geohash, S2 or H3?
Nested cells share an ID prefix, so containment becomes a prefix query on an ordinary index. The cost: nearby points can get distant IDs where the linear order tears, and you must choose a resolution.
Read moreDiscrete global grids
30Why must a coordinate reference system travel with a geometry?
Operations across mismatched coordinate systems give wrong answers silently. Making the system's identifier (SRID) part of the type prevents this.
Time series
31What is the cardinality wall in a time-series store?
The number of series is the product of each label's number of distinct values, and each series has a fixed overhead that cannot be compressed away. Adding a dimension multiplies.
32How does Gorilla compression work?
Delta-of-delta for timestamps (often 1 bit) and XOR against the previous value for floats (a few bits). A 16-byte point becomes about 1–2 bytes.
Read moreDelta-of-delta and Gorilla
33Which aggregates can be rolled up into coarser intervals?
Sum, count, min and max combine; a mean needs sum and count. Quantiles and distinct counts do not, unless you store mergeable sketches.
Read moreDownsampling and rollups
34What are retention tiers?
Keep raw data for days, then coarser rollups for longer. The value of data decays with resolution faster than with age.
Read moreRetention tiers by resolution
35Why is a gap in a time series ambiguous?
It may mean no change, a sensor that was down, dropped data, or that the thing did not exist yet, and all of these look the same in storage.
Read moreGap filling and interpolation
Features for machine learning
Across the families
36What are the four ways specialized systems escape the limits of ordinary indexes?
Project and refine; change the execution model; specialize the representation; and substitute reproducibility for verification.
Read moreThe one thing to carry forward
37Which two lessons from specialized systems apply most widely?
That how well a function can be optimized comes from its algebra (a score that is a sum can be bounded and skipped); and that a structure fitted to a distribution is valid only for that distribution.
Read moreWhich two will keep paying
38Why is the real cost of a specialized system its pipeline?
Each one adds a second write path, with its own freshness, failure modes, rebuild time and reconciliation against the source of truth.