Files
qdrant/tests/openapi/test_prefix_match.py
Andrey Vasnetsov efab63d024 Add prefix matching option to keyword index (#9683)
* Add prefix matching option to keyword index

Introduce an opt-in `prefix` option for the keyword payload index and a
new `match: { "prefix": ... }` filter condition, enabling efficient
byte-wise prefix filtering over keyword values (e.g. URL prefixes,
web-ui value autocompletion via facet + prefix filter).

Index side: a new `prefix_index.bin` file stores a sorted, front-coded
key dictionary with a resident block index (cumulative counts per
block); it is an ordered view over the keys of `values_to_points.bin`
and stores no postings. Presence of the file signals prefix support at
load time, so legacy segments load unchanged and enabling the option
goes through the standard incompatible-schema rebuild. The mutable
variant keeps an in-RAM ordered key set (not persisted), the immutable
variant builds a sorted key vector at load, and the on-disk variant
reads the dictionary lazily (block index resident, 1-2 block reads per
prefix lookup; reader is generic over UniversalRead).

Query side: prefix conditions are served from the dictionary when
available (filter + cardinality estimation from per-block aggregates),
from the forward index as per-point checks, and degrade to the payload
full-scan fallback otherwise - same execution model as other match
conditions. Strict mode (`unindexed_filtering_*`) rejects prefix
queries on fields without a prefix-enabled keyword index via a new
KeywordPrefix capability.

HNSW payload blocks: prefix-enabled indexes additionally emit prefix
blocks for heavy branching trie nodes (single-child chains collapsed to
their longest common prefix, one block per distinct point set, emitted
largest-first) so filtered search with prefix conditions gets navigable
subgraphs without rebuilding the same subset repeatedly.

API: `prefix` flag on KeywordIndexParams (REST bool, gRPC empty
message for extensibility), `prefix` variant in the Match oneof, edge
python bindings, regenerated OpenAPI spec.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>

* Split prefix index into a dedicated module, fix clippy in tests

Reorganize the flat prefix_index.rs / prefix_read.rs into a
map_index/prefix_index/ module: format.rs (on-disk layout primitives),
writer.rs, reader.rs (PrefixIndex), map_read.rs (StrMapIndexPrefixRead
with per-variant impls) and tests.rs, with a file-format diagram and a
read-path walkthrough in the module docs. No logic changes.

Also fix clippy --all-targets complaints in test code: replace a
wildcard Match arm with an exhaustive list and a field-reassign-with-
default with a struct literal.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>

* Add OpenAPI test for prefix match and snapshot file-tracking test

- tests/openapi/test_prefix_match.py: index-less fallback, prefix index
  creation with schema echo, scroll/count parity against ground truth,
  facet + prefix filter (the autocompletion flow), strict-mode rejection
  without the prefix capability.
- test_prefix_index_file_tracking: `prefix_index.bin` is listed in
  `files()` / `immutable_files()` exactly when built with the option.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>

* Replace hand-rolled varint parsing with bytemuck Pod records

Per review: the prefix index format now uses fixed-size little-endian
Pod records (BlockEntry 24 B, KeyEntry 12 B, Header 40 B) written with
bytemuck::bytes_of and read back by copy via pod_read_unaligned — no
manual varint encode/decode, no alignment requirement, one shared
read_record helper. Costs ~9 bytes per key on disk versus LEB128; the
raw key bytes dominate dictionary size, so the simplification wins.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>

* Fetch the whole candidate block range with a single storage read

Candidate key blocks of a prefix lookup are contiguous in the file, so
enumerate them from one ranged read instead of one read per block; the
over-read versus the exact key range is bounded by the two boundary
blocks. Block decoding is split into a storage-free helper reused by
the per-block path of stats estimation.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>

* Align prefix payload blocks with the geo index granularity principle

Geo's large_hashes emits only the smallest geohash regions above the
threshold — a disjoint antichain, never a parent nested with its
children. Prefix payload blocks now follow the same rule: a heavy
collapsed trie node is emitted only if nothing heavy is nested inside
it, counting both deeper qualifying prefixes and single heavy values
(which already get their own exact-match blocks). Emitted blocks are
therefore mutually disjoint and disjoint from exact-value blocks; no
near-collection-sized ancestor subgraphs, no reliance on the HNSW
connectivity check to skip nested duplicates.

Implemented as a `covered` flag propagated through the existing
LCP-interval scan, still one O(total key bytes) pass.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>

* Document block wire format and unaligned-read rationale in decode_block

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>

---------

Co-authored-by: Claude Fable 5 <noreply@anthropic.com>
2026-07-06 14:40:39 +02:00

232 lines
7.3 KiB
Python

import pytest
from .helpers.collection_setup import drop_collection
from .helpers.helpers import request_with_validation
COLLECTION_NAME = "test_prefix_match"
# id -> url payload; 4 holds an array value, 6 has no url at all.
POINT_URLS = {
1: "https://qdrant.tech",
2: "https://qdrant.tech/docs",
3: "https://example.com",
4: ["http://example.com", "https://qdrant.tech/blog"],
5: "ftp://files.example.com",
6: None,
}
def expected_ids(prefix):
result = []
for point_id, urls in POINT_URLS.items():
if urls is None:
continue
values = urls if isinstance(urls, list) else [urls]
if any(value.startswith(prefix) for value in values):
result.append(point_id)
return result
PREFIX_PROBES = [
"https://qdrant.",
"https://",
"http",
"ftp://",
"https://example.com",
"nonexistent",
"", # matches every point with a url value
]
@pytest.fixture(autouse=True, scope="module")
def setup():
create_collection(COLLECTION_NAME)
yield
drop_collection(collection_name=COLLECTION_NAME)
def create_collection(collection_name):
drop_collection(collection_name)
response = request_with_validation(
api='/collections/{collection_name}',
method="PUT",
path_params={'collection_name': collection_name},
body={
"vectors": {
"size": 2,
"distance": "Dot",
},
}
)
assert response.ok
points = []
for point_id, urls in POINT_URLS.items():
payload = {"tag": "even" if point_id % 2 == 0 else "odd"}
if urls is not None:
payload["url"] = urls
points.append({
"id": point_id,
"vector": [1.0, 0.0],
"payload": payload,
})
response = request_with_validation(
api='/collections/{collection_name}/points',
method="PUT",
path_params={'collection_name': collection_name},
query_params={'wait': 'true'},
body={"points": points},
)
assert response.ok
def _prefix_filter(key, prefix):
return {"must": [{"key": key, "match": {"prefix": prefix}}]}
def _scroll(filter_body):
return request_with_validation(
api='/collections/{collection_name}/points/scroll',
method="POST",
path_params={'collection_name': COLLECTION_NAME},
body={"filter": filter_body, "limit": 100},
)
def _scroll_ids(filter_body):
response = _scroll(filter_body)
assert response.ok, response.json()
return sorted(point['id'] for point in response.json()['result']['points'])
def _set_strict_mode(strict_mode_config):
response = request_with_validation(
api="/collections/{collection_name}",
method="PATCH",
path_params={"collection_name": COLLECTION_NAME},
body={"strict_mode_config": strict_mode_config},
)
response.raise_for_status()
# ---------------------------------------------------------------------------
# 1. Without any index, prefix match executes via the payload fallback.
# ---------------------------------------------------------------------------
def test_prefix_match_without_index():
for prefix in PREFIX_PROBES:
assert _scroll_ids(_prefix_filter("url", prefix)) == expected_ids(prefix), prefix
# ---------------------------------------------------------------------------
# 2. Create a prefix-enabled keyword index; schema is echoed in collection
# info, and results are unchanged.
# ---------------------------------------------------------------------------
def test_create_prefix_index():
response = request_with_validation(
api='/collections/{collection_name}/index',
method="PUT",
path_params={'collection_name': COLLECTION_NAME},
query_params={'wait': 'true'},
body={
"field_name": "url",
"field_schema": {
"type": "keyword",
"prefix": True,
},
}
)
assert response.ok
response = request_with_validation(
api='/collections/{collection_name}',
method="GET",
path_params={'collection_name': COLLECTION_NAME},
)
assert response.ok
url_schema = response.json()['result']['payload_schema']['url']
assert url_schema['data_type'] == "keyword"
assert url_schema['params']['prefix'] is True
def test_prefix_match_with_index():
for prefix in PREFIX_PROBES:
assert _scroll_ids(_prefix_filter("url", prefix)) == expected_ids(prefix), prefix
def test_prefix_match_count():
response = request_with_validation(
api='/collections/{collection_name}/points/count',
method="POST",
path_params={'collection_name': COLLECTION_NAME},
body={"filter": _prefix_filter("url", "https://qdrant."), "exact": True},
)
assert response.ok
assert response.json()['result']['count'] == len(expected_ids("https://qdrant."))
# ---------------------------------------------------------------------------
# 3. Facet with a prefix filter on the same key — the autocompletion flow.
# Facet counts all values of the matching points.
# ---------------------------------------------------------------------------
def test_facet_with_prefix_filter():
response = request_with_validation(
api='/collections/{collection_name}/facet',
method="POST",
path_params={'collection_name': COLLECTION_NAME},
body={
"key": "url",
"filter": _prefix_filter("url", "https://q"),
},
)
assert response.ok
hits = {hit['value']: hit['count'] for hit in response.json()['result']['hits']}
# Points 1, 2 and 4 match; facet counts every value they hold.
assert hits == {
"https://qdrant.tech": 1,
"https://qdrant.tech/docs": 1,
"https://qdrant.tech/blog": 1,
"http://example.com": 1,
}
# ---------------------------------------------------------------------------
# 4. Strict mode: prefix filtering requires a keyword index with the
# `prefix` option; a plain keyword index is not enough.
# ---------------------------------------------------------------------------
def test_strict_mode_requires_prefix_capability():
# Plain keyword index (no `prefix`) on another field.
response = request_with_validation(
api='/collections/{collection_name}/index',
method="PUT",
path_params={'collection_name': COLLECTION_NAME},
query_params={'wait': 'true'},
body={"field_name": "tag", "field_schema": "keyword"},
)
assert response.ok
_set_strict_mode({
"enabled": True,
"unindexed_filtering_retrieve": False,
})
try:
# Exact match on the plain keyword index is allowed...
response = _scroll({"must": [{"key": "tag", "match": {"value": "odd"}}]})
assert response.ok, response.json()
# ...but prefix match is rejected: the index lacks the prefix option.
response = _scroll(_prefix_filter("tag", "od"))
assert response.status_code == 400, response.json()
assert "Index required but not found" in response.json()['status']['error']
# On the prefix-enabled index the query is allowed.
response = _scroll(_prefix_filter("url", "https://qdrant."))
assert response.ok, response.json()
finally:
_set_strict_mode({"enabled": False})