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: #14294

• count executor: Improve the performance of WindowExec by using sliding window #14294 along with the framwork
• sum executor: Improve the performance of aggFuncSum by using sliding window #14887
• avg executor: Improve the performance of aggFuncAvg by using sliding window #15606
• min/max exector, planner: Improve the performance of the aggFuncMaxMin by using sliding window #16819
• bitXor: implement executor: Improve the performance of aggFuncBitXor by using sliding window #16091
• bitOr, bitAnd: no inverse operation, cannot
• 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]

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]

This issue already picked by vagetablechicken.

[TszKitLo40]

/pick-up
bitxor

[ti-challenge-bot]

This issue already picked by vagetablechicken.

[vagetablechicken]

/give-up

ok, give up this issue

[ti-challenge-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]

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

[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.