Skip to content

fix(hgraph): backport duplicate query handling to 1.0 - #2944

Open
jac0626 wants to merge 1 commit into
antgroup:1.0from
jac0626:codex/backport-hgraph-duplicate-query-1.0
Open

jac0626 wants to merge 1 commit into
antgroup:1.0from
jac0626:codex/backport-hgraph-duplicate-query-1.0

Conversation

@jac0626

@jac0626 jac0626 commented Sep 14, 2026

Copy link
Copy Markdown
Collaborator

Summary

Backport the HGraph duplicate-query behavior from #2615 / #2264 to 1.0, using its existing graph-level duplicate tracker.

  • Add hgraph.max_duplicates_per_group to standard, parallel, and iterator KNN graph search: -1 preserves unlimited expansion, 0 suppresses extra members, and positive values count members accepted by the filter, excluding the representative.
  • Expand the entry-point group even when its representative is filtered out, and trim the result heap after expanding a group.
  • Keep unreturned iterator duplicate members in lazily allocated pending state across pages and final drain. Expansion still happens during graph search, before reorder; this does not introduce delayed expansion or redesign graph-candidate persistence.
  • Skip duplicate-only IDs when the Analyzer reads graph adjacency for degree statistics.
  • Add regression coverage and document the parameter in English and Chinese.

Scope

This is the 1.0 query/iterator equivalent, not a wholesale cherry-pick of the 0.18 implementation. The graph-level deserialization validation from #2258 is already in 1.0. The 0.18-specific LabelTable/v0.14 streaming-format changes and min_distance parameter are not copied. Duplicate vector storage (#2244), construction locking, and RangeSearch/brute-force behavior are unchanged.

The separate SQ duplicate-candidate fix remains in #2892; it is not bundled into this PR. Both PRs are tracked separately in the issue's multi-version checklist.

Validation

  • Red: on unmodified 1.0 commit 87a8160ca3f7933eb59f62f7ff7307cda12fab78, 8 of the 11 new query regression cases failed.
  • Analyzer red: initialized unused memory-IO rows expose incorrect degree statistics before the fix (incoming degree sum 5 vs. outgoing sum 2).
  • Green: 35 targeted query, iterator context, parameter, basic/parallel searcher, and Analyzer tests pass (266,060 assertions). All 12 query/Analyzer regressions also pass three additional runs (377 assertions each).
  • Built with -j $(nproc); changed C++ files checked with clang-format 15 and clang-tidy 15; git diff --check passes.

This is targeted validation, not a claim that the full test suite or coverage run passed. Two existing non-finite bridge tests were excluded from the combined local Release run; the branch's existing non-finite distance handling is unchanged.

Fixes: #2614

Related: #2264, #2615, #2892.

Signed-off-by: jc543239 <jc543239@antgroup.com>
Assisted-by: Codex:GPT-5
@jac0626 jac0626 added kind/bug Bug fixes, defects, or unexpected behavior 修复程序错误、缺陷或异常行为 version/1.0 1. LazyHGraph & SIMQ 2. Unified search API 3. Streaming serialization 1. 新索引 2. 统一检索接口 3. 流式序列化 labels Sep 14, 2026
@jac0626 jac0626 self-assigned this Sep 14, 2026
@pull-request-size pull-request-size Bot added the size/XL 500-999 changed lines label Sep 14, 2026
@vsag-bot

vsag-bot commented Sep 14, 2026

Copy link
Copy Markdown
Collaborator

/label status/waiting-for-review
/waiting-on reviewer
/request-review @jiaweizone
/request-review @wxyucs
/request-review @inabao

@mergify mergify Bot added the area/docs Website and repository documentation 网站与仓库文档 label Sep 14, 2026
@mergify mergify Bot added module/api Public C++ API and headers 公共 C++ API 与头文件 module/index Index algorithms and implementations 索引算法与实现 area/testing Tests, fixtures, and test infrastructure 测试、夹具与测试基础设施 labels Sep 14, 2026
if (inner_search_param.max_duplicates_per_group >= 0 and
duplicate_count >= inner_search_param.max_duplicates_per_group) {
break;
}

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

[suggestion] The add_pending_duplicates lambda checks group_id != group_member_id and returns early, while add_duplicate_results in the non-iterator path passes group_member_id directly to GetDuplicateIds without this check. This asymmetry means the iterator path only expands duplicates when visiting the representative node, while the non-iterator path expands duplicates for any node. If GetDuplicateIds returns the same group regardless of which member is queried (i.e., it internally resolves to the representative), then the group_id check in add_pending_duplicates is redundant. If GetDuplicateIds requires the representative ID, then add_duplicate_results should also resolve the group representative first.

Please clarify the intended semantics and align both paths.

@@ -181,6 +240,7 @@ BasicSearcher::search_impl(const GraphInterfacePtr& graph,

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

[note] In the entry-point initialization path, add_pending_duplicates(dist, ep) is called unconditionally (position 74), but the original lower_bound update was also moved inside the if (not top_candidates->Empty()) guard. If ep is filtered out and its duplicates are added via add_pending_duplicates but then all evicted by shrink_top_candidates, top_candidates may become empty while lower_bound retains a stale value. Consider whether lower_bound should be reset to a sentinel (e.g. std::numeric_limitsts<float>::max()) when top_candidates is empty after this block, to prevent the subsequent search loop from using an incorrect lower bound.

}

int64_t duplicate_count = 0;
for (const auto duplicate_id : graph->GetDuplicateIds(group_member_id)) {

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

[suggestion] The add_duplicate_results lambda in parallel_searcher.cpp (and the equivalent in basic_searcher.cpp non-iterator path) calls graph->GetDuplicateIds(group_member_id) directly without resolving the group representative first. This differs from add_pending_duplicates which checks graph->GetGroupId(group_member_id) != group_member_id and returns early if the node is not the representative.

If GetDuplicateIds is only meaningful when called with the representative ID, both add_duplicate_results implementations should resolve the group representative first (e.g., via graph->GetGroupId). Otherwise, if GetDuplicateIds handles non-representative IDs gracefully, the check in add_pending_duplicates is unnecessary and can be removed for consistency.

See the related comment on basic_searcher.cpp for the same issue.

while (!iter_filter_ctx->Empty()) {
uint32_t cur_inner_id = iter_filter_ctx->GetTopID();
float cur_dist = iter_filter_ctx->GetTopDist();
search_result->Push(cur_dist, cur_inner_id);

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

[note] In the is_last_filter drain path, pending duplicates are pushed to search_result before the discard heap is drained (lines 121-128), and pending-duplicate entries in the discard heap are skipped (lines 133-135). After both loops complete, the pending_duplicates_ map still contains the drained entries. While SetPoint clears individual entries when they are later marked as visited, the map itself is not cleared after the final drain. This is harmless for correctness since the iterator context is typically discarded after the last page, but if the context were reused (e.g., for a new query with the same iterator), stale pending entries could interfere. Consider calling a ClearPendingDuplicates() or resetting pending_duplicates_ after the final drain for robustness.

CHECK_ARGUMENT(max_duplicates_json.IsNumberInteger(),
"max_duplicates_per_group must be an integer");
if (max_duplicates_json.IsNumberUnsigned()) {
CHECK_ARGUMENT(max_duplicates_json.GetUint64() <=

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

[suggestion] The validation for max_duplicates_per_group checks IsNumberUnsigned() and validates the uint64 value against int64_t::max(), then calls GetInt() which returns int64_t. However, if the JSON value is a negative integer (e.g., -1), IsNumberUnsigned() returns false and the range check is skipped, which is correct. But if the JSON value is a large unsigned integer just below int64_t::max(), GetInt() should handle it correctly since the range check ensures it fits in int64_t. This logic is sound, but consider adding a comment explaining why the unsigned path is needed (to catch large unsigned values that would overflow int64_t), as the flow is not immediately obvious to a reader.

@LHT129 LHT129 left a comment

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I noticed one additional issue beyond the existing review comments:

Range search path missing max_duplicates_per_group propagation

In SearchWithRequest(), the range-search branch (line 489) sets consider_duplicate = true but does not propagate max_duplicates_per_group from params. The KNN branch (line 504) correctly sets both:

// Range search (line 488-494)
search_param.consider_duplicate = true;
// NOTE: max_duplicates_per_group is NOT set, stays at default -1 (unlimited)

// KNN search (line 503-504)  
search_param.consider_duplicate = true;
search_param.max_duplicates_per_group = params.max_duplicates_per_group;

This means:

  1. Range search now expands duplicates (a behavioral change from before this PR, since consider_duplicate was already true pre-PR), but always uses unlimited expansion regardless of the user-specified limit.
  2. The test HGraph duplicate limit does not change range-search expansion passes max_duplicates_per_group=0 and -1 and observes identical results — because the parameter is never read by the range-search code path.

If this is intentional (range search should always expand all duplicates regardless of the limit), consider adding a comment to make it explicit. If the limit should apply to range search as well, add search_param.max_duplicates_per_group = params.max_duplicates_per_group; in the range-search block.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

area/docs Website and repository documentation 网站与仓库文档 area/testing Tests, fixtures, and test infrastructure 测试、夹具与测试基础设施 kind/bug Bug fixes, defects, or unexpected behavior 修复程序错误、缺陷或异常行为 module/api Public C++ API and headers 公共 C++ API 与头文件 module/index Index algorithms and implementations 索引算法与实现 size/XL 500-999 changed lines version/1.0 1. LazyHGraph & SIMQ 2. Unified search API 3. Streaming serialization 1. 新索引 2. 统一检索接口 3. 流式序列化

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants