[MDEV-29907] 10.11-selectivity tree: run Join Order Benchmark Created: 2022-10-28  Updated: 2023-03-24  Resolved: 2023-03-24

Status: Closed
Project: MariaDB Server
Component/s: Optimizer
Fix Version/s: 11.0.1

Type: Task Priority: Major
Reporter: Sergei Petrunia Assignee: Sergei Petrunia
Resolution: Done Votes: 0
Labels: benchmarking, optimizer

Attachments: File 10.11-selectivity.csv     File 10.11-vanilla.csv     Text File 24b.out.fast.txt     Text File 24b.out.slow.txt     File 24b.sql     Text File analyze-10.11-selectivity-force-plan.txt     File run-28nov.csv    

 Description   

Run Join Order Benchmark can compare 10.11 with 10.11-selectivity trees.

 Comments   
Comment by Sergei Petrunia [ 2022-10-28 ]

Results (raw): 10.11-selectivity.csv 10.11-vanilla.csv

Google doc:
https://docs.google.com/spreadsheets/d/1fs15GHFI_Vd9EACG0SbAM1XjkX9e3auFRNAfCYZ3sP4/edit#gid=1728943669

There are some speedups but also slowdowns. Need to investigate..

Comment by Sergei Petrunia [ 2022-11-10 ]

Another run. The results:

query_name 10.11-clean 10.11-selectivity Slowdown
10a 432 439 1.02
10b 146 151 1.03
10c 36475 37093 1.02
11a 92 96 1.04
11b 41 43 1.05
11c 721 592 0.82
11d 197 714 3.62
12a 2389 2407 1.01
12b 360 363 1.01
12c 2895 2924 1.01
13a 17342 17737 1.02
13b 5373 5571 1.04
13c 667 532 0.80
13d 19321 19652 1.02
14a 229 236 1.03
14b 66 69 1.05
14c 710 720 1.01
15a 3710 3778 1.02
15b 41 43 1.05
15c 3717 3783 1.02
15d 3385 3468 1.02
16a 114 118 1.04
16b 14987 15121 1.01
16c 1297 1313 1.01
16d 1022 1037 1.01
17a 7817 7945 1.02
17b 3637 3704 1.02
17c 3509 3572 1.02
17d 19803 20144 1.02
17e 7977 7944 1.00
17f 20000 20173 1.01
18a 4252 4280 1.01
18b 1988 2023 1.02
18c 9140 9236 1.01
19a 8151 14019 1.72
19b 3997 4050 1.01
19c 12017 18813 1.57
19d 19657 90403 4.60
1a 11 11 1.00
1b 0 0 1.00
1c 1 1 1.00
1d 0 0 1.00
20a 1483 1497 1.01
20b 634 647 1.02
20c 536 550 1.03
21a 100 169 1.69
21b 73 131 1.79
21c 127 248 1.95
22a 764 774 1.01
22b 166 171 1.03
22c 5407 5462 1.01
22d 10890 10984 1.01
23a 4102 4145 1.01
23b 125 126 1.01
23c 4086 4150 1.02
24a 1041 1057 1.02
24b 44 134187 3049.70
25a 5106 5134 1.01
25b 176 181 1.03
25c 11735 11832 1.01
26a 237 246 1.04
26b 53 55 1.04
26c 552 552 1.00
27a 71 105 1.48
27b 44 45 1.02
27c 87 172 1.98
28a 1694 1475 0.87
28b 872 698 0.80
28c 2449 2230 0.91
29a 32 17243 538.84
29b 27 2230 82.59
29c 205 211 1.03
2a 438 444 1.01
2b 436 444 1.02
2c 436 443 1.02
2d 445 448 1.01
30a 1072 1091 1.02
30b 229 238 1.04
30c 4376 4411 1.01
31a 2057 2085 1.01
31b 239 245 1.03
31c 2292 2322 1.01
32a 16 17 1.06
32b 150 154 1.03
33a 11 11 1.00
33b 5 16 3.20
33c 176 174 0.99
3a 192 196 1.02
3b 91 94 1.03
3c 437 444 1.02
4a 2312 2379 1.03
4b 503 521 1.04
4c 5015 5148 1.03
5a 1364 858 0.63
5b 1366 820 0.60
5c 1402 969 0.69
6a 20 21 1.05
6b 111 114 1.03
6c 16 17 1.06
6d 2713 2740 1.01
6e 19 21 1.11
6f 2748 2746 1.00
7a 1266 1284 1.01
7b 145 149 1.03
7c 13499 13752 1.02
8a 7406 2781 0.38
8b 204 213 1.04
8c 22924 23158 1.01
8d 2821 2856 1.01
9a 8159 1126 0.14
9b 8018 1057 0.13
9c 8946 4734 0.53
9d 11058 14157 1.28
Comment by Sergei Petrunia [ 2022-11-10 ]

Slowdowns of 2x or more:

query_name 10.11-clean 10.11-selectivity Slowdown
11d 197 714 3.62
19d 19657 90403 4.60
24b 44 134187 3049.70
29a 32 17243 538.84
29b 27 2230 82.59
33b 5 16 3.20

Speedups of 2x or more:

query_name 10.11-clean 10.11-selectivity Slowdown
8a 7406 2781 0.38
9a 8159 1126 0.14
9b 8018 1057 0.13
Comment by Sergei Petrunia [ 2022-11-11 ]

Another re-run, with ANALYZE statements:

query_name 10.11-clean 10.11-selectivity Slowdown
10a 436 434 1.00
10b 151 155 1.03
10c 37125 37093 1.00
11a 95 96 1.01
11b 44 45 1.02
11c 726 589 0.81
11d 204 703 3.45
12a 2403 2411 1.00
12b 361 364 1.01
12c 2929 2928 1.00
13a 17509 17714 1.01
13b 5415 5640 1.04
13c 685 559 0.82
13d 19396 19756 1.02
14a 240 240 1.00
14b 71 74 1.04
14c 724 732 1.01
15a 3733 3792 1.02
15b 43 47 1.09
15c 3720 3821 1.03
15d 3426 3498 1.02
16a 114 120 1.05
16b 15228 14832 0.97
16c 1304 1286 0.99
16d 1039 1016 0.98
17a 7839 7876 1.00
17b 3779 3676 0.97
17c 3521 3567 1.01
17d 20072 19949 0.99
17e 7930 7883 0.99
17f 20166 19967 0.99
18a 4219 4274 1.01
18b 1990 2016 1.01
18c 9120 9233 1.01
19a 8227 14002 1.70
19b 4010 4077 1.02
19c 12107 18748 1.55
19d 19809 89697 4.53
1a 11 11 1.00
1b 0 0 1.00
1c 1 1 1.00
1d 1 0 1.00
20a 1491 1523 1.02
20b 635 661 1.04
20c 545 557 1.02
21a 105 171 1.63
21b 77 134 1.74
21c 131 251 1.92
22a 775 786 1.01
22b 170 175 1.03
22c 5483 5529 1.01
22d 10956 11130 1.02
23a 4112 4185 1.02
23b 129 132 1.02
23c 4115 4178 1.02
24a 1041 1056 1.01
24b 49 135603 2767.41
25a 5106 5183 1.02
25b 188 188 1.00
25c 11747 11890 1.01
26a 249 250 1.00
26b 58 59 1.02
26c 574 565 0.98
27a 75 108 1.44
27b 48 49 1.02
27c 91 175 1.92
28a 1713 1492 0.87
28b 887 705 0.79
28c 2460 2247 0.91
29a 34 17711 520.91
29b 30 2292 76.40
29c 209 216 1.03
2a 451 444 0.98
2b 444 444 1.00
2c 446 450 1.01
2d 450 452 1.00
30a 1096 1118 1.02
30b 240 247 1.03
30c 4417 4459 1.01
31a 2067 2088 1.01
31b 252 255 1.01
31c 2306 2324 1.01
32a 17 18 1.06
32b 156 159 1.02
33a 12 12 1.00
33b 6 17 2.83
33c 177 177 1.00
3a 198 199 1.01
3b 96 96 1.00
3c 449 453 1.01
4a 2350 2384 1.01
4b 521 529 1.02
4c 5100 5140 1.01
5a 1400 889 0.64
5b 1399 847 0.61
5c 1424 993 0.70
6a 21 22 1.05
6b 114 118 1.04
6c 17 36 2.12
6d 2706 2759 1.02
6e 21 22 1.05
6f 2732 2743 1.00
7a 1287 1287 1.00
7b 145 148 1.02
7c 13808 13833 1.00
8a 7477 2784 0.37
8b 211 209 0.99
8c 23017 22979 1.00
8d 2843 2836 1.00
9a 8215 1149 0.14
9b 8079 1077 0.13
9c 9027 4746 0.53
9d 11158 14131 1.27
Comment by Sergei Petrunia [ 2022-11-11 ]

2x and bigger slowdowns in the last re-run:

query_name 10.11-clean 10.11-selectivity Slowdown
11d 204 703 3.45
19d 19809 89697 4.53
24b 49 135603 2767.41
29a 34 17711 520.91
29b 30 2292 76.40
33b 6 17 2.83
6c 17 36 2.12

Same queries as before, except there is one more query: 6c.

Speedups:

query_name 10.11-clean 10.11-selectivity Slowdown
8a 7477 2784 0.37
9a 8215 1149 0.14
9b 8079 1077 0.13

The same as before.

Comment by Sergei Petrunia [ 2022-11-11 ]

The worst slowdown is for query 24b
24b.sql 24b.out.fast.txt 24b.out.slow.txt

(the outputs are from this sequence

set optimizer_trace=1;
 
 ANALYZE FORMAT=JSON ... ; -- traced run
 
select * from optimizer_trace;
 
set optimizer_trace=1;
 
 ANALYZE FORMAT=JSON ... ; -- timed run

)

Comment by Sergei Petrunia [ 2022-11-12 ]

The difference comes from the changed join order:

@@ -1,12 +1,9 @@
 
 ANALYZE
 
 {
 
   "query_block": {
 
     "select_id": 1,
 
     "r_loops": 1,
 
-    "r_total_time_ms": 55.72930131,
 
+    "r_total_time_ms": 136022.1605,
 
     "nested_loop": [
 
       {
 
         "table": {
 
...


@@ -144,25 +143,6 @@
 
       },
 
       {
 
         "table": {
 
-          "table_name": "mi",
 
-          "access_type": "ref",
 
-          "possible_keys": ["info_type_id_movie_info", "movie_id_movie_info"],
 
-          "key": "movie_id_movie_info",
 
-          "key_length": "4",
 
-          "used_key_parts": ["movie_id"],
 
-          "ref": ["imdbload.mk.movie_id"],
 
-          "r_loops": 6,
 
-          "rows": 6,
 
-          "r_rows": 90.66666667,
 
-          "r_table_time_ms": 0.733321607,
 
-          "r_other_time_ms": 0.042313616,
 
-          "filtered": 100,
 
-          "r_filtered": 1.654411765,
 
-          "attached_condition": "mi.info_type_id = it.`id` and mi.info is not null and (mi.info like 'Japan:%201%' or mi.info like 'USA:%201%')"
 
-        }
 
-      },
 
-      {
 
-        "table": {
 
           "table_name": "ci",
 
           "access_type": "ref",
 
           "possible_keys": [
 
...


+      },
 
+      {
 
+        "table": {
 
+          "table_name": "mi",
 
+          "access_type": "ref",
 
+          "possible_keys": ["info_type_id_movie_info", "movie_id_movie_info"],
 
+          "key": "info_type_id_movie_info",
 
+          "key_length": "4",
 
+          "used_key_parts": ["info_type_id"],
 
+          "ref": ["imdbload.it.id"],
 
+          "r_loops": 37,
 
+          "rows": 208953,
 
+          "r_rows": 3036719,
 
+          "r_table_time_ms": 132110.4406,
 
+          "r_other_time_ms": 3861.600525,
 
+          "filtered": 0.002875851,
 
+          "r_filtered": 5.073043e-5,
 
+          "attached_condition": "mi.movie_id = mk.movie_id and mi.info is not null and (mi.info like 'Japan:%201%' or mi.info like 'USA:%201%')"
 
+        }
 
       }
 
     ]
 
   }

Comment by Sergei Petrunia [ 2022-11-12 ]

If I run the query manually, I get the query time of 134 seconds (close to 136 sec. observed in the benchmark), Last_query_cost=22.974574.

If I force the join order as in the fast query, I get:

query_time=21.751 seconds, Last_query_cost=22.974574 (the same).
Q1: why is query cost the same if the query is 6.38x slower?

Note that I still don't get the fast plan. This is because table 'mi' is using the wrong index:

  • fast plan uses movie_id_movie_info, mi.movie_id=imdbload.mk.movie_id (rows=6, r_rows=90)
  • slow plan uses info_type_id_movie_info, mi.info_type_id = imdbload.it.id (rows=208953, r_rows=3036719)
Comment by Sergei Petrunia [ 2022-11-12 ]

If I force the use of fast plan with STRAIGHT_JOIN and use of the right index for table mi, I get:

  • "r_total_time_ms": 52.9485066 (0.05 sec)
  • Last_query_cost=22.974574

Full analyze output: analyze-10.11-selectivity-force-plan.txt

for table mi, we still have:

          "filtered": 100,
 
          "r_filtered": 1.654411765,

It is not clear whether this is THE cause of discrepancy between the expected cost and the observed query time or there's something else at play as well.

Comment by Sergei Petrunia [ 2022-11-14 ]

... Can one change the definition of table movie_info to use VARCHAR(N) instead of text? average length of movie_info.info is 42 characters, but MAX(char_length(info))=19806, there are 43K rows with char_length(info)>1000. It is not trivial.

Would it help if EITS code was able to collect/use histograms on the prefixes of TEXT columns?

Selectivity of the query's condition:

 (mi.info like 'Japan:%201%' or mi.info like 'USA:%201%')

is 2%.
Selectivity of the condition that histogram could handle:

(mi.info like 'Japan:%' or mi.info like 'USA:%')

is 9.6%... It is not clear what choice the optimizer would have made if it was aware of this.

Comment by Sergei Petrunia [ 2022-11-28 ]

A re-run with this fix:

Author: Monty <monty@mariadb.org>
 
Date:   Sat Nov 26 13:06:23 2022 +0200
 
 
 
    Restrict number of estimated rows when joining tables to be >= 1.0

The results: run-28nov.csv .

Generated at Thu Feb 08 10:12:11 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.