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.

[ichn-hu]

for bitOr, bitAnd: no inverse operation, cannot I think you can use segment tree to calculate (as long as the operator is addictive, segment tree can always help), so it is not can not, but let's see if there is any volunteer who want to help implement this.

[TszKitLo40]

for bitOr, bitAnd: no inverse operation, cannot I think you can use segment tree to calculate (as long as the operator is addictive, segment tree can always help), so it is not can not, but let's see if there is any volunteer who want to help implement this.

I want to implement this. But it seems that I need more background knowledge of this issue.

[ichn-hu]

for bitOr, bitAnd: no inverse operation, cannot I think you can use segment tree to calculate (as long as the operator is addictive, segment tree can always help), so it is not can not, but let's see if there is any volunteer who want to help implement this.

I want to implement this. But it seems that I need more background knowledge of this issue.

Thanks for the quick reply, but I am currently refactoring the window funcion framework, which is about to be changed fundamentally, so I would suggest you to implement this later (after my refactorization).

I'll keep you informed for the process of the refactoring, and I'll let you know about the new design doc once it is ready to release.

Please expect to work on this after 3.12, which is the deadline the refactoring should be done.

Does this sounds good to you?

[TszKitLo40]

for bitOr, bitAnd: no inverse operation, cannot I think you can use segment tree to calculate (as long as the operator is addictive, segment tree can always help), so it is not can not, but let's see if there is any volunteer who want to help implement this.

I want to implement this. But it seems that I need more background knowledge of this issue.

Thanks for the quick reply, but I am currently refactoring the window funcion framework, which is about to be changed fundamentally, so I would suggest you to implement this later (after my refactorization).

I'll keep you informed for the process of the refactoring, and I'll let you know about the new design doc once it is ready to release.

Please expect to work on this after 3.12, which is the deadline the refactoring should be done.

Does this sounds good to you?

ok, I will wait for your further response.