Skip to content

Commit a899ded

Browse files
authored
[refine](ann index) Fix ann ut and minor refine for range search (apache#55237)
### What problem does this PR solve? 1. Expand the search space in ann ut. 2. Refine range search 3. Minor refactor on some class 4. Add efConstrucion support 5. Check index file format in ddl
1 parent bdb8cab commit a899ded

15 files changed

Lines changed: 291 additions & 54 deletions

File tree

‎be/src/olap/rowset/segment_v2/ann_index/ann_index_reader.cpp‎

Lines changed: 9 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -54,7 +54,7 @@ AnnIndexReader::AnnIndexReader(const TabletIndex* index_meta,
5454
const auto index_properties = _index_meta.properties();
5555
auto it = index_properties.find("index_type");
5656
DCHECK(it != index_properties.end());
57-
_index_type = it->second;
57+
_index_type = string_to_ann_index_type(it->second);
5858
it = index_properties.find("metric_type");
5959
DCHECK(it != index_properties.end());
6060
_metric_type = string_to_metric(it->second);
@@ -106,7 +106,7 @@ Status AnnIndexReader::query(io::IOContext* io_ctx, AnnTopNParam* param, AnnInde
106106
const float* query_vec = param->query_value;
107107
const int limit = static_cast<int>(param->limit);
108108
IndexSearchResult index_search_result;
109-
if (string_to_ann_index_type(_index_type) == AnnIndexType::HNSW) {
109+
if (_index_type == AnnIndexType::HNSW) {
110110
HNSWSearchParameters hnsw_search_params;
111111
hnsw_search_params.roaring = param->roaring;
112112
hnsw_search_params.rows_of_segment = param->rows_of_segment;
@@ -121,7 +121,8 @@ Status AnnIndexReader::query(io::IOContext* io_ctx, AnnTopNParam* param, AnnInde
121121
stats->engine_convert_ns.update(index_search_result.engine_convert_ns);
122122
stats->engine_prepare_ns.update(index_search_result.engine_prepare_ns);
123123
} else {
124-
throw Status::NotSupported("Unsupported index type: {}", _index_type);
124+
throw Status::NotSupported("Unsupported index type: {}",
125+
ann_index_type_to_string(_index_type));
125126
}
126127

127128
DCHECK(index_search_result.roaring != nullptr);
@@ -162,14 +163,15 @@ Status AnnIndexReader::range_search(const AnnRangeSearchParams& params,
162163
segment_v2::IndexSearchResult search_result;
163164
std::unique_ptr<segment_v2::IndexSearchParameters> search_param = nullptr;
164165

165-
if (string_to_ann_index_type(_index_type) == AnnIndexType::HNSW) {
166+
if (_index_type == AnnIndexType::HNSW) {
166167
auto hnsw_param = std::make_unique<segment_v2::HNSWSearchParameters>();
167168
hnsw_param->ef_search = custom_params.hnsw_ef_search;
168169
hnsw_param->check_relative_distance = custom_params.hnsw_check_relative_distance;
169170
hnsw_param->bounded_queue = custom_params.hnsw_bounded_queue;
170171
search_param = std::move(hnsw_param);
171172
} else {
172-
throw Status::NotSupported("Unsupported index type: {}", _index_type);
173+
throw Status::NotSupported("Unsupported index type: {}",
174+
ann_index_type_to_string(_index_type));
173175
}
174176

175177
search_param->is_le_or_lt = params.is_le_or_lt;
@@ -186,10 +188,12 @@ Status AnnIndexReader::range_search(const AnnRangeSearchParams& params,
186188
DCHECK(search_result.roaring != nullptr);
187189
result->roaring = search_result.roaring;
188190

191+
#ifndef NDEBUG
189192
if (params.is_le_or_lt == false) {
190193
DCHECK(search_result.distances == nullptr);
191194
DCHECK(search_result.row_ids == nullptr);
192195
}
196+
#endif
193197

194198
{
195199
SCOPED_TIMER(&(stats->result_process_costs_ns));

‎be/src/olap/rowset/segment_v2/ann_index/ann_index_reader.h‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -63,8 +63,7 @@ class AnnIndexReader : public IndexReader {
6363
TabletIndex _index_meta;
6464
std::shared_ptr<IndexFileReader> _index_file_reader;
6565
std::unique_ptr<VectorIndex> _vector_index;
66-
// TODO: Use integer.
67-
std::string _index_type;
66+
AnnIndexType _index_type;
6867
AnnIndexMetric _metric_type;
6968

7069
DorisCallOnce<Status> _load_index_once;

‎be/src/olap/rowset/segment_v2/ann_index/ann_index_writer.cpp‎

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -61,12 +61,16 @@ Status AnnIndexColumnWriter::init() {
6161
build_parameter.dim = std::stoi(get_or_default(properties, DIM, "512"));
6262
build_parameter.max_degree = std::stoi(get_or_default(properties, MAX_DEGREE, "32"));
6363
build_parameter.metric_type = FaissBuildParameter::string_to_metric_type(metric_type);
64+
build_parameter.ef_construction = std::stoi(get_or_default(properties, EF_CONSTRUCTION, "40"));
6465

6566
faiss_index->build(build_parameter);
6667

6768
_vector_index = faiss_index;
68-
LOG_INFO("Create a new faiss index, index_type {} dim {} metric_type {} max_degree {}",
69-
index_type, build_parameter.dim, metric_type, build_parameter.max_degree);
69+
LOG_INFO(
70+
"Create a new faiss index, index_type {} dim {} metric_type {} max_degree {}, "
71+
"ef_construction {}",
72+
index_type, build_parameter.dim, metric_type, build_parameter.max_degree,
73+
build_parameter.ef_construction);
7074
return Status::OK();
7175
}
7276

‎be/src/olap/rowset/segment_v2/ann_index/ann_index_writer.h‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,7 @@ class AnnIndexColumnWriter : public IndexColumnWriter {
4343
static constexpr const char* METRIC_TYPE = "metric_type";
4444
static constexpr const char* DIM = "dim";
4545
static constexpr const char* MAX_DEGREE = "max_degree";
46+
static constexpr const char* EF_CONSTRUCTION = "ef_construction";
4647

4748
explicit AnnIndexColumnWriter(IndexFileWriter* index_file_writer,
4849
const TabletIndex* index_meta);

‎be/src/olap/rowset/segment_v2/ann_index/faiss_ann_index.cpp‎

Lines changed: 31 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -175,17 +175,20 @@ void FaissVectorIndex::build(const FaissBuildParameter& params) {
175175
}
176176

177177
if (params.index_type == FaissBuildParameter::IndexType::HNSW) {
178+
std::unique_ptr<faiss::IndexHNSWFlat> hnsw_index;
178179
if (params.metric_type == FaissBuildParameter::MetricType::L2) {
179-
_index = std::make_unique<faiss::IndexHNSWFlat>(params.dim, params.max_degree,
180-
faiss::METRIC_L2);
180+
hnsw_index = std::make_unique<faiss::IndexHNSWFlat>(params.dim, params.max_degree,
181+
faiss::METRIC_L2);
181182
} else if (params.metric_type == FaissBuildParameter::MetricType::IP) {
182-
_index = std::make_unique<faiss::IndexHNSWFlat>(params.dim, params.max_degree,
183-
faiss::METRIC_INNER_PRODUCT);
183+
hnsw_index = std::make_unique<faiss::IndexHNSWFlat>(params.dim, params.max_degree,
184+
faiss::METRIC_INNER_PRODUCT);
184185
} else {
185186
throw doris::Exception(doris::ErrorCode::INVALID_ARGUMENT,
186187
"Unsupported metric type: {}",
187188
static_cast<int>(params.metric_type));
188189
}
190+
hnsw_index->hnsw.efConstruction = params.ef_construction;
191+
_index = std::move(hnsw_index);
189192
} else {
190193
throw doris::Exception(doris::ErrorCode::INVALID_ARGUMENT, "Unsupported index type: {}",
191194
static_cast<int>(params.index_type));
@@ -224,14 +227,13 @@ doris::Status FaissVectorIndex::ann_topn_search(const float* query_vec, int k,
224227
std::unique_ptr<faiss::IDSelector> id_sel = nullptr;
225228
// Costs of roaring to faiss selector is very high especially when the cardinality is very high.
226229
if (params.roaring->cardinality() != params.rows_of_segment) {
227-
LOG_INFO("Roaring to faiss selector, roaring {} rows, segment {} rows",
228-
params.roaring->cardinality(), params.rows_of_segment);
229-
{
230-
SCOPED_RAW_TIMER(&result.engine_prepare_ns);
231-
id_sel = roaring_to_faiss_selector(*params.roaring);
232-
}
230+
SCOPED_RAW_TIMER(&result.engine_prepare_ns);
231+
id_sel = roaring_to_faiss_selector(*params.roaring);
233232
param.sel = id_sel.get();
233+
} else {
234+
param.sel = nullptr;
234235
}
236+
235237
{
236238
SCOPED_RAW_TIMER(&result.engine_search_ns);
237239
_index->search(1, query_vec, k, distances, labels, &param);
@@ -283,26 +285,30 @@ doris::Status FaissVectorIndex::range_search(const float* query_vec, const float
283285
DCHECK(query_vec != nullptr);
284286
DCHECK(params.roaring != nullptr)
285287
<< "Roaring should not be null for range search, please set roaring in params";
286-
std::unique_ptr<faiss::IDSelector> sel;
287-
{
288-
// Engine prepare: convert roaring bitmap to FAISS selector
289-
SCOPED_RAW_TIMER(&result.engine_prepare_ns);
290-
sel = roaring_to_faiss_selector(*params.roaring);
291-
}
292-
faiss::RangeSearchResult native_search_result(1, true);
293-
const HNSWSearchParameters* hnsw_params = dynamic_cast<const HNSWSearchParameters*>(&params);
294-
// Currently only support HNSW index for range search.
295-
DCHECK(hnsw_params != nullptr) << "HNSW search parameters should not be null for HNSW index";
296-
297288
faiss::SearchParametersHNSW param;
289+
const HNSWSearchParameters* hnsw_params = dynamic_cast<const HNSWSearchParameters*>(&params);
298290
{
299291
// Engine prepare: set search parameters and bind selector
300292
SCOPED_RAW_TIMER(&result.engine_prepare_ns);
301293
param.efSearch = hnsw_params->ef_search;
302294
param.check_relative_distance = hnsw_params->check_relative_distance;
303295
param.bounded_queue = hnsw_params->bounded_queue;
304-
param.sel = sel.get();
305296
}
297+
std::unique_ptr<faiss::IDSelector> sel;
298+
{
299+
// Engine prepare: convert roaring bitmap to FAISS selector
300+
SCOPED_RAW_TIMER(&result.engine_prepare_ns);
301+
if (params.roaring->cardinality() != params.rows_of_segment) {
302+
sel = roaring_to_faiss_selector(*params.roaring);
303+
param.sel = sel.get();
304+
} else {
305+
param.sel = nullptr;
306+
}
307+
}
308+
309+
faiss::RangeSearchResult native_search_result(1, true);
310+
// Currently only support HNSW index for range search.
311+
DCHECK(hnsw_params != nullptr) << "HNSW search parameters should not be null for HNSW index";
306312
{
307313
// Engine search: FAISS range_search
308314
SCOPED_RAW_TIMER(&result.engine_search_ns);
@@ -347,7 +353,7 @@ doris::Status FaissVectorIndex::range_search(const float* query_vec, const float
347353
<< "row_ids size: " << result.row_ids->size()
348354
<< ", roaring size: " << result.roaring->cardinality();
349355
} else if (_metric == AnnIndexMetric::IP) {
350-
// For IP, we can use the distance directly.
356+
// For IP, we can not use the distance directly.
351357
// range search on ip gets all vectors with inner product greater than or equal to the radius.
352358
// so we need to do a convertion.
353359
const roaring::Roaring& origin_row_ids = *params.roaring;
@@ -362,6 +368,8 @@ doris::Status FaissVectorIndex::range_search(const float* query_vec, const float
362368
// remove all rows that should not be included.
363369
*(result.roaring) = origin_row_ids - *roaring;
364370
// Just update the roaring. distance can not be used.
371+
result.distances = nullptr;
372+
result.row_ids = nullptr;
365373
}
366374
} else {
367375
throw doris::Exception(doris::ErrorCode::INVALID_ARGUMENT,

‎be/src/olap/rowset/segment_v2/ann_index/faiss_ann_index.h‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -93,6 +93,7 @@ struct FaissBuildParameter {
9393
int max_degree = 0; ///< Maximum number of connections per node in HNSW graph
9494
IndexType index_type = IndexType::HNSW; ///< Type of index to build
9595
MetricType metric_type = MetricType::L2; ///< Distance metric to use
96+
int ef_construction = 40; ///< Size of dynamic list for nearest neighbors during construction
9697
};
9798

9899
/**

‎be/test/olap/vector_search/faiss_vector_index_test.cpp‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -262,7 +262,7 @@ TEST_F(VectorSearchTest, SearchAllVectors) {
262262

263263
FaissBuildParameter params;
264264
params.dim = 64;
265-
params.max_degree = 32;
265+
params.max_degree = 128;
266266
params.index_type = FaissBuildParameter::IndexType::HNSW;
267267
index1->build(params);
268268

@@ -289,6 +289,7 @@ TEST_F(VectorSearchTest, SearchAllVectors) {
289289
for (int i = 0; i < num_vectors; ++i) roaring->add(i);
290290
search_params.roaring = roaring.get();
291291
search_params.rows_of_segment = num_vectors;
292+
search_params.ef_search = 128;
292293
IndexSearchResult search_result;
293294

294295
// Search for all vectors - use a vector we know is in the index

‎fe/fe-core/src/main/java/org/apache/doris/analysis/AnnIndexPropertiesChecker.java‎

Lines changed: 13 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -23,11 +23,6 @@
2323

2424
public class AnnIndexPropertiesChecker {
2525
public static void checkProperties(Map<String, String> properties) {
26-
// // ANN index is not supported in cloud mode
27-
// if (Config.isCloudMode()) {
28-
// throw new AnalysisException("ANN index is not supported in cloud mode");
29-
// }
30-
3126
String type = null;
3227
String metric = null;
3328
String dim = null;
@@ -70,6 +65,19 @@ public static void checkProperties(Map<String, String> properties) {
7065
"max_degree of ann index must be a positive integer, got: " + maxDegree);
7166
}
7267
break;
68+
case "ef_construction":
69+
String efConstruction = properties.get(key);
70+
try {
71+
int ef = Integer.parseInt(efConstruction);
72+
if (ef <= 0) {
73+
throw new AnalysisException(
74+
"ef_construction of ann index must be a positive integer, got: " + efConstruction);
75+
}
76+
} catch (NumberFormatException e) {
77+
throw new AnalysisException(
78+
"ef_construction of ann index must be a positive integer, got: " + efConstruction);
79+
}
80+
break;
7381
default:
7482
throw new AnalysisException("unknown ann index property: " + key);
7583
}

‎fe/fe-core/src/main/java/org/apache/doris/analysis/IndexDef.java‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -260,6 +260,9 @@ public void checkColumn(Column column, KeysType keysType, boolean enableUniqueKe
260260
if (keysType != KeysType.DUP_KEYS) {
261261
throw new AnalysisException("ANN index can only be used in DUP_KEYS table");
262262
}
263+
if (invertedIndexFileStorageFormat == TInvertedIndexFileStorageFormat.V1) {
264+
throw new AnalysisException("ANN index is not supported in index format V1");
265+
}
263266
return;
264267
}
265268

‎fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/commands/info/CreateTableInfo.java‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -715,6 +715,12 @@ public void validate(ConnectContext ctx) {
715715
throw new AnalysisException(
716716
"index only support in olap engine at current version.");
717717
}
718+
if (indexDef.getIndexType() == IndexType.ANN) {
719+
if (invertedIndexFileStorageFormat != null
720+
&& invertedIndexFileStorageFormat == TInvertedIndexFileStorageFormat.V1) {
721+
throw new AnalysisException("ANN index is not supported in index format V1");
722+
}
723+
}
718724
for (String indexColName : indexDef.getColumnNames()) {
719725
boolean found = false;
720726
for (ColumnDefinition column : columns) {

0 commit comments

Comments
 (0)