# Vector search in GizDB

GizDB keeps vectors in ordinary columns and finds their nearest neighbors with an HNSW index. The SQL is the SQL of
pgvector: the types `vector`, `halfvec` and `sparsevec`, the operators `<->`, `<=>` and `<#>`, `USING hnsw` and
`hnsw.ef_search`. A pgvector client, ORM or tutorial works without a change. The index is built with the rows, commits
with them and follows the permission rules of the table. There is no second server and no extension to install.

This guide is for developers who know SQL. You can search a table of embeddings from any PostgreSQL client in about ten
minutes.

- Part 1 is a tutorial. You make a table of vectors, find the nearest rows and meet the dimension check.
- Part 2 has how-to guides, one task each: index a table, filter, tune, load data, and search data that is larger than
  memory.
- Part 3 is the reference: types, operators, functions, index options and counters.

Each output on this page is the real output of its example, run on the GizDB development build with `psql`.

## Before you start

You need a GizDB server and `psql`. Refer to [Use GizDB](data.md) to start the server on port 61201 and connect:

```sh
psql -h 127.0.0.1 -p 61201 -U postgres
```

You do not need to turn the vector support on. The types and operators are always there.

## Tutorial: find the nearest rows

### Step 1: make a table of vectors

A `vector(3)` column holds vectors of exactly three numbers. Real embeddings have hundreds of dimensions; three keep
this table readable. The vectors are in the order apple, pear, lemon, lime and plum.

```sql
CREATE TABLE fruit (id int PRIMARY KEY, name text, v vector(3));
INSERT INTO fruit VALUES
  (1, 'apple', '[1, 0.1, 0]'), (2, 'pear', '[0.9, 0.2, 0.1]'), (3, 'lemon', '[0.1, 1, 0]'),
  (4, 'lime', '[0.2, 0.9, 0.1]'), (5, 'plum', '[0, 0.2, 1]');
```

```text
CREATE TABLE
INSERT 0 5
```

### Step 2: find the three nearest

`<->` is the Euclidean (L2) distance. Order by it and limit the rows to get the nearest.

```sql
SELECT name, round((v <-> '[1, 0, 0]')::numeric, 3) AS distance
FROM fruit ORDER BY v <-> '[1, 0, 0]' LIMIT 3;
```

```text
 name  | distance
-------+----------
 apple |    0.100
 pear  |    0.245
 lime  |    1.208
(3 rows)
```

### Step 3: choose the distance

Three operators give three distances. The nearest row is the one with the smallest value.

| Operator | Distance | Use it for |
| --- | --- | --- |
| `<->` | Euclidean (L2) | Vectors where length matters |
| `<=>` | Cosine distance, `1 - cosine similarity` | Text embeddings; only the direction matters |
| `<#>` | Negative inner product | Normalized vectors, or a ranking by dot product |

```sql
SELECT name, round((v <=> '[0, 1, 0]')::numeric, 3) AS cosine FROM fruit ORDER BY v <=> '[0, 1, 0]' LIMIT 2;
SELECT name, round((v <#> '[1, 0, 0]')::numeric, 2) AS neg_inner FROM fruit ORDER BY v <#> '[1, 0, 0]' LIMIT 2;
```

```text
 name  | cosine
-------+--------
 lemon |  0.005
 lime  |  0.030
(2 rows)

 name  | neg_inner
-------+-----------
 apple |     -1.00
 pear  |     -0.90
(2 rows)
```

The inner product is negated so that, as for the other two, the smallest value is the nearest.

### Step 4: meet the dimension check

A vector must have the dimension of its column.

```sql
INSERT INTO fruit VALUES (9, 'bad', '[1, 2]');
```

```text
ERROR:  expected 3 dimensions for column v, not 2
```

Small tables need no index: the search reads every row, and the answer is exact. The next part makes a table that is
large enough to need one.

## How-to guides

### Index a table

An index makes a search read a small part of the rows. This table has 30,000 vectors of 8 dimensions in 5 tenants.

```sql
CREATE TABLE items (id int PRIMARY KEY, tenant int, v vector(8));
INSERT INTO items
SELECT i, i % 5, ('[' || ((i * 7919) % 1009) / 1009.0 || ',' || ((i * 6007) % 1013) / 1013.0 || ','
                      || ((i * 4999) % 1019) / 1019.0 || ',' || ((i * 3001) % 1021) / 1021.0 || ','
                      || ((i * 2003) % 1031) / 1031.0 || ',' || ((i * 1009) % 1033) / 1033.0 || ','
                      || ((i * 701) % 1039) / 1039.0 || ',' || ((i * 503) % 1049) / 1049.0 || ']')::vector
FROM generate_series(1, 30000) i;
CREATE INDEX items_v ON items USING hnsw (v vector_l2_ops);
```

```text
CREATE TABLE
INSERT 0 30000
CREATE INDEX
```

Name the operator class that matches the operator you search with:

| Operator class | Operator |
| --- | --- |
| `vector_l2_ops` | `<->` |
| `vector_cosine_ops` | `<=>` |
| `vector_ip_ops` | `<#>` |

A query that orders by another distance than the index's gives the same rows through a full sort; it does not use the
index. `ivfflat` and `diskann` are accepted in `USING` and build the same index, so a script written for pgvector runs.

Search as before. The index answers `ORDER BY distance LIMIT k`, with an `OFFSET` and with any `WHERE`.

```sql
SELECT id FROM items ORDER BY v <-> '[0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5]' LIMIT 5;
```

```text
  id
-------
  2562
  8326
 17711
  3730
 17413
(5 rows)
```

The index finds neighbors approximately. Most of the true nearest rows are in the answer, and the next section shows how
to ask for more of them.

### Tune recall and speed

`hnsw.ef_search` is how many candidates a search keeps. A larger value finds more of the true nearest rows and takes
longer. The default is 40, as in pgvector.

```sql
SET hnsw.ef_search = 64;
```

This table is the result on 1 million vectors of 128 dimensions (SIFT) in memory, with one connection. Recall is the
share of the true ten nearest rows in the answer.

| `ef_search` | 16 | 40 | 64 | 128 | 512 |
| --- | --: | --: | --: | --: | --: |
| Recall of 10 | 0.885 | 0.966 | 0.984 | 0.996 | 0.999 |
| Queries a second | 9,746 | 6,601 | 5,038 | 3,137 | 1,037 |

Your data decides the numbers. To find the value for your table, take a few hundred real queries, compare the answer of
the index with the exact answer, and raise `ef_search` until the recall is what you need. To get the exact answer, order
by the distance plus zero: `ORDER BY (v <-> q) + 0` is another expression, so the index is not used.

A filter that passes only a share of the rows widens the search by itself, so the number of rows you get does not fall.

### Filter, page and search a range

A `WHERE` clause on other columns works. The search takes the rows the filter passes.

```sql
SELECT id FROM items WHERE tenant = 3 ORDER BY v <-> '[0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5]' LIMIT 5;
```

```text
  id
-------
 17413
 18568
 16543
  8028
 17498
(5 rows)
```

- When the filter passes few rows, GizDB ranks them exactly instead of walking the graph, so the answer is exact.
- `LIMIT 10 OFFSET 5` pages through the nearest rows.
- `WHERE v <-> q < 0.05` is a range search: it returns the rows within the radius, up to the `LIMIT`.
- Rows you wrote in the current transaction are in the answer. A row you updated or deleted is not.

### Load vectors

- `INSERT ... VALUES` and `INSERT ... SELECT`, as above.
- `COPY items FROM STDIN` in the text format, and the binary format of pgvector.
- A Parquet file with a `LIST<FLOAT>` column: `INSERT INTO items SELECT * FROM read_parquet('items.parquet')`. The files
  are those of the server's `--files` folder; refer to [Operate the GizDB server](../operations/gizdb-server.md).

Create the index before or after the load. After a load of many rows the index is built in one pass when the rows are
written to a segment file, which is faster than one row at a time. Rows that are not in a segment yet are searched
exactly, so an answer always includes them.

### Choose the codes of the index

A search walks the graph on short codes of the vectors and then ranks the nearest candidates by their exact distance.
The option `quantizer` chooses the codes:

```sql
CREATE INDEX items_q ON items USING hnsw (v vector_l2_ops)
  WITH (quantizer = rabitq, graph = auto);
```

| `quantizer` | Codes | Use it |
| --- | --- | --- |
| `rabitq` (default) | 4 bits a dimension (RaBitQ) | Almost always. The recall of `sq8` at half the bytes. |
| `sq8` | 1 byte a dimension | A faster build; the codes are twice as large. |
| `none` | The vectors | Vectors of a few dimensions, where codes save nothing. |

`pg_indexes` shows the options:

```sql
SELECT indexdef FROM pg_indexes WHERE indexname = 'items_q';
```

```text
                                                 indexdef
-----------------------------------------------------------------------------------------------------------
 CREATE INDEX items_q ON public.items USING hnsw (v vector_l2_ops) WITH (quantizer='rabitq', graph='auto')
(1 row)
```

The options `bits` (4 or 8) and `ef_construction` go in the same list: `bits = 8` gives RaBitQ 8 bits a dimension, and very short vectors use it without being asked. A larger
`ef_construction` (4 to 1000, default 128) builds a better graph more slowly. An invalid value is an error:

```sql
CREATE INDEX x ON items USING hnsw (v vector_l2_ops) WITH (quantizer = pq);
```

```text
ERROR:  invalid value for enum option "quantizer": pq
```

### Search data that is larger than memory

You do not have to fit the vectors in memory. The server keeps a table's data in memory up to a budget that it sizes
from the host, and moves the oldest segments of the table out to their files when the data grows past it. There is
nothing to set. An index on a segment that left memory keeps in memory only what a search needs to walk: the short
codes, the upper levels of the graph and, if they fit, the level 0 links. The vectors stay in the file, and a search
reads back about 70 of them (for `LIMIT 10`) in one batch.

The option `graph` chooses where the level 0 links of such a segment are:

| `graph` | In memory | A search reads from the file |
| --- | --- | --- |
| `auto` (default) | The links while they take at most a quarter of the budget, else not | As the choice made |
| `memory` | The codes and the links | The vectors of the nearest `4 × LIMIT` candidates, in one batch |
| `disk` | The codes only | The links and vectors of each 4 nodes it takes, in one batch each (about 340 rows) |

The recall of a search on a segment in the file is that of the same search in memory. This table is 1 million SIFT
vectors with a data budget of 32 MB, one connection:

| `ef_search` | `graph = memory` | `graph = disk` | All in memory |
| --- | --- | --- | --- |
| 16 | 0.885, 5,815 a second | 0.906, 2,781 | 0.885, 9,746 |
| 64 | 0.984, 3,741 | 0.985, 2,130 | 0.984, 5,038 |
| 128 | 0.9955, 2,477 | 0.9957, 1,361 | 0.9955, 3,137 |

`memory` is the fastest. `disk` needs the least memory (about 75 MB of codes for the million vectors). Leave `auto` unless
you want the same behavior on every host.

### Check that the index answers

`pg_stat_gizdb` counts what the vector search did. Read the counters before and after your query:

```sql
SELECT vector_searches, vector_direct, vector_filtered, vector_disk_rows FROM pg_stat_gizdb;
```

```text
 vector_searches | vector_direct | vector_filtered | vector_disk_rows
-----------------+---------------+-----------------+------------------
               5 |             4 |               1 |                0
(1 row)
```

If a query returns the right rows but `vector_searches` does not change, the index did not answer it: for example, the
distance in the query is not the index's.

### Other vector types and functions

`halfvec` stores 16-bit numbers and `sparsevec` stores only the non-zero elements, as `{index:value,...}/dimensions`.
The functions of pgvector are there:

```sql
SELECT '[1,2,3]'::halfvec(3), '{1:1.5,3:2}/5'::sparsevec;
SELECT l2_normalize('[3, 4]'::vector), subvector('[1,2,3,4,5]'::vector, 2, 3);
SELECT '[1,2,3]'::vector + '[1,1,1]'::vector;
```

```text
 halfvec |   sparsevec
---------+---------------
 [1,2,3] | {1:1.5,3:2}/5
(1 row)

 l2_normalize | subvector
--------------+-----------
 [0.6,0.8]    | [2,3,4]
(1 row)

 ?column?
----------
 [2,3,4]
(1 row)
```

To combine a vector search with a text search in one query, refer to *Search text and vectors* in
[Use GizDB](data.md).

### Move from pgvector

Use the same SQL. The differences you can meet:

- `ivfflat` and `diskann` indexes are built as HNSW indexes. Their other parameters, such as `lists`, are accepted and not used.
- The index options are `quantizer`, `bits`, `ef_construction` and `graph`. `m` is accepted and not used.
- Data larger than memory is searched from its segment files (refer to the how-to guide above).

## Reference

### Types

| Type | Holds |
| --- | --- |
| `vector(n)` | `n` 32-bit floats |
| `halfvec(n)` | `n` 16-bit floats |
| `sparsevec(n)` | up to `n` elements, as `{index:value,...}/n` |

NaN and infinite values are errors (SQLSTATE 22000), and so is a vector of a wrong dimension.

### Operators and functions

| Operator | Function | Meaning |
| --- | --- | --- |
| `<->` | `l2_distance` | Euclidean distance |
| `<=>` | `cosine_distance` | Cosine distance |
| `<#>` | `negative_inner_product` | Negative inner product (`inner_product` is the positive value) |
| `<+>` | `l1_distance` | Taxicab distance |
| `+`, `\|\|` | | Add by element, concatenate |

Other functions: `vector_dims`, `vector_norm`, `l2_normalize`, `subvector`, `binary_quantize`, and the aggregates `sum` and
`avg` over vectors.

### Index options

| Option | Values | Default | Meaning |
| --- | --- | --- | --- |
| `quantizer` | `rabitq`, `sq8`, `none` | `rabitq` | The codes a search walks on |
| `bits` | `4`, `8` | by dimension | Bits a dimension of `rabitq` codes |
| `ef_construction` | 4 to 1000 | 128 | The breadth of the build's search |
| `graph` | `auto`, `memory`, `disk` | `auto` | Where a segment in its file keeps the level 0 links |

### Settings

| Setting | Default | Meaning |
| --- | --- | --- |
| `hnsw.ef_search` | 40 | The candidates a search keeps |

### Counters in `pg_stat_gizdb`

| Counter | Counts |
| --- | --- |
| `vector_searches` | Queries that the index answered |
| `vector_direct` | Answers that the search ordered itself, with no generic sort |
| `vector_filtered` | Searches that applied a filter before the walk |
| `vector_disk_rows` | Vectors read back from segment files |