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

vector search

Details

    • Epic
    • Status: Stalled (View Workflow)
    • Critical
    • Resolution: Unresolved
    • N/A
    • Server
    • vector search

    Description

      A common operation for multi-dimensional vectors is to find k nearest vectors to the given one.
      This task is about implementing indexes that allow to do it fast.

      • ideally they'll be engine independent
      • indexes should be update-able
      • in this task we'll only do Euclidean distance
      • we'll benchmark it on real multi-million-rows data sets
      • what algorithm, exactly, to use is still unclear

      Attachments

        Issue Links

          relates to

          New Feature - A new feature of the product, which has yet to be developed. MDEV-32886 VEC_FromText() and VEC_ToText() functions

          • Major - Major loss of function.
          • Closed

          New Feature - A new feature of the product, which has yet to be developed. MDEV-33404 Engine-independent indexes: subtable method

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

          Task - A task that needs to be done. MDEV-33405 Engine-independent indexes: low-level API method

          • Minor - Minor loss of function, or other problem where easy workaround is present.
          • Closed

          New Feature - A new feature of the product, which has yet to be developed. MDEV-33406 basic optimizer support for k-NN searches

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

          New Feature - A new feature of the product, which has yet to be developed. MDEV-33407 Parser support for vector indexes

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

          New Feature - A new feature of the product, which has yet to be developed. MDEV-33408 HNSW for k-ANN vector searches

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

          New Feature - A new feature of the product, which has yet to be developed. MDEV-33410 VECTOR data type

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

          New Feature - A new feature of the product, which has yet to be developed. MDEV-33411 OPTIMIZE for graph indexes

          • Major - Major loss of function.
          • Open

          Task - A task that needs to be done. MDEV-33413 cache k-ANN graph in memory

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

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

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

          Task - A task that needs to be done. MDEV-33415 graph index search: heuristical edge choice

          • Major - Major loss of function.
          • Closed

          New Feature - A new feature of the product, which has yet to be developed. MDEV-33417 VEC_DISTANCE_COSINE() function

          • Major - Major loss of function.
          • Closed

          Task - A task that needs to be done. MDEV-33419 graph index insert: consider more neighbors

          • Minor - Minor loss of function, or other problem where easy workaround is present.
          • Open

          New Feature - A new feature of the product, which has yet to be developed. MDEV-34436 DDL: per-index attributes

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

          Task - A task that needs to be done. MDEV-34698 mhnsw: support AVX-512 instructions

          • Major - Major loss of function.
          • Closed

          New Feature - A new feature of the product, which has yet to be developed. MDEV-34699 mhnsw: support aarch64 SIMD instructions

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

          Task - A task that needs to be done. MDEV-34804 mhnsw: compiler-independent choice of CPU-specific optimizations

          • Minor - Minor loss of function, or other problem where easy workaround is present.
          • Open

          New Feature - A new feature of the product, which has yet to be developed. MDEV-34805 provide various information about vector indexes

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

          Task - A task that needs to be done. MDEV-34806 mhnsw: use start_bulk_insert to estmate min_rows

          • Minor - Minor loss of function, or other problem where easy workaround is present.
          • Closed

          Task - A task that needs to be done. MDEV-34811 handlerton refactoring

          • Major - Major loss of function.
          • Closed

          New Feature - A new feature of the product, which has yet to be developed. MDEV-35196 XA support for mhnsw indexes

          • Major - Major loss of function.
          • Open

          New Feature - A new feature of the product, which has yet to be developed. MDEV-35264 Improve InnoDB concurrent insert into vector index performance

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

          New Feature - A new feature of the product, which has yet to be developed. MDEV-35283 support nullable indexed vector columns

          • Major - Major loss of function.
          • Open

          New Feature - A new feature of the product, which has yet to be developed. MDEV-35314 multi-part vector indexes

          • Major - Major loss of function.
          • Open

          New Feature - A new feature of the product, which has yet to be developed. MDEV-35315 vector indexes in partitioned tables

          • Major - Major loss of function.
          • Open

          New Feature - A new feature of the product, which has yet to be developed. MDEV-35316 more than one vector index per table

          • Major - Major loss of function.
          • Open

          Task - A task that needs to be done. MDEV-35418 Better support for multiple duplicates vectors in the index

          • Minor - Minor loss of function, or other problem where easy workaround is present.
          • Open

          Epic - Created by Jira Software - do not edit or delete. Issue type for a big user story that needs to be broken down. MDEV-35629 Hybrid Search (Text + Vector) w/ Simple Re-Ranking

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

          Task - A task that needs to be done. MDEV-36184 mhnsw: support powerpc64 SIMD instructions

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

          New Feature - A new feature of the product, which has yet to be developed. MDEV-32885 VEC_DISTANCE() function

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

          New Feature - A new feature of the product, which has yet to be developed. MDEV-33409 Index Condition Pushdown for k-ANN graph searches

          • Minor - Minor loss of function, or other problem where easy workaround is present.
          • Open

          New Feature - A new feature of the product, which has yet to be developed. MDEV-33412 cost-based optimizer choice for k-NN indexes

          • Major - Major loss of function.
          • Open

          Task - A task that needs to be done. MDEV-33416 graph index: use smaller floating point numbers

          • Major - Major loss of function.
          • Closed

          Task - A task that needs to be done. MDEV-33418 graph index insert: stronger selection of neighbors

          • Major - Major loss of function.
          • Closed

          Task - A task that needs to be done. MDEV-34862 Fix ALTER TABLE to work with high-level indexes

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

          New Feature - A new feature of the product, which has yet to be developed. MDEV-35327 Add VEC_DISTANCE_MANHATTAN (L1) distance function on Vector

          • Minor - Minor loss of function, or other problem where easy workaround is present.
          • Open

          New Feature - A new feature of the product, which has yet to be developed. MDEV-35831 MYSQL_TYPE_VECTOR

          • Major - Major loss of function.
          • Open

          New Feature - A new feature of the product, which has yet to be developed. MDEV-35841 replicate MySQL 9.0 Vector to MariaDB

          • Major - Major loss of function.
          • Open

          New Feature - A new feature of the product, which has yet to be developed. MDEV-36100 Generate embeddings automatically on INSERT

          • Major - Major loss of function.
          • Open
          links to

          Web Link early gdoc

          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 -
            Description A common operation for multi-dimensional vectors is to find k nearest vectors to the given one.
            This task is about implementing indexes that allow to do it fast.

            * ideally they'll be engine independent
            * indexes should be update-able
            * in this task we'll only do Euclidean distance
            * we'll benchmark it on real multi-million-rows data sets

            * what algorithm, exactly, to use is still unclear             		A common operation for multi-dimensional vectors is to find k nearest vectors to the given one.
            This task is about implementing indexes that allow to do it fast.

            * ideally they'll be engine independent
            * indexes should be update-able
            * in this task we'll only do Euclidean distance
            * we'll benchmark it on real multi-million-rows data sets
            * optimizer-wise we'll do like with fulltext search

            * what algorithm, exactly, to use is still unclear
            serg Sergei Golubchik made changes -
            Fix Version/s 11.5 [ 29506 ]
            serg Sergei Golubchik made changes -
            Status Open [ 1 ] In Progress [ 3 ]
            serg Sergei Golubchik added a comment -

            parser, grammar. CREATE TABLE works,

            serg Sergei Golubchik added a comment - parser, grammar. CREATE TABLE works,
            serg Sergei Golubchik added a comment -

            metadata is stored in the frm, read from frm, type checks (only BLOB and NOT NULL)
            SHOW commands and INFORMATION_SCHEMA.STATISTICS

            serg Sergei Golubchik added a comment - metadata is stored in the frm, read from frm, type checks (only BLOB and NOT NULL ) SHOW commands and INFORMATION_SCHEMA.STATISTICS
            serg Sergei Golubchik added a comment -

            An API for a graph algorithm.

            Algorithm implementation needs to provide methods for

            • add a vector to the graph
            • remove a vector from a graph
            • update — only if there will be some algorithm that can do it much faster that delete+insert
            • build a graph from a set of vectors

            The server will provide methods for

            • read/update list of edges for a specific node
            serg Sergei Golubchik added a comment - An API for a graph algorithm. Algorithm implementation needs to provide methods for add a vector to the graph remove a vector from a graph update — only if there will be some algorithm that can do it much faster that delete+insert build a graph from a set of vectors The server will provide methods for read/update list of edges for a specific node
            serg Sergei Golubchik made changes -
            Comment [ (/) index storage: first version. inside the table row, in the internal (not visible to a user) column

            won't be performant, but allows to implement and debug the algorithm

            the engine doesn't see the key at all, so enable/disable keys likely won't work. but as we'll probably change the storage in the future, it doesn't matter now. ]
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            Description A common operation for multi-dimensional vectors is to find k nearest vectors to the given one.
            This task is about implementing indexes that allow to do it fast.

            * ideally they'll be engine independent
            * indexes should be update-able
            * in this task we'll only do Euclidean distance
            * we'll benchmark it on real multi-million-rows data sets
            * optimizer-wise we'll do like with fulltext search

            * what algorithm, exactly, to use is still unclear             		A common operation for multi-dimensional vectors is to find k nearest vectors to the given one.
            This task is about implementing indexes that allow to do it fast.

            * ideally they'll be engine independent
            * indexes should be update-able
            * in this task we'll only do Euclidean distance
            * we'll benchmark it on real multi-million-rows data sets
            * optimizer-wise we'll do like with fulltext search

            * what algorithm, exactly, to use is still unclear

            h1. this task is at the moment in the _early design phase_ the ideas are recorded, added, changed, and -removed- in the linked gdoc
            serg Sergei Golubchik made changes -
            Description A common operation for multi-dimensional vectors is to find k nearest vectors to the given one.
            This task is about implementing indexes that allow to do it fast.

            * ideally they'll be engine independent
            * indexes should be update-able
            * in this task we'll only do Euclidean distance
            * we'll benchmark it on real multi-million-rows data sets
            * optimizer-wise we'll do like with fulltext search

            * what algorithm, exactly, to use is still unclear

            h1. this task is at the moment in the _early design phase_ the ideas are recorded, added, changed, and -removed- in the linked gdoc             		A common operation for multi-dimensional vectors is to find k nearest vectors to the given one.
            This task is about implementing indexes that allow to do it fast.

            * ideally they'll be engine independent
            * indexes should be update-able
            * in this task we'll only do Euclidean distance
            * we'll benchmark it on real multi-million-rows data sets
            * optimizer-wise we'll do like with fulltext search

            * what algorithm, exactly, to use is still unclear

            h1. *this task is at the moment in the _early design phase_ the ideas are recorded, added, changed, and -removed- in the linked gdoc*
            serg Sergei Golubchik made changes -
            Description A common operation for multi-dimensional vectors is to find k nearest vectors to the given one.
            This task is about implementing indexes that allow to do it fast.

            * ideally they'll be engine independent
            * indexes should be update-able
            * in this task we'll only do Euclidean distance
            * we'll benchmark it on real multi-million-rows data sets
            * optimizer-wise we'll do like with fulltext search

            * what algorithm, exactly, to use is still unclear

            h1. *this task is at the moment in the _early design phase_ the ideas are recorded, added, changed, and -removed- in the linked gdoc*             		A common operation for multi-dimensional vectors is to find k nearest vectors to the given one.
            This task is about implementing indexes that allow to do it fast.

            * ideally they'll be engine independent
            * indexes should be update-able
            * in this task we'll only do Euclidean distance
            * we'll benchmark it on real multi-million-rows data sets
            * optimizer-wise we'll do like with fulltext search

            * what algorithm, exactly, to use is still unclear

            h1. *this task is at the moment in the _early design phase_ the ideas are recorded, added, changed, and -removed- *in the linked gdoc*
            serg Sergei Golubchik made changes -
            Description A common operation for multi-dimensional vectors is to find k nearest vectors to the given one.
            This task is about implementing indexes that allow to do it fast.

            * ideally they'll be engine independent
            * indexes should be update-able
            * in this task we'll only do Euclidean distance
            * we'll benchmark it on real multi-million-rows data sets
            * optimizer-wise we'll do like with fulltext search

            * what algorithm, exactly, to use is still unclear

            h1. *this task is at the moment in the _early design phase_ the ideas are recorded, added, changed, and -removed- *in the linked gdoc*             		A common operation for multi-dimensional vectors is to find k nearest vectors to the given one.
            This task is about implementing indexes that allow to do it fast.

            * ideally they'll be engine independent
            * indexes should be update-able
            * in this task we'll only do Euclidean distance
            * we'll benchmark it on real multi-million-rows data sets
            * optimizer-wise we'll do like with fulltext search

            * what algorithm, exactly, to use is still unclear

            h1. *this task is at the moment in the _early design phase_ the ideas are recorded, added, changed, and -removed- in the linked gdoc*
            serg Sergei Golubchik made changes -
            Description A common operation for multi-dimensional vectors is to find k nearest vectors to the given one.
            This task is about implementing indexes that allow to do it fast.

            * ideally they'll be engine independent
            * indexes should be update-able
            * in this task we'll only do Euclidean distance
            * we'll benchmark it on real multi-million-rows data sets
            * optimizer-wise we'll do like with fulltext search

            * what algorithm, exactly, to use is still unclear

            h1. *this task is at the moment in the _early design phase_ the ideas are recorded, added, changed, and -removed- in the linked gdoc*             		A common operation for multi-dimensional vectors is to find k nearest vectors to the given one.
            This task is about implementing indexes that allow to do it fast.

            * ideally they'll be engine independent
            * indexes should be update-able
            * in this task we'll only do Euclidean distance
            * we'll benchmark it on real multi-million-rows data sets
            * optimizer-wise we'll do like with fulltext search

            * what algorithm, exactly, to use is still unclear
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            Description A common operation for multi-dimensional vectors is to find k nearest vectors to the given one.
            This task is about implementing indexes that allow to do it fast.

            * ideally they'll be engine independent
            * indexes should be update-able
            * in this task we'll only do Euclidean distance
            * we'll benchmark it on real multi-million-rows data sets
            * optimizer-wise we'll do like with fulltext search

            * what algorithm, exactly, to use is still unclear             		A common operation for multi-dimensional vectors is to find k nearest vectors to the given one.
            This task is about implementing indexes that allow to do it fast.

            * ideally they'll be engine independent
            * indexes should be update-able
            * in this task we'll only do Euclidean distance
            * we'll benchmark it on real multi-million-rows data sets

            * what algorithm, exactly, to use is still unclear
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            Fix Version/s 11.6 [ 29515 ]
            Fix Version/s 11.5 [ 29506 ]
            JIraAutomate JiraAutomate made changes -
            Status In Progress [ 3 ] Stalled [ 10000 ]
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            julien.fritsch Julien Fritsch added a comment -

            From the product point of view, this is critical.

            julien.fritsch Julien Fritsch added a comment - From the product point of view, this is critical.
            julien.fritsch Julien Fritsch made changes -
            Priority Major [ 3 ] Critical [ 2 ]
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            Status Stalled [ 10000 ] In Progress [ 3 ]
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            Fix Version/s 11.7 [ 29815 ]
            Fix Version/s 11.6 [ 29515 ]
            serg Sergei Golubchik made changes -
            Fix Version/s 11.8 [ 29921 ]
            Fix Version/s 11.7 [ 29815 ]
            sanja Oleksandr Byelkin added a comment - - edited

            Here is my review:
            This

            share->total_keys > share->keys
            		 
            to->s->keys == to->s->total_keys

            better cnvert to SHARE::has_hlindex() or something like that

            I am not sure about this changes (at least buffer size should be increaed to
            better reflect default length of vector test representation):

            diff --git a/sql/item_vectorfunc.cc b/sql/item_vectorfunc.cc
            		 
            index 8b9ea188490..315ad4e06fa 100644
            		 
            --- a/sql/item_vectorfunc.cc
            		 
            +++ b/sql/item_vectorfunc.cc
            		 
            @@ -134,6 +134,9 @@ String *Item_func_vec_fromtext::val_str(String *buf)
            		 
             {
            		 
               json_engine_t je;
            		 
               bool end_ok= false;
            		 
            +  char buff[STRING_BUFFER_USUAL_SIZE]; // maynbe *2 or *3 has more sens
            		 
            +                                       // (usual vector representation)
            		 
            +  String tmp_js(buff,sizeof(buff), &my_charset_bin);
            		 
               String *value = args[0]->val_json(&tmp_js);
            		 
               CHARSET_INFO *cs= value->charset();
            		 
             
            diff --git a/sql/item_vectorfunc.h b/sql/item_vectorfunc.h
            		 
            index 58dc300c451..1687eed7e29 100644
            		 
            --- a/sql/item_vectorfunc.h
            		 
            +++ b/sql/item_vectorfunc.h
            		 
            @@ -136,7 +136,6 @@ class Item_func_vec_totext: public Item_str_ascii_checksum_func
            		 
             
             class Item_func_vec_fromtext: public Item_str_func
            		 
             {
            		 
            -  String tmp_js;
            		 
             public:
            		 
               bool fix_length_and_dec(THD *thd) override;
            		 
               Item_func_vec_fromtext(THD *thd, Item *a);

            Should be tested with maribackup (high posibility of fail with the new ndex)

            Should be tested with mariadb-dump (probably pass, but will check that what
            was printed by SHOW CREATE TABLE willbe read back)

            It would be nice to have test with different types of indexses in one table
            and they used by optimiser (I also do not expect problems, just to have it
            checked).

            IMHO VECTOR(N) type should be done before release to avoid table converting
            on upgrade in the future.

            IMHO this cleanups a bit fixes and better be backported if possible:

            cleanup: remove unconditional #ifdef's

            cleanup: key algorithm vs key flags

            sanja Oleksandr Byelkin added a comment - - edited Here is my review: This share->total_keys > share->keys to->s->keys == to->s->total_keys better cnvert to SHARE::has_hlindex() or something like that I am not sure about this changes (at least buffer size should be increaed to better reflect default length of vector test representation): diff --git a/sql/item_vectorfunc.cc b/sql/item_vectorfunc.cc index 8b9ea188490..315ad4e06fa 100644 --- a/sql/item_vectorfunc.cc +++ b/sql/item_vectorfunc.cc @@ -134,6 +134,9 @@ String *Item_func_vec_fromtext::val_str(String *buf) { json_engine_t je; bool end_ok= false; + char buff[STRING_BUFFER_USUAL_SIZE]; // maynbe *2 or *3 has more sens + // (usual vector representation) + String tmp_js(buff,sizeof(buff), &my_charset_bin); String *value = args[0]->val_json(&tmp_js); CHARSET_INFO *cs= value->charset(); diff --git a/sql/item_vectorfunc.h b/sql/item_vectorfunc.h index 58dc300c451..1687eed7e29 100644 --- a/sql/item_vectorfunc.h +++ b/sql/item_vectorfunc.h @@ -136,7 +136,6 @@ class Item_func_vec_totext: public Item_str_ascii_checksum_func class Item_func_vec_fromtext: public Item_str_func { - String tmp_js; public: bool fix_length_and_dec(THD *thd) override; Item_func_vec_fromtext(THD *thd, Item *a); Should be tested with maribackup (high posibility of fail with the new ndex) Should be tested with mariadb-dump (probably pass, but will check that what was printed by SHOW CREATE TABLE willbe read back) It would be nice to have test with different types of indexses in one table and they used by optimiser (I also do not expect problems, just to have it checked). IMHO VECTOR(N) type should be done before release to avoid table converting on upgrade in the future. IMHO this cleanups a bit fixes and better be backported if possible: cleanup: remove unconditional #ifdef's cleanup: key algorithm vs key flags
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            Fix Version/s 11.8 [ 29921 ]
            serg Sergei Golubchik made changes -
            Issue Type New Feature [ 2 ] Epic [ 5 ]
            serg Sergei Golubchik made changes -
            Status In Progress [ 3 ] Stalled [ 10000 ]
            serg Sergei Golubchik made changes -
            Fix Version/s N/A [ 14700 ]
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            Summary k-ANN indexes for vectors vector search
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            serg Sergei Golubchik made changes -
            svoj Sergey Vojtovich made changes -
            julien.fritsch Julien Fritsch made changes -
            Epic Name vectore search
            julien.fritsch Julien Fritsch made changes -
            Epic Name vectore search vector search
            adamluciano Adam Luciano made changes -
            Epic Child MDEV-36568 [ 133790 ]
            adamluciano Adam Luciano made changes -
            Epic Child MDEV-36605 [ 133866 ]

            People

              serg Sergei Golubchik
              serg Sergei Golubchik
              Votes:
              2 Vote for this issue
              Watchers:
              19 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.