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

cache k-ANN graph in memory

Details

    Description

      Let's keep the graph in memory. Like, in TABLE_SHARE.
      Add nodes there as they're read from the table, e.g. on searches.
      Update on inserts.

      When it'll grow beyond some (configurable) limit, start removing nodes that are close to each other. Or remove the bottom level in HNSW. The goal is to still keep enough in memory to find any row with no more than one table access.

      Not clear how to do transaction isolation.

      Attachments

        Issue Links

          is blocked by

          Task - A task that needs to be done. MDEV-33414 benchmark vector indexes

          • Critical - Crashes, loss of data, severe memory leak.
          • Closed
          is part of

          New Feature - A new feature of the product, which has yet to be developed. MDEV-34939 vector search in 11.7

          • Critical - Crashes, loss of data, severe memory leak.
          • Closed
          relates to

          Epic - Created by Jira Software - do not edit or delete. Issue type for a big user story that needs to be broken down. MDEV-32887 vector search

          • Critical - Crashes, loss of data, severe memory leak.
          • Stalled

          Activity

            Ascending order - Click to sort in descending order
            serg Sergei Golubchik created issue -
            serg Sergei Golubchik made changes -
            Field Original Value New Value
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            Assignee Vicențiu Ciorbaru [ cvicentiu ]
            serg Sergei Golubchik made changes -
            Assignee Vicențiu Ciorbaru [ cvicentiu ] Sergei Golubchik [ serg ]
            serg Sergei Golubchik made changes -
            Fix Version/s 11.6 [ 29515 ]
            serg Sergei Golubchik made changes -
            Priority Major [ 3 ] Critical [ 2 ]
            serg Sergei Golubchik made changes -
            Status Open [ 1 ] In Progress [ 3 ]
            serg Sergei Golubchik made changes -
            Comment [ InnoDB. Solutions:
            # we'll use a separate local cache, in a {{TABLE}}, not {{TABLE_SHARE}}.
            #* not ideal, there can be many TABLE's, with different caches
            #** better would be to have one cache per {{TABLE_SHARE}} per transaction
            #* this cache will be merged into the shared one on commit
            #** otherwise the shared one will become stale as modified nodes won't be re-read from the table
            # the shared cache is always {{READ COMMITTED}}, due to 1. But the transaction may be using {{REPEATABLE READ}}
            #* it'll need to verify every position from the cache, whether it's visible or not. While {{rnd_pos()}} will do, a faster alternative is desirable
            #* the cache will work better in corner cases (less "approximate") if InnoDB will always use read-committed when accessing the hlindex. Likely, need new handler API for that
            # solved by 1 ]
            serg Sergei Golubchik made changes -
            Status In Progress [ 3 ] In Testing [ 10301 ]
            serg Sergei Golubchik made changes -
            Fix Version/s 11.7 [ 29815 ]
            Fix Version/s 11.6 [ 29515 ]
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            Component/s Vector search [ 20205 ]
            Fix Version/s 11.7.1 [ 29913 ]
            Fix Version/s 11.7 [ 29815 ]
            Resolution Fixed [ 1 ]
            Status In Testing [ 10301 ] Closed [ 6 ]

            People

              serg Sergei Golubchik
              serg Sergei Golubchik
              Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved:

                Git Integration

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