Reduce repeated matching work during deep ranked traversal

Đang mở
  • Có gì không ổn?
#64 0 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức phù hợp với người mới
25/100
Loại issue
Tái cấu trúc
Độ rõ ràng
Khá rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
node.js, rust
Lĩnh vực
backend, databases, performance

Hướng nghiên cứu

Start with the existing traversal benchmark and benchmarks/traversal-driver.mjs, then inspect the unpublished traversal implementation referenced in issue #60 and evaluate supported Tantivy query reuse and composite sorting. Compare alternatives across the workload dimensions in the issue, recording CPU, memory, disk, handles, lifetime, cancellation, and ordinary-search progress. Done means publishing reproducible results, choosing an approach with explicit costs, and qualifying exact scored sequences, snapshot expiration, total-count behavior, and release compatibility.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

Outcome

Investigate and implement a lower-cost way to traverse large ranked snapshots while preserving exact score/UTF-8 ID ordering and bounded resource use.

Evidence and scope

The ranked traversal delivered in Add bounded snapshot traversal for full-text and autocomplete results rescans matches and recomputes exact totals on every page. Traversing N matches in pages of P therefore requires approximately N²/P matching-document visits, plus query/scorer setup. This is an explicit design tradeoff, not a measured regression in the released API. Existing local qualification covers correctness and finite workloads; no production latency target or customer incident is claimed.

Acceptance criteria

  • Benchmark repeated scans against alternatives such as amortized snapshot-owned query state or a separately specified export order. Include many segments, large IDs, sparse host eligibility, expensive queries, sustained writes, and concurrent readers.
  • Select an approach with explicit CPU, memory, retained-disk, handle-count and lifetime costs. Do not introduce unbounded cursor state or silently switch ranked traversal to ID order.
  • Preserve snapshot ownership/expiration and exact scored sequences without skips or duplicates. Define any total-count API change explicitly.
  • Compare against the existing traversal benchmark and publish reproducible results before replacing the simpler collector. Recheck cancellation, ordinary-search progress and release compatibility.

Parent: Epic: Extend fulltext search capabilities beyond the initial wrapper API. Separate from shipping the bounded traversal in Add bounded deep-result traversal and qualify autocomplete limits.

Priority: P3; optimization backlog with no committed roadmap lane or measured production blocker. Effort: High; algorithm/lifetime design and compatibility qualification. No milestone, customer-specific context or security incident is associated.

Local performance baseline for follow-up

The unpublished benchmarks/traversal-driver.mjs compares ordinary search and the first traversal page on one snapshot, with identical scored hits, exact totals and page size. On optimized macOS arm64 / Node v24.16.0, three pre-cleanup runs over 65,536 two-term records and 60 alternating calls per method observed ordinary medians of 0.63–0.68 ms and traversal medians of 0.74–0.79 ms (ratios 1.17–1.18). These are end-to-end local observations, not isolated dispatch measurements or production latency bounds.

A separate local 32,768-match sample observed 256 pages / 8.39 million matching visits at page size 128, versus 64 pages / 2.10 million visits at size 512; median complete traversal times were 64 ms and 24 ms. Visit counts follow the current exhaustive collector; timings do not establish a catalog-scale SLO.

Evaluate bounded query/preparation reuse and inclusive score/ID boundary pruning through supported Tantivy facilities. Caching the first-page total alone does not change the current full-scan collector; a score-only threshold can also skip required equal-score IDs. Preserve cancellation, scored sequence equivalence and batched dictionary resolution. Tantivy's composite sort API is an evaluation candidate, not a demonstrated drop-in cancellation or search-after implementation.

Ordinary-search handoff from Harper

The Harper integration starts ordinary full-text and autocomplete searches with the existing reader.search path. Its result has no traversal token. A query needing more candidates therefore starts searchPage from the beginning, replays at most the initial raw batch, and checks that ordering agrees before continuing. This is bounded overhead, separate from the repeated full matching scans described above.

  • Evaluate a native first-page handoff that preserves existing ordinary/prefix ordering and returns a supported traversal boundary without requiring Harper to replay the prefix.
  • Measure native matching work and the additional ID/score/version payload crossing into Harper. Compare the same queries, scored sequences, Unicode tie boundaries and page sizes; a whole-version latency comparison does not isolate replay cost.
  • Keep ranking and traversal in fulltext/Tantivy, using supported Tantivy facilities. Avoid another collector or snapshot cache in Harper solely to remove this handoff cost.

Related: Support full-text and autocomplete continuation in Table.search and REST. This remains optimization backlog without a release commitment.

Comment generated by kAIle (GPT-6)

Tantivy 0.27 boundary review follow-up

Reconfirmed from Upgrade fulltext to Tantivy 0.27 with safe index rebuilds: keep traversal ranking and pruning in fulltext/Tantivy, reuse supported scorer and collector facilities, and measure query/scorer preparation separately from per-page matching. The current custom collector already reuses Tantivy TopNComputer and batched string-dictionary resolution.

  • Include exact score bits, UTF-8 ID ties, deleted documents, snapshot retention and collection-stage timeout behavior in any native replacement comparison.
  • Preserve the ordinary-search fast path: do not put traversal-only cancellation or continuation checks in every ordinary match callback.

This adds qualification detail to the existing optimization, not a new performance claim or release commitment.

Comment generated by kAIle (GPT-6)

Ngôn ngữ chính
Rust
Star
3
Fork
0
Merge trung bình
15 giờ 12 phút
Pull request đã merge (30 ngày)
11

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của HarperFast/fulltext

Tất cả issue của HarperFast/fulltext

Issue tương tự

Thêm issue về Rust

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.