Tidb: Improve the performance of `WindowExec` by using sliding window or segment tree

[SunRunAway]

Description

TiDB implements window function feature compatible with MySQL (https://dev.mysql.com/doc/refman/8.0/en/window-functions.html). The performance has much space to improve.

Considering implementing an algorithm of sliding window or segment tree within the different frames of the same window partition, when doing the aggregate calculation step.

And here’s a paper to read http://www.vldb.org/pvldb/vol8/p1058-leis.pdf for reference, describing and comparing some effective implementations. A paper reading video (in Chinese) is here(https://www.bilibili.com/video/av70860233). Due to this paper, we have a chance to make a SQL like select sum(a) over (order by b rows between ? preceding and current row) from r; 600% faster.

Goals:

• Implement an algorithm of sliding window or segment tree within the different frames of the same window partition

Score

• 3000

Mentor(s)

• @SunRunAway

Recommended Skills

• SQL Optimization
• Golang Profiling
• Code Refactoring

PRs

Framework: https://github.com/pingcap/tidb/pull/14294

• [x] count https://github.com/pingcap/tidb/pull/14294 along with the framwork
• [x] sum https://github.com/pingcap/tidb/pull/14887
• [x] avg https://github.com/pingcap/tidb/pull/15606
• [x] min/max https://github.com/pingcap/tidb/pull/16819
• [x] bitXor: implement https://github.com/pingcap/tidb/pull/16091
• [x] bitOr, bitAnd: no inverse operation, cannot
• [x] group_concat: it's not window func, won't implement

[mmyj]

/pick-up-challenge

[sre-bot]

@mmyj don't have enough score, pick up failed
Progress 0/400
You may pick up some easy issues first.

[mmyj]

/pick-up-challenge

[sre-bot]

@mmyj pick up issue success

[vagetablechicken]

/pick-up

avg

[ti-challenge-bot[bot]]

Pick up success.

[mmyj]

/pick-up

avg

hi, the slide window interface of the avg aggFunc had been implemented.@vagetablechicken

[mmyj]

@SunRunAway please update the todo list, I had been compelated the avg and the xor.

[TszKitLo40]

/pick-up
group_concat

[ti-challenge-bot[bot]]

This issue already picked by vagetablechicken.

[TszKitLo40]

/pick-up
bitxor

[ti-challenge-bot[bot]]

This issue already picked by vagetablechicken.

[vagetablechicken]

/give-up

ok, give up this issue

[ti-challenge-bot[bot]]

Give up success.

[TszKitLo40]

Maybe individual issue should be created for each item. Otherwise the issues could not be picked up.

[mmyj]

/pick-up

[ti-challenge-bot[bot]]

Pick up success.

[XuHuaiyu]

@TszKitLo40
Thanks for the reminder.
I've updated the progress in the description, this is only one subtask remained which is working in progress. Thus we'll not create new issues for the sub-tasks.

[qw4990]

It seems all issues of this sliding window optimization have been completed 🎊 !
Can we close this issue now? @SunRunAway @mmyj

[ti-challenge-bot[bot]]

@mmyj You did not submit PR within 7 days, so give up automatically.