HNSW: ef and top_K

[skylersky]

I understand that in HNSW, the search parameter ef (efSearch) should be larger than top_k. I wonder in Milvus, if I set ef = 20 and top_k = 40, what's the 21-40 returned result part? Is there any similarity relationship exist between those second returned part and search target or they just came randomly?

[yhmo]

You cannot set ef < top_k.
This doc has mentioned:
https://milvus.io/docs/index.md?tab=floating#HNSW

ef Range: [top_k, int_max]

[skylersky]

Theoretically top K should be smaller than ef (efSearch), it seems like there is no restriction/check about relationship between top k an ef in Milvus search function. I tested with case1 where I have ef = 200, top K = 500, and case 2 with ef = 500, top K = 500. The results I got from these two cases are same. So I am wondering in Milvus HNSW algorithm, will the ef automatically adjust based on top k when ef is smaller than top K.

[yhmo]

Milvus has "growing segment" and "sealed segment". Growing segment is an in-memory buffer without index. Sealed segment is converted from growing segment when the size of a growing segment exceeds a threshold. Sealed segment is persisted in storage.
Only "sealed segment" can be indexed.

With a few data, the data stays in growing segment. No matter what parameters, the search engine always uses brute-force or interim index to search growing segments.
Only when data is persisted to be sealed segment, the index parameters take effect.

The following script shows if you call collection.flush() to force flush growing segments to be sealed segments, and the ef value is smalled than topk, you will get an search error.

import random
import time

from pymilvus import (
    MilvusClient,
    connections,
    FieldSchema, CollectionSchema, DataType,
    Collection,
    utility,
)

connections.connect(host='localhost', port='19530')
print(utility.get_server_version())

collection_name = "AAA"
dim = 128
metric_type = "COSINE"

if utility.has_collection(collection_name):
    utility.drop_collection(collection_name)

schema = CollectionSchema(fields=[
    FieldSchema(name="id", dtype=DataType.INT64, is_primary=True, auto_id=False),
    FieldSchema(name="vector", dtype = DataType.FLOAT_VECTOR, dim=dim),
])

collection = Collection(name=collection_name, schema=schema)
print(f"Collection '{collection_name}' created")

count = 10000
data = [
    [i for i in range(count)],
    [[random.random() for _ in range(dim)] for _ in range(count)],
]
for i in range(1):
    collection.insert(data=data)
print("insert done")

collection.flush() ### comment out this line, the data will stay in growing segment and do brute-force search

index_params = {
    'metric_type': metric_type,
    'index_type': "HNSW",
    'params': {'M': 50, 'efConstruction': 20},
}
collection.create_index(field_name="vector", index_params=index_params)
print("index created")

utility.wait_for_index_building_complete(collection_name=collection_name)
print("index done")

collection.load()

collection = Collection(collection_name)
for index in collection.indexes:
    print(index.to_dict())

target_vector = [random.random() for _ in range(dim)]
res = collection.search(data=[target_vector],
                        limit=100,
                        anns_field="vector",
                        param={"metric_type":metric_type, "params": {"ef": 20}})
print(f"Search result:\n{res}")

[yhmo]

I call collection.flush() here to demonstrate that there is a checker to verify ef value less than topk value. In practice, users do not need to manually call collection.flush() since frequently flush() might lead to a large amount of tiny segments and slow down the entire system.

[yhmo]

The error:
pymilvus.exceptions.MilvusException: <MilvusException: (code=65535, message=failed to search/query delegator 1 for channel by-dev-rootcoord-dml_5_451020889178388643v0: fail to Search, QueryNode ID=1, reason=worker(1) query failed: => failed to search: out of range in json: ef(20) should be larger than k(100))>

[skylersky]

Thanks for the explanation.
I have several follow-up questions:

1. When you say "Sealed segment is converted from growing segment when the size of a growing segment exceeds a threshold", does this mean the size of growing segment depend on the size inserted data?
2. "With a few data, the data stays in growing segment. No matter what parameters, the search engine always uses brute-force or interim index to search growing segments.", when this happens, does that means the returned results will be in same order no matter what my search parameter is?
3. I am now running a test with dataset less than 1GB, one is around 230GB and another one is around 530GB, I want to test VDB performance with different HNSW parameter combinations (different M, efConstruction, ef), the evaluate metrics includes VDB search time, also some metrics computed based on top_K returned results. Since my data is relatively small, do I need to call collection.flush() before search? Is there any method you might know to make my results reflects the effect of my HNSW search/construction parameters?