yujun777 commented on PR #69890:
URL: https://github.com/apache/doris/pull/69890#issuecomment-6519641457
The incremental MIN/MAX state in one place, as formulas. Everything below is
per group; `MAX` is the same with the order reversed.
**Notation**
```
n number of non-NULL input rows of the group (the COUNT state)
S [(v1,c1), ..., (vm,cm)] the retained pairs, values ascending, m <= K,
ci > 0
b the trusted bound: only values <= b are known exactly; b = NULL means
complete
K ivm_minmax_top_k
```
`S` is a bounded top-K list, so a value that falls off the list is only
known to be worse than every retained one: the state is exact for `v <= b` and
a lower bound beyond it.
**One refresh batch**
```
I = top-K of the inserted rows, ascending, with their counts
D = top-K of the deleted rows, ascending, with their counts
dn = inserted non-NULL rows - deleted non-NULL rows
bI = (|I| == K) ? I[K].value : NULL -- a full side may have
dropped values
bD = (|D| == K) ? D[K].value : NULL
bE = min over the non-NULL values of {b, bI, bD} (NULL when all three
are NULL)
```
Truncating each side is safe because `topK(A u B) = topK(topK(A) u
topK(B))`, and a side that holds exactly K entries is conservatively treated as
truncated.
**Apply**
```
merge(S, I, D) = sorted by value, count(v) = cS(v) + cI(v) - cD(v), keep
count > 0
(only values v <= bE are used: outside it a truncated side
may be missing rows)
S_pre = merge(S, I, D)
S' = S_pre[1 .. min(K, |S_pre|)] -- the new state
n' = n + dn
```
So the state update is `S' = first K of (S + I - D)` over the trusted range,
and the visible `MIN` is `S'[1].value` with its count `S'[1].count`.
**Bound**
```
b' = NULL if n' == 0
(the group is gone)
b' = NULL if b == bI == bD == NULL
and |S_pre| <= K
(still complete)
b' = S_pre[K+1].value if |S_pre| > K
(new truncation point)
b' = bE otherwise
(carry the merged bound)
```
The second case is where the state becomes complete again: every side was
complete and the merged list still fits, so nothing was dropped.
**Fallback**
```
if |S_pre| == 0 and n' > 0:
MIN_MAX_BOUNDARY_HIT
```
An empty candidate list with rows still in the group means the batch deleted
the last row of the current extreme, and a deleted value inside a truncated
range is not recoverable from the state. The refresh then fails, or falls back
to a complete refresh when the MV was created with `FALLBACK`, leaving the MV's
rows untouched until it succeeds.
**K = 0 (extreme-only mode)**
The list holds at most one pair, so `S' = (min(S[1].value, I[1].value), sum
of the counts when they are equal)`; a non-empty `D` means a non-NULL value was
retracted, which breaks the append-only premise the mode is created on and
trips the same fallback. This is the mode an append-only plan is created with
when `ivm_minmax_top_k` is not set explicitly.
--
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]
