doris
doris copied to clipboard
apache
[fix](Nereids): Optimize BFS Memory Usage to Mitigate Exponential Data Growth
Proposed changes
The origin pr is #34948 and the temporary solution is #35408 In our effort to streamline and optimize dependency handling, we implement the following steps:
- Detect Circular Dependencies: Identify any circular references within functional dependencies. If any are found, we remove the specific dependencies responsible for creating these cycles.
- Clean Up Group By Dependencies: Remove all dependencies listed in the 'group by' clauses to simplify and enhance query performance.
Further comments
If this is a relatively large or complex change, kick off the discussion at [email protected] by explaining why you chose the solution you did and what alternatives you considered, etc...
Thank you for your contribution to Apache Doris. Don't know what should be done next? See How to process your PR
Since 2024-03-18, the Document has been moved to doris-website. See Doris Document.
TPC-H: Total hot run time: 40821 ms
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpch-tools
Tpch sf100 test result on commit f506a3e58919a1bf2ed582c53a38175b7ddd12d4, data reload: false
------ Round 1 ----------------------------------
q1 17607 4278 4184 4184
q2 2009 181 204 181
q3 10491 1192 1262 1192
q4 10194 760 720 720
q5 7465 2728 2649 2649
q6 227 132 128 128
q7 988 598 617 598
q8 9216 2105 2092 2092
q9 9044 6704 6675 6675
q10 9759 3878 3875 3875
q11 432 235 233 233
q12 489 235 225 225
q13 18474 3180 3225 3180
q14 248 213 225 213
q15 508 462 470 462
q16 488 417 389 389
q17 976 697 707 697
q18 8367 7772 7695 7695
q19 3290 1537 1542 1537
q20 621 316 315 315
q21 5120 3310 3983 3310
q22 353 271 278 271
Total cold run time: 116366 ms
Total hot run time: 40821 ms
----- Round 2, with runtime_filter_mode=off -----
q1 4496 4408 4428 4408
q2 365 273 267 267
q3 3144 2909 2880 2880
q4 1972 1583 1592 1583
q5 5341 5474 5493 5474
q6 211 119 124 119
q7 2216 1844 1775 1775
q8 3210 3372 3351 3351
q9 8567 8612 8625 8612
q10 4018 3734 3751 3734
q11 602 489 491 489
q12 816 613 600 600
q13 16205 3152 3114 3114
q14 296 267 270 267
q15 524 505 489 489
q16 501 431 442 431
q17 1788 1517 1536 1517
q18 7938 7683 7474 7474
q19 1673 1582 1536 1536
q20 2014 1800 1770 1770
q21 4737 4573 4639 4573
q22 569 494 503 494
Total cold run time: 71203 ms
Total hot run time: 54957 ms
TPC-DS: Total hot run time: 169576 ms
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpcds-tools
TPC-DS sf100 test result on commit f506a3e58919a1bf2ed582c53a38175b7ddd12d4, data reload: false
query1 914 368 373 368
query2 6437 2521 2440 2440
query3 6640 202 203 202
query4 19242 17611 17375 17375
query5 4084 410 421 410
query6 253 173 152 152
query7 4589 291 287 287
query8 238 181 191 181
query9 8537 2359 2374 2359
query10 456 272 278 272
query11 10554 10099 9999 9999
query12 136 89 87 87
query13 1674 367 366 366
query14 9939 6934 7374 6934
query15 210 173 163 163
query16 7726 261 265 261
query17 1593 516 510 510
query18 1954 270 264 264
query19 188 150 150 150
query20 90 86 87 86
query21 191 130 128 128
query22 4330 3892 4008 3892
query23 33550 33034 33255 33034
query24 6772 2880 2955 2880
query25 532 355 351 351
query26 710 172 154 154
query27 1917 317 327 317
query28 3791 2042 2024 2024
query29 833 599 597 597
query30 203 149 157 149
query31 958 773 754 754
query32 89 54 58 54
query33 501 264 258 258
query34 869 469 466 466
query35 700 605 611 605
query36 1078 921 902 902
query37 104 67 77 67
query38 2893 2782 2767 2767
query39 876 812 787 787
query40 202 126 129 126
query41 48 79 43 43
query42 96 95 94 94
query43 607 557 552 552
query44 1095 737 748 737
query45 180 159 173 159
query46 1044 717 708 708
query47 1817 1736 1746 1736
query48 391 298 304 298
query49 761 392 385 385
query50 771 395 387 387
query51 6889 6692 6702 6692
query52 105 91 94 91
query53 351 286 281 281
query54 527 429 423 423
query55 71 74 73 73
query56 260 240 243 240
query57 1101 1008 1048 1008
query58 241 231 214 214
query59 3423 3135 3552 3135
query60 275 263 261 261
query61 89 86 83 83
query62 542 433 458 433
query63 310 284 282 282
query64 8360 2248 1731 1731
query65 3190 3155 3124 3124
query66 789 327 322 322
query67 15149 15065 14707 14707
query68 4552 542 524 524
query69 442 273 268 268
query70 1157 1136 1158 1136
query71 386 275 275 275
query72 7873 5463 2707 2707
query73 758 317 321 317
query74 5970 5605 5560 5560
query75 3309 2616 2615 2615
query76 2274 962 1006 962
query77 373 263 278 263
query78 10480 9826 9880 9826
query79 1507 508 515 508
query80 811 438 429 429
query81 516 220 217 217
query82 643 93 93 93
query83 243 175 169 169
query84 245 89 84 84
query85 889 277 269 269
query86 454 303 321 303
query87 3291 3156 3151 3151
query88 3512 2480 2493 2480
query89 474 395 381 381
query90 2122 194 195 194
query91 134 106 112 106
query92 62 50 50 50
query93 1752 578 488 488
query94 1128 186 183 183
query95 408 316 311 311
query96 596 276 274 274
query97 3199 3034 3001 3001
query98 227 223 216 216
query99 1127 845 839 839
Total cold run time: 255949 ms
Total hot run time: 169576 ms
ClickBench: Total hot run time: 30.16 s
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/clickbench-tools
ClickBench test result on commit f506a3e58919a1bf2ed582c53a38175b7ddd12d4, data reload: false
query1 0.04 0.03 0.03
query2 0.08 0.04 0.04
query3 0.23 0.05 0.05
query4 1.67 0.06 0.06
query5 0.47 0.50 0.48
query6 1.13 0.73 0.72
query7 0.02 0.01 0.01
query8 0.05 0.04 0.04
query9 0.55 0.48 0.49
query10 0.55 0.56 0.54
query11 0.16 0.11 0.11
query12 0.14 0.11 0.11
query13 0.60 0.59 0.60
query14 0.76 0.79 0.78
query15 0.82 0.81 0.81
query16 0.36 0.37 0.37
query17 0.94 0.98 1.00
query18 0.23 0.25 0.24
query19 1.79 1.66 1.63
query20 0.01 0.02 0.01
query21 15.50 0.67 0.67
query22 4.27 8.06 1.70
query23 18.36 1.41 1.25
query24 2.10 0.20 0.20
query25 0.16 0.07 0.09
query26 0.26 0.17 0.16
query27 0.08 0.07 0.08
query28 13.25 1.01 1.00
query29 13.32 3.32 3.27
query30 0.24 0.06 0.05
query31 2.89 0.38 0.37
query32 3.30 0.46 0.46
query33 2.86 2.88 2.91
query34 17.12 4.41 4.42
query35 4.45 4.48 4.63
query36 0.65 0.46 0.49
query37 0.18 0.14 0.14
query38 0.16 0.14 0.15
query39 0.04 0.04 0.04
query40 0.16 0.15 0.15
query41 0.09 0.04 0.05
query42 0.06 0.05 0.04
query43 0.03 0.04 0.03
Total cold run time: 110.13 s
Total hot run time: 30.16 s
TPC-H: Total hot run time: 40571 ms
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpch-tools
Tpch sf100 test result on commit 5e28a01dad9fd666cdc79f403b0d38e43ab0c99f, data reload: false
------ Round 1 ----------------------------------
q1 18005 4464 4356 4356
q2 2561 190 195 190
q3 11101 1129 1233 1129
q4 10243 716 755 716
q5 7624 2763 2704 2704
q6 219 149 139 139
q7 971 607 594 594
q8 9346 2122 2092 2092
q9 9156 6473 6492 6473
q10 8961 3656 3666 3656
q11 471 248 243 243
q12 435 226 214 214
q13 17766 2995 2952 2952
q14 272 202 213 202
q15 515 469 464 464
q16 521 375 381 375
q17 960 665 793 665
q18 8208 7482 7379 7379
q19 6234 1566 1539 1539
q20 663 308 307 307
q21 5208 3901 3913 3901
q22 348 281 284 281
Total cold run time: 119788 ms
Total hot run time: 40571 ms
----- Round 2, with runtime_filter_mode=off -----
q1 4285 4182 4235 4182
q2 364 256 272 256
q3 2925 2759 2755 2755
q4 1852 1599 1657 1599
q5 5251 5291 5280 5280
q6 240 139 123 123
q7 2131 1753 1747 1747
q8 3218 3300 3328 3300
q9 8341 8391 8369 8369
q10 3880 3666 3689 3666
q11 576 484 492 484
q12 750 617 604 604
q13 17282 2973 2971 2971
q14 291 244 264 244
q15 549 476 478 476
q16 472 404 415 404
q17 1776 1483 1476 1476
q18 7596 7553 7365 7365
q19 1700 1588 1535 1535
q20 2062 1788 1784 1784
q21 4791 4784 4705 4705
q22 573 475 506 475
Total cold run time: 70905 ms
Total hot run time: 53800 ms
TPC-DS: Total hot run time: 169840 ms
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpcds-tools
TPC-DS sf100 test result on commit 5e28a01dad9fd666cdc79f403b0d38e43ab0c99f, data reload: false
query1 929 387 371 371
query2 6457 2437 2322 2322
query3 6652 203 206 203
query4 19213 17370 17298 17298
query5 4199 419 409 409
query6 253 154 148 148
query7 4589 305 294 294
query8 242 179 182 179
query9 8533 2475 2459 2459
query10 437 272 262 262
query11 10577 10182 10126 10126
query12 134 87 86 86
query13 1635 371 351 351
query14 9257 6782 6975 6782
query15 229 167 163 163
query16 7818 263 261 261
query17 1518 521 524 521
query18 1954 270 272 270
query19 204 168 165 165
query20 98 91 110 91
query21 206 137 133 133
query22 4661 4230 4104 4104
query23 33575 33017 32985 32985
query24 12214 2933 2822 2822
query25 655 363 359 359
query26 1786 158 150 150
query27 2963 325 331 325
query28 7553 2101 2100 2100
query29 1127 614 594 594
query30 271 150 155 150
query31 955 768 776 768
query32 92 56 53 53
query33 759 268 278 268
query34 999 494 494 494
query35 763 609 590 590
query36 1065 924 912 912
query37 276 65 66 65
query38 2907 2792 2754 2754
query39 838 804 791 791
query40 274 126 124 124
query41 48 44 44 44
query42 102 98 98 98
query43 571 554 550 550
query44 1220 732 737 732
query45 172 161 157 157
query46 1077 709 704 704
query47 1835 1768 1768 1768
query48 372 303 301 301
query49 1194 384 382 382
query50 785 403 394 394
query51 6978 6927 6695 6695
query52 101 114 91 91
query53 346 285 286 285
query54 959 456 427 427
query55 82 72 72 72
query56 257 247 253 247
query57 1120 1069 1031 1031
query58 239 210 217 210
query59 3526 3157 3196 3157
query60 277 261 261 261
query61 91 89 87 87
query62 663 446 468 446
query63 311 292 287 287
query64 9867 2189 1700 1700
query65 3208 3091 3102 3091
query66 1380 329 326 326
query67 15288 15255 14803 14803
query68 4654 536 550 536
query69 439 272 275 272
query70 1121 1144 1133 1133
query71 416 272 272 272
query72 7429 5104 2745 2745
query73 701 332 327 327
query74 5919 5704 5579 5579
query75 3431 2663 2635 2635
query76 2849 1069 1006 1006
query77 465 268 264 264
query78 10179 9970 9719 9719
query79 2302 515 518 515
query80 1028 434 426 426
query81 517 228 219 219
query82 646 91 90 90
query83 245 167 170 167
query84 240 87 83 83
query85 1878 275 332 275
query86 486 311 292 292
query87 3341 3192 3135 3135
query88 4260 2436 2436 2436
query89 495 404 383 383
query90 1986 185 185 185
query91 124 98 98 98
query92 59 47 48 47
query93 2203 514 495 495
query94 1242 187 192 187
query95 397 323 310 310
query96 588 278 273 273
query97 3163 3030 3054 3030
query98 233 240 214 214
query99 1102 844 868 844
Total cold run time: 275074 ms
Total hot run time: 169840 ms
ClickBench: Total hot run time: 30.4 s
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/clickbench-tools
ClickBench test result on commit 5e28a01dad9fd666cdc79f403b0d38e43ab0c99f, data reload: false
query1 0.04 0.04 0.03
query2 0.08 0.04 0.04
query3 0.24 0.05 0.04
query4 1.68 0.07 0.08
query5 0.51 0.50 0.49
query6 1.13 0.74 0.73
query7 0.02 0.01 0.01
query8 0.05 0.04 0.05
query9 0.54 0.48 0.48
query10 0.55 0.54 0.54
query11 0.16 0.11 0.11
query12 0.14 0.12 0.12
query13 0.59 0.59 0.60
query14 0.75 0.78 0.85
query15 0.83 0.81 0.81
query16 0.37 0.36 0.36
query17 0.96 0.99 0.99
query18 0.21 0.23 0.24
query19 1.72 1.67 1.68
query20 0.01 0.01 0.01
query21 15.57 0.68 0.68
query22 4.48 7.22 1.81
query23 18.27 1.37 1.26
query24 1.97 0.21 0.21
query25 0.14 0.08 0.09
query26 0.26 0.16 0.17
query27 0.08 0.08 0.07
query28 13.37 1.02 1.00
query29 12.64 3.28 3.24
query30 0.25 0.05 0.05
query31 2.87 0.37 0.37
query32 3.31 0.47 0.47
query33 2.89 2.93 2.89
query34 17.11 4.45 4.45
query35 4.48 4.50 4.48
query36 0.65 0.46 0.47
query37 0.18 0.16 0.16
query38 0.17 0.15 0.16
query39 0.05 0.03 0.03
query40 0.16 0.13 0.15
query41 0.09 0.04 0.04
query42 0.06 0.05 0.04
query43 0.05 0.03 0.04
Total cold run time: 109.68 s
Total hot run time: 30.4 s
TPC-H: Total hot run time: 40928 ms
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpch-tools
Tpch sf100 test result on commit 11200c0c6e0bd0f9e4b7bd1a1858c5d0c5c2741d, data reload: false
------ Round 1 ----------------------------------
q1 17668 5047 4252 4252
q2 2036 192 188 188
q3 10520 1164 1225 1164
q4 10212 825 861 825
q5 7486 2718 2653 2653
q6 224 134 136 134
q7 958 595 606 595
q8 9219 2134 2108 2108
q9 9453 6724 6672 6672
q10 10084 3914 3805 3805
q11 451 233 237 233
q12 451 221 230 221
q13 17285 3194 3264 3194
q14 257 212 224 212
q15 525 467 463 463
q16 467 379 403 379
q17 997 662 792 662
q18 8411 7914 7777 7777
q19 2714 1571 1533 1533
q20 626 326 320 320
q21 5130 3970 3256 3256
q22 337 282 283 282
Total cold run time: 115511 ms
Total hot run time: 40928 ms
----- Round 2, with runtime_filter_mode=off -----
q1 4547 4370 4455 4370
q2 387 275 274 274
q3 3117 2932 2930 2930
q4 1966 1614 1646 1614
q5 5414 5531 5501 5501
q6 218 127 125 125
q7 2211 1822 1804 1804
q8 3234 3413 3420 3413
q9 8623 8635 8747 8635
q10 4075 3637 3789 3637
q11 568 497 485 485
q12 786 605 596 596
q13 16211 3123 3110 3110
q14 304 284 278 278
q15 519 454 473 454
q16 490 428 440 428
q17 1844 1539 1522 1522
q18 7897 8049 7403 7403
q19 3168 1581 1572 1572
q20 2000 1796 1778 1778
q21 9142 4708 4639 4639
q22 553 486 474 474
Total cold run time: 77274 ms
Total hot run time: 55042 ms
TPC-DS: Total hot run time: 168386 ms
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpcds-tools
TPC-DS sf100 test result on commit 11200c0c6e0bd0f9e4b7bd1a1858c5d0c5c2741d, data reload: false
query1 926 381 366 366
query2 6442 2452 2265 2265
query3 6636 204 203 203
query4 19473 17250 17238 17238
query5 4109 422 417 417
query6 252 152 151 151
query7 4593 297 286 286
query8 243 180 177 177
query9 8574 2343 2330 2330
query10 440 279 255 255
query11 10458 10065 10126 10065
query12 136 94 87 87
query13 1632 372 370 370
query14 9354 7639 6267 6267
query15 213 166 167 166
query16 7717 260 256 256
query17 1752 518 507 507
query18 1833 268 262 262
query19 203 146 149 146
query20 93 83 87 83
query21 197 136 128 128
query22 4259 3920 3887 3887
query23 33767 32828 32976 32828
query24 8179 2938 2831 2831
query25 573 360 355 355
query26 703 156 153 153
query27 2231 312 311 311
query28 5763 1986 2005 1986
query29 845 610 610 610
query30 223 151 150 150
query31 980 751 751 751
query32 90 53 54 53
query33 611 270 277 270
query34 882 477 477 477
query35 697 607 605 605
query36 1082 909 903 903
query37 108 66 65 65
query38 2893 2805 2785 2785
query39 857 789 772 772
query40 201 131 125 125
query41 48 43 44 43
query42 105 96 98 96
query43 591 528 552 528
query44 1093 731 743 731
query45 185 166 169 166
query46 1068 729 728 728
query47 1861 1741 1761 1741
query48 399 292 292 292
query49 830 375 377 375
query50 774 374 399 374
query51 6809 6843 6748 6748
query52 100 87 98 87
query53 352 287 290 287
query54 691 433 431 431
query55 75 70 72 70
query56 272 241 252 241
query57 1079 1031 1055 1031
query58 227 206 214 206
query59 3310 3203 3213 3203
query60 296 265 296 265
query61 89 90 87 87
query62 608 446 459 446
query63 305 288 288 288
query64 8486 2205 1734 1734
query65 3227 3093 3160 3093
query66 809 338 343 338
query67 15370 14972 14845 14845
query68 4516 528 531 528
query69 467 284 276 276
query70 1120 1089 1124 1089
query71 381 274 270 270
query72 7420 5794 2749 2749
query73 713 326 319 319
query74 5947 5612 5635 5612
query75 3311 2659 2602 2602
query76 2395 1026 1017 1017
query77 387 269 265 265
query78 10397 9811 9684 9684
query79 2378 505 515 505
query80 1986 422 428 422
query81 535 221 215 215
query82 803 92 86 86
query83 281 174 169 169
query84 266 87 84 84
query85 2106 322 269 269
query86 486 316 293 293
query87 3284 3107 3112 3107
query88 4036 2420 2436 2420
query89 481 385 378 378
query90 2050 191 189 189
query91 128 96 101 96
query92 59 48 53 48
query93 2985 491 496 491
query94 1279 188 186 186
query95 403 302 317 302
query96 597 277 265 265
query97 3201 2983 3016 2983
query98 241 214 213 213
query99 1145 864 838 838
Total cold run time: 265063 ms
Total hot run time: 168386 ms
ClickBench: Total hot run time: 30.66 s
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/clickbench-tools
ClickBench test result on commit 11200c0c6e0bd0f9e4b7bd1a1858c5d0c5c2741d, data reload: false
query1 0.04 0.03 0.04
query2 0.08 0.04 0.04
query3 0.24 0.05 0.05
query4 1.66 0.08 0.08
query5 0.50 0.50 0.52
query6 1.13 0.72 0.71
query7 0.02 0.02 0.01
query8 0.05 0.03 0.04
query9 0.53 0.49 0.49
query10 0.54 0.57 0.56
query11 0.15 0.11 0.11
query12 0.15 0.12 0.11
query13 0.60 0.59 0.59
query14 0.75 0.77 0.78
query15 0.82 0.81 0.80
query16 0.36 0.35 0.36
query17 1.01 0.95 0.97
query18 0.21 0.24 0.27
query19 1.74 1.64 1.65
query20 0.02 0.01 0.01
query21 15.63 0.65 0.63
query22 3.72 7.25 2.13
query23 18.32 1.40 1.33
query24 1.36 0.41 0.23
query25 0.15 0.09 0.08
query26 0.27 0.17 0.17
query27 0.07 0.08 0.07
query28 13.29 1.00 1.00
query29 13.85 3.25 3.29
query30 0.24 0.05 0.06
query31 2.99 0.38 0.37
query32 3.22 0.47 0.47
query33 2.83 2.89 2.88
query34 17.19 4.47 4.42
query35 4.53 4.48 4.69
query36 0.65 0.46 0.48
query37 0.18 0.15 0.15
query38 0.15 0.15 0.14
query39 0.04 0.03 0.04
query40 0.16 0.13 0.14
query41 0.08 0.04 0.05
query42 0.06 0.06 0.05
query43 0.04 0.04 0.03
Total cold run time: 109.62 s
Total hot run time: 30.66 s
PR approved by at least one committer and no changes requested.
![github-actions[bot] avatar](https://avatars.githubusercontent.com/in/15368?v=4 "Published by a pub.dev verified publisher"){kind=small}