mirror of
https://github.com/qdrant/qdrant.git
synced 2026-07-26 12:41:04 -05:00
* 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>
232 lines
7.3 KiB
Python
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})
|