2023-11-25 14:58:06 +01:00
|
|
|
#ifndef ITEM_VECTORFUNC_INCLUDED
|
|
|
|
#define ITEM_VECTORFUNC_INCLUDED
|
|
|
|
|
|
|
|
/* Copyright (C) 2023, MariaDB
|
|
|
|
|
|
|
|
This program is free software; you can redistribute it and/or modify
|
|
|
|
it under the terms of the GNU General Public License as published by
|
|
|
|
the Free Software Foundation; version 2 of the License.
|
|
|
|
|
|
|
|
This program is distributed in the hope that it will be useful,
|
|
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
|
GNU General Public License for more details.
|
|
|
|
|
|
|
|
You should have received a copy of the GNU General Public License
|
|
|
|
along with this program; if not, write to the Free Software
|
|
|
|
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */
|
|
|
|
|
|
|
|
/* This file defines all vector functions */
|
Initial HNSW implementation
This commit includes the work done in collaboration with Hugo Wen from
Amazon:
MDEV-33408 Alter HNSW graph storage and fix memory leak
This commit changes the way HNSW graph information is stored in the
second table. Instead of storing connections as separate records, it now
stores neighbors for each node, leading to significant performance
improvements and storage savings.
Comparing with the previous approach, the insert speed is 5 times faster,
search speed improves by 23%, and storage usage is reduced by 73%, based
on ann-benchmark tests with random-xs-20-euclidean and
random-s-100-euclidean datasets.
Additionally, in previous code, vector objects were not released after
use, resulting in excessive memory consumption (over 20GB for building
the index with 90,000 records), preventing tests with large datasets.
Now ensure that vectors are released appropriately during the insert and
search functions. Note there are still some vectors that need to be
cleaned up after search query completion. Needs to be addressed in a
future commit.
All new code of the whole pull request, including one or several files
that are either new files or modified ones, are contributed under the
BSD-new license. I am contributing on behalf of my employer Amazon Web
Services, Inc.
As well as the commit:
Introduce session variables to manage HNSW index parameters
Three variables:
hnsw_max_connection_per_layer
hnsw_ef_constructor
hnsw_ef_search
ann-benchmark tool is also updated to support these variables in commit
https://github.com/HugoWenTD/ann-benchmarks/commit/e09784e for branch
https://github.com/HugoWenTD/ann-benchmarks/tree/mariadb-configurable
All new code of the whole pull request, including one or several files
that are either new files or modified ones, are contributed under the
BSD-new license. I am contributing on behalf of my employer Amazon Web
Services, Inc.
Co-authored-by: Hugo Wen <wenhug@amazon.com>
2024-02-17 17:03:30 +02:00
|
|
|
#include <my_global.h>
|
|
|
|
#include "item.h"
|
2023-11-25 14:58:06 +01:00
|
|
|
#include "lex_string.h"
|
|
|
|
#include "item_func.h"
|
|
|
|
|
2024-12-08 17:14:42 +01:00
|
|
|
class Item_func_vec_distance: public Item_real_func
|
2023-11-25 14:58:06 +01:00
|
|
|
{
|
initial support for vector indexes
MDEV-33407 Parser support for vector indexes
The syntax is
create table t1 (... vector index (v) ...);
limitation:
* v is a binary string and NOT NULL
* only one vector index per table
* temporary tables are not supported
MDEV-33404 Engine-independent indexes: subtable method
added support for so-called "high level indexes", they are not visible
to the storage engine, implemented on the sql level. For every such
an index in a table, say, t1, the server implicitly creates a second
table named, like, t1#i#05 (where "05" is the index number in t1).
This table has a fixed structure, no frm, not accessible directly,
doesn't go into the table cache, needs no MDLs.
MDEV-33406 basic optimizer support for k-NN searches
for a query like SELECT ... ORDER BY func() optimizer will use
item_func->part_of_sortkey() to decide what keys can be used
to resolve ORDER BY.
2024-01-17 15:32:45 +01:00
|
|
|
Item_field *get_field_arg() const
|
|
|
|
{
|
|
|
|
if (args[0]->type() == Item::FIELD_ITEM && args[1]->const_item())
|
|
|
|
return (Item_field*)(args[0]);
|
|
|
|
if (args[1]->type() == Item::FIELD_ITEM && args[0]->const_item())
|
|
|
|
return (Item_field*)(args[1]);
|
|
|
|
return NULL;
|
|
|
|
}
|
2023-11-25 14:58:06 +01:00
|
|
|
bool check_arguments() const override
|
|
|
|
{
|
|
|
|
return check_argument_types_or_binary(NULL, 0, arg_count);
|
|
|
|
}
|
2024-12-08 17:14:42 +01:00
|
|
|
double (*calc_distance)(float *v1, float *v2, size_t v_len);
|
Initial HNSW implementation
This commit includes the work done in collaboration with Hugo Wen from
Amazon:
MDEV-33408 Alter HNSW graph storage and fix memory leak
This commit changes the way HNSW graph information is stored in the
second table. Instead of storing connections as separate records, it now
stores neighbors for each node, leading to significant performance
improvements and storage savings.
Comparing with the previous approach, the insert speed is 5 times faster,
search speed improves by 23%, and storage usage is reduced by 73%, based
on ann-benchmark tests with random-xs-20-euclidean and
random-s-100-euclidean datasets.
Additionally, in previous code, vector objects were not released after
use, resulting in excessive memory consumption (over 20GB for building
the index with 90,000 records), preventing tests with large datasets.
Now ensure that vectors are released appropriately during the insert and
search functions. Note there are still some vectors that need to be
cleaned up after search query completion. Needs to be addressed in a
future commit.
All new code of the whole pull request, including one or several files
that are either new files or modified ones, are contributed under the
BSD-new license. I am contributing on behalf of my employer Amazon Web
Services, Inc.
As well as the commit:
Introduce session variables to manage HNSW index parameters
Three variables:
hnsw_max_connection_per_layer
hnsw_ef_constructor
hnsw_ef_search
ann-benchmark tool is also updated to support these variables in commit
https://github.com/HugoWenTD/ann-benchmarks/commit/e09784e for branch
https://github.com/HugoWenTD/ann-benchmarks/tree/mariadb-configurable
All new code of the whole pull request, including one or several files
that are either new files or modified ones, are contributed under the
BSD-new license. I am contributing on behalf of my employer Amazon Web
Services, Inc.
Co-authored-by: Hugo Wen <wenhug@amazon.com>
2024-02-17 17:03:30 +02:00
|
|
|
|
2023-11-25 14:58:06 +01:00
|
|
|
public:
|
2024-12-09 17:11:08 +01:00
|
|
|
enum distance_kind { EUCLIDEAN, COSINE, AUTO } kind;
|
2024-12-08 17:14:42 +01:00
|
|
|
Item_func_vec_distance(THD *thd, Item *a, Item *b, distance_kind kind);
|
|
|
|
LEX_CSTRING func_name_cstring() const override
|
2023-11-25 14:58:06 +01:00
|
|
|
{
|
2024-12-08 17:14:42 +01:00
|
|
|
static LEX_CSTRING name[3]= {
|
|
|
|
{ STRING_WITH_LEN("VEC_DISTANCE_EUCLIDEAN") },
|
2024-12-09 17:11:08 +01:00
|
|
|
{ STRING_WITH_LEN("VEC_DISTANCE_COSINE") },
|
|
|
|
{ STRING_WITH_LEN("VEC_DISTANCE") }
|
2024-12-08 17:14:42 +01:00
|
|
|
};
|
|
|
|
return name[kind];
|
2023-11-25 14:58:06 +01:00
|
|
|
}
|
2024-12-08 17:14:42 +01:00
|
|
|
bool fix_length_and_dec(THD *thd) override;
|
2023-11-25 14:58:06 +01:00
|
|
|
double val_real() override;
|
2024-06-01 00:17:05 +02:00
|
|
|
Item *get_const_arg() const
|
|
|
|
{
|
|
|
|
if (args[0]->type() == Item::FIELD_ITEM && args[1]->const_item())
|
|
|
|
return args[1];
|
|
|
|
if (args[1]->type() == Item::FIELD_ITEM && args[0]->const_item())
|
|
|
|
return args[0];
|
|
|
|
return NULL;
|
|
|
|
}
|
initial support for vector indexes
MDEV-33407 Parser support for vector indexes
The syntax is
create table t1 (... vector index (v) ...);
limitation:
* v is a binary string and NOT NULL
* only one vector index per table
* temporary tables are not supported
MDEV-33404 Engine-independent indexes: subtable method
added support for so-called "high level indexes", they are not visible
to the storage engine, implemented on the sql level. For every such
an index in a table, say, t1, the server implicitly creates a second
table named, like, t1#i#05 (where "05" is the index number in t1).
This table has a fixed structure, no frm, not accessible directly,
doesn't go into the table cache, needs no MDLs.
MDEV-33406 basic optimizer support for k-NN searches
for a query like SELECT ... ORDER BY func() optimizer will use
item_func->part_of_sortkey() to decide what keys can be used
to resolve ORDER BY.
2024-01-17 15:32:45 +01:00
|
|
|
key_map part_of_sortkey() const override;
|
2024-08-29 20:49:54 +02:00
|
|
|
Item *do_get_copy(THD *thd) const override
|
2024-12-08 17:14:42 +01:00
|
|
|
{ return get_item_copy<Item_func_vec_distance>(thd, this); }
|
2024-08-29 20:49:54 +02:00
|
|
|
};
|
|
|
|
|
|
|
|
|
2024-07-24 22:01:53 +03:00
|
|
|
class Item_func_vec_totext: public Item_str_ascii_checksum_func
|
|
|
|
{
|
|
|
|
bool check_arguments() const override
|
|
|
|
{
|
|
|
|
return check_argument_types_or_binary(NULL, 0, arg_count);
|
|
|
|
}
|
|
|
|
|
|
|
|
public:
|
|
|
|
bool fix_length_and_dec(THD *thd) override;
|
|
|
|
Item_func_vec_totext(THD *thd, Item *a);
|
|
|
|
String *val_str_ascii(String *buf) override;
|
|
|
|
LEX_CSTRING func_name_cstring() const override
|
|
|
|
{
|
|
|
|
static LEX_CSTRING name= { STRING_WITH_LEN("VEC_ToText") };
|
|
|
|
return name;
|
|
|
|
}
|
|
|
|
Item *do_get_copy(THD *thd) const override
|
|
|
|
{ return get_item_copy<Item_func_vec_totext>(thd, this); }
|
|
|
|
};
|
|
|
|
|
|
|
|
|
|
|
|
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);
|
|
|
|
String *val_str(String *buf) override;
|
|
|
|
LEX_CSTRING func_name_cstring() const override
|
|
|
|
{
|
|
|
|
static LEX_CSTRING name= { STRING_WITH_LEN("VEC_FromText") };
|
|
|
|
return name;
|
|
|
|
}
|
|
|
|
Item *do_get_copy(THD *thd) const override
|
|
|
|
{ return get_item_copy<Item_func_vec_fromtext>(thd, this); }
|
|
|
|
};
|
2023-11-25 14:58:06 +01:00
|
|
|
#endif
|