jacktengg opened a new pull request, #68093:
URL: https://github.com/apache/doris/pull/68093
### What problem does this PR solve?
Problem Summary:
`window_funnel(..., 'increase', ...)` returned a lower level than expected
when an intermediate condition matched more than once, because the INCREASE
path of the V2 implementation (`WindowFunnelStateV2::_get_increase`) kept only
a single state per level and overwrote it unconditionally with the later event.
The overwriting event is not always able to extend the chain (the timestamps
have to increase strictly), while the overwritten one still was, so the
remaining events could no longer be attached to the chain.
Reproduction:
```sql
SELECT window_funnel(10, 'increase', ts, e = 'A', e = 'B', e = 'C') AS inc
FROM (
SELECT CAST('2026-01-01 00:00:00' AS DATETIMEV2(6)) AS ts, 'A' AS e
UNION ALL SELECT CAST('2026-01-01 00:00:01' AS DATETIMEV2(6)), 'B'
UNION ALL SELECT CAST('2026-01-01 00:00:02' AS DATETIMEV2(6)), 'B'
UNION ALL SELECT CAST('2026-01-01 00:00:02' AS DATETIMEV2(6)), 'C'
) t;
```
Before the fix this returned 2, because `B@2` overwrote `B@1` and the
strict-increase check then rejected `C@2` (`2 < 2` is false). The valid chain
is `A@0 -> B@1 -> C@2`.
Root cause:
For every level the algorithm stored exactly one `(first_ts, last_ts,
list_idx)` state and replaced it whenever a later event extended the same
level. Two different states of one level are not interchangeable: the earlier
one is the only one that can still satisfy the strict increase for an event
with the same timestamp, while the later one is required to extend an event
that lies after it. Both have to be kept until one of them is provably
dominated.
Fix:
The INCREASE scan now keeps, per level, the most permissive partial chain
instead of the last one:
- when several states of a level are reachable, the state with the latest
chain start is retained, because it expires last in the time-window check and
every event that can be attached to another state can be attached to it as well;
- a state is dropped once a state of a higher level has a last timestamp
that is not greater, because that state can extend every event the lower one
can extend and already reaches a higher level;
- each event extends the most permissive eligible state of the previous
level.
With the fix the statement above returns 3. The default, deduplication and
fixed modes are untouched, and the new rule was cross-checked against
`window_funnel_v1` semantics.
### Release note
Fix `window_funnel` with the `increase` mode returning a too small number of
levels when an intermediate condition occurs more than once.
### Check List (For Author)
- Test: Unit Test / Regression test
- New unit test
`VWindowFunnelV2Test.testIncreaseModeExtendableIntermediateLevelKept` covering
`A@0, B@1, B@2, C@2`; all 36 `*WindowFunnel*` unit tests pass.
- New regression blocks in
`regression-test/suites/query_p0/aggregate/window_funnel_v2.groovy`; the `.out`
file was generated with `-forceGenOut` and the suite passed afterwards. The
final re-run of the suite was blocked by a worktree port re-allocation in the
test host, the recorded output is unchanged by the follow-up refactoring of the
fix.
- The new algorithm was additionally validated against an exhaustive
search over chain lengths on 80k randomized inputs (conditions 2..6, rows up to
10, several window sizes).
- Behavior changed: Yes (see above)
- Does this need documentation: No
### What problem does this PR solve?
Issue Number: close #xxx
Related PR: #xxx
Problem Summary:
### Release note
None
### Check List (For Author)
- Test <!-- At least one of them must be included. -->
- [ ] Regression test
- [ ] Unit Test
- [ ] Manual test (add detailed scripts or steps below)
- [ ] No need to test or manual test. Explain why:
- [ ] This is a refactor/code format and no logic has been changed.
- [ ] Previous test can cover this change.
- [ ] No code files have been changed.
- [ ] Other reason <!-- Add your reason? -->
- Behavior changed:
- [ ] No.
- [ ] Yes. <!-- Explain the behavior change -->
- Does this need documentation?
- [ ] No.
- [ ] Yes. <!-- Add document PR link here. eg:
https://github.com/apache/doris-website/pull/1214 -->
### Check List (For Reviewer who merge this PR)
- [ ] Confirm the release note
- [ ] Confirm test cases
- [ ] Confirm document
- [ ] Add branch pick label <!-- Add branch pick label that this PR should
merge into -->
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
