Uploaded image for project: 'MariaDB Server'
  1. MariaDB Server
  2. MDEV-33408

HNSW for k-ANN vector searches

    XMLWordPrintable

Details

    • New Feature
    • Status: In Testing (View Workflow)
    • Critical
    • Resolution: Unresolved
    • 11.7
    • None

    Description

      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.

      Attachments

        Issue Links

          Activity

            People

              cvicentiu Vicențiu Ciorbaru
              serg Sergei Golubchik
              Votes:
              3 Vote for this issue
              Watchers:
              12 Start watching this issue

              Dates

                Created:
                Updated:

                Git Integration

                  Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.