You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@skywalking.apache.org by "SammyUrfen (via GitHub)" <gi...@apache.org> on 2026/09/06 21:19:22 UTC
[PR] perf(stream): bound the filtered index-order vectorized Top-N merge [skywalking-banyandb]
SammyUrfen opened a new pull request, #1331:
URL: https://github.com/apache/skywalking-banyandb/pull/1331
A filtered index-order stream query left its vectorized merge unbounded. Follow-up to
#1322, which bounded the criteria-less case and left this one open.
- [x] If this pull request closes/resolves/fixes an existing issue, replace the issue number. Fixes apache/skywalking#14056.
- [x] Update the [`CHANGES` log](https://github.com/apache/skywalking-banyandb/blob/main/CHANGES.md).
## What changed
The criteria tag filter now runs before `SortedMerge`, as a fusible operator that narrows
`batch.Selection`. The merge orders only rows that already match, so its `maxElementSize`
cap holds the top-N of the filtered set. Gated on index order — filtered timestamp-order
queries still filter at the egress, unchanged. The scan-level cap and the client
`offset:offset+limit` slice are unchanged.
The operator is one new file, `pkg/query/vectorized/stream/tag_filter.go`. It copies the
shape of `Distinct` and `Limit` in the same package: the same `FusibleOperator` methods and
the same idempotent `Close`. It reuses `logical.TagFilter` rather than reimplementing
predicate semantics, so a criteria expression means the same thing on both paths.
The deleted merge-cap comment argued that a cap is unsound because a top-(limit+offset)
window taken before the filter can hold arbitrarily few survivors. That is correct while
the filter is at the egress, and the pushdown removes its premise.
The egress filter stays, and `hasFilter` stays true. That bool also gates the columnar
frame path off, and disabling it would stop the only hidden-tag strip on the vec path and
leak filter-only tags to the client.
New import edge: `pkg/query/vectorized/stream` now imports `pkg/query/logical`, to reuse
`logical.TagFilter`. It is cycle-free, and `check-import-boundaries` does not cover it.
## Completeness and verification
The merge-state bound is complete. `make lint` 0 findings, `make check` clean,
`banyand/stream` 17 of 17 Ginkgo specs, standalone integration 16 suites / 1840 specs, distributed
integration 14 suites / 885 specs. No golden fixture was regenerated.
Benchmark: 100k rows, 1024-row batches, cap 20, fixed seed, medians of `-count=5`.
"Before" is merge cap 0 with no pre-merge filter.
| criteria keeps | time | bytes |
|---|---|---|
| 1% | 91.86 ms → 4.13 ms | 13.09 MB → 1.88 MB |
| 95% | 93.22 ms → 35.91 ms | 13.09 MB → 1.98 MB |
The filter adds work: at a 95% pass rate, +1.5-3.7 ms per 100k rows, about 15-37 ns and
one allocation per scanned row, from the `parseExpr` call `logical.tagExpr` makes on every
`Match`. The measured win is a lower bound, because the "before" arm passes limit 20 while
the real pre-change shape passed `math.MaxUint32`.
This does not bound scan I/O, batch pinning (`SortedMerge` still retains batches), or the
liaison-side distributed merge.
Server cases: `sort_duration_no_index_limit` already pinned this shape — DESC, limit 2, a
non-indexed criteria tag. This PR adds `sort_duration_filter_range_limit_offset`: ASC, with
an offset and an indexed range criteria. The offset matters because the cap is
`limit+offset` while the egress slice is `offset:offset+limit`. No integration golden can
be red against this change, because the pre-change code was correct and only unbounded, so
only a white-box merge-state or element-count test tells the two apart.
## Behaviour differences
One, on duplicate `ElementID`. Before, an element survives the criteria if its first row in
the path's order matches. After, it survives if any of its rows matches.
Duplicate `ElementID`s are reachable three ways: the write path appends with no upsert or
uniqueness check (`write_standalone.go:181,184`), a part merge never dedups by element id
(`merger.go:425-460`), and `ElementID` is a 64-bit xxhash of `group|name|<client id>`
(`write_standalone.go:181`, `pkg/convert/hash.go:28-30`), so two distinct client ids in the
same stream collide at the 2^64 birthday bound. Ids in different streams cannot.
That region is already undefined — the row path keeps the first row in storage order, vec
`Distinct` the first in sort order — so the two engines disagree about which row's values
they return. This change escalates that from which values to whether the element
appears, which changes result cardinality.
Keeping the old rule needs a running set of every `ElementID` seen, which trades an
unbounded merge buffer for an unbounded dedup set.
## Open questions
**Duplicate `ElementID` semantics.** Described above. Which rule should hold is a design
call rather than an implementation one, so this PR ships the pushdown and leaves the
question open.
**Sequencing against #1326.** R1 of #14056 names the row path as the oracle, and #1326
deletes it. This is built on `main`. Applied on top of #1326 instead, the production diff
is identical and four mechanical edits are needed: delete the row-path `result` field,
delete a three-line row-path stub in the new pushdown test, add `schema: vecTestSchema(t)`
to one scan literal, and move the CHANGES.md bullet under a new `### Chores` heading. Git
reports no conflict on that stub, so the file merges silently and then fails to compile.
## Other issues found while working on this
Three, none fixed here.
1. **Null ordered tags sort at opposite ends.** Pre-existing — this change neither causes
nor worsens it. The row path orders by the inverted index, which places a document
missing the sort field last in both directions, while the vec path marshals a null cell
to empty bytes, which sorts first ascending. An ASC query with a limit below the number
of null-ordered elements therefore returns disjoint sets on the two engines. It
reproduces today on the criteria-less capped path.
2. **The `!hasFilter` frame-egress gate.** Lifting it would let criteria queries use the
columnar wire, but the frame path first needs a hidden-tag strip of its own.
3. **Early scan termination.** The scan still emits every matching row. Bounding that needs
the filter inside `banyand/stream/query_vectorized.go` plus a sort-key watermark from
the merge.
Happy to change anything here, and to file those three as separate issues or include any
in this PR — whichever you prefer.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@skywalking.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(stream): bound the filtered index-order vectorized Top-N merge [skywalking-banyandb]
Posted by "hanahmily (via GitHub)" <gi...@apache.org>.
hanahmily commented on PR #1331:
URL: https://github.com/apache/skywalking-banyandb/pull/1331#issuecomment-5579291378
Thanks for the investigation and the duplicate coverage. Filter-first is the intended behavior: evaluate the criteria first, then among matching rows with the same ElementID, keep the first in the requested sort order. A matching version should make the element eligible even if another version fails the criteria.
Please keep the pushdown. Do not use the row path as the oracle for this decision; it will be removed. The behavior difference from the old vectorized pipeline is accepted under this rule.
Please finalize the regression tests against this contract, retaining the cross-batch and offset/limit coverage and asserting the selected version’s values/sort key as well as the ordered IDs. Update the PR description, release note, and relevant comments to mark the duplicate semantics as settled rather than an open question, and remove claims of unconditional row-path parity.
The existing benchmark is sufficient for this change. Please also rerun the failed Zipkin Vec check; its log shows a swctl archive installation failure rather than a query assertion failure.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@skywalking.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(stream): bound the filtered index-order vectorized Top-N merge [skywalking-banyandb]
Posted by "SammyUrfen (via GitHub)" <gi...@apache.org>.
SammyUrfen commented on PR #1331:
URL: https://github.com/apache/skywalking-banyandb/pull/1331#issuecomment-5571109013
Thanks, that reproduces — and you're right that the egress re-check can't recover it.
I've added a regression for it: `TestTagFilterDuplicateWinnerSemantics` in `pkg/query/vectorized/stream`. Six rows, two elements carrying conflicting versions, asserting exact ordered ids in a single batch and with each duplicate pair straddling a batch boundary, for limit and for offset+limit. It also runs the pushdown with the merge cap disabled and gets the same ids back, so the cap isn't what changes membership, and no cap can undo it.
One thing I hit while writing it that bears on the rule you pick: the row path isn't the old vec pipeline either. For a filtered index-order query it admits an element if any of its index documents matches (`inverted.go:232` inserts rather than updates), takes the sort position from the first doc in sort order (`query_by_idx.go:228-240`), then re-tests the criteria on the first row in storage order among the rows actually scanned (`mergeByTagValue`, `query_by_idx.go:301-311`). For your example that comes out as `[B]` or `[A,B]` depending on which of A's rows was stored first, and on compaction state. The old vec pipeline keys on the sort-first row, so the two already disagree on a corpus like this.
Preserving the sort-first rule under the pushdown also looks incompatible with the bound. The representative is picked before the predicate runs, and two rows of one element can sit arbitrarily far apart in sort order, so the state needed grows with every distinct id in the scan whenever the criteria is selective. I tried four designs and broke all four — happy to write that up if it's useful.
Could you pin the rule for me: first-in-storage, first-in-sort, or any-row-matches? I'll make the test assert whichever you choose, and if it isn't any-row-matches I'll pull the pushdown out of this PR and open a separate design issue for it.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@skywalking.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(stream): bound the filtered index-order vectorized Top-N merge [skywalking-banyandb]
Posted by "SammyUrfen (via GitHub)" <gi...@apache.org>.
SammyUrfen commented on PR #1331:
URL: https://github.com/apache/skywalking-banyandb/pull/1331#issuecomment-5585360706
Pushed, and the description is updated — the duplicate rule reads as settled there, in the release note and in the comments, and the row-path parity claims are gone.
`TestTagFilterDuplicateWinnerSemantics` asserts your rule with the selected version's tag values and sort key alongside the ordered ids, ascending and descending, across a batch boundary, and with an offset. `TestTagFilterDuplicateTieOnSortKey` covers the equal-sort-key case, where the tie falls to arrival order in both directions.
I also tightened `TestPushdown_FilteredIndexOrder_BoundsMerge`, item 1 from your first review. It was count-only over a corpus where every row matched, so the pushdown could be deleted without failing anything. It now asserts exact ordered ids.
Zipkin Vec is green.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@skywalking.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(stream): bound the filtered index-order vectorized Top-N merge [skywalking-banyandb]
Posted by "hanahmily (via GitHub)" <gi...@apache.org>.
hanahmily commented on code in PR #1331:
URL: https://github.com/apache/skywalking-banyandb/pull/1331#discussion_r3947335949
##########
pkg/query/logical/stream/stream_plan_indexscan_local_vectorized.go:
##########
@@ -310,32 +316,24 @@ func (i *localIndexScan) ExecuteVectorized(ctx context.Context) ([]*vectorized.R
// applies the SAME limit with offset 0 as a defensive client slice; the final
// client offset:offset+limit slice is the enclosing *limit node's job (row path
// parity).
- // A criteria query applies a tag filter at egress AFTER this merge. Capping the
- // merge at maxElementSize here would keep only the top-N BEFORE the filter runs
- // and starve it (the row path streams the whole ordered set and filters lazily).
- // So defer the cap to the egress: run the merge UNCAPPED (mergeCap 0) and make the
- // trailing pipeline Limit a pass-through (MaxUint32, since a 0 limit emits
- // NOTHING) — the egress then applies the tag filter and the true
- // offset:offset+limit slice.
- //
- // This path is therefore NOT bounded by limit+offset, and cannot be until the
- // tag filter moves ahead of the merge. Any cap here is unsound in general: the
- // filter's selectivity is unknown, so the top-(limit+offset) rows BEFORE it can
- // contain arbitrarily few surviving rows — including zero — while the row path
- // keeps pulling until it has enough. Bounding it needs columnar tag-filter
- // pushdown (out of scope here), not a bigger cap.
+ // A criteria query runs its tag filter as a PRE-MERGE fusible, so the merge sees
+ // only surviving rows and the cap keeps the top-N of the FILTERED set — not a
+ // top-N taken before the filter, which the filter's unknown selectivity could
+ // leave empty. The egress still applies the same filter; on rows that already
+ // passed here that re-check is a no-op, and it remains the hidden-tag strip.
+ var preMerge []vectorized.FusibleOperator
+ if i.preMergeFilter != nil {
+ preMerge = append(preMerge,
+ vstream.NewTagFilter(schema, i.projectionTags, i.preMergeFilter, i.filterRegistry))
Review Comment:
[P1] Preserve duplicate-winner semantics before pushing down the predicate. This filter runs before SortedMerge's distinct-ID pruning and Distinct. If the first ordered version of ID A fails the predicate but a later version passes, the first version is removed and A is now emitted. A production-operator reproduction with `(A, closed), (A, open), (B, open)`, `state=open`, limit 2 returns `[B]` on the previous pipeline and `[A,B]` here. Rechecking at egress cannot undo this. Existing bounds/selectivity tests do not exercise conflicting predicate values for the same ID; please add exact-result duplicate parity coverage and resolve the semantic regression.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@skywalking.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(stream): bound the filtered index-order vectorized Top-N merge [skywalking-banyandb]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #1331:
URL: https://github.com/apache/skywalking-banyandb/pull/1331#issuecomment-5562305220
## [Codecov](https://app.codecov.io/gh/apache/skywalking-banyandb/pull/1331?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `91.42857%` with `6 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 50.11%. Comparing base ([`3530dd9`](https://app.codecov.io/gh/apache/skywalking-banyandb/commit/3530dd9b5cefaa4fef60eec91ecbfbdfcaf243c5?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`b55c0aa`](https://app.codecov.io/gh/apache/skywalking-banyandb/commit/b55c0aa88f16b831cd1a5aca620a01b052087a07?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 418 commits behind head on main.
| [Files with missing lines](https://app.codecov.io/gh/apache/skywalking-banyandb/pull/1331?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [pkg/query/vectorized/stream/tag\_filter.go](https://app.codecov.io/gh/apache/skywalking-banyandb/pull/1331?src=pr&el=tree&filepath=pkg%2Fquery%2Fvectorized%2Fstream%2Ftag_filter.go&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cGtnL3F1ZXJ5L3ZlY3Rvcml6ZWQvc3RyZWFtL3RhZ19maWx0ZXIuZ28=) | 93.10% | [2 Missing and 2 partials :warning: ](https://app.codecov.io/gh/apache/skywalking-banyandb/pull/1331?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [pkg/query/vectorized/stream/pipeline.go](https://app.codecov.io/gh/apache/skywalking-banyandb/pull/1331?src=pr&el=tree&filepath=pkg%2Fquery%2Fvectorized%2Fstream%2Fpipeline.go&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cGtnL3F1ZXJ5L3ZlY3Rvcml6ZWQvc3RyZWFtL3BpcGVsaW5lLmdv) | 50.00% | [1 Missing and 1 partial :warning: ](https://app.codecov.io/gh/apache/skywalking-banyandb/pull/1331?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #1331 +/- ##
==========================================
+ Coverage 45.97% 50.11% +4.14%
==========================================
Files 328 283 -45
Lines 55505 29686 -25819
==========================================
- Hits 25520 14878 -10642
+ Misses 27909 13439 -14470
+ Partials 2076 1369 -707
```
| [Flag](https://app.codecov.io/gh/apache/skywalking-banyandb/pull/1331/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Coverage Δ | |
|---|---|---|
| [fodc](https://app.codecov.io/gh/apache/skywalking-banyandb/pull/1331/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `59.89% <ø> (?)` | |
| [pkg](https://app.codecov.io/gh/apache/skywalking-banyandb/pull/1331/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `47.50% <91.42%> (?)` | |
Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#carryforward-flags-in-the-pull-request-comment) to find out more.
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/skywalking-banyandb/pull/1331?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@skywalking.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(stream): bound the filtered index-order vectorized Top-N merge [skywalking-banyandb]
Posted by "hanahmily (via GitHub)" <gi...@apache.org>.
hanahmily merged PR #1331:
URL: https://github.com/apache/skywalking-banyandb/pull/1331
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@skywalking.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org