pingcap / pingcap/tidb

optimize the long nested recursive expression performance

Open
#43,885 2 comments 0 reactions 0 assignees View on GitHub
type/enhancement
Dominant language
Go
Stars
40.5k
Forks
6.2k
PR merge metrics
PR metrics pending

Description

## Enhancement

There are a lot of recursive function used in our code base. Especially the expression related.
Depending on the user's sql, it may sometimes cause performance issues.

For example, this one https://github.com/pingcap/tidb/issues/42788

Here I upload a flamegraph for this kind of sql:

```
select * from t where 1=0 or (t.a = '0' and t.c = 0) or (t.a = '1' and t.c = 1) or (t.a = '2' and t.c = 2) or (t.a = '3' and t.c = 3)
or (t.a = '4' and t.c = 4) or (t.a = '5' and t.c = 5) or (t.a = '6' and t.c = 6) or (t.a = '7' and t.c = 7) or (t.a = '8' and t.c = 8
) or (t.a = '9' and t.c = 9) or (t.a = '10' and t.c = 10) or (t.a = '11' and t.c = 11) or (t.a = '12' and t.c = 12) or (t.a = '13' and
t.c = 13) or (t.a = '14' and t.c = 14) or (t.a = '15' and t.c = 15) or (t.a = '16' and t.c = 16) or (t.a = '17' and t.c = 17) or (t.a
= '18' and t.c = 18) or (t.a = '19' and t.c = 19) or (t.a = '20' and t.c = 20) or (t.a = '21' and t.c = 21) or (t.a = '22' and t.c =
22) or (t.a = '23' and t.c = 23) or (t.a = '24' and t.c = 24) or (t.a = '25' and t.c = 25) or (t.a = '26' and t.c = 26) or (t.a = '27'
and t.c = 27) or (t.a = '28' and t.c = 28) or (t.a = '29' and t.c = 29) or (t.a = '30' and t.c = 0) or (t.a = '31' and t.c = 1) or (t
.a = '32' and t.c = 2) or (t.a = '33' and t.c = 3) or (t.a = '34' and t.c = 4) or (t.a = '35' and t.c = 5) or (t.a = '36' and t.c = 6)
or (t.a = '37' and t.c = 7) or (t.a = '38' and t.c = 8) or (t.a = '39' and t.c = 9) or (t.a = '40' and t.c = 10) or (t.a = '41' and t
.c = 11) or (t.a = '42' and t.c = 12) or (t.a = '43' and t.c = 13) or (t.a = '44' and t.c = 14) or (t.a = '45' and t.c = 15) or (t.a =
'46' and t.c = 16) or (t.a = '47' and t.c = 17) or (t.a = '48' and t.c = 18) or (t.a = '49' and t.c = 19) or (t.a = '50' and t.c = 20
) or (t.a = '51' and t.c = 21) or (t.a = '52' and t.c = 22) or (t.a = '53' and t.c = 23) or (t.a = '54' and t.c = 24) or (t.a = '55' a
nd t.c = 25) or (t.a = '56' and t.c = 26) or (t.a = '57' and t.c = 27) or (t.a = '58' and t.c = 28) or (t.a = '59' and t.c = 29) or (t
.a = '60' and t.c = 0) or (t.a = '61' and t.c = 1) or (t.a = '62' and t.c = 2) or (t.a = '63' and t.c = 3) or (t.a = '64' and t.c = 4)
or (t.a = '65' and t.c = 5) or (t.a = '66' and t.c = 6) or (t.a = '67' and t.c = 7) or (t.a = '68' and t.c = 8) or (t.a = '69' and t.
c = 9) or (t.a = '70' and t.c = 10) or (t.a = '71' and t.c = 11) or (t.a = '72' and t.c = 12) or (t.a = '73' and t.c = 13) or (t.a = '
74' and t.c = 14) or (t.a = '75' and t.c = 15) or (t.a = '76' and t.c = 16) or (t.a = '77' and t.c = 17) or (t.a = '78' and t.c = 18)
or (t.a = '79' and t.c = 19) or (t.a = '80' and t.c = 20) or (t.a = '81' and t.c = 21) or (t.a = '82' and t.c = 22) or (t.a = '83' and
t.c = 23) or (t.a = '84' and t.c = 24) or (t.a = '85' and t.c = 25) or (t.a = '86' and t.c = 26) or (t.a = '87' and t.c = 27) or (t.a
= '88' and t.c = 28) or (t.a = '89' and t.c = 29) or (t.a = '90' and t.c = 0) or (t.a = '91' and t.c = 1) or (t.a = '92' and t.c = 2)
or (t.a = '93' and t.c = 3) or (t.a = '94' and t.c = 4) or (t.a = '95' and t.c = 5) or (t.a = '96' and t.c = 6) or (t.a = '97' and t.
c = 7) or (t.a = '98' and t.c = 8) or (t.a = '99' and t.c = 9) or (t.a = '100' and t.c = 10) or (t.a = '101' and t.c = 11) or (t.a = '
102' and t.c = 12) or (t.a = '103' and t.c = 13) or (t.a = '104' and t.c = 14) or (t.a = '105' and t.c = 15) or (t.a = '106' and t.c =
16) or (t.a = '107' and t.c = 17) or (t.a = '108' and t.c = 18) or (t.a = '109' and t.c = 19) or (t.a = '110' and t.c = 20) or (t.a =
'111' and t.c = 21) or (t.a = '112' and t.c = 22) or (t.a = '113' and t.c = 23) or (t.a = '114' and t.c = 24) or (t.a = '115' and t.c
= 25) or (t.a = '116' and t.c = 26) or (t.a = '117' and t.c = 27) or (t.a = '118' and t.c = 28) or (t.a = '119' and t.c = 29) or (t.a
= '120' and t.c = 0) or (t.a = '121' and t.c = 1) or (t.a = '122' and t.c = 2) or (t.a = '123' and t.c = 3) or (t.a = '124' and t.c =
4) or (t.a = '125' and t.c = 5) or (t.a = '126' and t.c = 6) or (t.a = '127' and t.c = 7) or (t.a = '128' and t.c = 8) or (t.a = '129
' and t.c = 9) or (t.a = '130' and t.c = 10) or (t.a = '131' and t.c = 11) or (t.a = '132' and t.c = 12) or (t.a = '133' and t.c = 13)
or (t.a = '134' and t.c = 14) or (t.a = '135' and t.c = 15) or (t.a = '136' and t.c = 16) or (t.a = '137' and t.c = 17) or (t.a = '13
8' and t.c = 18) or (t.a = '139' and t.c = 19) or (t.a = '140' and t.c = 20) or (t.a = '141' and t.c = 21) or (t.a = '142' and t.c = 2
2) or (t.a = '143' and t.c = 23) or (t.a = '144' and t.c = 24) or (t.a = '145' and t.c = 25) or (t.a = '146' and t.c = 26) or (t.a = '
....
```

And you can see that the deep call stack are all by the recursive calling:

![image](https://github.com/pingcap/tidb/assets/1420062/4d96fbcd-5eb4-4d9c-b89a-2ca85c9f41cd)

Contributor guide

Open the contributing guide

Research direction

Start by reproducing the long nested SQL expression shown in the issue and reviewing the linked TiDB issue and flamegraph. Trace the recursive expression-related calls responsible for the deep call stack, then define and benchmark a change that improves performance for this workload without changing query results.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases, performance
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.