optimize the long nested recursive expression performance
- 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:

Contributor 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