Vec1

Vec1 User Manual
Login

Contents:

This is a user manual that attempts to explain how vec1 may be used and integrated with other SQL queries. It is not a complete reference guide. For that, please see this page.

1. Using The Virtual Table

A vec1 virtual table is created using the following syntax:

    CREATE VIRTUAL TABLE vec1tbl USING vec1(vector);

where "vector" may be replaced with any legal SQLite column name. Or omitted entirely, in which case it defaults to "vector". This creates a virtual table that behaves similarly to a regular table with the following schema:

    CREATE TABLE vec1tbl(vector BLOB);

The virtual table can then be populated using the usual SQL commands (e.g. INSERT, UPDATE, DELETE). The "vector" column of each row should be populated with a vector, in Vec1's native blob format. Each row is identified by a "rowid" column, which may, as for regular SQLite tables, be populated explicitly or automatically.

    -- Insert a row with explicitly specified rowid value 1234. A blob 
    -- containing an array of 32-bit IEEE floating point values in machine-byte
    -- format must be bound to parameter :v1.
    INSERT INTO vec1tbl(rowid, vector) (1234, :v1);

    -- Insert a row with an automatically assigned rowid - which will
    -- presumably be retrieved later using sqlite3_last_insert_rowid() or 
    -- similar.
    INSERT INTO vec1tbl(vector) (:v2);

The virtual table will resist attempts to insert anything other than a blob into the "vector" column. And, once the first vector has been inserted, it will also refuse to accept blobs of a different length. All vectors must have the name number of dimensions.

Once the virtual table is populated, it may be used as a table-valued function for nearest-neighbor queries on its contents. For example:

    -- Retrieve the rowid values identifying the 10 nearest-neighbors 
    -- to vector :v. Parameter :v must be a blob containing a vector with
    -- the same number of dimensions as the table contents. 
    SELECT rowid FROM vec1tbl(:v, '{k: 10}');

The above works, but there are two drawbacks:

  1. Performance is poorer than it could be, and
  2. The distance metric used to determine the nearest-neighbors is always Euclidean.

Fortunately, both these problems can be addressed by configuring the virtual table.

2. NN and ANN Configurations

It is currently considered impractical to provide exact results to a nearest-neighbor (NN) query without an exhaustive search, which can be slow. So many systems compromise and implement approximate nearest-neighbor (ANN) queries. The results returned may not be the true nearest-neighbors, but they'll usually be pretty close, and can be computed far more quickly than an exhaustive search. For many applications this tradeoff - slightly lower accuracy in exchange for much lower latency - is acceptable.

Vec1 may be configured to support either NN or ANN queries. Use NN mode if:

Otherwise, use ANN mode.

2.1. Exhaustive Search (NN) Modes

If exact results are required, or using a trained ANN model is impractical for some reason, vec1 may still be used in either of the following modes:

To set a vec1 table to one of the above NN modes, an SQL statement like:

    -- Persistently configure the vec1 table to use flat index mode with
    -- the Euclidian (l2) distance metric.
    -- 
    INSERT INTO vec1tbl(cmd, arg) VALUES('rebuild', '{index:"flat", distance:"l2"}');

The JSON object written to the "arg" column supports two parameters:

Because they always return exact results, queries against vec1 in NN mode do NOT benefit from reranking.

2.2. Approximate (ANN) NN mode

To be most useful with a substantial number of vectors, a vec1 table should be configured to provide ANN search using a trained model.

2.2.1. Theory

Approximate Nearest-Neighbor search in this system is implemented using IVFADC (sometimes called IVFPQ). There are many good introductions to this on the internet, but briefly:

2.2.2. Training and Index Building

Practically, a vec1 ANN model is a blob returned by running the SQL aggregate function vec1_train() over a representative set of vectors - the training set. For example, to create a model based on the first 100,000 vectors currently stored in table vec1tbl:

    -- Obtain a model - a blob - trained on the first 10,000 rows of
    -- table vec1tbl.  
    WITH training_set(vector) AS (
      SELECT vector FROM vec1tbl LIMIT 100000
    )
    SELECT 
      vec1_train(vector, '{codesize: 16, nbucket: 1024, distance: "cos"}')
    FROM training_set;

The first parameter passed to vec1_train() is a training vector. The second parameter is a JSON object specifying parameters for the model training. These parameters are currently supported:

Once obtained, a model is provided to the vec1 table using a special INSERT command:

    -- Provide a model - a blob returned by vec1_train() - to the 
    -- vec1 virtual table. 
    INSERT INTO vec1tbl(cmd, arg) VALUES('rebuild', :model);

The 'rebuild' command above provides the model to the vec1 virtual table and tells it to build its index based on the model and its current contents. Following this, nearest-neighbor queries should run faster and use the correct distance metric.

A new model may be provided to an existing table at any time. The old index and model are discarded before the new ones are installed and built. Models may be trained on one host and used on another, provided that the hosts use the same byte-ordering for 32-bit floating point values.

Training models and building indexes are both compute-heavy operations. Vec1 can be configured to use multiple threads using the vec1_config scalar function, as shown below. This setting applies to the database connection - it affects all training and rebuilding operations performed using the same (sqlite3*) handle. This should not be set to value greater than the number of real cores that the CPU has.

    -- Configure vec1 to use 8 threads for both training and index building
    SELECT vec1_config('nthread', 8);

Selecting the nbucket, codesize and quantizer parameters for an index can be difficult. Oft repeated guidelines are:

It is not usually necessary to train on the entire dataset, especially if the dataset is large. A representative sample of (100 * nbucket) vectors, where nbucket is the value assigned to the nbucket parameter, is often recommended. Using a smaller sample is also possible, but index performance and recall may degrade.

A representative sample is often a random sample. A random sample may be extracted from a table and used to train a model as follows:

    -- Extract roughly 100,000 random rows from vec1 table v1 and 
    -- train a model with the results.
    SELECT 
      vec1_train(v1.vector, '{nbucket:1000,codesize:32,quantizer:"opq"}') 
    FROM v1 
    WHERE (
        (abs(random()) / 9223372036854775807.0) * (SELECT count(*) FROM v1) < 100_000
    );

Often the best thing to do is to experiment with a variety of different parameters. Application developers need not regard these as set in stone. New models may be trained and indexes rebuilt as the dataset evolves.

2.2.4. Querying

Vec1 tables in ANN mode are queried in the same way as other vec1 tables, except that an extra JSON parameter, "nprobe", is relevant. For example:

    -- Retrieve 50 approximate nearest-neighbors to vector :v. Search
    -- 8% of the buckets in the index to find results.  
    SELECT rowid FROM vec1tbl(:v, '{k:50, nprobe:0.08}');

Currently, three query parameters are supported:

Larger values of nprobe improve the quality of results returned, but also increase query processing time.

2.2.5. Reranking

Unless the model uses codesize of 0, vec1 returns nearest-neighbors based on computing the distance between the query vector and the compressed vectors stored in the index. And because these vectors are heavily compressed (often 32 times or more), there is a discrepancy between the distance between the query vector and the compressed vector, and the distance between the query vector and the actual, uncompressed database vector. This difference is enough to make results look quite poor.

The standard solution is "reranking". Reranking is basically saying - "instead of asking the index for the best 10 matches, I'll ask it for the best 100, then calculate the distances between the query vector and the actual vectors for those 100 and return the best 10". Because it's more flexible and just as easy to do in SQL, vec1 does not provide an option to automatically rerank results. For example:

    SELECT rowid, vector 
    FROM vec1tbl(:v, '{k:100}')            -- 1. grab 100 neighbors from the index
    ORDER BY vec1_l2_distance(:v, vector)  -- 2. order them by actual distance 
    LIMIT 10;                              -- 3. return only the best 10

The query above uses vec1_l2_distance(), a scalar function for calculating the Euclidean distance between two vectors of the same length. There is also vec1_cos_distance(), to be used with vec1 tables that use cosine distance.

There are some tests run on publicly available datasets here that show clearly the advantages of reranking.

To be 100% clear, reranking is usually essential for ANN queries with vec1. Unless you know otherwise, you need it. Unless of course you have a model with "codesize:0". Then it's pointless extra work.

4. Filtered Vector Queries

Many applications require more than simply the nearest K neighbors to a query vector. Often the results must also satisfy additional database criteria. For example, a user searching an online store might want the nearest 10 items to a query vector that are in stock and cost less than $200.

Vec1 offers two features to facilitate these types of queries:

4.1. Streaming Queries

Consider the following schema:

    -- Each row in vec1products has a corresonding row in table products,
    -- linked by (vec1products.rowid=products.id).
    CREATE VIRTUAL TABLE vec1products USING vec1(vector);
    CREATE TABLE products(
        id INTEGER PRIMARY KEY,
        in_stock BOOLEAN,         -- 1 for in stock
        price INTEGER             -- price in cents
    );

The user wants to find the nearest neighbour vectors corresponding to rows of the products table for which in_stock is true and price is less than 20000. It is awkward to formulate the query in SQL, because you have to pick a fixed value of "K" to pass to the virtual table. No matter what value you pick, it is possible that none of the best K results match the criteria.

A streaming query solves this problem. Internally, vec1 assumes that SQLite will consume roughly K results. However, if SQLite continues to request rows after the first K have been returned, vec1 will continue producing additional results in roughly ascending order of distance to the query vector. Streaming mode is enabled by adding "streaming:1" to the JSON query parameters.

Suppose the user's query vector is :v:

    -- The CTE collects 100 approximate matches that survive the
    -- metadata filters.
    --
    -- "K:200" tells vec1 to expect that roughly 200 rows will be
    -- requested. We estimate that about half will pass the filter.
    -- If more rows are needed, vec1 continues streaming results until
    -- SQLite hits the "LIMIT 100" and stops requesting them.
    WITH best100(rowid, vector) AS (
      SELECT vp.rowid, vp.vector
      FROM vec1products(:v, '{K:200, streaming:1, nprobe:32}') vp
      JOIN products p ON (vp.rowid=p.id)
      WHERE p.in_stock AND p.price < 20000
      LIMIT 100
    )

    -- Rerank the 100 matches from the CTE and return the best 10.
    SELECT rowid FROM best100 
    ORDER BY vec1_l2_distance(:v, vector)
    LIMIT 10;

Using the SQL above, 100 post-filter approximate neighbors are accumulated for reranking before returning the best 10 to the user.

4.2. Metadata Columns

A vec1 table may be configured with metadata columns. Values stored in metadata columns are embedded directly within the ANN index. This allows filters to be applied before computing the distance between database vectors and the query vector. Metadata columns are declared by adding column names after the vector column in the CREATE VIRTUAL TABLE statement. For example:

    CREATE VIRTUAL TABLE vec1products USING vec1(vector, in_stock, price);

Metadata columns do not have declared types. Any valid SQLite column name may be used, except that it must not contain the "=" character. This character is reserved for future extensions.

Any value may be stored in a metadata column. However, the system is optimized for small values - NULL, numbers or small text or blob fields (say 8 bytes).

Metadata values may be read and written like ordinary columns. They also have a useful property: simple WHERE clause expressions that reference metadata columns may be evaluated inside the ANN index search. This allows filtering to occur before the nearest-neighbors are accumulated, which is usually much more efficient than filtering outside the index using streaming queries.

A WHERE clause expression may be evaluated as part of the ANN index search if it:

Expressions that cannot be evaluated inside the ANN search are applied after candidate vectors are returned from the index.

So, for example, the following query retrieves 100 neighbors that match the two constraints from the vec1 table, then reranks them and returns the 10 best results:

    SELECT rowid 
    FROM vec1products(:v, '{K:100}')
    WHERE in_stock = 1 AND price < 20000
    ORDER BY vec1_l2_distance(:v, vector)
    LIMIT 10;

But it is easy to make mistakes when writing this type of query. For example, if the user wrote WHERE in_stock AND price < 20000, which is logically equivalent, the results may differ. In this case the constraint on in_stock would not be evaluated inside the ANN search, because it does not use a comparison operator.

As a result, vec1 would retrieve 100 nearest-neighbors that satisfy (price < 20000), then apply the in_stock filter afterwards. If the in_stock filter removes too many rows, fewer than 10 results may remain. Even if 10 or more rows remain, this is effectively equivalent to silently reducing the value of K, which may reduce recall.

This pitfall can be avoided by formulating the query as follows, which ensures that the LIMIT clause determines how many rows vec1 must produce:

    WITH best100(rowid, vector) AS (
      SELECT rowid, vector
      FROM vec1products(:v, '{}')
      WHERE in_stock = 1 AND price < 20000
      LIMIT 100
    )
    SELECT rowid FROM best100
    ORDER BY vec1_l2_distance(:v, vector)
    LIMIT 10;

In this case, no "K" value at all is passed to the vec1products virtual table. Usually, this would be an error. But, under some circumstances, vec1 is able to use the value attached to a LIMIT clause as its K value. These circumstances are:

If no K value is supplied, and the query cannot use a value extracted from a LIMIT clause, it is an error. This means that if the user made a mistake and accidentally used WHERE clause terms that cannot be handled within the ANN search, SQLite would return an error trying to prepare the SQL statement.

Alternatively, if using the second formulation of the query the user could supply a "K" value and also specify "streaming:1". Then vec1 would handle filtering as part of the ANN search whenever possible, falling back to a streaming query in other cases.