For the first iteration of Vector search, we will implement HNSW algorithm.

The implementation will only support Euclidean distance initially.

Basic plan:
Graph construction will be done according to HNSW paper.

Storage wise, we'll store the graph as part of a subtable (MDEV-33404).

The table's definition will be something along these lines:

  CREATE TABLE i (

    level int unsigned not null,

    src varbinary(255) not null,

    dst varbinary(255) not null,

    index (level,src),

    index (level,dst));

For each link in the graph, there will be a corresponding entry in the table.

• src and dst will store handler::position, a quick link to the actual vector blob in the main table.

The index (level,src) will allow for quick jumping between nodes.
To go deeper in search, one just needs to decrement the level and search using the same "src" value.

If src is found on level n, then it is also found on level n - 1 and so on. Level 0 is the base level with all the nodes.

Performance considerations:

• Storing the vector in the subtable might be required. Looking up the blob value in the base table might be too costly.