Skip to content

ARCHITECTURE.md

Latest commit

 

History

History
423 lines (329 loc) · 18.8 KB

ARCHITECTURE.md

File metadata and controls

423 lines (329 loc) · 18.8 KB
Raw

sqlite-vec Architecture

Internal documentation for how sqlite-vec works under-the-hood. Not meant for users of the sqlite-vec project, consult the official sqlite-vec documentation for how-to-guides. Rather, this is for people interested in how sqlite-vec works and some guidelines to any future contributors.

Very much a WIP.

vec0

Shadow Tables

xyz_chunks

  • chunk_id INTEGER
  • size INTEGER
  • validity BLOB
  • rowids BLOB

xyz_rowids

  • rowid INTEGER
  • id
  • chunk_id INTEGER
  • chunk_offset INTEGER

xyz_vector_chunksNN

  • rowid INTEGER
  • vectors BLOB

xyz_rescore_chunksNN

The vectors of a column indexed by rescore(), quantized, in the layout of xyz_vector_chunksNN.

  • rowid INTEGER
  • vectors BLOB

xyz_rescore_vectorsNN

The float32 vectors of a column indexed by rescore(), one row per row of the table.

  • rowid INTEGER
  • vector BLOB

xyz_vectorsNN

The vectors of a column indexed by diskann(), one row per row of the table.

  • rowid INTEGER
  • vector BLOB

xyz_diskann_nodesNN

The graph of a column indexed by diskann(), one row per node. A node has n_neighbors slots: neighbors_validity holds a bit per slot, set when the slot holds a neighbor, neighbor_ids the neighbor's rowid as a 64-bit integer in the machine's byte order, and neighbor_quantized_vectors its vector quantized by the column's neighbor_quantizer, a bit or a byte per dimension. The diskann_medoid_NN row of xyz_info names the node every search starts at, and is NULL while the graph has no node.

  • rowid INTEGER
  • neighbors_validity BLOB
  • neighbor_ids BLOB
  • neighbor_quantized_vectors BLOB

xyz_diskann_bufferNN

The vectors of a column indexed by diskann(..., buffer_threshold=N) that have not joined the graph yet.

  • rowid INTEGER
  • vector BLOB

A table whose every vector column is indexed by diskann() keeps no chunks: its xyz_chunks stays empty, and its xyz_rowids rows have no chunk_id or chunk_offset.

xyz_auxiliary

  • rowid INTEGER
  • valueNN [type]

xyz_metadatachunksNN

  • rowid INTEGER
  • data BLOB

xyz_metadatatextNN

  • rowid INTEGER
  • data TEXT

Identifying shadow tables

The supported way to tell which tables belong to a vec0 table is by name. A vec0 table xyz owns these tables and no others (NN is two digits):

  • xyz_info, xyz_chunks, xyz_rowids: always
  • xyz_vector_chunksNN: one per vector column, except those indexed by rescore() or diskann()
  • xyz_rescore_chunksNN, xyz_rescore_vectorsNN: one each per vector column indexed by rescore()
  • xyz_vectorsNN, xyz_diskann_nodesNN, xyz_diskann_bufferNN: one each per vector column indexed by diskann()
  • xyz_auxiliary: only if there are auxiliary columns
  • xyz_metadatachunksNN: one per metadata column
  • xyz_metadatatextNN: one per text metadata column

This query lists them for every vec0 table in a database. It reads only sqlite_master, so it works on every SQLite version and on a connection that has not loaded sqlite-vec:

select v.name as vec0_table, s.name as backing_table
from sqlite_master as v
join sqlite_master as s
  on s.type = 'table'
 and substr(s.name, 1, length(v.name) + 1) = v.name || '_'
 and (substr(s.name, length(v.name) + 2) in ('rowids', 'chunks', 'info', 'auxiliary')
   or substr(s.name, length(v.name) + 2) glob 'vector_chunks[0-9][0-9]'
   or substr(s.name, length(v.name) + 2) glob 'rescore_chunks[0-9][0-9]'
   or substr(s.name, length(v.name) + 2) glob 'rescore_vectors[0-9][0-9]'
   or substr(s.name, length(v.name) + 2) glob 'vectors[0-9][0-9]'
   or substr(s.name, length(v.name) + 2) glob 'diskann_nodes[0-9][0-9]'
   or substr(s.name, length(v.name) + 2) glob 'diskann_buffer[0-9][0-9]'
   or substr(s.name, length(v.name) + 2) glob 'metadatachunks[0-9][0-9]'
   or substr(s.name, length(v.name) + 2) glob 'metadatatext[0-9][0-9]')
where v.type = 'table' and v.rootpage = 0
  and v.sql like 'create virtual table%using vec0%'
order by 1, 2;

type = 'shadow' in PRAGMA table_list is best-effort and should not be relied on:

  • A connection that has not loaded sqlite-vec reports every backing table as table.
  • Up to SQLite 3.53, so does a connection that parsed the schema before loading the extension.
  • Before SQLite 3.37 there is no PRAGMA table_list and no prefix marking (see below), so the tables whose suffix has an underscore (vector_chunksNN, rescore_chunksNN, rescore_vectorsNN, diskann_nodesNN, diskann_bufferNN) are never shadow tables.
  • SQLite finds the virtual table that owns a newly created or newly parsed table by splitting its name at the last underscore (documented). For xyz_vector_chunks00 it looks for a virtual table called xyz_vector, so xShadowName is never asked about it on that path.
  • xShadowName does report those suffixes, and SQLite also marks shadow tables by name prefix when it parses the virtual table's own schema entry. That only sees tables parsed earlier, which in practice means after a VACUUM (it rewrites sqlite_master with virtual tables last). A vec0 table created after that VACUUM is not covered until the next one.
  • SQLite 3.54 additionally marks by prefix after every xConnect. There those tables become shadow once the vec0 table has been used in the connection, except in the connection that created it. PRAGMA table_list connects every virtual table first, so it always reports them as shadow, but under SQLITE_DBCONFIG_DEFENSIVE a direct write to one of them is still accepted until the vec0 table is first touched. This prefix matching is not part of the documented contract.

Rules that follow from this:

  • A new backing table that has no upstream counterpart should use a suffix without underscores (metadatachunksNN, not metadata_chunksNN), so that it follows the documented rule. A table ported from upstream keeps upstream's name, to stay file-compatible, and is added to vec0ShadowName.
  • xyz_vector_chunksNN is not renamed, because that would make databases unreadable by upstream sqlite-vec and by earlier releases of this fork.
  • Do not rename a backing table from inside xConnect. In vlasky/sqlite-vec's test of a minimal module under AddressSanitizer on SQLite 3.45.3, an ALTER TABLE ... RENAME issued there was a heap-use-after-free in the statement that triggered the connect.

idxStr

The vec0 idxStr is a string composed of a single "header" character and 0 or more "blocks" of 4 characters each.

The "header" character denotes the type of query plan, as determined by the enum vec0_query_plan values. The current possible values are:

Name Value Description
VEC0_QUERY_PLAN_FULLSCAN '1' Perform a full-scan on all rows
VEC0_QUERY_PLAN_POINT '2' Perform a single-lookup point query for the provided rowid
VEC0_QUERY_PLAN_KNN '3' Perform a KNN-style query on the provided query vector and parameters.

Each 4-character "block" is associated with a corresponding value in argv[]. For example, the 1st block at byte offset 1-4 (inclusive) is the 1st block and is associated with argv[0]. The 2nd block at byte offset 5-8 (inclusive) is associated with argv[1] and so on. Each block describes what kind of value or filter the given argv[i] value is.

A KNN plan needs its arguments: the MATCH on a vector column, k, and mmr_lambda. When one of them reads another table of the query, SQLite also weighs plans that scan vec0 before that table, in which the argument is unusable. xBestIndex returns SQLITE_CONSTRAINT for such a plan (vec0_constraint_is_knn_argument), so the planner takes one that gives vec0 every argument.

Filters on rowid, partition key, metadata, and distance columns are not refused this way. A filter whose value comes from another table is unusable in a plan that scans vec0 first, and xBestIndex reports the same cost for that plan as for one with the filter. When the query lets SQLite scan vec0 first, SQLite uses the plan without the filter, even if it scans the other table first, and applies the filter to the k rows vec0 returns. That keeps a lookup join at k rows, and vec0 cannot tell a lookup join from a filter join. In

select v.rowid, c.name from v join categories c on c.id = v.category
where v.embedding match ? and k = 10

refusing the plan without v.category = c.id would run one KNN per categories row and return 10 rows per category. vlasky/sqlite-vec#14 refuses those plans as well; this fork takes only its argument part.

When the query requires the other table to be read before vec0, because the table supplies a KNN argument, a CROSS JOIN names it first, or vec0 is on the right of a LEFT JOIN, every plan has the filter usable, so vec0 runs once per row of that table and applies the filter before the k. In a LEFT JOIN this holds only for a filter in the ON clause: a filter in the WHERE clause applies to the k rows each KNN returns, whichever table supplies the arguments. A correlated subquery, whose outer columns are constants to vec0, also applies the filter before the k. tests/test-knn-joined-constraints.py pins the lookup join and the case of a table that supplies an argument.

VEC0_IDXSTR_KIND_KNN_MATCH ('{')

argv[i] is the query vector of the KNN query.

The remaining 3 characters of the block are _ fillers.

VEC0_IDXSTR_KIND_KNN_K ('}')

argv[i] is the limit/k value of the KNN query.

The remaining 3 characters of the block are _ fillers.

VEC0_IDXSTR_KIND_KNN_ROWID_IN ('[')

argv[i] is the optional rowid in (...) value, and must be handled with sqlite3_vtab_in_first() / sqlite3_vtab_in_next().

The remaining 3 characters of the block are _ fillers.

VEC0_IDXSTR_KIND_KNN_ROWID_EQ ('=')

argv[i] is the optional rowid = ? value, or id = ? for a table with a primary key column. SQLite also passes a one-value rowid in (?) this way. vec0 restricts the KNN search to the row it names, as it does for each value of a '[' list, so a query has at most one of the two blocks: with both constraints, vec0 takes the = value and leaves the list to SQLite. It leaves a text primary key constraint whose collation is not BINARY to SQLite. For a text primary key, a value that is not text names no row, in this block or in a '[' list.

The remaining 3 characters of the block are _ fillers.

VEC0_IDXSTR_KIND_KNN_PARTITON_CONSTRAINT (']')

argv[i] is a "constraint" on a specific partition key.

The second character of the block denotes which partition key to filter on, using A to denote the first partition key column, B for the second, etc. It is encoded with 'A' + partition_idx and can be decoded with c - 'A'.

The third character of the block denotes which operator is used in the constraint. It will be one of the values of enum vec0_partition_operator. vec0_chunks_iter() turns each block into a condition on the _chunks table's partitionNN column:

Operator Value Condition
EQ 'a' partitionNN = ?
GT 'b' partitionNN > ?
LE 'c' partitionNN <= ?
LT 'd' partitionNN < ?
GE 'e' partitionNN >= ?
NE 'f' partitionNN != ?
IN 'g' partitionNN IN (?, ...)
LIKE 'h' partitionNN LIKE ?
GLOB 'i' partitionNN GLOB ?
IS 'j' partitionNN IS ?
ISNOT 'k' partitionNN IS NOT ?
ISNULL 'l' partitionNN IS NULL
ISNOTNULL 'm' partitionNN IS NOT NULL

argv[i] of an IN block is read with sqlite3_vtab_in_first() / sqlite3_vtab_in_next(), and each of its values is bound to its own parameter of the _chunks query, so the query fails to prepare when the distinct values of its IN blocks and its other partition key values together number more than SQLITE_LIMIT_VARIABLE_NUMBER. ISNULL and ISNOTNULL blocks bind nothing.

These conditions see only argv[i]'s value, not the affinity of the expression that produced it, so p IS CAST(5 AS INTEGER) does not match a text '5'. On a text key, EQ and the range operators compare under the collation sqlite3_vtab_collation() reports, which the fourth character of the block carries as for a metadata constraint ('_', 'n' or 'r', below) and vec0_chunks_iter() appends to the condition as COLLATE NOCASE or COLLATE RTRIM; xBestIndex rejects any other collation on them. LIKE and GLOB keep their own case rules, and LIKE follows PRAGMA case_sensitive_like. An IN or IS constraint is encoded as such only when sqlite3_vtab_collation() reports BINARY: an IN with another collation is encoded as EQ, which SQLite runs once per value that is distinct under that collation, as before vec0 encoded IN, and an IS with another collation is left to SQLite. SQLite reports BINARY for NE and IS NOT whatever collation the query names, so on a text key xBestIndex leaves omit unset for them and SQLite re-checks each row.

The fourth character of the block is the collation of a text key's EQ or range constraint, and a _ filler otherwise.

VEC0_IDXSTR_KIND_POINT_ID ('!')

argv[i] is the value of the rowid or id to match against for the point query. For a text primary key, xBestIndex leaves omit unset and SQLite re-checks the row: vec0 looks the id up in _rowids.id, which is declared TEXT, so the integer 5 finds '5', and SQLite drops that row unless the other side of the = has numeric affinity.

The remaining 3 characters of the block are _ fillers.

VEC0_IDXSTR_KIND_METADATA_CONSTRAINT ('&')

argv[i] is the value of the WHERE constraint for a metadata column in a KNN query.

The second character of the block denotes which metadata column the constraint belongs to, using A to denote the first metadata column, B for the second, etc. It is encoded with 'A' + metadata_idx and can be decoded with c - 'A'.

The third character of the block is the constraint operator. It will be one of enum vec0_metadata_operator, as only a subset of operators are supported on metadata column KNN filters.

The fourth character of the block is the collation a text constraint compares with, one of enum vec0_metadata_collation:

Collation Value
BINARY '_'
NOCASE 'n'
RTRIM 'r'

Only =, IS, <, <=, >, >=, and IN constraints on a text column carry the collation that sqlite3_vtab_collation() reports for them; xBestIndex rejects any other collation on them. SQLite also calls xBestIndex with each branch of an OR offered as a constraint, which vec0 cannot tell from a top-level one, so the error fires for such a constraint inside an OR too, although SQLite may evaluate that OR itself.

Every other constraint carries '_': SQLite compares an INTEGER or REAL without a collation, LIKE and GLOB have their own case rules, and SQLite reports BINARY for a text != or IS NOT whatever collation the query names. vec0 compares those two bytewise and leaves omit unset, so SQLite re-checks each row with the query's collation.

vec0 keeps text metadata as UTF-8, while SQLite orders text under BINARY by the bytes of the database's encoding, and UTF-16 orders some characters differently (SQLite registers BINARY in each encoding and NOCASE and RTRIM for UTF-8 only). So vec0_init() reads the encoding into textEncoding, from sqlite3_value_encoding() of a string literal on SQLite 3.41 and later and with PRAGMA encoding before that (no row means UTF-8 only in a build without UTF-16, SQLITE_OMIT_UTF16), and in a UTF-16 database vec0_text_cmp() compares under BINARY by the bytes SQLite stores for each value, converting its UTF-8 as SQLite's utf.c does.

VEC0_IDXSTR_KIND_KNN_DISTANCE_CONSTRAINT ('*')

argv[i] is a constraint on the distance column in a KNN query.

This enables filtering KNN results by distance thresholds, useful for:

  • Cursor-based pagination: WHERE embedding MATCH ? AND k = 10 AND distance > 0.21
  • Range queries: WHERE embedding MATCH ? AND k = 100 AND distance BETWEEN 0.5 AND 1.0

The second character of the block denotes the constraint operator. It will be one of the values of enum vec0_distance_constraint_operator:

Operator Value Description SQL Example
GT 'a' Greater than distance > 0.5
GE 'b' Greater than or equal to distance >= 0.5
LT 'c' Less than distance < 1.0
LE 'd' Less than or equal to distance <= 1.0

The third and fourth characters of the block are _ fillers.

Note on precision: Distance values are cast from f64 to f32 for comparison, which may result in precision loss for very small distance differences.

Note on pagination: When multiple vectors have identical distances, pagination using distance > X may skip some results. For stable pagination, combine distance with rowid: WHERE (distance > 0.5) OR (distance = 0.5 AND rowid > 123). On a column indexed by rescore(), distance constraints filter only the k * oversample candidates (five times that with MMR, at most 4096), so paging with distance > X reaches at most that many rows. On a column indexed by diskann(), they filter only the rows the search found, the larger of the search list size and k (five times k with MMR, at most 4096) plus every row in the buffer, so paging reaches at most that many rows too.

VEC0_IDXSTR_KIND_KNN_MMR_LAMBDA ('#')

argv[i] is the value of the optional mmr_lambda = ? constraint of a KNN query. Unless k is 0, vec0Filter_knn applies numeric affinity to it with sqlite3_value_numeric_type(), as SQLite does to a LIMIT value, and fails the query unless it is then an INTEGER or REAL: '0.5' reads as 0.5, and NULL, a blob, or text such as 'abc' fails. It converts the number to f32 and fails the query if it is below 0.0 or above 1.0. For a value below 1.0, it fetches the k * 5 nearest rows (at most 4096) and, if it finds more than k, selects k of them by MMR.

The remaining 3 characters of the block are _ fillers.