search

pingcap / tidb

TiDB - the open-source, cloud-native, distributed SQL database designed for modern applications.
https://pingcap.com
Apache License 2.0
37.41k stars 5.85k forks source link

IndexJoin is 2 times faster than IndexHashJoin for TPC-H Q3 #18430

Open eurekaka opened 4 years ago

eurekaka commented 4 years ago

Development Task

For TPC-H Q3 with sf=10, the chosen plan and its execution statistics are:

+------------------------------------------+-------------+----------+-----------+---------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------+---------+
| id                                       | estRows     | actRows  | task      | access object                                           | execution info                                                                                                                                                            | operator info                                                                                                                                                                                                                                                           | memory                | disk    |
+------------------------------------------+-------------+----------+-----------+---------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------+---------+
| Projection_14                            | 10.00       | 10       | root      |                                                         | time:11.54104994s, loops:2, Concurrency:OFF                                                                                                                               | tpch10g.lineitem.l_orderkey, Column#35, tpch10g.orders.o_orderdate, tpch10g.orders.o_shippriority                                                                                                                                                                       | 2.484375 KB           | N/A     |
| └─TopN_17                                | 10.00       | 10       | root      |                                                         | time:11.541040338s, loops:2                                                                                                                                               | Column#35:desc, tpch10g.orders.o_orderdate, offset:0, count:10                                                                                                                                                                                                          | 76.71875 KB           | N/A     |
|   └─HashAgg_23                           | 8155051.08  | 113719   | root      |                                                         | time:11.527524469s, loops:113, PartialConcurrency:4, FinalConcurrency:4                                                                                                   | group by:Column#48, Column#49, Column#50, funcs:sum(Column#44)->Column#35, funcs:firstrow(Column#45)->tpch10g.orders.o_orderdate, funcs:firstrow(Column#46)->tpch10g.orders.o_shippriority, funcs:firstrow(Column#47)->tpch10g.lineitem.l_orderkey                      | 777.375 KB            | N/A     |
|     └─Projection_81                      | 17699590.52 | 300219   | root      |                                                         | time:11.412639355s, loops:295, Concurrency:4                                                                                                                              | mul(tpch10g.lineitem.l_extendedprice, minus(1, tpch10g.lineitem.l_discount))->Column#44, tpch10g.orders.o_orderdate, tpch10g.orders.o_shippriority, tpch10g.lineitem.l_orderkey, tpch10g.lineitem.l_orderkey, tpch10g.orders.o_orderdate, tpch10g.orders.o_shippriority | 824.625 KB            | N/A     |
|       └─IndexHashJoin_31                 | 17699590.52 | 300219   | root      |                                                         | time:11.411761146s, loops:295, Concurrency:4                                                                                                                              | inner join, inner:IndexLookUp_28, outer key:tpch10g.orders.o_orderkey, inner key:tpch10g.lineitem.l_orderkey                                                                                                                                                            | 83.15203380584717 MB  | N/A     |
|         ├─HashJoin_71(Build)             | 4448757.21  | 1455173  | root      |                                                         | time:1.334031473s, loops:1427, Concurrency:5, probe collision:0, build:100.953144ms                                                                                       | inner join, equal:[eq(tpch10g.customer.c_custkey, tpch10g.orders.o_custkey)]                                                                                                                                                                                            | 9.06076431274414 MB   | 0 Bytes |
|         │ ├─TableReader_77(Build)        | 299450.00   | 300036   | root      |                                                         | time:587.534025ms, loops:293, rpc num: 3, rpc max:623.853713ms, min:375.737184ms, avg:468.932367ms, p80:623.853713ms, p95:623.853713ms, proc keys max:603265, p95:603265  | data:Selection_76                                                                                                                                                                                                                                                       | 5.2422637939453125 MB | N/A     |
|         │ │ └─Selection_76               | 299450.00   | 300036   | cop[tikv] |                                                         | proc max:602ms, min:352ms, p80:602ms, p95:602ms, iters:1478, tasks:3                                                                                                      | eq(tpch10g.customer.c_mktsegment, "AUTOMOBILE")                                                                                                                                                                                                                         | N/A                   | N/A     |
|         │ │   └─TableFullScan_75         | 1500000.00  | 1500000  | cop[tikv] | table:customer                                          | proc max:551ms, min:305ms, p80:551ms, p95:551ms, iters:1478, tasks:3                                                                                                      | keep order:false                                                                                                                                                                                                                                                        | N/A                   | N/A     |
|         │ └─TableReader_74(Probe)        | 7402500.00  | 7276947  | root      |                                                         | time:662.922968ms, loops:7084, rpc num: 26, rpc max:682.251773ms, min:397.65573ms, avg:559.458973ms, p80:598.100655ms, p95:672.024702ms, proc keys max:582548, p95:582493 | data:Selection_73                                                                                                                                                                                                                                                       | 188.066725730896 MB   | N/A     |
|         │   └─Selection_73               | 7402500.00  | 7276947  | cop[tikv] |                                                         | proc max:620ms, min:353ms, p80:551ms, p95:617ms, iters:14760, tasks:26                                                                                                    | lt(tpch10g.orders.o_orderdate, 1995-03-13 00:00:00.000000)                                                                                                                                                                                                              | N/A                   | N/A     |
|         │     └─TableFullScan_72         | 15000000.00 | 15000000 | cop[tikv] | table:orders                                            | proc max:591ms, min:336ms, p80:525ms, p95:585ms, iters:14760, tasks:26                                                                                                    | keep order:false                                                                                                                                                                                                                                                        | N/A                   | N/A     |
|         └─IndexLookUp_28(Probe)          | 3.98        | 300219   | root      |                                                         | time:38.690824625s, loops:403, rpc num: 160, rpc max:682.653587ms, min:845.103µs, avg:249.236106ms, p80:439.455448ms, p95:588.220147ms, proc keys max:91417, p95:89586    |                                                                                                                                                                                                                                                                         | 164.0625 KB           | N/A     |
|           ├─IndexRangeScan_25(Build)     | 7.36        | 5820007  | cop[tikv] | table:lineitem, index:PRIMARY(L_ORDERKEY, L_LINENUMBER) | proc max:655ms, min:0s, p80:415ms, p95:560ms, iters:6403, tasks:160                                                                                                       | range: decided by [eq(tpch10g.lineitem.l_orderkey, tpch10g.orders.o_orderkey)], keep order:false                                                                                                                                                                        | N/A                   | N/A     |
|           └─Selection_27(Probe)          | 3.98        | 300219   | cop[tikv] |                                                         | proc max:223ms, min:0s, p80:116ms, p95:151ms, iters:9157, tasks:751                                                                                                       | gt(tpch10g.lineitem.l_shipdate, 1995-03-13 00:00:00.000000)                                                                                                                                                                                                             | N/A                   | N/A     |
|             └─TableRowIDScan_26          | 7.36        | 5820007  | cop[tikv] | table:lineitem                                          | proc max:222ms, min:0s, p80:115ms, p95:150ms, iters:9157, tasks:751                                                                                                       | keep order:false                                                                                                                                                                                                                                                        | N/A                   | N/A     |
+------------------------------------------+-------------+----------+-----------+---------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------+---------+
16 rows in set (11.54 sec)

with nth_plan(6) hint, the plan and execution statistics are:

+-------------------------------------------+-------------+----------+-----------+---------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------+---------+
| id                                        | estRows     | actRows  | task      | access object                                           | execution info                                                                                                                                                            | operator info                                                                                                                                                                                                                                                           | memory                | disk    |
+-------------------------------------------+-------------+----------+-----------+---------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------+---------+
| Projection_14                             | 10.00       | 10       | root      |                                                         | time:5.364414964s, loops:2, Concurrency:OFF                                                                                                                               | tpch10g.lineitem.l_orderkey, Column#35, tpch10g.orders.o_orderdate, tpch10g.orders.o_shippriority                                                                                                                                                                       | 2.484375 KB           | N/A     |
| └─TopN_83                                 | 10.00       | 10       | root      |                                                         | time:5.36440852s, loops:2                                                                                                                                                 | Column#35:desc, tpch10g.orders.o_orderdate, offset:0, count:10                                                                                                                                                                                                          | 76.71875 KB           | N/A     |
|   └─HashAgg_149                           | 8155051.08  | 113719   | root      |                                                         | time:5.358248342s, loops:113, PartialConcurrency:4, FinalConcurrency:4                                                                                                    | group by:Column#72, Column#73, Column#74, funcs:sum(Column#68)->Column#35, funcs:firstrow(Column#69)->tpch10g.orders.o_orderdate, funcs:firstrow(Column#70)->tpch10g.orders.o_shippriority, funcs:firstrow(Column#71)->tpch10g.lineitem.l_orderkey                      | 777.375 KB            | N/A     |
|     └─Projection_283                      | 17699590.52 | 300219   | root      |                                                         | time:5.279948747s, loops:295, Concurrency:4                                                                                                                               | mul(tpch10g.lineitem.l_extendedprice, minus(1, tpch10g.lineitem.l_discount))->Column#68, tpch10g.orders.o_orderdate, tpch10g.orders.o_shippriority, tpch10g.lineitem.l_orderkey, tpch10g.lineitem.l_orderkey, tpch10g.orders.o_orderdate, tpch10g.orders.o_shippriority | 809.625 KB            | N/A     |
|       └─IndexJoin_212                     | 17699590.52 | 300219   | root      |                                                         | time:5.279120233s, loops:295, Concurrency:4                                                                                                                               | inner join, inner:IndexLookUp_211, outer key:tpch10g.orders.o_orderkey, inner key:tpch10g.lineitem.l_orderkey                                                                                                                                                           | 83.10132122039795 MB  | N/A     |
|         ├─HashJoin_272(Build)             | 4448757.21  | 1455173  | root      |                                                         | time:2.325616659s, loops:1425, Concurrency:5, probe collision:0, build:1.534917296s                                                                                       | inner join, equal:[eq(tpch10g.customer.c_custkey, tpch10g.orders.o_custkey)]                                                                                                                                                                                            | 279.01934814453125 MB | 0 Bytes |
|         │ ├─TableReader_276(Build)        | 7402500.00  | 7276947  | root      |                                                         | time:673.228103ms, loops:7084, rpc num: 26, rpc max:714.125602ms, min:424.95643ms, avg:550.508356ms, p80:634.788289ms, p95:675.938846ms, proc keys max:582548, p95:582493 | data:Selection_275                                                                                                                                                                                                                                                      | 127.59269714355469 MB | N/A     |
|         │ │ └─Selection_275               | 7402500.00  | 7276947  | cop[tikv] |                                                         | proc max:661ms, min:383ms, p80:580ms, p95:617ms, iters:14760, tasks:26                                                                                                    | lt(tpch10g.orders.o_orderdate, 1995-03-13 00:00:00.000000)                                                                                                                                                                                                              | N/A                   | N/A     |
|         │ │   └─TableFullScan_274         | 15000000.00 | 15000000 | cop[tikv] | table:orders                                            | proc max:634ms, min:363ms, p80:552ms, p95:591ms, iters:14760, tasks:26                                                                                                    | keep order:false                                                                                                                                                                                                                                                        | N/A                   | N/A     |
|         │ └─TableReader_282(Probe)        | 299450.00   | 300036   | root      |                                                         | time:345.308971ms, loops:294, rpc num: 3, rpc max:676.367673ms, min:336.921862ms, avg:457.467896ms, p80:676.367673ms, p95:676.367673ms, proc keys max:603265, p95:603265  | data:Selection_281                                                                                                                                                                                                                                                      | 7.482260704040527 MB  | N/A     |
|         │   └─Selection_281               | 299450.00   | 300036   | cop[tikv] |                                                         | proc max:640ms, min:310ms, p80:640ms, p95:640ms, iters:1478, tasks:3                                                                                                      | eq(tpch10g.customer.c_mktsegment, "AUTOMOBILE")                                                                                                                                                                                                                         | N/A                   | N/A     |
|         │     └─TableFullScan_280         | 1500000.00  | 1500000  | cop[tikv] | table:customer                                          | proc max:590ms, min:279ms, p80:590ms, p95:590ms, iters:1478, tasks:3                                                                                                      | keep order:false                                                                                                                                                                                                                                                        | N/A                   | N/A     |
|         └─IndexLookUp_211(Probe)          | 3.98        | 300219   | root      |                                                         | time:9.451050827s, loops:404, rpc num: 4095, rpc max:96.705832ms, min:847.74µs, avg:21.804577ms, p80:30.179852ms, p95:45.238809ms, proc keys max:1988, p95:1778           |                                                                                                                                                                                                                                                                         | 153.53125 KB          | N/A     |
|           ├─IndexRangeScan_208(Build)     | 7.36        | 5820007  | cop[tikv] | table:lineitem, index:PRIMARY(L_ORDERKEY, L_LINENUMBER) | proc max:39ms, min:0s, p80:24ms, p95:29ms, iters:22775, tasks:4095                                                                                                        | range: decided by [eq(tpch10g.lineitem.l_orderkey, tpch10g.orders.o_orderkey)], keep order:false                                                                                                                                                                        | N/A                   | N/A     |
|           └─Selection_210(Probe)          | 3.98        | 300219   | cop[tikv] |                                                         | proc max:20ms, min:0s, p80:10ms, p95:12ms, iters:45635, tasks:10826                                                                                                       | gt(tpch10g.lineitem.l_shipdate, 1995-03-13 00:00:00.000000)                                                                                                                                                                                                             | N/A                   | N/A     |
|             └─TableRowIDScan_209          | 7.36        | 5820007  | cop[tikv] | table:lineitem                                          | proc max:20ms, min:0s, p80:10ms, p95:12ms, iters:45635, tasks:10826                                                                                                       | keep order:false                                                                                                                                                                                                                                                        | N/A                   | N/A     |
+-------------------------------------------+-------------+----------+-----------+---------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------+---------+
16 rows in set (5.37 sec)

The significant difference of these 2 plans is IndexHashJoin vs IndexJoin. The root cause should be the row count estimation error of the IndexJoin / IndexHashJoin and their child HashJoin, specifically, NDV for one of the join children nodes is not fully contained by the other one.

The stats of the tables are stats.zip

zz-jason commented 4 years ago

related to https://github.com/pingcap/tidb/issues/18431