4.8 Multidimensional and Full-Text Indexes

8.1 Concatenated vs multidimensional

Concatenated index = combine several fields into one key by appending one column to another (order specified in the index definition). Like an old-fashioned paper phone book: an index from (lastname, firstname) to phone number.

An index on (lastname, firstname):

• ✔ Find all people with a particular lastname
• ✔ Find a particular lastname + firstname combination
• ✗ Useless for finding all people with a particular firstname

Why it fails for geospatial:

SELECT * FROM restaurants WHERE latitude  > 51.4946 AND latitude  < 51.5079
                            AND longitude > -0.1162 AND longitude < -0.1004;

Solutions:

1. Translate 2-D into a single number via a space-filling curve (Z-order/Morton, Hilbert), then use a regular B-tree
2. More commonly, specialized spatial indexes: R-trees or Bkd-trees, which divide the space so nearby points tend to be grouped in the same subtree. PostGIS implements geospatial indexes as R-trees using PostgreSQL's GiST facility
3. Regularly spaced grids of triangles, squares, or hexagons (H3, S2)

Multidimensional indexes are not just geographic:

• Ecommerce: a 3-D index on (red, green, blue) to search products in a color range
• Weather: a 2-D index on (date, temperature) to find observations in a given year with temperature 25–30°C. With a 1-D index you'd have to scan all records from that year and then filter by temperature, or vice versa.

8.2 Full-text search and the inverted index

The reframing that makes it click:

Full-text search is another kind of multidimensional query. Each term that might appear in a text is a DIMENSION. A document containing term x has value 1 in dimension x; otherwise 0. Searching "red apples" = a 1 in the red dimension AND simultaneously a 1 in the apples dimension. The number of dimensions may be very large.

Inverted index = key-value structure where key = a term, value = the list of IDs of all documents containing it (the postings list).

Query "red apples": 1 0 1 1 AND 1 0 1 0 = 1 0 1 0 → d1 and d3. This is exactly the vectorized warehouse query from the column-store section, and it stays efficient even run-length encoded.

If document IDs are sequential numbers, the postings list can be a sparse bitmap — the nth bit for term x is 1 if document n contains x.

Real implementations:

• Lucene (the engine behind Elasticsearch and Solr) stores term → postings list in SSTable-like sorted files, merged in the background using the same log-structured approach as §2. (So Lucene is an LSM engine — that connection is worth internalizing.)
• PostgreSQL's GIN index uses postings lists for full-text search and for indexing inside JSON documents.

Two extensions:

Note the honest scoping: information retrieval is a big specialist topic involving language-specific processing — several Asian languages are written without spaces or punctuation between words, so splitting text into words requires a model that says which character sequences constitute a word — plus synonyms and grammatical forms. Beyond the book's scope.

8.3 Vector embeddings and semantic search

The problem: a help page titled "canceling your subscription" should be findable by "how to close my account" or "terminate contract" — close in meaning, completely different words. Important for retrieval-augmented generation (RAG), which incorporates search results into an LLM's output.

How: an embedding model (often an LLM) translates a document into a vector embedding — a vector of floating-point values. The vector is a point in multidimensional space; each value is the document's location along one dimension's axis. Semantically similar inputs get vectors near each other.

agriculture   [0.38, 0.83,  0.41]  ┐ near each other
vegetables    [0.36, 0.64,  0.67]  ┘
star schemas  [0.85, 0.10, -0.52]    far away

Real models use vectors of often more than 1,000 numbers. We do not try to understand what individual numbers mean — they are simply a way for the model to point to a location in an abstract space.

• Cosine similarity — the cosine of the angle between two vectors
• Euclidean distance — the straight-line distance between two points

⚠️ Terminology collision: in vectorized processing (§7.6), a vector is a batch of values processed with specially optimized code. In embedding models, a vector is an array of floats representing a location in multidimensional space. Same word, different meanings.

Model history: early text models Word2Vec, BERT, GPT, usually implemented as neural networks. Then models for video, audio, images. More recently multimodal: one model generating embeddings for multiple modalities.

Query flow: user query + related context (e.g. the user's location) → embedding model → query vector → vector index returns documents whose vectors are closest.

Three index types (R-trees don't work well for high-dimensional vectors):

Implemented in Facebook's Faiss (several variants of each) and PostgreSQL's pgvector (both).