Fast queries and search indexes

Compiled or vectorized queries

A query plan is a chain of steps called operators, like "price > 15". Over millions of rows, checking the plan again for every row wastes CPU time. Query compilation writes machine code for this one query. Vectorized processing runs ready-made operators over a batch of column values at a time. Both read memory in order, run tight loops, use many threads and SIMD (one instruction on many values), and can work on compressed data.

Materialized views and data cubes

A virtual view is a saved query that runs each time. A materialized view stores the results, and must be updated when the data changes. A data cube stores totals grouped by several dimensions, like store by month. Lookups become instant, but a cube cannot answer questions on columns it did not group by.

Inverted indexes

A full-text index maps each word to a postings list: the IDs of documents that contain it. You can see each word as its own dimension, so search is a query over many dimensions. For "red AND apple", combine the two lists. Indexing every 3-letter group (trigram) finds any substring, but the index is bigger. Typos are handled by also matching words within a small edit distance.

Vector embeddings

Semantic search matches meaning, not words; AI apps use it to feed relevant documents to an LLM (RAG). An embedding model turns a document into a vector: a list of numbers marking a point in space. Similar meanings sit close. Cosine similarity compares the angle between vectors; Euclidean distance measures the straight line.

Vector indexes

Given a query vector, a vector index returns the nearest stored ones. R-trees fail with so many dimensions. A flat index compares with every vector: exact but slow. IVF searches only a few clusters; more probes, more accurate. HNSW walks layered graphs from coarse to fine. Both are approximate.

Remember

• Compile or vectorize to save CPU.
• Precomputed answers are fast but less flexible.
• Inverted index: word to list of documents.
• Embeddings put meaning in space; vector indexes find neighbors.