This is an automated email from the ASF dual-hosted git repository.
JingsongLi pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/paimon.git
The following commit(s) were added to refs/heads/master by this push:
new 4d365cae7b [python] Stabilize scored global index top-k tie-breaking
(#8749)
4d365cae7b is described below
commit 4d365cae7be373ff6df7ac2aadbe032c0db4e31e
Author: QuakeWang <[email protected]>
AuthorDate: Tue Jul 21 14:05:08 2026 +0800
[python] Stabilize scored global index top-k tie-breaking (#8749)
---
paimon-python/pypaimon/globalindex/vector_search_result.py | 13 +++++++------
paimon-python/pypaimon/tests/vindex_vector_index_test.py | 8 ++++++++
2 files changed, 15 insertions(+), 6 deletions(-)
diff --git a/paimon-python/pypaimon/globalindex/vector_search_result.py
b/paimon-python/pypaimon/globalindex/vector_search_result.py
index fe2b974550..74d76c5042 100644
--- a/paimon-python/pypaimon/globalindex/vector_search_result.py
+++ b/paimon-python/pypaimon/globalindex/vector_search_result.py
@@ -87,20 +87,21 @@ class ScoredGlobalIndexResult(GlobalIndexResult):
return self
score_getter_fn = self.score_getter()
- # Use a min-heap of size k to find top-k scores in O(n log k)
+ # The heap head is the weakest candidate: lowest score, then largest
row ID.
heap = []
for row_id in row_ids:
score = score_getter_fn(row_id)
if score is None:
score = 0.0
+ item = (score, -row_id)
if len(heap) < k:
- heapq.heappush(heap, (score, row_id))
- elif score > heap[0][0]:
- heapq.heapreplace(heap, (score, row_id))
+ heapq.heappush(heap, item)
+ elif item > heap[0]:
+ heapq.heapreplace(heap, item)
top_k_bitmap = RoaringBitmap64()
- for _, row_id in heap:
- top_k_bitmap.add(row_id)
+ for _, neg_row_id in heap:
+ top_k_bitmap.add(-neg_row_id)
return SimpleScoredGlobalIndexResult(top_k_bitmap, score_getter_fn)
diff --git a/paimon-python/pypaimon/tests/vindex_vector_index_test.py
b/paimon-python/pypaimon/tests/vindex_vector_index_test.py
index ee64512cb2..a549c43af8 100644
--- a/paimon-python/pypaimon/tests/vindex_vector_index_test.py
+++ b/paimon-python/pypaimon/tests/vindex_vector_index_test.py
@@ -100,6 +100,14 @@ class VindexVectorIndexTest(unittest.TestCase):
top1 = DictBasedScoredIndexResult(id_to_scores).top_k(1)
self.assertEqual([10], top1.results().to_list())
+ def test_top_k_breaks_boundary_ties_by_row_id(self):
+ scores = {1: 0.5, 2: 0.5, 3: 0.5, 4: 0.9}
+
+ self.assertEqual(
+ [1, 4],
+ DictBasedScoredIndexResult(scores).top_k(2).results().to_list(),
+ )
+
def test_batch_search_uses_native_batch_api(self):
old_module = sys.modules.get("paimon_vindex")
sys.modules["paimon_vindex"] = types.SimpleNamespace(
