pepijnve commented on PR #18152: URL: https://github.com/apache/datafusion/pull/18152#issuecomment-3447841401
> I haven't had a chance to re-review the case body evaluation in detail yet
but I will try and do so soon
@alamb I'm only now coming to the realisation what a secondary benefit of
the change in the case body evaluation is. Deserves some extra explanation.
Suppose you're evaluating `CASE WHEN c1 = 1 THEN c2 WHEN c1 = 2 then c3 WHEN
c1 = 3 THEN c4 END`.
The current implementation will go through the steps I sketched below. In
every iteration it starts from the full input record batch, and uses
evaluate_selection to compute results for subsets. In each round the result is
merged using `zip` and the progress so far is tracked using a 'remaining'
boolean array.
<details>
<summary>Diagram of current algorithm</summary>
```
cur rem c1 c2 c3 c4 when
┌───┐┌───┐ ┌───┬───┬───┬───┐ ┌───┐
┌───┐
│ ││ x │ │ 1 │ a │ u │ 9 │ │ x │
│ a │
├───┤├───┤ ├───┼───┼───┼───┤ ├───┤
├───┤
│ ││ x │ │ 3 │ b │ v │ 8 │ │ │ c1 c2 c3 c4 c2
│ │
├───┤├───┤ ├───┼───┼───┼───┤ ├───┤ ┌───┬───┬───┬───┐ ┌───┐
├───┤
│ ││ x │ │ 2 │ c │ w │ 7 │ │ │ │ 1 │ a │ u │ 9 │ │ a │
│ │
├───┤├───┤ ├───┼───┼───┼───┤ ├───┤ ├───┼───┼───┼───┤ ─► ├───┤
─► ├───┤
│ ││ x │ │ 1 │ d │ x │ 6 │ │ x │ │ 1 │ d │ x │ 6 │eval│ d
│scat│ d │
├───┤├───┤ ├───┼───┼───┼───┤ ├───┤ └───┴───┴───┴───┘ └───┘
├───┤
│ ││ x │ │ 2 │ e │ y │ 5 │ │ │ ▲
│ │
├───┤├───┤ ├───┼───┼───┼───┤ ├───┤ │
├───┤
│ ││ x │ │ 3 │ f │ z │ 4 │ │ │ │
│ │
└─┬─┘└───┘ └───┴───┴───┴───┘ └───┘ │
└───┘
│ │││ │ eval_sel ▲ │ │
│
│ └││────────────┴──────────────┘ │ │eval_sel
│
│ └│─────────────────────────────┴─────────────┘
│
├─────┴───────────────────────────────────────────────────────────────────┘
│
│
│zip
▼
cur rem c1 c2 c3 c4 when
┌───┐┌───┐ ┌───┬───┬───┬───┐ ┌───┐
┌───┐
│ a ││ │ │ 1 │ a │ u │ 9 │ c1 c2 c3 c4 │ │
│ │
├───┤├───┤ ├───┼───┼───┼───┤ ┌───┬───┬───┬───┐ ┌───┐ ├───┤
├───┤
│ ││ x │ │ 3 │ b │ v │ 8 │ │ 3 │ b │ v │ 8 │ │ │ │ │
c1 c2 c3 c4 c3 │ │
├───┤├───┤ ├───┼───┼───┼───┤ ├───┼───┼───┼───┤ ├───┤ ├───┤
┌───┬───┬───┬───┐ ┌───┐ ├───┤
│ ││ x │ │ 2 │ c │ w │ 7 │ │ 2 │ c │ w │ 7 │ │ x │ │ x │
│ 2 │ c │ w │ 7 │ │ w │ │ w │
├───┤├───┤ ├───┼───┼───┼───┤ ├───┼───┼───┼───┤ ─► ├───┤ ─► ├───┤
├───┼───┼───┼───┤ ─► ├───┤ ─► ├───┤
│ d ││ │ │ 1 │ d │ x │ 6 │ │ 2 │ e │ y │ 5 │eval│ x │scat │ │
│ 2 │ e │ y │ 5 │eval│ y │scat│ │
├───┤├───┤ ├───┼───┼───┼───┤ ├───┼───┼───┼───┤ ├───┤ ├───┤
└───┴───┴───┴───┘ └───┘ ├───┤
│ ││ x │ │ 2 │ e │ y │ 5 │ │ 3 │ f │ z │ 4 │ │ │ │ x │
▲ │ y │
├───┤├───┤ ├───┼───┼───┼───┤ └───┴───┴───┴───┘ └───┘ ├───┤
│ ├───┤
│ ││ x │ │ 3 │ f │ z │ 4 │ ▲ │ │
│ │ │
└─┬─┘└───┘ └───┴───┴───┴───┘ │ └───┘
│ └───┘
│ │││ │ eval_sel │ │
│ │
│ └││────────────┴───────────────────┘ │
│eval_sel │
│
└│─────────────────────────────────────────────────────────┴──────────────┘
│
├─────┴────────────────────────────────────────────────────────────────────────────────────────────────┘
│
│
│zip
▼
cur rem c1 c2 c3 c4 when
┌───┐┌───┐ ┌───┬───┬───┬───┐ ┌───┐
┌───┐
│ a ││ │ │ 1 │ a │ u │ 9 │ │ │
│ │
├───┤├───┤ ├───┼───┼───┼───┤ ├───┤
├───┤
│ ││ x │ │ 3 │ b │ v │ 8 │ c1 c2 c3 c4 │ x │
c1 c2 c3 c4 c4 │ 8 │
├───┤├───┤ ├───┼───┼───┼───┤ ┌───┬───┬───┬───┐ ┌───┐ ├───┤
┌───┬───┬───┬───┐ ┌───┐ ├───┤
│ w ││ │ │ 2 │ c │ w │ 7 │ │ 3 │ b │ v │ 8 │ │ x │ │ │
│ 3 │ b │ v │ 8 │ │ 8 │ │ │
├───┤├───┤ ├───┼───┼───┼───┤ ├───┼───┼───┼───┤ ─► ├───┤ ─► ├───┤
├───┼───┼───┼───┤ ─► ├───┤ ─► ├───┤
│ d ││ │ │ 1 │ d │ x │ 6 │ │ 3 │ f │ z │ 4 │eval│ x │scat │ │
│ 3 │ f │ z │ 4 │eval│ 4 │scat│ │
├───┤├───┤ ├───┼───┼───┼───┤ └───┴───┴───┴───┘ └───┘ ├───┤
└───┴───┴───┴───┘ └───┘ ├───┤
│ y ││ │ │ 2 │ e │ y │ 5 │ ▲ │ │
▲ │ │
├───┤├───┤ ├───┼───┼───┼───┤ │ ├───┤
│ ├───┤
│ ││ x │ │ 3 │ f │ z │ 4 │ │ │ x │
│ 0 │ 4 │
└─┬─┘└───┘ └───┴───┴───┴───┘ │ └───┘
│ └───┘
│ │││ │ eval_sel │ │
│ │
│ └││────────────┴───────────────────┘ │
│eval_sel │
│
└│─────────────────────────────────────────────────────────┴──────────────┘
│
├─────┴────────────────────────────────────────────────────────────────────────────────────────────────┘
│
│
│zip
▼
cur
┌───┐
│ a │
├───┤
│ 8 │
├───┤
│ w │
├───┤
│ d │
├───┤
│ y │
├───┤
│ 4 │
└───┘
```
</details>
In this PR, the record batch is augmented with a row index array. This array
gets filtered along with the record batch. Regular evaluate is used to compute
results. After each round a filter is used so that we only retain the remaining
rows (and their indices). The partial result is added to the arrays list and
the result indices array is updated.
At the end we merge everything. Hopefully you can see these steps reflected
in the code.
<details>
<summary>Diagram of modified algorithm</summary>
```
ind arr row c1 c2 c3 c4 when
┌───┐ ┌───┐┌───┬───┬───┬───┐ ┌───┐
│ / │ │ 0 ││ 1 │ a │ u │ 9 │ │ x │
├───┤ ├───┤├───┼───┼───┼───┤ ├───┤
│ / │ │ 1 ││ 3 │ b │ v │ 8 │ │ │ row c1 c2 c3 c4
c2
├───┤ ├───┤├───┼───┼───┼───┤ ├───┤
┌───┐┌───┬───┬───┬───┐ ┌───┐
│ / │ │ 2 ││ 2 │ c │ w │ 7 │ │ │ │ 0 ││ 1 │ a │ u │ 9
│ │ a │
├───┤ ├───┤├───┼───┼───┼───┤ ├───┤
├───┤├───┼───┼───┼───┤ ─► ├───┤
│ / │ │ 3 ││ 1 │ d │ x │ 6 │ │ x │ │ 3 ││ 1 │ d │ x │ 6
│eval│ d │
├───┤ ├───┤├───┼───┼───┼───┤ ├───┤
└───┘└───┴───┴───┴───┘ └───┘
│ / │ │ 4 ││ 2 │ e │ y │ 5 │ │ │ │ ▲
│
├───┤ ├───┤├───┼───┼───┼───┤ ├───┤ │ │
│
│ / │ │ 5 ││ 3 │ f │ z │ 4 │ │ │ │ │
│
└─┬─┘ └───┘└───┴───┴───┴───┘ └───┘ │ │filter
│
│ │ │ │ eval │ ▲││ │ │
│
│ └─│───┴─────────│──────────┘└│───────┼──────────┘
│
└──┬───────────│─────────────│────────────│───────┴─────────────────────────┘
│ │ │ │
│ │ │ │
add_batch│ └─┬───────────┴────────────┘
│ │ filter
▼ ▼
ind arr row c1 c2 c3 c4 when
┌───┐┌───┐ ┌───┐┌───┬───┬───┬───┐ ┌───┐
│ 0 ││ a │ │ 1 ││ 3 │ b │ v │ 8 │ │ │ row c1 c2 c3 c4
c3
├───┤├───┤ ├───┤├───┼───┼───┼───┤ ├───┤
┌───┐┌───┬───┬───┬───┐ ┌───┐
│ / ││ d │ │ 2 ││ 2 │ c │ w │ 7 │ │ x │ │ 2 ││ 2 │ c │ w │ 7
│ │ w │
├───┤└───┘ ├───┤├───┼───┼───┼───┤ ├───┤
├───┤├───┼───┼───┼───┤ ─► ├───┤
│ / │ │ 4 ││ 2 │ e │ y │ 5 │ │ x │ │ 4 ││ 2 │ e │ y │ 5
│eval│ y │
├───┤ ├───┤├───┼───┼───┼───┤ ├───┤
└───┘└───┴───┴───┴───┘ └───┘
│ 0 │ │ 5 ││ 3 │ f │ z │ 4 │ │ │ │ ▲
│
├───┤ └───┘└───┴───┴───┴───┘ └─┬┬┘ │ │
│
│ / │ │ │ │ eval │ ▲││ │ │filter
│
├───┤ └─│───┴─────────│──────────┘└│───────┼──────────┘
│
│ / │ │ │ │ │
│
└─┬─┘ │ │ │ │
│
└──┬───────────│─────────────│────────────│───────┴─────────────────────────┘
│ │ │ │
│ │ │ │
add_batch│ └─┬───────────┴────────────┘
│ │ filter
▼ ▼
ind arr row c1 c2 c3 c4 when row c1 c2 c3 c4
c3
┌───┐┌───┐ ┌───┐┌───┬───┬───┬───┐ ┌───┐ ┌───┐┌───┬───┬───┬───┐
┌───┐
│ 0 ││ a │ │ 1 ││ 3 │ b │ v │ 8 │ │ x │ │ 1 ││ 3 │ b │ v │ 8 │
│ 8 │
├───┤├───┤ ├───┤├───┼───┼───┼───┤ ├───┤ ├───┤├───┼───┼───┼───┤
─► ├───┤
│ / ││ d │ │ 5 ││ 3 │ f │ z │ 4 │ │ x │ │ 5 ││ 3 │ f │ z │ 4
│eval│ 4 │
├───┤└───┘ └───┘└───┴───┴───┴───┘ └───┘ └───┘└───┴───┴───┴───┘
└───┘
│ 1 │┌───┐ │ │ eval ▲ │ │ │ ▲filter
│
├───┤│ w │ └─────┴────────────────────┘ └──────┴─│─────────┘
│
│ 0 │├───┤ │
│
├───┤│ y │ │
│
│ 1 │└───┘ │
│
├───┤ │
│
│ / │ │
│
└─┬─┘ │
│
└──┬───────────────────────────────────────────────┴────────────────────────┘
│
│
add_batch│
│
▼
merge
ind arr
┌───┐┌───┐ ┌───┐
│ 0 ││ a │ ┌─────►│ a ├─────┐
├───┤├───┤───┐ ┌───┐│ ├───┤ │ ┌───┐
│ 2 ││ d │ │ │ 0 ├┘┌────►│ d ├──┐ └─►│ a │
├───┤└───┘ │ ├───┤ │ └───┘ │ ├───┤
│ 1 │┌───┐ │ │ 2 ├─│──┐ │ ┌──►│ 8 │
├───┤│ w │ │ ├───┤ │ │ ┌───┐ │ │ ├───┤
│ 0 │├───┤───┤ finish │ 1 ├─│────►│ w │────│──►│ w │
├───┤│ y │ ├────────► ├───┤ │ │ ├───┤ │ │ ├───┤
│ 1 │└───┘ │ │ 0 ├─┘ ┌──►│ y ├─┐└─│──►│ d │
├───┤┌───┐ │ ├───┤ ││ └───┘ │ │ ├───┤
│ 2 ││ 8 │ │ │ 1 ├───┘│ └──│──►│ y │
└───┘├───┤───┤ ├───┤ │ ┌───┐ │ ├───┤
│ │ 4 │ │ │ 2 ├──┐ └─►│ 8 ├────┘┌─►│ 4 │
│ └───┘ │ └───┘ │ ├───┤ │ └───┘
└──────────┘ └───►│ 4 ├─────┘
└───┘
```
</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: [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]
