Skip to content

planner: use BatchPointGet to improve the SELECT ...WHERE IN performance#11750

Merged
eurekaka merged 12 commits intopingcap:masterfrom
lonng:convert-to-union
Aug 20, 2019
Merged

planner: use BatchPointGet to improve the SELECT ...WHERE IN performance#11750
eurekaka merged 12 commits intopingcap:masterfrom
lonng:convert-to-union

Conversation

@lonng
Copy link
Contributor

@lonng lonng commented Aug 15, 2019 •
edited
Loading

What problem does this PR solve?

This PR adds a BatchPointGet executor to improve the SELECT ...WHERE IN performance if the WHERE clause is applied to a unique key.

mysql root@127.0.0.1:test> show create table tbl;
+-------+-------------------------------------------------------------+
| Table | Create Table                                                |
+-------+-------------------------------------------------------------+
| tbl   | CREATE TABLE `tbl` (                                        |
|       |   `a` int(11) DEFAULT NULL,                                 |
|       |   `b` int(11) DEFAULT NULL,                                 |
|       |   `c` int(11) DEFAULT NULL,                                 |
|       |   UNIQUE KEY `idx` (`a`,`b`,`c`)                            |
|       | ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin |
+-------+-------------------------------------------------------------+

Before this PR

mysql root@127.0.0.1:test> desc select * from tbl where (a, b, c) in ((1,2,3),(2,4,5));
+---------------+-------+------+----------------------------------------------------------------------------------------------+
| id            | count | task | operator info                                                                                |
+---------------+-------+------+----------------------------------------------------------------------------------------------+
| IndexReader_6 | 2.00  | root | index:IndexScan_5                                                                            |
| └─IndexScan_5 | 2.00  | cop  | table:tbl, index:a, b, c, range:[1 2 3,1 2 3], [2 4 5,2 4 5], keep order:false, stats:pseudo |
+---------------+-------+------+----------------------------------------------------------------------------------------------+
2 rows in set

After this PR

mysql root@127.0.0.1:test> desc select * from tbl where (a, b, c) in ((1,2,3),(2,4,5));
+---------------+-------+------+------------------------+
| id            | count | task | operator info          |
+---------------+-------+------+------------------------+
| Union_3       | 2.00  | root |                        |
| ├─Point_Get_1 | 1.00  | root | table:tbl, index:a b c |
| └─Point_Get_2 | 1.00  | root | table:tbl, index:a b c |
+---------------+-------+------+------------------------+
3 rows in set

What is changed and how it works?

  1. Try to convert the select * from tbl where (a, b, c) in ((1,2,3),(2,4,5)); to a union statement.
  2. Try to use PointGet for all select statement in the union statement.
  3. Back to the original logic if any select statement cannot use PointGet.

Check List

Tests

  • Unit test
  • Integration test
  • Manual test (add detailed scripts or steps below)

Benchmark (gist)

Tests a various combination of index column count and expressions count in the IN clause.

----- batch point get -----
colCount 1 inCount 100 min 3.264995ms max 13.700072ms avg 3.953088ms
colCount 1 inCount 200 min 5.889228ms max 6.767658ms avg 6.231987ms
colCount 1 inCount 300 min 8.361536ms max 9.258089ms avg 8.79512ms
colCount 1 inCount 400 min 11.114085ms max 12.818915ms avg 11.605334ms
colCount 1 inCount 500 min 13.018075ms max 31.493361ms avg 14.423509ms
colCount 1 inCount 600 min 15.367862ms max 123.129487ms avg 18.652704ms
colCount 1 inCount 700 min 18.930547ms max 21.866355ms avg 19.876498ms
colCount 1 inCount 800 min 20.801272ms max 43.103556ms avg 23.01241ms
colCount 1 inCount 900 min 21.105466ms max 25.033213ms avg 22.936394ms
colCount 1 inCount 1000 min 22.429819ms max 49.011357ms avg 24.696616ms
colCount 3 inCount 100 min 3.276467ms max 3.82595ms avg 3.453249ms
colCount 3 inCount 200 min 6.422832ms max 120.16667ms avg 11.058662ms
colCount 3 inCount 300 min 11.733525ms max 15.649921ms avg 12.443075ms
colCount 3 inCount 400 min 15.484122ms max 39.141485ms avg 16.883035ms
colCount 3 inCount 500 min 15.76651ms max 22.355391ms avg 17.878194ms
colCount 3 inCount 600 min 18.674431ms max 29.305322ms avg 19.697981ms
colCount 3 inCount 700 min 21.086659ms max 129.639697ms avg 26.409742ms
colCount 3 inCount 800 min 29.463324ms max 50.613424ms avg 31.894119ms
colCount 3 inCount 900 min 27.983334ms max 39.558304ms avg 31.274798ms
colCount 3 inCount 1000 min 29.84892ms max 156.806251ms avg 35.283408ms
colCount 5 inCount 100 min 5.781827ms max 14.239799ms avg 6.42316ms
colCount 5 inCount 200 min 10.064872ms max 26.192189ms avg 11.628128ms
colCount 5 inCount 300 min 14.130938ms max 16.619077ms avg 14.874737ms
colCount 5 inCount 400 min 14.582665ms max 19.104273ms avg 16.708192ms
colCount 5 inCount 500 min 17.212758ms max 45.181506ms avg 18.895603ms
colCount 5 inCount 600 min 20.205794ms max 135.99379ms avg 24.582391ms
colCount 5 inCount 700 min 29.469003ms max 35.432632ms avg 31.056447ms
colCount 5 inCount 800 min 26.499308ms max 74.434644ms avg 30.067951ms
colCount 5 inCount 900 min 29.788011ms max 152.482239ms avg 34.818933ms
colCount 5 inCount 1000 min 34.113848ms max 58.588995ms avg 43.286854ms
colCount 7 inCount 100 min 5.475554ms max 14.652263ms avg 5.975428ms
colCount 7 inCount 200 min 8.965315ms max 33.637819ms avg 10.74342ms
colCount 7 inCount 300 min 12.678774ms max 14.972786ms avg 13.706757ms
colCount 7 inCount 400 min 16.317382ms max 59.781672ms avg 18.006163ms
colCount 7 inCount 500 min 20.449888ms max 125.474865ms avg 28.627678ms
colCount 7 inCount 600 min 23.307631ms max 72.127425ms avg 27.69563ms
colCount 7 inCount 700 min 26.159246ms max 69.017394ms avg 28.955916ms
colCount 7 inCount 800 min 30.201012ms max 151.751213ms avg 40.633701ms
colCount 7 inCount 900 min 34.149236ms max 74.898693ms avg 39.543643ms
colCount 7 inCount 1000 min 38.717039ms max 126.761521ms avg 49.331584ms
colCount 9 inCount 100 min 7.140837ms max 24.59458ms avg 7.927618ms
colCount 9 inCount 200 min 10.778898ms max 16.842728ms avg 14.147246ms
colCount 9 inCount 300 min 15.394714ms max 38.114064ms avg 17.002018ms
colCount 9 inCount 400 min 19.431243ms max 24.63663ms avg 21.078946ms
colCount 9 inCount 500 min 22.986795ms max 133.072754ms avg 32.170664ms
colCount 9 inCount 600 min 26.535539ms max 75.660702ms avg 32.986824ms
colCount 9 inCount 700 min 30.380575ms max 81.730979ms avg 33.822502ms
colCount 9 inCount 800 min 34.274958ms max 155.424611ms avg 48.593365ms
colCount 9 inCount 900 min 37.822488ms max 78.438832ms avg 40.604347ms
colCount 9 inCount 1000 min 42.075029ms max 164.764913ms avg 56.321728ms


----- master -------
colCount 1 inCount 100 min 3.858481ms max 18.571063ms avg 4.725589ms
colCount 1 inCount 200 min 5.998274ms max 17.332842ms avg 7.392626ms
colCount 1 inCount 300 min 8.087811ms max 19.322017ms avg 9.481114ms
colCount 1 inCount 400 min 9.82614ms max 21.59106ms avg 11.175945ms
colCount 1 inCount 500 min 11.556513ms max 25.434264ms avg 13.193988ms
colCount 1 inCount 600 min 13.612825ms max 27.451418ms avg 15.060893ms
colCount 1 inCount 700 min 15.292728ms max 30.691836ms avg 16.645156ms
colCount 1 inCount 800 min 17.565637ms max 58.014705ms avg 20.448409ms
colCount 1 inCount 900 min 19.622542ms max 35.107622ms avg 21.94908ms
colCount 1 inCount 1000 min 21.69654ms max 36.870357ms avg 22.863111ms
colCount 3 inCount 100 min 11.926035ms max 22.005147ms avg 12.765221ms
colCount 3 inCount 200 min 25.776479ms max 39.09139ms avg 26.862659ms
colCount 3 inCount 300 min 41.111752ms max 78.655366ms avg 46.416194ms
colCount 3 inCount 400 min 57.79165ms max 99.474778ms avg 61.107977ms
colCount 3 inCount 500 min 76.471862ms max 102.593897ms avg 84.039436ms
colCount 3 inCount 600 min 97.149113ms max 155.25871ms avg 109.342452ms
colCount 3 inCount 700 min 122.188767ms max 181.756346ms avg 139.323735ms
colCount 3 inCount 800 min 144.288112ms max 205.389505ms avg 165.457704ms
colCount 3 inCount 900 min 166.140399ms max 231.004126ms avg 186.097169ms
colCount 3 inCount 1000 min 193.827458ms max 266.079634ms avg 213.448767ms
colCount 5 inCount 100 min 18.424773ms max 36.226384ms avg 22.248411ms
colCount 5 inCount 200 min 38.932373ms max 56.585808ms avg 41.047612ms
colCount 5 inCount 300 min 62.59931ms max 112.424153ms avg 69.770678ms
colCount 5 inCount 400 min 88.909579ms max 145.728884ms avg 96.560175ms
colCount 5 inCount 500 min 116.7584ms max 193.780115ms avg 125.756352ms
colCount 5 inCount 600 min 148.62623ms max 212.186836ms avg 163.38593ms
colCount 5 inCount 700 min 181.44945ms max 249.177493ms avg 199.005251ms
colCount 5 inCount 800 min 216.918386ms max 285.337437ms avg 237.861529ms
colCount 5 inCount 900 min 252.710609ms max 352.019569ms avg 282.054356ms
colCount 5 inCount 1000 min 293.557836ms max 413.722714ms avg 324.297456ms
colCount 7 inCount 100 min 23.647769ms max 55.354012ms avg 27.626315ms
colCount 7 inCount 200 min 50.509131ms max 83.417903ms avg 58.554042ms
colCount 7 inCount 300 min 81.95352ms max 144.598677ms avg 95.218438ms
colCount 7 inCount 400 min 115.263755ms max 181.237605ms avg 131.069767ms
colCount 7 inCount 500 min 153.40786ms max 247.006143ms avg 177.752246ms
colCount 7 inCount 600 min 200.314736ms max 297.26203ms avg 222.245746ms
colCount 7 inCount 700 min 240.578144ms max 338.784116ms avg 267.360644ms
colCount 7 inCount 800 min 285.398121ms max 410.879854ms avg 314.051483ms
colCount 7 inCount 900 min 333.215498ms max 476.919536ms avg 366.305367ms
colCount 7 inCount 1000 min 385.097776ms max 567.671639ms avg 435.75487ms
colCount 9 inCount 100 min 30.13948ms max 73.599053ms avg 37.101386ms
colCount 9 inCount 200 min 64.827048ms max 97.168455ms avg 70.863003ms
colCount 9 inCount 300 min 105.510085ms max 172.078313ms avg 120.172979ms
colCount 9 inCount 400 min 144.737308ms max 208.167352ms avg 162.529387ms
colCount 9 inCount 500 min 192.464723ms max 281.529332ms avg 219.015489ms
colCount 9 inCount 600 min 241.626309ms max 374.851232ms avg 280.731974ms
colCount 9 inCount 700 min 291.84274ms max 419.864699ms avg 341.060149ms
colCount 9 inCount 800 min 352.981263ms max 505.991833ms avg 400.787737ms
colCount 9 inCount 900 min 415.319636ms max 555.577764ms avg 462.835561ms
colCount 9 inCount 1000 min 473.933486ms max 647.997466ms avg 539.467756ms

Release note:

- Adds a `BatchPointGet` executor to improve the `SELECT ...WHERE IN` performance if the `WHERE` clause is applied to a unique key.

@codecov
Copy link

codecov bot commented Aug 15, 2019

Codecov Report

Merging #11750 into master will decrease coverage by 0.0313%.
The diff coverage is 42.268%.

@@               Coverage Diff               @@
##             master    #11750        +/-   ##
===============================================
- Coverage   81.4204%   81.389%   -0.0314%     
===============================================
  Files           433       433                
  Lines         93194     93284        +90     
===============================================
+ Hits          75879     75923        +44     
- Misses        11882     11923        +41     
- Partials       5433      5438         +5

@codecov
Copy link

codecov bot commented Aug 15, 2019 •
edited
Loading

Codecov Report

Merging #11750 into master will decrease coverage by 0.2061%.
The diff coverage is 81.7204%.

@@              Coverage Diff               @@
##             master   #11750        +/-   ##
==============================================
- Coverage   81.6561%   81.45%   -0.2062%     
==============================================
  Files           435      435                
  Lines         94206    93709       -497     
==============================================
- Hits          76925    76326       -599     
- Misses        11820    11906        +86     
- Partials       5461     5477        +16

eurekaka
eurekaka reviewed Aug 16, 2019
View reviewed changes
@lonng lonng added the sig/planner SIG: Planner label Aug 16, 2019
@lonng lonng marked this pull request as ready for review August 16, 2019 14:47
@lonng lonng changed the title [DNM] try to convert SELECT ... IN to UNION statement try to convert SELECT ... IN to UNION statement Aug 19, 2019
lonng added 3 commits August 19, 2019 13:55
@lonng
planner: try to convert SELECT ... IN to UNION statement
d05df0a 
Signed-off-by: Lonng <heng@lonng.org>
@lonng
planner: fix SELECT ... WHERE NOT IN
0cf83c5 
Signed-off-by: Lonng <heng@lonng.org>
@lonng
planner,executor: add more unit tests
867151b 
Signed-off-by: Lonng <heng@lonng.org>
@lonng
Copy link
Contributor Author

lonng commented Aug 19, 2019

@zz-jason @winoros PTAL

@lonng lonng requested review from winoros and zz-jason August 19, 2019 05:59
@lonng lonng changed the title try to convert SELECT ... IN to UNION statement planner: use BatchPointGet to improve the SELECT ...WHERE IN performance Aug 19, 2019
winoros
winoros reviewed Aug 19, 2019
View reviewed changes
jackysp
jackysp reviewed Aug 19, 2019
View reviewed changes
eurekaka
eurekaka reviewed Aug 20, 2019
View reviewed changes
Copy link
Contributor

@eurekaka eurekaka left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

@eurekaka eurekaka added status/LGT1 Indicates that a PR has LGTM 1. type/enhancement The issue or PR belongs to an enhancement. labels Aug 20, 2019
winoros
winoros previously approved these changes Aug 20, 2019
View reviewed changes
Copy link
Member

@winoros winoros left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

lgtm

@winoros winoros added status/can-merge Indicates a PR has been approved by a committer. and removed status/LGT1 Indicates that a PR has LGTM 1. labels Aug 20, 2019
@winoros winoros added the status/LGT2 Indicates that a PR has LGTM 2. label Aug 20, 2019
@sre-bot
Copy link
Contributor

sre-bot commented Aug 20, 2019

/run-all-tests

@sre-bot
Copy link
Contributor

sre-bot commented Aug 20, 2019

@lonng merge failed.

@lonng
fix duplicated check leak
ef40d55 
Signed-off-by: Lonng <heng@lonng.org>
@lonng
Copy link
Contributor Author

lonng commented Aug 20, 2019

/run-all-tests

@eurekaka eurekaka merged commit 2addc25 into pingcap:master Aug 20, 2019
@lonng lonng deleted the convert-to-union branch August 20, 2019 11:11
@sre-bot
Copy link
Contributor

sre-bot commented Aug 20, 2019

cherry pick to release-3.0 failed

@lonng lonng mentioned this pull request Sep 23, 2019
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@jackysp jackysp jackysp left review comments

@eurekaka eurekaka eurekaka approved these changes

@winoros winoros winoros left review comments

@zz-jason zz-jason Awaiting requested review from zz-jason

Assignees

No one assigned

Labels

sig/planner SIG: Planner status/can-merge Indicates a PR has been approved by a committer. status/LGT2 Indicates that a PR has LGTM 2. type/enhancement The issue or PR belongs to an enhancement.

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

5 participants

@lonng @sre-bot @jackysp @eurekaka @winoros