The B-trees and LSM-trees we saw in the first half of this topic allow range queries over a single attribute; for example, if the key is a username, you can use them as an index to efficiently find all names starting with an L. But sometimes, searching by a single attribute is not enough.
The most common type of multicolumn index is called a concatenated index, which simply combines several fields into one key by appending one column to another (the index definition specifies in which order the fields are concatenated). This is like an old-fashioned paper phone book, which provides an index from (lastname, firstname) to phone number. Because of the sort order, the index can be used to find all the people with a particular last name, or all the people with a particular lastname–firstname combination. However, the index is useless if you want to find all the people with a particular first name.
On the other hand, multidimensional indexes allow you to query several columns at once. This is particularly important with geospatial data. For example, a restaurant search website may have a database containing the latitude and longitude of each restaurant. When a user is looking at the restaurants on a map, the website needs to search for all the restaurants within the rectangular map area that the user is currently viewing. This requires a two-dimensional range query like the following:
SELECT * FROM restaurants WHERE latitude > 51.4946 AND latitude < 51.5079
AND longitude > -0.1162 AND longitude < -0.1004;
A concatenated index over the latitude and longitude columns is not able to answer that kind of query efficiently. The index can give you either all the restaurants in a range of latitudes (but at any longitude) or all the restaurants in a range of longitudes (but anywhere between the North and South Poles), but not both simultaneously.
One option is to translate a two-dimensional location into a single number via a space-filling curve, then use a regular B-tree index. More commonly, specialized spatial indexes such as R-trees or Bkd-trees are used; they divide up the space so that nearby data points tend to be grouped in the same subtree. For example, PostGIS implements geospatial indexes as R-trees by using PostgreSQL’s Generalized Search Tree indexing facility. It is also possible to use regularly spaced grids of triangles, squares, or hexagons.
Multidimensional indexes are not just for geographic locations, though. For example, on an ecommerce website you could use a three-dimensional index on the dimensions (red, green, blue) to search for products in a certain range of colors, or in a database of weather observations you could have a two-dimensional index on (date, temperature) to efficiently search for all the observations during a given year where the temperature was between 25°C and 30°C. With a one-dimensional index, you would have to either scan over all the records from that year (regardless of temperature) and then filter them by temperature, or vice versa. A two-dimensional index can narrow the results by timestamp and temperature simultaneously.
Full-Text Search
Full-text search allows you to search a collection of text documents (web pages, product descriptions, etc.) by keywords that might appear anywhere in the text. Information retrieval is a big, specialist topic that often involves language-specific processing; for example, several Asian languages are written without spaces or punctuation between words, and therefore splitting text into words requires a model that indicates which character sequences constitute a word. Full-text search also often involves matching words that are similar but not identical (accounting for typos or different grammatical forms of words) and synonyms. Those problems go beyond the scope of these notes.
However, at its core, you can think of full-text search as another kind of multidimensional query. In this case, each word that might appear in a text (a term) is a dimension. A document that contains term x has a value of 1 in dimension x, and a document that doesn’t contain x has a value of 0. Searching for documents mentioning “red apples” means a query that looks for a 1 in the red dimension and, simultaneously, a 1 in the apples dimension. The number of dimensions may thus be very large.
The data structure that many search engines use to answer such queries is called an inverted index. This is a key-value structure where the key is a term and the value is the list of IDs of all the documents that contain the term (the postings list). If the document IDs are sequential numbers, the postings list can also be represented as a sparse bitmap, as in Figure 4-8; the nth bit in the bitmap for term x is a 1 if the document with ID n contains the term x.
Finding all the documents that contain both terms x and y is now similar to a vectorized data warehouse query that searches for rows matching two conditions (Figure 4-9): load the two bitmaps for terms x and y and compute their bitwise AND. Even if the bitmaps are run-length encoded, this can be done very efficiently.
For example, Lucene, the full-text indexing engine used by Elasticsearch and Solr, works like this. It stores the mapping from term to postings list in SSTable-like sorted files, which are merged in the background using the same log-structured approach we saw earlier in this topic. PostgreSQL’s GIN index type also uses postings lists to support full-text search and indexing inside JSON documents.
Instead of breaking text into words, an alternative is to find all the substrings of length n, which are called n-grams. For example, the trigrams (n = 3) of the string hello are hel, ell, and llo. If we build an inverted index of all trigrams, we can search the documents for arbitrary substrings that are at least three characters long. Trigram indexes even allow regular expressions in search queries; the downside is that they are quite large.
To cope with typos in documents or queries, Lucene is able to search text for words within a certain edit distance (an edit distance of 1 means that one letter has been added, removed, or replaced). It does this by storing the set of terms as a finite state automaton over the characters in the keys, similar to a trie, and transforming it into a Levenshtein automaton, which supports efficient search for words within a given edit distance.
Vector Embeddings
Semantic search goes beyond synonyms and typos to try to understand document concepts and user intentions. It is becoming an important part of AI applications, such as retrieval-augmented generation, which incorporates search results into the output of a large language model (LLM). For example, if your help pages contain a page titled “canceling your subscription,” users should still be able to find that page when searching for “how to close my account” or “terminate contract,” which are close in terms of meaning even though they use completely different words.
To understand a document’s semantics—its meaning—semantic search indexes use embedding models to translate a text document into a vector of floating-point values, called a vector embedding. Often this is done using LLMs. The vector represents a point in a multidimensional space, and each floating-point value represents the document’s location along one dimension’s axis. Embedding models generate vector embeddings that are near each other (in this multidimensional space) when the embedding’s input documents are semantically similar.
Note
We saw the term vectorized processing in “Query Execution: Compilation and Vectorization”. Vectors in semantic search have a different meaning. In vectorized processing, the vector refers to a batch of bits that can be processed with specially optimized code. In embedding models, a vector is an array of floating-point numbers that represents a location in multidimensional space.
For example, a three-dimensional vector embedding for a Wikipedia page about agriculture might be [0.38, 0.83, 0.41]. A Wikipedia page about vegetables would be quite near, perhaps with an embedding of [0.36, 0.64, 0.67]. A page about star schemas might have an embedding of [0.85, 0.10, -0.52], comparatively far away. We can tell by looking that the first two vectors are closer than the third.
Embedding models use much larger vectors (often over 1,000 numbers), but the principles are the same. We don’t try to understand what the individual numbers mean; they’re simply a way for the model to point to a location in an abstract multidimensional space. Search engines use distance functions such as cosine similarity or Euclidean distance to measure the distance between vectors: cosine similarity measures the cosine of the angle of two vectors to determine how close they are, while Euclidean distance measures the straight-line distance between two points in space.
Many early embedding models, such as Word2Vec, BERT, and GPT, worked with text data. Such models are usually implemented as neural networks. Researchers went on to create embedding models for video, audio, and images as well. More recently, model architecture has become multimodal: a single model can generate vector embeddings for multiple modalities, such as text and images.
Semantic search engines use an embedding model to generate a vector embedding when a user enters a query. The user’s query and related context (such as the user’s location) are fed into the embedding model. After the embedding model generates the query’s vector embedding, the search engine must find documents with similar vector embeddings by using a vector index.
Vector indexes store the vector embeddings of a collection of documents. To query the index, you pass in the vector embedding of the query, and the index returns the documents whose vectors are closest to the query vector. Since the R-trees we saw previously don’t work well for vectors with many dimensions, specialized vector indexes are used, such as these:
Flat indexes
Vectors are stored in the index as they are. A query must read every vector and measure its distance to the query vector. Flat indexes are accurate, but measuring the distance between the query and each vector is slow.
Inverted file (IVF) indexes
The vector space is clustered into partitions (called centroids) of vectors to reduce the number of vectors that must be compared. IVF indexes are faster than flat indexes but can give only approximate results; the query and a document may fall into different partitions, even though they are close to each other. A query on an IVF index first defines probes, which are simply the number of partitions to check. Queries that use more probes will be more accurate but slower, as more vectors must be compared.
Hierarchical Navigable Small World (HNSW) indexes
HNSW indexes maintain multiple layers of the vector space, as illustrated in Figure 4-11. Each layer is represented as a graph, where nodes represent vectors and edges represent proximity to nearby vectors. A query starts by locating the nearest vector in the topmost layer, which has a small number of nodes. The query then moves to the same node in the layer below and follows the edges in that layer, which is more densely connected, looking for a vector that is closer to the query vector. The process continues until the last layer is reached. Like IVF indexes, HNSW indexes are approximate.
Diagram illustrating the hierarchical layers in a Hierarchical Navigable Small World (HNSW) index, showing the traversal path of a query vector through interconnected nodes across multiple layers.
Figure 4-11. Searching for the database entry that is closest to a given query vector in an HNSW index
Many popular vector databases implement IVF and HNSW indexes. Facebook’s Faiss library has several variations of each, and PostgreSQL’s pgvector supports both as well. The full details of the IVF and HNSW algorithms are beyond the scope of these notes, but their papers are excellent resources.