[MDEV-32887] vector search - Jira

Details

Type: Epic
Status: Stalled (View Workflow)
Priority: Critical
Resolution: Unresolved
Fix Version/s: N/A
Component/s: Server
Labels:
- vector

Epic Name:
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

MDEV-32886 VEC_FromText() and VEC_ToText() functions

Closed

MDEV-33404 Engine-independent indexes: subtable method

Closed

MDEV-33405 Engine-independent indexes: low-level API method

Closed

MDEV-33406 basic optimizer support for k-NN searches

Closed

MDEV-33407 Parser support for vector indexes

Closed

MDEV-33408 HNSW for k-ANN vector searches

Closed

MDEV-33410 VECTOR data type

Closed

MDEV-33411 OPTIMIZE for graph indexes

Open

MDEV-33413 cache k-ANN graph in memory

Closed

MDEV-33414 benchmark vector indexes

Closed

MDEV-33415 graph index search: heuristical edge choice

Closed

MDEV-33417 VEC_DISTANCE_COSINE() function

Closed

MDEV-33419 graph index insert: consider more neighbors

Open

MDEV-34436 DDL: per-index attributes

Closed

MDEV-34698 mhnsw: support AVX-512 instructions

Closed

MDEV-34699 mhnsw: support aarch64 SIMD instructions

Closed

MDEV-34804 mhnsw: compiler-independent choice of CPU-specific optimizations

Open

MDEV-34805 provide various information about vector indexes

Open

MDEV-34806 mhnsw: use start_bulk_insert to estmate min_rows

Closed

MDEV-34811 handlerton refactoring

Closed

MDEV-35196 XA support for mhnsw indexes

Open

MDEV-35264 Improve InnoDB concurrent insert into vector index performance

Open

MDEV-35283 support nullable indexed vector columns

Open

MDEV-35314 multi-part vector indexes

Open

MDEV-35315 vector indexes in partitioned tables

Open

MDEV-35316 more than one vector index per table

Open

MDEV-35418 Better support for multiple duplicates vectors in the index

Open

MDEV-35629 Hybrid Search (Text + Vector) w/ Simple Re-Ranking

Open

MDEV-36184 mhnsw: support powerpc64 SIMD instructions

In Review

MDEV-32885 VEC_DISTANCE() function

Closed

MDEV-33409 Index Condition Pushdown for k-ANN graph searches

Open

MDEV-33412 cost-based optimizer choice for k-NN indexes

Open

MDEV-33416 graph index: use smaller floating point numbers

Closed

MDEV-33418 graph index insert: stronger selection of neighbors

Closed

MDEV-34862 Fix ALTER TABLE to work with high-level indexes

Closed

MDEV-35327 Add VEC_DISTANCE_MANHATTAN (L1) distance function on Vector

Open

MDEV-35831 MYSQL_TYPE_VECTOR

Open

MDEV-35841 replicate MySQL 9.0 Vector to MariaDB

Open

MDEV-36100 Generate embeddings automatically on INSERT

Open

links to

early gdoc

(34 relates to, 1 links to)

Activity

Ascending order - Click to sort in descending order

Sergei Golubchik added a comment - 2024-01-19 18:29

parser, grammar. CREATE TABLE works,

Sergei Golubchik added a comment - 2024-01-19 18:29 parser, grammar. CREATE TABLE works,

Sergei Golubchik added a comment - 2024-01-19 18:30

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

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

Sergei Golubchik added a comment - 2024-01-19 19:13

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

Sergei Golubchik added a comment - 2024-01-19 19:13 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

Julien Fritsch added a comment - 2024-07-01 13:49

From the product point of view, this is critical.

Julien Fritsch added a comment - 2024-07-01 13:49 From the product point of view, this is critical.

Oleksandr Byelkin added a comment - 2024-09-27 10:06 - 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

Oleksandr Byelkin added a comment - 2024-09-27 10:06 - 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

People

Assignee:: Sergei Golubchik

Reporter:: Sergei Golubchik

Votes:: 2 Vote for this issue

Watchers:: 19 Start watching this issue

Dates

Created:: 2023-11-26 19:50

Updated:: 6 days ago 14:21

Git Integration

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

MariaDB Server