github-actions[bot] commented on code in PR #68093:
URL: https://github.com/apache/doris/pull/68093#discussion_r4027208502
##########
be/src/exprs/aggregate/aggregate_function_window_funnel_v2.h:
##########
@@ -288,6 +288,54 @@ struct WindowFunnelStateV2 {
}
};
+ /// One partial chain of the INCREASE mode.
+ /// first_ts is the timestamp of the chain start and is used for the
time-window check,
+ /// last_ts is the timestamp of the chain's last matched event and is used
for the
+ /// strict-increase check, list_idx is the position of that event in
events_list.
+ struct IncreaseLevelState {
+ TimestampType first_ts = 0;
+ TimestampType last_ts = 0;
+ size_t list_idx = 0;
+ };
+
+ /// Keep the state of `level_states` that can reach at least as far as any
other one: the
+ /// chain start that is the latest, because every event the other states
can extend has to be
+ /// strictly greater than their last timestamp, and the earlier chain
start expires first.
+ static void _merge_increase_state(std::vector<IncreaseLevelState>&
level_states,
+ const IncreaseLevelState& new_state) {
+ level_states.push_back(new_state);
+ IncreaseLevelState best = level_states[0];
+ for (const auto& state : level_states) {
+ if (state.first_ts > best.first_ts ||
Review Comment:
[P2] Preserve the advertised V1 behavior, or make the semantic break
explicit. For the reachable sorted order `A@0, B@0, B@1, [email protected], B@2, C@2`, V1
stops the first start at `B@0` and the second at `C@2`, so it returns 2;
pre-patch V2 also returns 2 because `B@2` overwrites `B@1`. This helper retains
`B@1` and returns 3 through `C@2`. V1's timestamp-only sort makes tie order
unstable, but that does not remove this reachable old=V1/new!=V1 transition. If
V1 compatibility remains the contract, use its sequential expected-level scan;
if existential longest-chain semantics are intended, please document that
compatibility change and add this case as a deliberate divergence.
##########
regression-test/suites/query_p0/aggregate/window_funnel_v2.groovy:
##########
@@ -899,4 +899,39 @@ suite("window_funnel_v2") {
SELECT window_funnel(864000, 'fixed', ts, val>8, val<8, val>15) FROM
windowfunnel_v2_fixed_edge;
"""
sql """ DROP TABLE IF EXISTS windowfunnel_v2_fixed_edge """
+
+ // Test INCREASE mode: a later event of an intermediate level must not
overwrite the state
+ // that is still able to extend the chain.
+ // A@0 -> B@1 -> C@2 is valid, the second B@2 must not hide B@1 from C@2.
+ sql """ DROP TABLE IF EXISTS windowfunnel_v2_increase_overwrite """
+ sql """
+ CREATE TABLE windowfunnel_v2_increase_overwrite (
+ ts datetimev2(6) NULL,
+ e varchar(10) NULL
+ )
+ DUPLICATE KEY(ts) DISTRIBUTED BY HASH(ts) BUCKETS 3
+ PROPERTIES ("replication_num" = "1");
+ """
+ sql """
+ INSERT INTO windowfunnel_v2_increase_overwrite VALUES
+ ('2022-03-12 10:00:00', 'A'), ('2022-03-12 10:00:01', 'B'),
+ ('2022-03-12 10:00:02', 'B'), ('2022-03-12 10:00:02', 'C');
+ """
+ // increase mode: only c2@1 can be extended by c3@2, so the level is 3.
+ order_qt_v2_increase_extendable_level """
+ SELECT window_funnel(10, 'increase', ts, e = 'A', e = 'B', e = 'C') AS
level
+ FROM windowfunnel_v2_increase_overwrite;
+ """
+ // default mode is not affected: each condition has a matching event after
the previous one.
+ order_qt_v2_increase_extendable_level_default """
+ SELECT window_funnel(10, 'default', ts, e = 'A', e = 'B', e = 'C') AS
level
+ FROM windowfunnel_v2_increase_overwrite;
+ """
+ // deduplication mode also reaches 3: the repeated 'B' row is not inside
the gap that is
+ // checked when the chain advances, so the chain A@0 -> B@1 -> C@2 stays
valid.
+ order_qt_v2_increase_extendable_level_dedup """
Review Comment:
[P2] Make this equal-timestamp regression self-consistent. The old INCREASE
code fails only when `B@2` is visited before `C@2`, but under that same order
deduplication finds `B@2` in the gap before `C` and returns 2, not the recorded
3. Reversing the tie yields deduplication 3, but then the old INCREASE code
already returns 3, so this SQL case no longer proves the fix. Since `ts` is the
only key/order value, please force the intended order and expect deduplication
2, or split/remove the unrelated dedup assertion.
##########
be/src/exprs/aggregate/aggregate_function_window_funnel_v2.h:
##########
@@ -288,6 +288,54 @@ struct WindowFunnelStateV2 {
}
};
+ /// One partial chain of the INCREASE mode.
+ /// first_ts is the timestamp of the chain start and is used for the
time-window check,
+ /// last_ts is the timestamp of the chain's last matched event and is used
for the
+ /// strict-increase check, list_idx is the position of that event in
events_list.
+ struct IncreaseLevelState {
+ TimestampType first_ts = 0;
+ TimestampType last_ts = 0;
+ size_t list_idx = 0;
+ };
+
+ /// Keep the state of `level_states` that can reach at least as far as any
other one: the
+ /// chain start that is the latest, because every event the other states
can extend has to be
+ /// strictly greater than their last timestamp, and the earlier chain
start expires first.
+ static void _merge_increase_state(std::vector<IncreaseLevelState>&
level_states,
+ const IncreaseLevelState& new_state) {
+ level_states.push_back(new_state);
+ IncreaseLevelState best = level_states[0];
+ for (const auto& state : level_states) {
+ if (state.first_ts > best.first_ts ||
+ (state.first_ts == best.first_ts && state.last_ts <
best.last_ts)) {
+ best = state;
+ }
+ }
+ level_states.assign(1, best);
+ }
+
+ /// Remove the states of the levels below `updated_level` that can no
longer be part of a
+ /// better chain: a state of a higher level whose last timestamp is not
greater can extend
+ /// every event the lower state can extend, and it already reaches a
higher level.
+ static void
_prune_increase_levels(std::vector<std::vector<IncreaseLevelState>>& levels,
+ int updated_level) {
+ for (int level = updated_level; level >= 0 && !levels[level].empty();
--level) {
+ bool dominated = false;
+ for (int higher = level + 1; higher <
static_cast<int>(levels.size()) && !dominated;
Review Comment:
[P1] Avoid the all-level scan on every successful event. With 127 supported
conditions, a valid group containing many event-0 rows followed by one strictly
increasing match for levels 1..125 and no level 126 never hits the full-chain
return; this loop performs about 675k higher-level checks per start before the
normal event scan, versus one predecessor update per event before this patch.
Repeated level-125 matches add 8,001 checks each even when the retained state
does not change. Please use flat per-level state and an O(K) frontier/suffix
pass (or remove the unnecessary cross-level pruning) so this fix does not turn
high-arity funnels into an O(M*N*K^2) hot path.
##########
regression-test/suites/query_p0/aggregate/window_funnel_v2.groovy:
##########
@@ -899,4 +899,39 @@ suite("window_funnel_v2") {
SELECT window_funnel(864000, 'fixed', ts, val>8, val<8, val>15) FROM
windowfunnel_v2_fixed_edge;
"""
sql """ DROP TABLE IF EXISTS windowfunnel_v2_fixed_edge """
+
+ // Test INCREASE mode: a later event of an intermediate level must not
overwrite the state
+ // that is still able to extend the chain.
+ // A@0 -> B@1 -> C@2 is valid, the second B@2 must not hide B@1 from C@2.
+ sql """ DROP TABLE IF EXISTS windowfunnel_v2_increase_overwrite """
+ sql """
+ CREATE TABLE windowfunnel_v2_increase_overwrite (
+ ts datetimev2(6) NULL,
+ e varchar(10) NULL
+ )
+ DUPLICATE KEY(ts) DISTRIBUTED BY HASH(ts) BUCKETS 3
+ PROPERTIES ("replication_num" = "1");
+ """
+ sql """
+ INSERT INTO windowfunnel_v2_increase_overwrite VALUES
+ ('2022-03-12 10:00:00', 'A'), ('2022-03-12 10:00:01', 'B'),
+ ('2022-03-12 10:00:02', 'B'), ('2022-03-12 10:00:02', 'C');
+ """
+ // increase mode: only c2@1 can be extended by c3@2, so the level is 3.
+ order_qt_v2_increase_extendable_level """
+ SELECT window_funnel(10, 'increase', ts, e = 'A', e = 'B', e = 'C') AS
level
+ FROM windowfunnel_v2_increase_overwrite;
+ """
+ // default mode is not affected: each condition has a matching event after
the previous one.
+ order_qt_v2_increase_extendable_level_default """
+ SELECT window_funnel(10, 'default', ts, e = 'A', e = 'B', e = 'C') AS
level
+ FROM windowfunnel_v2_increase_overwrite;
+ """
+ // deduplication mode also reaches 3: the repeated 'B' row is not inside
the gap that is
+ // checked when the chain advances, so the chain A@0 -> B@1 -> C@2 stays
valid.
+ order_qt_v2_increase_extendable_level_dedup """
+ SELECT window_funnel(10, 'deduplication', ts, e = 'A', e = 'B', e =
'C') AS level
+ FROM windowfunnel_v2_increase_overwrite;
+ """
+ sql """ DROP TABLE IF EXISTS windowfunnel_v2_increase_overwrite """
Review Comment:
[P2] Keep this table after the regression runs. The repository test contract
requires dropping before use, not after completion, so failure state remains
available for debugging; this block already has the required pre-test DROP at
line 906. Please remove this trailing cleanup.
--
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]
