You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@doris.apache.org by "starocean999 (via GitHub)" <gi...@apache.org> on 2026/03/09 08:51:50 UTC
[PR] [feat](join) support outer join reorder in dphyper [doris]
starocean999 opened a new pull request, #61146:
URL: https://github.com/apache/doris/pull/61146
### What problem does this PR solve?
Issue Number: close #xxx
Related PR: #xxx
Problem Summary:
### Release note
None
### Check List (For Author)
- Test <!-- At least one of them must be included. -->
- [ ] Regression test
- [ ] Unit Test
- [ ] Manual test (add detailed scripts or steps below)
- [ ] No need to test or manual test. Explain why:
- [ ] This is a refactor/code format and no logic has been changed.
- [ ] Previous test can cover this change.
- [ ] No code files have been changed.
- [ ] Other reason <!-- Add your reason? -->
- Behavior changed:
- [ ] No.
- [ ] Yes. <!-- Explain the behavior change -->
- Does this need documentation?
- [ ] No.
- [ ] Yes. <!-- Add document PR link here. eg: https://github.com/apache/doris-website/pull/1214 -->
### Check List (For Reviewer who merge this PR)
- [ ] Confirm the release note
- [ ] Confirm test cases
- [ ] Confirm document
- [ ] Add branch pick label <!-- Add branch pick label that this PR should merge into -->
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4023869922
<details>
<summary>TPC-H: <b>Total hot run time: 27382 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpch-tools
Tpch sf100 test result on commit 4169a8c8a747c8e888a3c93cbad5edf7acd0baae, data reload: false
------ Round 1 ----------------------------------
============================================
q1 17660 4531 4281 4281
q2 q3 10637 780 513 513
q4 4691 368 247 247
q5 7565 1184 982 982
q6 180 178 146 146
q7 779 844 659 659
q8 9403 1452 1270 1270
q9 4849 4733 4654 4654
q10 6314 1918 1650 1650
q11 492 258 250 250
q12 741 570 475 475
q13 18035 2921 2174 2174
q14 236 232 216 216
q15 918 798 801 798
q16 750 720 659 659
q17 691 828 437 437
q18 5985 5458 5223 5223
q19 1388 1005 601 601
q20 493 516 398 398
q21 4475 2082 1464 1464
q22 383 335 285 285
Total cold run time: 96665 ms
Total hot run time: 27382 ms
----- Round 2, with runtime_filter_mode=off -----
============================================
q1 4593 4567 4576 4567
q2 q3 3892 4320 3814 3814
q4 890 1185 784 784
q5 4058 4356 4322 4322
q6 181 172 136 136
q7 1792 1684 1554 1554
q8 2528 2748 2505 2505
q9 7554 7250 7356 7250
q10 3806 4004 3596 3596
q11 508 432 415 415
q12 479 577 453 453
q13 2685 3209 2365 2365
q14 283 294 273 273
q15 841 833 809 809
q16 725 753 714 714
q17 1341 1429 1383 1383
q18 7210 6828 6587 6587
q19 1073 886 864 864
q20 2162 2203 2067 2067
q21 3912 3447 3331 3331
q22 448 451 367 367
Total cold run time: 50961 ms
Total hot run time: 48156 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4293189664
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4073591985
<details>
<summary>TPC-DS: <b>Total hot run time: 168082 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpcds-tools
TPC-DS sf100 test result on commit ff5784f0f1c27c4c0dc48a9c6250186e905921dc, data reload: false
query5 4326 652 520 520
query6 329 221 204 204
query7 4206 469 265 265
query8 346 239 222 222
query9 8794 2730 2749 2730
query10 522 379 344 344
query11 6934 5078 4891 4891
query12 191 135 130 130
query13 1268 450 361 361
query14 5767 3690 3483 3483
query14_1 2874 2851 2845 2845
query15 211 194 173 173
query16 982 432 470 432
query17 898 751 648 648
query18 2464 454 353 353
query19 223 225 198 198
query20 142 133 127 127
query21 217 142 117 117
query22 13280 13923 15039 13923
query23 16121 15930 15504 15504
query23_1 15737 15996 15575 15575
query24 8022 1815 1298 1298
query24_1 1282 1271 1211 1211
query25 587 461 440 440
query26 1245 264 148 148
query27 2767 489 294 294
query28 4486 1861 1866 1861
query29 899 581 476 476
query30 297 224 187 187
query31 1005 969 873 873
query32 98 71 69 69
query33 515 333 280 280
query34 897 884 542 542
query35 648 684 620 620
query36 1059 1132 985 985
query37 140 94 84 84
query38 2949 2991 2881 2881
query39 855 843 809 809
query39_1 780 820 793 793
query40 235 157 134 134
query41 64 61 58 58
query42 259 250 257 250
query43 242 243 224 224
query44
query45 201 195 185 185
query46 898 974 609 609
query47 2157 2139 2078 2078
query48 309 314 229 229
query49 648 464 379 379
query50 684 277 206 206
query51 4033 4080 3953 3953
query52 259 284 258 258
query53 293 341 285 285
query54 307 280 267 267
query55 98 85 84 84
query56 314 335 312 312
query57 1936 1712 1671 1671
query58 296 276 273 273
query59 2816 2943 2745 2745
query60 346 337 335 335
query61 160 166 154 154
query62 609 584 534 534
query63 316 285 278 278
query64 4933 967 669 669
query65
query66 1465 453 361 361
query67 24141 24242 24095 24095
query68
query69 425 339 293 293
query70 977 974 934 934
query71 354 315 308 308
query72 2740 2722 2524 2524
query73 536 540 324 324
query74 9599 9525 9392 9392
query75 2848 2734 2485 2485
query76 2294 1044 672 672
query77 360 385 309 309
query78 10938 11223 10506 10506
query79 1099 825 584 584
query80 708 634 561 561
query81 480 259 231 231
query82 1344 156 139 139
query83 380 267 244 244
query84 306 121 103 103
query85 875 523 505 505
query86 375 313 292 292
query87 3116 3066 3012 3012
query88 3559 2657 2649 2649
query89 438 387 349 349
query90 1975 175 167 167
query91 178 169 141 141
query92 84 75 74 74
query93 911 886 500 500
query94 446 325 297 297
query95 588 345 377 345
query96 658 516 233 233
query97 2487 2534 2390 2390
query98 233 221 216 216
query99 1029 992 919 919
Total cold run time: 248394 ms
Total hot run time: 168082 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4072939679
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4287514950
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4393872097
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4133741019
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4022151983
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "hello-stephen (via GitHub)" <gi...@apache.org>.
hello-stephen commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4134393379
# FE UT Coverage Report
Increment line coverage ` 85.71% (1362/1589)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/61146_4c3213072c9207313f847ed1f00358df682f23f5/fe_increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/61146_4c3213072c9207313f847ed1f00358df682f23f5/fe_report/index.html)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4181247142
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4073526140
<details>
<summary>TPC-H: <b>Total hot run time: 26922 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpch-tools
Tpch sf100 test result on commit ff5784f0f1c27c4c0dc48a9c6250186e905921dc, data reload: false
------ Round 1 ----------------------------------
orders Doris NULL NULL 0 0 0 NULL 0 NULL NULL 2023-12-26 18:27:23 2023-12-26 18:42:55 NULL utf-8 NULL NULL
============================================
q1 17633 4483 4268 4268
q2 q3 10647 808 516 516
q4 4706 365 258 258
q5 7789 1206 1017 1017
q6 217 173 148 148
q7 815 898 674 674
q8 10587 1491 1359 1359
q9 6281 4779 4740 4740
q10 6303 1940 1666 1666
q11 457 256 245 245
q12 742 601 463 463
q13 18061 2929 2174 2174
q14 229 232 207 207
q15 q16 751 726 682 682
q17 745 829 476 476
q18 5953 5508 5283 5283
q19 1214 977 617 617
q20 537 496 379 379
q21 4446 2356 1477 1477
q22 392 325 273 273
Total cold run time: 98505 ms
Total hot run time: 26922 ms
----- Round 2, with runtime_filter_mode=off -----
orders Doris NULL NULL 150000000 42 6422171781 NULL 22778155 NULL NULL 2023-12-26 18:27:23 2023-12-26 18:42:55 NULL utf-8 NULL NULL
============================================
q1 4758 4693 4626 4626
q2 q3 3929 4372 3845 3845
q4 897 1202 772 772
q5 4092 4435 4496 4435
q6 196 188 147 147
q7 1848 1643 1552 1552
q8 2490 2778 2619 2619
q9 7477 7229 7421 7229
q10 3746 4102 3699 3699
q11 514 445 431 431
q12 518 608 500 500
q13 2904 3228 2313 2313
q14 291 314 320 314
q15 q16 743 749 758 749
q17 1211 1424 1421 1421
q18 7143 6798 6598 6598
q19 998 933 914 914
q20 2076 2156 2069 2069
q21 3984 3587 3336 3336
q22 443 418 382 382
Total cold run time: 50258 ms
Total hot run time: 47951 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4116522185
<details>
<summary>TPC-H: <b>Total hot run time: 26891 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpch-tools
Tpch sf100 test result on commit 39f6944b96ba91bfbd1de459f5f3ae5d58d2b39f, data reload: false
------ Round 1 ----------------------------------
orders Doris NULL NULL 0 0 0 NULL 0 NULL NULL 2023-12-26 18:27:23 2023-12-26 18:42:55 NULL utf-8 NULL NULL
============================================
q1 17609 4535 5278 4535
q2 q3 10650 794 526 526
q4 4677 361 249 249
q5 7571 1241 1008 1008
q6 181 172 149 149
q7 779 855 672 672
q8 9297 1490 1329 1329
q9 4831 4770 4723 4723
q10 6247 1915 1667 1667
q11 462 254 237 237
q12 732 589 472 472
q13 18023 2712 1943 1943
q14 228 238 218 218
q15 q16 722 744 665 665
q17 738 845 448 448
q18 5967 5417 5200 5200
q19 1185 976 641 641
q20 536 498 377 377
q21 4554 1854 1519 1519
q22 485 385 313 313
Total cold run time: 95474 ms
Total hot run time: 26891 ms
----- Round 2, with runtime_filter_mode=off -----
orders Doris NULL NULL 150000000 42 6422171781 NULL 22778155 NULL NULL 2023-12-26 18:27:23 2023-12-26 18:42:55 NULL utf-8 NULL NULL
============================================
q1 4758 4640 4605 4605
q2 q3 3938 4416 3862 3862
q4 918 1199 764 764
q5 4123 4402 4371 4371
q6 186 171 147 147
q7 1779 1694 1585 1585
q8 2494 2747 2615 2615
q9 7676 7461 7687 7461
q10 3751 3987 3672 3672
q11 540 471 437 437
q12 515 628 511 511
q13 2543 2962 2096 2096
q14 310 298 283 283
q15 q16 734 744 723 723
q17 1138 1421 1359 1359
q18 7144 6810 6616 6616
q19 993 931 908 908
q20 2145 2210 2021 2021
q21 4180 3470 3461 3461
q22 454 459 388 388
Total cold run time: 50319 ms
Total hot run time: 47885 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4116333103
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4053908827
<details>
<summary>TPC-DS: <b>Total hot run time: 167112 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpcds-tools
TPC-DS sf100 test result on commit d96ce294f381610ac73afdfed1f199cca996e633, data reload: false
query5 4324 626 515 515
query6 324 222 210 210
query7 4226 487 266 266
query8 335 254 224 224
query9 8800 2750 2724 2724
query10 519 363 335 335
query11 6992 5110 4881 4881
query12 187 127 128 127
query13 1267 458 342 342
query14 5539 3720 3442 3442
query14_1 2871 2822 2791 2791
query15 226 198 180 180
query16 1003 462 429 429
query17 984 717 633 633
query18 2448 455 356 356
query19 215 206 185 185
query20 138 130 126 126
query21 221 129 111 111
query22 13170 13902 14530 13902
query23 16258 15712 15617 15617
query23_1 15973 15531 15338 15338
query24 7324 1571 1223 1223
query24_1 1221 1235 1242 1235
query25 543 454 398 398
query26 1244 257 143 143
query27 2788 469 290 290
query28 4497 1862 1853 1853
query29 837 579 486 486
query30 297 227 193 193
query31 1013 940 870 870
query32 84 68 70 68
query33 503 365 279 279
query34 884 871 543 543
query35 638 700 592 592
query36 1075 1095 954 954
query37 132 99 82 82
query38 2944 2926 2888 2888
query39 857 833 820 820
query39_1 778 779 787 779
query40 230 150 135 135
query41 62 58 59 58
query42 259 258 255 255
query43 242 250 223 223
query44
query45 191 189 185 185
query46 860 990 609 609
query47 2088 2116 2045 2045
query48 320 308 227 227
query49 615 450 383 383
query50 675 275 222 222
query51 4060 4030 4011 4011
query52 266 264 255 255
query53 298 344 281 281
query54 293 258 256 256
query55 94 82 83 82
query56 314 320 308 308
query57 1934 1865 1728 1728
query58 310 273 272 272
query59 2814 2945 2733 2733
query60 343 331 320 320
query61 149 149 150 149
query62 633 586 526 526
query63 301 281 273 273
query64 4765 941 658 658
query65
query66 1456 445 352 352
query67 24248 24474 24148 24148
query68
query69 405 301 289 289
query70 988 1013 966 966
query71 347 307 311 307
query72 2756 2594 2281 2281
query73 524 542 310 310
query74 9578 9585 9351 9351
query75 2854 2730 2441 2441
query76 2281 1030 678 678
query77 351 363 302 302
query78 10809 11132 10438 10438
query79 1121 761 574 574
query80 670 626 552 552
query81 484 257 221 221
query82 1368 148 122 122
query83 375 264 250 250
query84 286 117 94 94
query85 863 479 445 445
query86 374 310 296 296
query87 3176 3103 3054 3054
query88 3526 2650 2630 2630
query89 433 372 358 358
query90 1988 173 168 168
query91 168 153 130 130
query92 78 74 73 73
query93 897 820 505 505
query94 458 308 287 287
query95 587 340 381 340
query96 625 512 227 227
query97 2501 2492 2358 2358
query98 240 221 227 221
query99 1000 962 922 922
Total cold run time: 247967 ms
Total hot run time: 167112 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4066820979
<details>
<summary>TPC-DS: <b>Total hot run time: 167837 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpcds-tools
TPC-DS sf100 test result on commit 707151bd57c310c21b891070e8fa39bdfa8bed76, data reload: false
query5 4314 628 503 503
query6 340 233 212 212
query7 4230 476 268 268
query8 337 244 237 237
query9 8752 2809 2774 2774
query10 525 378 356 356
query11 6998 5097 4911 4911
query12 186 127 125 125
query13 1270 460 345 345
query14 5788 3725 3457 3457
query14_1 2827 2807 2781 2781
query15 206 192 176 176
query16 974 476 465 465
query17 924 710 614 614
query18 2461 446 356 356
query19 224 219 190 190
query20 140 127 126 126
query21 210 138 114 114
query22 13245 14145 14605 14145
query23 16217 15913 15423 15423
query23_1 15593 15591 15385 15385
query24 7281 1589 1225 1225
query24_1 1185 1212 1215 1212
query25 535 462 396 396
query26 1244 262 146 146
query27 2781 489 293 293
query28 4491 1873 1859 1859
query29 834 550 507 507
query30 293 226 188 188
query31 1021 962 867 867
query32 81 70 71 70
query33 510 346 288 288
query34 908 875 530 530
query35 638 680 602 602
query36 1071 1178 1002 1002
query37 136 89 81 81
query38 2917 2953 2885 2885
query39 859 837 817 817
query39_1 789 790 797 790
query40 233 151 134 134
query41 61 60 58 58
query42 263 256 253 253
query43 243 245 224 224
query44
query45 202 193 179 179
query46 868 978 599 599
query47 3298 2129 2035 2035
query48 304 315 232 232
query49 627 455 368 368
query50 668 280 206 206
query51 4055 4089 4007 4007
query52 266 262 258 258
query53 283 331 286 286
query54 303 268 266 266
query55 93 85 84 84
query56 318 333 309 309
query57 1932 1680 1682 1680
query58 289 287 273 273
query59 2813 2916 2743 2743
query60 344 335 310 310
query61 155 144 148 144
query62 651 596 534 534
query63 316 281 273 273
query64 4708 934 678 678
query65
query66 1471 443 348 348
query67 24246 24231 24261 24231
query68
query69 408 325 288 288
query70 972 967 933 933
query71 347 323 306 306
query72 2758 2663 2392 2392
query73 525 532 319 319
query74 9632 9587 9414 9414
query75 2843 2738 2446 2446
query76 2291 1014 678 678
query77 361 390 318 318
query78 10955 11153 10471 10471
query79 1094 844 585 585
query80 713 625 533 533
query81 475 255 221 221
query82 1358 151 118 118
query83 376 266 251 251
query84 304 129 103 103
query85 928 558 515 515
query86 382 347 325 325
query87 3206 3107 3027 3027
query88 3621 2704 2700 2700
query89 426 370 346 346
query90 1984 179 177 177
query91 167 161 132 132
query92 74 75 70 70
query93 910 856 504 504
query94 440 320 285 285
query95 590 394 316 316
query96 635 510 234 234
query97 2459 2439 2382 2382
query98 228 222 225 222
query99 1025 996 929 929
Total cold run time: 249395 ms
Total hot run time: 167837 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4037705198
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4053732525
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "morrySnow (via GitHub)" <gi...@apache.org>.
morrySnow commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4132076790
## Code Review β PR #61146 `[feat](join) support outer join reorder in dphyper`
Reviewed with 4 models: **Gemini 3 Pro**, **GPT-5.4**, **GPT-5.3-Codex**, **Claude Opus 4.6**. 12 findings total.
---
### π΄ Critical / High Severity
#### 1. Copy-paste bug: `otherConditions` uses wrong getter
**`GraphSimplifier.constructEdge()`**
Both `hashConditions` and `otherConditions` call `.getHashJoinConjuncts()`. The second should be `.getOtherJoinConjuncts()`. This **silently drops non-equi predicates** and **duplicates hash predicates**, corrupting cost estimation during graph simplification.
#### 2. PriorityQueue never re-heapified after key mutation
**`GraphSimplifier.updatePQ()`**
When `bestStep.benefit` changes on a queued `BestSimplification`, the `PriorityQueue` is not `remove()+add()`ed. Java `PriorityQueue` doesn't re-sort on in-place key mutations, so `poll()` may return a stale, non-optimal simplification step. The old hypergraph implementation (`hypergraph/GraphSimplifier.java`) explicitly reinserted entries β this v2 should do the same.
#### 3. `threeRightJoin` caches cost using wrong edge
**`GraphSimplifier.threeRightJoin()`**
Stats are derived with `edge2`, but cost is cached with `calCost(edge1, bitmap2, bitmap3)`. `threeLeftJoin()` is consistent; this is asymmetric and incorrect. Should be `calCost(edge2, bitmap2, bitmap3)`.
#### 4. `getLiteralAlias()` destructively removes entries, breaks enumeration retry
**`HyperGraph.getLiteralAlias()` / `PlanReceiver.reset()`**
`getLiteralAlias()` calls `nodeToLiteralAlias.remove()`, but `reset()` doesn't restore alias state. When enumeration is retried after simplification, literal aliases are lost, potentially dropping constant/derived slots needed by upper joins or the final output.
#### 5. `foundEdgesContain` mutates cached BitSet by reference
**`SubgraphEnumerator.EdgeCalculator.foundEdgesContain()`**
Gets cached `BitSet` by reference from `containSimpleEdges`, then `.or()`s complex edges into it, **permanently corrupting** the cache entry. Fix: clone before mutating: `BitSet edgeMap = (BitSet) containSimpleEdges.get(subgraph).clone();`
#### 6. `dpHypOptimize()` restores stale `rewritePlan` after memo rebuild
**`Optimizer.dpHypOptimize()`**
After rebuilding memo from the rewritten plan, it calls `setRewritePlan(oldRewrittenPlan)`, leaving `CascadesContext` internally inconsistent (memo no longer matches `rewritePlan`). Either keep them aligned or explicitly document the intentional divergence.
#### 7. Fragile `getBestLogicalPlan` may silently discard optimization results
**`Group.getBestLogicalPlan()`**
If no logical expression's children match the best physical plan's children, the fallback returns the first (original, unoptimized) logical expression. DPhyper's optimized join order can be silently discarded in this path.
---
### π‘ Medium Severity
#### 8. Cost model: division-by-zero + ignoring probe cost
**`GraphSimplifier.calCost()`**
`1 / leftStats.getRowCount()` β `Infinity` when left table is empty. Also, the formula ignores probe-side magnitude, making cost comparisons unreliable for large probe sides.
#### 9. NPE when stats are null in `GraphSimplifier`
**`GraphSimplifier.calCost()`**
`cacheCost.get(bitmap)` auto-unboxes null `Double` β NPE when stats were missing during initialization and `cacheCost` was not populated for that bitmap.
#### 10. `nonInnerJoinedNodes` overwritten instead of accumulated
**`HyperGraph.Builder.addJoin()`**
Uses `=` instead of `|=` when setting `nonInnerJoinedNodes`, losing earlier non-inner join node tracking when processing sibling subtrees. Should be: `nonInnerJoinedNodes |= LongBitmap.or(leftSubtreeNodes, rightSubtreeNodes);`
#### 11. Dead null-check in `DPhyperNode` constructor
**`DPhyperNode(int, Group)`**
`Preconditions.checkArgument(group != null)` is placed after `super(group.getLogicalExpression()...)`, which would NPE first. The check is unreachable dead code. Use `Objects.requireNonNull(group)` before the `super()` call, or remove the redundant check.
#### 12. Test catches exceptions without failing
**`GraphSimplifierConsistencyTest.randomTest()`**
Catches `Exception`, prints diagnostics, but does not call `Assertions.fail()` or rethrow. Regressions will silently pass. Add `Assertions.fail(ex)` in the catch block.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "hello-stephen (via GitHub)" <gi...@apache.org>.
hello-stephen commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4293596143
# FE Regression Coverage Report
Increment line coverage ` 69.45% (1107/1594)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/61146_31779cc4e6272bd5610fc479f80978dbc0311307_merge_fe/increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/61146_31779cc4e6272bd5610fc479f80978dbc0311307_merge_fe/report/index.html)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "hello-stephen (via GitHub)" <gi...@apache.org>.
hello-stephen commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4022140083
Thank you for your contribution to Apache Doris.
Don't know what should be done next? See [How to process your PR](https://cwiki.apache.org/confluence/display/DORIS/How+to+process+your+PR).
Please clearly describe your PR:
1. What problem was fixed (it's best to include specific error reporting information). How it was fixed.
2. Which behaviors were modified. What was the previous behavior, what is it now, why was it modified, and what possible impacts might there be.
3. What features were added. Why was this function added?
4. Which code was refactored and why was this part of the code refactored?
5. Which functions were optimized and what is the difference before and after the optimization?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "hello-stephen (via GitHub)" <gi...@apache.org>.
hello-stephen commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4023310593
# FE UT Coverage Report
Increment line coverage ` 85.99% (1356/1577)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/61146_2bbaea10353cdb35e4f172620c799950350f246c/fe_increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/61146_2bbaea10353cdb35e4f172620c799950350f246c/fe_report/index.html)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4269360385
/review
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "hello-stephen (via GitHub)" <gi...@apache.org>.
hello-stephen commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4312737748
# FE Regression Coverage Report
Increment line coverage ` 69.75% (1107/1587)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/61146_dcce2402900b972d25c0c96a77f6553a54fc34e4_merge_fe/increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/61146_dcce2402900b972d25c0c96a77f6553a54fc34e4_merge_fe/report/index.html)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 merged PR #61146:
URL: https://github.com/apache/doris/pull/61146
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "morrySnow (via GitHub)" <gi...@apache.org>.
morrySnow commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4132316484
## Deep Dive: Remaining 7 Non-GraphSimplifier Issues
### Issue #4: `getLiteralAlias()` destructive removal breaks retry (HIGH β CONFIRMED)
**Evidence chain:**
1. `JoinOrderJob.tryEnumerateJoin()` (line 94-101): first calls `subgraphEnumerator.enumerate()`, and if it fails, calls `graphSimplifier.simplifyGraph(limit) && subgraphEnumerator.enumerate()` (retry).
2. During the first `enumerate()`, `PlanReceiver.addGroup()` calls `proposeProject()` which calls `hyperGraph.getLiteralAlias(bitmap, bitmap)`.
3. `HyperGraph.getLiteralAlias()` does `nodeToLiteralAlias.remove(left)` on leaf groups (when `left == right`).
4. `PlanReceiver.reset()` clears `planTable` and `usdEdges` but **does NOT restore** `nodeToLiteralAlias`.
5. On the retry `enumerate()` call, `getLiteralAlias()` finds empty map β literal alias projections are lost.
**Fix:** Either make `getLiteralAlias()` non-destructive (don't `remove()`, just `get()`), or save/restore `nodeToLiteralAlias` in `PlanReceiver.reset()`. Since `nodeToLiteralAlias` lives in `HyperGraph` (not `PlanReceiver`), the cleanest fix is to not mutate it:
```java
// Before:
nodeToLiteralAlias.remove(left);
// After:
// Just read without removing β the map is consulted per-join anyway
```
---
### Issue #5: `foundEdgesContain` corrupts cached `containSimpleEdges` BitSet (HIGH β CONFIRMED)
**Evidence:** `SubgraphEnumerator.EdgeCalculator`:
```java
public List<Edge> foundEdgesContain(long subgraph) {
BitSet edgeMap = containSimpleEdges.get(subgraph); // reference, not copy
Preconditions.checkState(edgeMap != null);
edgeMap.or(containComplexEdges.get(subgraph)); // mutates cached entry!
return edgeMap.stream().mapToObj(edges::get).collect(Collectors.toList());
}
```
Note: `foundEdgesContain()` is currently **not called** in active code paths (only `foundSimpleEdgesContain` and `foundComplexEdgesContain` are used separately). So this is a latent bug / landmine. Still should be fixed as it's `public`.
**Fix:** `BitSet edgeMap = (BitSet) containSimpleEdges.get(subgraph).clone();`
---
### Issue #6: `dpHypOptimize()` restores stale `rewritePlan` (HIGH β CONFIRMED)
**Evidence flow:**
```java
Plan oldRewrittenPlan = cascadesContext.getRewritePlan(); // save old
// ... build rewritten plan from DPhyper output ...
cascadesContext.setRewritePlan(rewritten); // set new
cascadesContext.toMemo(); // memo built from 'rewritten'
cascadesContext.setRewritePlan(oldRewrittenPlan); // RESTORE OLD β mismatch!
```
After this, `cascadesContext.getRewritePlan()` returns the pre-DPhyper plan while memo contains the post-DPhyper structure. Any code that reads `getRewritePlan()` later (e.g., for error reporting, plan display, or fallback) sees stale data.
**Verdict:** This looks intentional to preserve the "original rewrite plan" for potential later use, but it creates an invariant violation. If `getRewritePlan()` is only used before optimization, this is harmless. But it's fragile and undocumented.
**Fix:** Either don't restore (keep aligned), or add a comment explaining the intentional divergence.
---
### Issue #7: `getBestLogicalPlan` silent fallback (MEDIUM β NUANCED)
**Logic:**
```java
public Plan getBestLogicalPlan(GroupExpression groupExpression) {
// Try to match physical plan's children to a logical expression
for (GroupExpression logicalExpression : logicalExpressions) {
if (childrenGroups.equals(logicalExpression.children())) {
return logicalExpression.getPlan(); // exact match
}
}
// Fallback: skip enforcers (Distribute/Sort), otherwise return FIRST logical expr
if (groupExpression.getPlan() instanceof PhysicalDistribute
|| groupExpression.getPlan() instanceof PhysicalQuickSort || logicalExpressions.isEmpty()) {
return null; // enforcers have no logical equivalent
} else {
return getLogicalExpression().getPlan(); // returns FIRST = possibly original
}
}
```
The fallback `getLogicalExpression().getPlan()` returns the first logical expression, which may be the **original unoptimized** one. However, in `Memo.copyOutBestLogicalPlan()`, when this returns a non-null plan, it's used as the output. If DPhyper found a better join order but the physical plan's children don't match any logical expression's children (due to group merging), the fallback silently returns the old plan.
**Verdict:** In practice, DPhyper creates both logical and physical expressions in the same groups, so the children match should usually succeed. The risk is in edge cases with group merging. This is a correctness concern but likely rare.
---
### Issue #10: `nonInnerJoinedNodes` overwrite (MEDIUM β CONFIRMED, LOW PRACTICAL IMPACT)
**Code:**
```java
} else {
nonInnerJoinedNodes = LongBitmap.or(leftSubtreeNodes, rightSubtreeNodes); // overwrites!
```
Should be: `nonInnerJoinedNodes |= LongBitmap.or(leftSubtreeNodes, rightSubtreeNodes);`
**Practical impact:** Due to the tree traversal order in `addJoin()`, a non-inner join at a higher level in the tree will always have its subtree nodes as a superset of any lower non-inner joins. But for sibling non-inner joins under an inner join, the first sibling's tracking is lost. E.g., `INNER(LEFT(T1,T2), LEFT(T3,T4))` β after processing LEFT(T3,T4), `nonInnerJoinedNodes = {T3,T4}`, losing `{T1,T2}`. This could lead to incorrectly splitting inner join conjuncts that reference T1/T2.
---
### Issue #11: Dead null-check in `DPhyperNode` (LOW β CONFIRMED)
```java
public DPhyperNode(int index, Group group) {
super(group.getLogicalExpression().getPlan(), index); // NPE if null
Preconditions.checkArgument(group != null, "..."); // dead code
```
Per Doris coding standards, assertions are preferred over defensive checks. The `super()` call already fails fast on null. Either use `Objects.requireNonNull(group)` in the super call or remove the dead check.
---
### Issue #12: Tests swallow exceptions without failing (MEDIUM β CONFIRMED)
Found in **two** test files, not just one:
1. **`hypergraph/OtherJoinTest.java`** (line ~109):
```java
} catch (Exception ex) {
ex.printStackTrace(System.out);
// NO Assertions.fail() or rethrow!
}
```
2. **`hypergraphv2/OtherJoinTest.java`** (line ~79): Same pattern.
Both tests catch exceptions during optimization/evaluation and print them, but let the test pass. This masks real failures.
**Fix:** Add `Assertions.fail("Unexpected exception: " + ex.getMessage(), ex);` in each catch block.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4023554555
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4022899533
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4037875670
<details>
<summary>TPC-H: <b>Total hot run time: 27761 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpch-tools
Tpch sf100 test result on commit 48bc77792381e05a7eece5abe21cbd000382ddb8, data reload: false
------ Round 1 ----------------------------------
============================================
q1 17642 4557 4290 4290
q2 q3 10647 782 521 521
q4 4680 357 256 256
q5 7542 1205 1017 1017
q6 180 174 146 146
q7 796 834 678 678
q8 9311 1451 1519 1451
q9 4831 4693 4676 4676
q10 6260 1870 1644 1644
q11 472 255 239 239
q12 692 581 481 481
q13 18044 2882 2189 2189
q14 230 242 217 217
q15 893 795 795 795
q16 733 729 678 678
q17 729 852 437 437
q18 6012 5355 5223 5223
q19 1253 995 630 630
q20 496 498 397 397
q21 4698 2103 1507 1507
q22 393 326 289 289
Total cold run time: 96534 ms
Total hot run time: 27761 ms
----- Round 2, with runtime_filter_mode=off -----
============================================
q1 4711 4555 4562 4555
q2 q3 3872 4304 3827 3827
q4 904 1192 762 762
q5 4100 4383 4320 4320
q6 181 177 141 141
q7 1868 1677 1526 1526
q8 2451 2778 2555 2555
q9 7531 7263 7376 7263
q10 3805 3978 3604 3604
q11 514 430 419 419
q12 484 602 437 437
q13 2695 3177 2270 2270
q14 276 368 394 368
q15 930 792 808 792
q16 713 768 721 721
q17 1144 1376 1376 1376
q18 7033 6699 6621 6621
q19 841 877 899 877
q20 2065 2155 2209 2155
q21 3942 3490 3415 3415
q22 461 421 397 397
Total cold run time: 50521 ms
Total hot run time: 48401 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4116595167
<details>
<summary>TPC-DS: <b>Total hot run time: 168931 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpcds-tools
TPC-DS sf100 test result on commit 39f6944b96ba91bfbd1de459f5f3ae5d58d2b39f, data reload: false
query5 4332 631 511 511
query6 343 225 200 200
query7 4212 487 266 266
query8 345 249 234 234
query9 8813 2735 2696 2696
query10 532 412 363 363
query11 6986 5109 4887 4887
query12 192 129 129 129
query13 1286 443 347 347
query14 5785 3772 3433 3433
query14_1 2859 2832 2822 2822
query15 210 192 177 177
query16 1022 478 457 457
query17 1123 736 635 635
query18 2454 465 366 366
query19 223 222 195 195
query20 137 160 127 127
query21 214 136 111 111
query22 13415 14140 14620 14140
query23 16956 16448 15975 15975
query23_1 15812 15662 15945 15662
query24 7214 1597 1215 1215
query24_1 1214 1212 1228 1212
query25 549 470 412 412
query26 1233 261 148 148
query27 2791 481 306 306
query28 4467 1856 1833 1833
query29 849 561 473 473
query30 336 233 192 192
query31 1032 946 877 877
query32 85 73 70 70
query33 501 329 284 284
query34 898 878 533 533
query35 669 695 604 604
query36 1081 1176 948 948
query37 140 95 81 81
query38 2931 2918 2928 2918
query39 879 848 817 817
query39_1 792 802 795 795
query40 239 154 137 137
query41 62 59 58 58
query42 268 253 258 253
query43 236 254 220 220
query44
query45 202 185 184 184
query46 877 998 596 596
query47 2123 2122 2071 2071
query48 317 309 229 229
query49 626 463 374 374
query50 693 279 216 216
query51 4132 4108 4072 4072
query52 266 272 255 255
query53 293 361 294 294
query54 304 279 289 279
query55 92 92 81 81
query56 317 310 337 310
query57 1939 1762 1739 1739
query58 284 275 278 275
query59 2877 2957 2789 2789
query60 336 340 322 322
query61 176 152 156 152
query62 626 592 538 538
query63 308 283 288 283
query64 4776 957 660 660
query65
query66 1460 466 350 350
query67 24385 24443 24257 24257
query68
query69 412 309 290 290
query70 958 936 979 936
query71 351 307 306 306
query72 2822 2702 2414 2414
query73 538 540 323 323
query74 9649 9544 9413 9413
query75 2910 2790 2494 2494
query76 2277 1061 704 704
query77 376 384 318 318
query78 10935 11051 10500 10500
query79 1126 798 589 589
query80 746 679 584 584
query81 479 264 223 223
query82 1366 157 121 121
query83 378 268 255 255
query84 253 127 104 104
query85 895 502 450 450
query86 366 305 284 284
query87 3142 3139 3019 3019
query88 3544 2670 2648 2648
query89 435 375 347 347
query90 1943 176 172 172
query91 177 170 140 140
query92 79 78 66 66
query93 909 818 505 505
query94 454 317 296 296
query95 607 399 340 340
query96 651 524 224 224
query97 2490 2498 2385 2385
query98 240 227 219 219
query99 1022 996 932 932
Total cold run time: 249820 ms
Total hot run time: 168931 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4123131906
<details>
<summary>TPC-DS: <b>Total hot run time: 168817 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpcds-tools
TPC-DS sf100 test result on commit 98824a06516d3dd396c5fbd6cbba50448c6baa8d, data reload: false
query5 4329 637 509 509
query6 345 243 219 219
query7 4206 481 272 272
query8 369 257 235 235
query9 8767 2745 2715 2715
query10 512 409 354 354
query11 6918 5106 4896 4896
query12 191 132 134 132
query13 1297 443 351 351
query14 5773 3706 3460 3460
query14_1 2874 2834 2817 2817
query15 198 193 177 177
query16 1018 467 465 465
query17 1112 766 636 636
query18 2482 450 363 363
query19 214 222 190 190
query20 138 128 130 128
query21 218 134 116 116
query22 13171 14131 14701 14131
query23 16776 16567 15965 15965
query23_1 15885 15694 15700 15694
query24 7214 1605 1225 1225
query24_1 1291 1251 1244 1244
query25 537 464 415 415
query26 1235 268 145 145
query27 2744 474 297 297
query28 4428 1832 1827 1827
query29 837 571 478 478
query30 297 221 189 189
query31 1019 939 868 868
query32 90 74 72 72
query33 522 357 285 285
query34 886 860 536 536
query35 639 694 594 594
query36 1077 1127 1015 1015
query37 133 111 85 85
query38 2943 2902 2849 2849
query39 861 860 800 800
query39_1 802 789 807 789
query40 233 155 141 141
query41 63 59 58 58
query42 262 261 255 255
query43 234 242 230 230
query44
query45 198 189 182 182
query46 873 975 597 597
query47 2116 2126 2101 2101
query48 308 324 223 223
query49 634 472 386 386
query50 688 286 208 208
query51 4089 4159 4045 4045
query52 258 277 261 261
query53 292 331 291 291
query54 312 276 263 263
query55 97 89 84 84
query56 330 319 321 319
query57 1936 1717 1698 1698
query58 285 276 287 276
query59 2818 2943 2724 2724
query60 348 344 331 331
query61 159 154 158 154
query62 622 590 546 546
query63 306 279 293 279
query64 4719 992 690 690
query65
query66 1468 451 368 368
query67 24277 24290 24174 24174
query68
query69 414 339 291 291
query70 962 959 932 932
query71 351 315 297 297
query72 3030 2725 2482 2482
query73 543 543 312 312
query74 9600 9557 9418 9418
query75 2863 2773 2441 2441
query76 2284 1061 667 667
query77 358 378 319 319
query78 11025 11150 10492 10492
query79 1111 772 594 594
query80 1028 653 555 555
query81 542 258 222 222
query82 1292 152 119 119
query83 344 260 245 245
query84 255 122 104 104
query85 983 503 457 457
query86 445 310 328 310
query87 3080 3114 3026 3026
query88 3489 2621 2613 2613
query89 427 368 362 362
query90 1839 176 172 172
query91 184 172 140 140
query92 81 73 70 70
query93 903 835 497 497
query94 495 317 286 286
query95 610 356 390 356
query96 648 524 224 224
query97 2474 2509 2422 2422
query98 234 225 222 222
query99 1043 1010 899 899
Total cold run time: 249823 ms
Total hot run time: 168817 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "morrySnow (via GitHub)" <gi...@apache.org>.
morrySnow commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4132263710
## Concrete Fix Suggestions for GraphSimplifier Issues
### Fix #1: `constructEdge()` β use `getOtherJoinConjuncts()` for `otherConditions`
```java
// Before (line ~533):
List<Expression> otherConditions = connectionEdges.stream()
.mapToObj(i -> graph.getJoinEdge(i).getJoin().getHashJoinConjuncts()) // BUG
.flatMap(Collection::stream)
.collect(Collectors.toList());
// After:
List<Expression> otherConditions = connectionEdges.stream()
.mapToObj(i -> graph.getJoinEdge(i).getJoin().getOtherJoinConjuncts()) // FIX
.flatMap(Collection::stream)
.collect(Collectors.toList());
```
---
### Fix #2: `updatePQ()` β always re-heapify when benefit changes
The old `hypergraph/GraphSimplifier.java:330` does `remove()+add()` when the element is already queued. The new v2 skips this. Fix:
```java
// Before:
private void updatePQ(int edgeIdx) {
BestSimplification cacheNode = simplifications.get(edgeIdx);
Preconditions.checkState(!Double.isNaN(cacheNode.bestStep.benefit));
if (!cacheNode.isInPriorityQueue) {
if (cacheNode.bestNeighbor != -1) {
priorityQueue.add(cacheNode);
cacheNode.isInPriorityQueue = true;
}
} else {
if (cacheNode.bestNeighbor == -1) {
priorityQueue.remove(cacheNode);
cacheNode.isInPriorityQueue = false;
}
}
}
// After:
private void updatePQ(int edgeIdx) {
BestSimplification cacheNode = simplifications.get(edgeIdx);
Preconditions.checkState(!Double.isNaN(cacheNode.bestStep.benefit));
if (!cacheNode.isInPriorityQueue) {
if (cacheNode.bestNeighbor != -1) {
priorityQueue.add(cacheNode);
cacheNode.isInPriorityQueue = true;
}
} else {
// Always remove first, then re-add if still valid β ensures heap order
priorityQueue.remove(cacheNode);
if (cacheNode.bestNeighbor == -1) {
cacheNode.isInPriorityQueue = false;
} else {
priorityQueue.add(cacheNode);
}
}
}
```
---
### Fix #3: `threeRightJoin()` β use `edge2` for inner-join cost
```java
// Before (line ~629):
calCost(edge1, bitmap2, bitmap3);
// After:
calCost(edge2, bitmap2, bitmap3);
```
Rationale: `threeRightJoin` computes `bitmap1 βedge1 (bitmap2 βedge2 bitmap3)`. The inner sub-join `(bitmap2 β bitmap3)` uses `edge2`, so cost should use `edge2` as well. `threeLeftJoin` is already correct and consistent.
---
### Fix #8/#9: `calCost()` β operator precedence + null safety
```java
// Before (lines ~580-584):
if (JoinUtils.shouldNestedLoopJoin(join)) {
cost = cacheCost.get(leftBitmap) + cacheCost.get(rightBitmap)
+ rightStats.getRowCount() + 1 / leftStats.getRowCount();
} else {
cost = cacheCost.get(leftBitmap) + cacheCost.get(rightBitmap)
+ (rightStats.getRowCount() + 1 / leftStats.getRowCount()) * 1.2;
}
// After β fix precedence, guard against zero/null:
double leftRows = leftStats != null ? Math.max(1.0, leftStats.getRowCount()) : 1.0;
double rightRows = rightStats != null ? Math.max(1.0, rightStats.getRowCount()) : 1.0;
double leftCost = cacheCost.getOrDefault(leftBitmap, leftRows);
double rightCost = cacheCost.getOrDefault(rightBitmap, rightRows);
if (JoinUtils.shouldNestedLoopJoin(join)) {
cost = leftCost + rightCost + rightRows + leftRows; // or intended formula
} else {
cost = leftCost + rightCost + (rightRows + leftRows) * 1.2;
}
```
Note: The original `1 / leftStats.getRowCount()` is likely an operator-precedence bug β Java evaluates it as `1.0 / rows` (reciprocal), not `(rightRows + 1) / leftRows`. Please clarify the intended cost formula. Using `getOrDefault` prevents NPE from auto-unboxing null `Double`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4133992523
<details>
<summary>TPC-DS: <b>Total hot run time: 167845 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpcds-tools
TPC-DS sf100 test result on commit 4c3213072c9207313f847ed1f00358df682f23f5, data reload: false
query5 4341 623 508 508
query6 337 228 202 202
query7 4219 471 261 261
query8 343 241 230 230
query9 8742 2723 2709 2709
query10 504 400 365 365
query11 6923 5115 4870 4870
query12 180 139 125 125
query13 1279 450 341 341
query14 5765 3657 3440 3440
query14_1 2853 2808 2836 2808
query15 201 193 179 179
query16 999 486 428 428
query17 1119 723 618 618
query18 2463 456 352 352
query19 223 212 187 187
query20 131 125 125 125
query21 221 140 115 115
query22 13237 13961 14685 13961
query23 16939 16258 15912 15912
query23_1 16081 15613 15784 15613
query24 7170 1583 1194 1194
query24_1 1230 1224 1205 1205
query25 545 449 398 398
query26 1243 270 143 143
query27 2769 485 288 288
query28 4444 1859 1833 1833
query29 860 561 477 477
query30 297 228 193 193
query31 1006 947 917 917
query32 86 80 74 74
query33 518 331 288 288
query34 883 875 520 520
query35 627 680 601 601
query36 1063 1114 1005 1005
query37 141 95 86 86
query38 2919 2922 2833 2833
query39 861 823 814 814
query39_1 781 799 785 785
query40 233 149 133 133
query41 64 58 57 57
query42 252 256 255 255
query43 247 247 222 222
query44
query45 205 190 181 181
query46 887 989 589 589
query47 2147 2141 2034 2034
query48 305 318 221 221
query49 637 461 388 388
query50 698 267 207 207
query51 4087 4046 4021 4021
query52 261 264 256 256
query53 292 335 278 278
query54 311 274 266 266
query55 92 87 82 82
query56 312 315 305 305
query57 1957 1819 1644 1644
query58 288 271 270 270
query59 2820 2961 2762 2762
query60 336 341 325 325
query61 156 152 155 152
query62 659 594 524 524
query63 310 272 274 272
query64 4814 977 692 692
query65
query66 1454 485 355 355
query67 24328 24295 24253 24253
query68
query69 410 314 282 282
query70 965 875 966 875
query71 337 332 305 305
query72 2810 2636 2407 2407
query73 536 536 325 325
query74 9602 9589 9399 9399
query75 2860 2760 2488 2488
query76 2293 1028 679 679
query77 361 382 313 313
query78 10950 11151 10453 10453
query79 1087 759 577 577
query80 694 644 525 525
query81 504 262 224 224
query82 1377 161 123 123
query83 382 269 248 248
query84 253 121 99 99
query85 870 502 452 452
query86 378 312 288 288
query87 3168 3126 2986 2986
query88 3546 2629 2612 2612
query89 425 380 336 336
query90 1968 179 174 174
query91 176 167 134 134
query92 84 75 73 73
query93 936 845 501 501
query94 455 321 284 284
query95 608 349 400 349
query96 646 522 224 224
query97 2450 2495 2396 2396
query98 227 217 232 217
query99 1001 997 927 927
Total cold run time: 249355 ms
Total hot run time: 167845 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4023086723
<details>
<summary>TPC-DS: <b>Total hot run time: 151599 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpcds-tools
TPC-DS sf100 test result on commit 2bbaea10353cdb35e4f172620c799950350f246c, data reload: false
query5 4333 647 520 520
query6 323 249 233 233
query7 4204 466 274 274
query8 344 238 224 224
query9 8717 2721 2731 2721
query10 560 478 431 431
query11 7215 5633 5447 5447
query12 189 131 132 131
query13 1273 472 350 350
query14 6071 3779 3550 3550
query14_1 2703 2701 2706 2701
query15 208 195 180 180
query16 995 467 354 354
query17 1069 698 585 585
query18 2562 438 342 342
query19 210 203 184 184
query20 144 135 131 131
query21 230 150 127 127
query22 4823 4988 4895 4895
query23 16075 15688 15503 15503
query23_1 15572 16173 16072 16072
query24 8024 1008 590 590
query24_1 623 593 642 593
query25 581 480 418 418
query26 1311 275 160 160
query27 3342 499 324 324
query28 4661 1999 1941 1941
query29 789 517 430 430
query30 253 202 170 170
query31 1404 1328 1220 1220
query32 79 72 74 72
query33 502 340 297 297
query34 914 917 570 570
query35 634 664 590 590
query36 1101 1125 994 994
query37 140 92 87 87
query38 2953 2916 2930 2916
query39 888 872 841 841
query39_1 831 837 819 819
query40 232 195 132 132
query41 67 59 61 59
query42 309 296 306 296
query43 233 254 219 219
query44
query45 201 191 194 191
query46 931 1012 626 626
query47 2113 2138 2116 2116
query48 320 316 222 222
query49 634 472 408 408
query50 697 272 210 210
query51 4148 4067 4066 4066
query52 287 292 277 277
query53 295 330 274 274
query54 281 256 257 256
query55 92 86 77 77
query56 307 298 292 292
query57 1362 1341 1313 1313
query58 279 275 268 268
query59 1321 1419 1339 1339
query60 337 321 308 308
query61 130 127 132 127
query62 602 586 542 542
query63 314 275 270 270
query64 4734 944 658 658
query65
query66 1429 449 357 357
query67 16470 16377 16313 16313
query68
query69 388 315 277 277
query70 1041 952 865 865
query71 344 327 305 305
query72 14773 14045 14194 14045
query73 494 576 334 334
query74 9911 9869 9777 9777
query75 2798 2785 2450 2450
query76 2296 1077 650 650
query77 363 384 309 309
query78
query79 967 1064 590 590
query80 611 610 516 516
query81 480 285 240 240
query82 214 143 116 116
query83 190 188 171 171
query84 250 111 101 101
query85 779 435 369 369
query86 315 325 300 300
query87 3075 3119 3024 3024
query88 3526 2651 2638 2638
query89 394 380 351 351
query90 1998 174 175 174
query91 158 149 124 124
query92 79 74 71 71
query93 877 889 511 511
query94 406 304 268 268
query95 518 312 299 299
query96 630 527 227 227
query97 2453 2524 2420 2420
query98 235 223 216 216
query99 1002 993 919 919
Total cold run time: 230556 ms
Total hot run time: 151599 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4023933683
<details>
<summary>TPC-DS: <b>Total hot run time: 152511 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpcds-tools
TPC-DS sf100 test result on commit 4169a8c8a747c8e888a3c93cbad5edf7acd0baae, data reload: false
query5 4316 634 504 504
query6 324 231 209 209
query7 4213 466 267 267
query8 363 253 240 240
query9 8779 2755 2719 2719
query10 522 383 340 340
query11 7336 5928 5573 5573
query12 187 130 122 122
query13 1268 472 369 369
query14 5749 3851 3593 3593
query14_1 2810 2795 2825 2795
query15 210 195 175 175
query16 1000 476 453 453
query17 1104 731 634 634
query18 2450 454 352 352
query19 221 209 180 180
query20 140 136 129 129
query21 233 140 123 123
query22 4878 5060 4888 4888
query23 16783 16014 15721 15721
query23_1 15714 15778 15713 15713
query24 8499 1694 1270 1270
query24_1 1313 1251 1377 1251
query25 573 530 455 455
query26 1015 282 182 182
query27 2816 498 309 309
query28 4428 1851 1847 1847
query29 843 563 462 462
query30 316 247 214 214
query31 1344 1296 1211 1211
query32 88 69 72 69
query33 508 323 267 267
query34 922 924 551 551
query35 648 666 615 615
query36 1095 1164 1010 1010
query37 134 92 86 86
query38 2972 2971 2835 2835
query39 942 878 854 854
query39_1 845 875 814 814
query40 228 149 137 137
query41 64 59 58 58
query42 308 298 292 292
query43 248 240 218 218
query44
query45 204 187 181 181
query46 895 977 622 622
query47 2121 2136 2062 2062
query48 306 327 232 232
query49 617 456 383 383
query50 676 279 210 210
query51 4143 4066 4016 4016
query52 288 295 284 284
query53 288 345 290 290
query54 291 266 271 266
query55 89 86 84 84
query56 326 319 312 312
query57 1363 1322 1297 1297
query58 284 275 275 275
query59 1320 1408 1318 1318
query60 336 343 314 314
query61 148 144 143 143
query62 618 572 540 540
query63 309 273 269 269
query64 4432 983 657 657
query65
query66 1435 497 358 358
query67 16351 16665 16321 16321
query68
query69 393 318 286 286
query70 984 975 968 968
query71 332 308 302 302
query72 2855 2696 2484 2484
query73 535 543 318 318
query74 10021 9881 9769 9769
query75 2843 2749 2480 2480
query76 2294 1038 672 672
query77 357 365 313 313
query78 11072 11246 10615 10615
query79 3260 778 584 584
query80 1722 624 547 547
query81 592 281 249 249
query82 989 148 116 116
query83 328 271 234 234
query84 256 111 94 94
query85 896 480 425 425
query86 502 301 290 290
query87 3140 3138 2987 2987
query88 4553 2643 2606 2606
query89 419 371 350 350
query90 2079 165 164 164
query91 166 164 132 132
query92 85 71 75 71
query93 2763 819 490 490
query94 660 285 291 285
query95 612 396 309 309
query96 629 515 225 225
query97 2468 2490 2400 2400
query98 259 221 216 216
query99 1029 1019 904 904
Total cold run time: 239702 ms
Total hot run time: 152511 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "hello-stephen (via GitHub)" <gi...@apache.org>.
hello-stephen commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4024074890
# FE UT Coverage Report
Increment line coverage ` 85.14% (1335/1568)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/61146_4169a8c8a747c8e888a3c93cbad5edf7acd0baae/fe_increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/61146_4169a8c8a747c8e888a3c93cbad5edf7acd0baae/fe_report/index.html)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4181316904
<details>
<summary>TPC-DS: <b>Total hot run time: 179478 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpcds-tools
TPC-DS sf100 test result on commit 7086d3bb0b0e5412c4bedfa4391c31029de24d8f, data reload: false
query5 4322 667 498 498
query6 352 225 209 209
query7 4235 576 355 355
query8 343 253 222 222
query9 8751 3921 3931 3921
query10 479 378 345 345
query11 6651 5487 5154 5154
query12 199 146 128 128
query13 1295 630 431 431
query14 5687 5177 4826 4826
query14_1 4185 4109 4135 4109
query15 211 204 184 184
query16 1033 463 459 459
query17 1162 814 645 645
query18 2557 520 379 379
query19 251 234 193 193
query20 140 133 132 132
query21 227 151 118 118
query22 14026 14858 14558 14558
query23 18389 16919 16830 16830
query23_1 17026 16707 16650 16650
query24 7558 1727 1353 1353
query24_1 1376 1348 1368 1348
query25 626 492 426 426
query26 1253 327 179 179
query27 2672 627 378 378
query28 4414 1940 1885 1885
query29 951 700 561 561
query30 293 233 193 193
query31 1094 1038 929 929
query32 86 70 72 70
query33 557 348 282 282
query34 1204 1172 656 656
query35 760 779 670 670
query36 1216 1229 1038 1038
query37 151 94 85 85
query38 3104 3037 2955 2955
query39 914 888 852 852
query39_1 849 837 835 835
query40 238 162 140 140
query41 61 58 100 58
query42 283 270 272 270
query43 321 320 275 275
query44
query45 201 197 184 184
query46 1155 1253 830 830
query47 2310 2316 2208 2208
query48 402 414 296 296
query49 640 524 426 426
query50 701 278 219 219
query51 4372 4215 4143 4143
query52 282 284 265 265
query53 327 344 268 268
query54 337 296 270 270
query55 101 99 93 93
query56 325 322 322 322
query57 1678 1737 1630 1630
query58 304 270 268 268
query59 2914 2964 2732 2732
query60 325 331 314 314
query61 160 151 152 151
query62 685 629 574 574
query63 313 268 283 268
query64 4891 940 706 706
query65
query66 1456 476 366 366
query67 24354 24255 24124 24124
query68
query69 460 348 311 311
query70 1031 980 1022 980
query71 359 328 314 314
query72 2944 2680 2391 2391
query73 832 780 475 475
query74 9902 9780 9574 9574
query75 3552 3362 2994 2994
query76 2350 1116 728 728
query77 385 400 332 332
query78 11299 11451 10831 10831
query79 1542 1075 815 815
query80 850 744 642 642
query81 479 276 232 232
query82 1384 159 120 120
query83 407 290 269 269
query84 267 147 119 119
query85 882 504 454 454
query86 401 321 294 294
query87 3291 3160 3153 3153
query88 3606 2705 2706 2705
query89 475 419 378 378
query90 2001 178 173 173
query91 180 172 143 143
query92 80 77 73 73
query93 899 895 519 519
query94 534 347 285 285
query95 652 374 346 346
query96 1017 808 326 326
query97 2694 2678 2562 2562
query98 238 228 243 228
query99 1078 1076 964 964
Total cold run time: 259008 ms
Total hot run time: 179478 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4181290129
<details>
<summary>TPC-H: <b>Total hot run time: 29292 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpch-tools
Tpch sf100 test result on commit 7086d3bb0b0e5412c4bedfa4391c31029de24d8f, data reload: false
------ Round 1 ----------------------------------
orders Doris NULL NULL 0 0 0 NULL 0 NULL NULL 2023-12-26 18:27:23 2023-12-26 18:42:55 NULL utf-8 NULL NULL
============================================
q1 17660 3694 3673 3673
q2 q3 10677 855 606 606
q4 4679 463 369 369
q5 7457 1325 1148 1148
q6 198 165 140 140
q7 903 959 745 745
q8 9307 1373 1370 1370
q9 5444 5308 5301 5301
q10 6257 2014 1779 1779
q11 480 274 270 270
q12 885 692 503 503
q13 18013 2788 2166 2166
q14 282 284 259 259
q15 q16 857 835 782 782
q17 1041 1060 696 696
q18 6454 5677 5555 5555
q19 1157 1296 1107 1107
q20 628 540 409 409
q21 4926 2519 2055 2055
q22 490 418 359 359
Total cold run time: 97795 ms
Total hot run time: 29292 ms
----- Round 2, with runtime_filter_mode=off -----
orders Doris NULL NULL 150000000 42 6422171781 NULL 22778155 NULL NULL 2023-12-26 18:27:23 2023-12-26 18:42:55 NULL utf-8 NULL NULL
============================================
q1 4513 4498 4667 4498
q2 q3 4689 4786 4202 4202
q4 2124 2094 1359 1359
q5 4897 5031 5136 5031
q6 205 165 134 134
q7 2036 1781 1639 1639
q8 3415 2978 3033 2978
q9 8201 8196 8586 8196
q10 4488 4442 4238 4238
q11 608 400 398 398
q12 657 688 493 493
q13 2700 3043 2331 2331
q14 298 299 280 280
q15 q16 755 772 747 747
q17 1386 1275 1195 1195
q18 8209 7093 7059 7059
q19 1145 1167 1103 1103
q20 2190 2185 1932 1932
q21 5937 5256 4776 4776
q22 537 492 427 427
Total cold run time: 58990 ms
Total hot run time: 53016 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4037937345
<details>
<summary>TPC-DS: <b>Total hot run time: 152906 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpcds-tools
TPC-DS sf100 test result on commit 48bc77792381e05a7eece5abe21cbd000382ddb8, data reload: false
query5 4326 644 525 525
query6 342 232 219 219
query7 4206 494 276 276
query8 348 259 241 241
query9 8771 2785 2758 2758
query10 531 380 341 341
query11 7378 5953 5660 5660
query12 184 131 128 128
query13 1264 475 361 361
query14 5957 3945 3644 3644
query14_1 2885 2923 2887 2887
query15 215 189 177 177
query16 992 479 452 452
query17 1133 730 617 617
query18 2482 451 345 345
query19 221 210 187 187
query20 140 132 128 128
query21 228 161 126 126
query22 4984 4890 4836 4836
query23 15935 15500 15291 15291
query23_1 15416 16131 15839 15839
query24 7408 1726 1334 1334
query24_1 1322 1291 1321 1291
query25 623 534 486 486
query26 1425 277 167 167
query27 2911 510 301 301
query28 4992 2078 1915 1915
query29 912 594 497 497
query30 314 251 209 209
query31 1364 1296 1218 1218
query32 86 69 70 69
query33 515 331 267 267
query34 979 923 571 571
query35 641 678 589 589
query36 1097 1110 965 965
query37 133 95 80 80
query38 2963 2942 2942 2942
query39 898 890 855 855
query39_1 873 953 831 831
query40 228 153 137 137
query41 66 60 59 59
query42 311 302 291 291
query43 249 258 233 233
query44
query45 202 187 193 187
query46 887 1007 604 604
query47 2100 2092 1998 1998
query48 303 328 233 233
query49 632 465 404 404
query50 692 290 216 216
query51 4051 4100 4020 4020
query52 296 300 285 285
query53 286 334 288 288
query54 300 274 267 267
query55 95 95 88 88
query56 322 317 306 306
query57 1344 1306 1268 1268
query58 292 283 279 279
query59 1372 1469 1319 1319
query60 342 328 318 318
query61 149 151 141 141
query62 605 587 540 540
query63 316 280 285 280
query64 4760 932 665 665
query65
query66 1455 453 352 352
query67 16329 16545 16423 16423
query68
query69 400 325 282 282
query70 1005 978 909 909
query71 352 331 310 310
query72 2821 2654 2384 2384
query73 548 555 322 322
query74 10013 9907 9786 9786
query75 2853 2782 2490 2490
query76 2304 1055 696 696
query77 361 404 300 300
query78 11169 11410 10650 10650
query79 1137 799 609 609
query80 1556 623 540 540
query81 575 276 243 243
query82 1226 152 114 114
query83 341 269 240 240
query84 247 111 100 100
query85 1202 489 459 459
query86 419 318 298 298
query87 3246 3117 3097 3097
query88 3525 2657 2644 2644
query89 441 376 342 342
query90 1893 177 174 174
query91 176 187 132 132
query92 77 78 72 72
query93 940 882 503 503
query94 636 316 263 263
query95 577 404 321 321
query96 627 538 234 234
query97 2493 2481 2411 2411
query98 238 237 223 223
query99 1024 1000 905 905
Total cold run time: 234672 ms
Total hot run time: 152906 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4122764031
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4053854414
<details>
<summary>TPC-H: <b>Total hot run time: 26927 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpch-tools
Tpch sf100 test result on commit d96ce294f381610ac73afdfed1f199cca996e633, data reload: false
------ Round 1 ----------------------------------
orders Doris NULL NULL 0 0 0 NULL 0 NULL NULL 2023-12-26 18:27:23 2023-12-26 18:42:55 NULL utf-8 NULL NULL
============================================
q1 17624 4424 4286 4286
q2 q3 10639 775 509 509
q4 4680 370 258 258
q5 7564 1200 1031 1031
q6 177 178 150 150
q7 772 844 675 675
q8 9290 1490 1337 1337
q9 4910 4792 4709 4709
q10 6255 1923 1646 1646
q11 449 270 249 249
q12 724 572 471 471
q13 18062 2925 2169 2169
q14 234 240 225 225
q15 q16 750 722 658 658
q17 731 819 493 493
q18 6094 5389 5343 5343
q19 1162 992 607 607
q20 546 499 390 390
q21 4408 1816 1407 1407
q22 496 421 314 314
Total cold run time: 95567 ms
Total hot run time: 26927 ms
----- Round 2, with runtime_filter_mode=off -----
orders Doris NULL NULL 150000000 42 6422171781 NULL 22778155 NULL NULL 2023-12-26 18:27:23 2023-12-26 18:42:55 NULL utf-8 NULL NULL
============================================
q1 4855 4544 4588 4544
q2 q3 3892 4317 3815 3815
q4 880 1238 801 801
q5 4066 4400 4369 4369
q6 190 184 145 145
q7 1772 1666 1531 1531
q8 2494 2757 2562 2562
q9 7869 7420 7485 7420
q10 3847 4041 3611 3611
q11 518 454 412 412
q12 477 602 449 449
q13 2687 3087 2325 2325
q14 275 286 269 269
q15 q16 707 776 755 755
q17 1186 1356 1356 1356
q18 7189 6659 6579 6579
q19 900 909 904 904
q20 2089 2237 2006 2006
q21 4080 3710 3339 3339
q22 453 443 388 388
Total cold run time: 50426 ms
Total hot run time: 47580 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4023029543
<details>
<summary>TPC-H: <b>Total hot run time: 28409 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpch-tools
Tpch sf100 test result on commit 2bbaea10353cdb35e4f172620c799950350f246c, data reload: false
------ Round 1 ----------------------------------
============================================
q1 17628 4537 4297 4297
q2 q3 10651 809 546 546
q4 4677 362 253 253
q5 7543 1210 1026 1026
q6 171 174 143 143
q7 1344 1385 1196 1196
q8 9285 1454 1353 1353
q9 4869 4780 4661 4661
q10 6743 1373 1103 1103
q11 457 259 242 242
q12 705 566 469 469
q13 18046 2944 2210 2210
q14 233 230 212 212
q15 837 773 772 772
q16 723 717 672 672
q17 698 847 432 432
q18 5864 5425 5341 5341
q19 1261 967 603 603
q20 558 495 396 396
q21 4709 2199 2275 2199
q22 389 319 283 283
Total cold run time: 97391 ms
Total hot run time: 28409 ms
----- Round 2, with runtime_filter_mode=off -----
============================================
q1 4846 4557 4548 4548
q2 q3 3884 4387 3785 3785
q4 904 1216 781 781
q5 4035 4391 4329 4329
q6 182 180 136 136
q7 2241 2062 1926 1926
q8 2623 2715 2566 2566
q9 7433 7426 7537 7426
q10 3325 3468 3088 3088
q11 523 428 423 423
q12 482 615 510 510
q13 2860 3086 2338 2338
q14 283 285 276 276
q15 845 835 825 825
q16 731 752 706 706
q17 1170 1534 1358 1358
q18 7292 6803 6583 6583
q19 872 818 908 818
q20 2151 2163 2003 2003
q21 4152 3686 3455 3455
q22 446 430 382 382
Total cold run time: 51280 ms
Total hot run time: 48262 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4133917008
<details>
<summary>TPC-H: <b>Total hot run time: 26494 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpch-tools
Tpch sf100 test result on commit 4c3213072c9207313f847ed1f00358df682f23f5, data reload: false
------ Round 1 ----------------------------------
orders Doris NULL NULL 0 0 0 NULL 0 NULL NULL 2023-12-26 18:27:23 2023-12-26 18:42:55 NULL utf-8 NULL NULL
============================================
q1 17578 4466 4311 4311
q2 q3 10656 782 525 525
q4 4680 356 266 266
q5 7573 1233 1018 1018
q6 178 172 147 147
q7 790 845 662 662
q8 9293 1483 1355 1355
q9 4641 4967 4683 4683
q10 6253 1912 1664 1664
q11 459 267 258 258
q12 714 601 462 462
q13 18019 2690 1934 1934
q14 228 230 215 215
q15 q16 716 726 662 662
q17 714 831 438 438
q18 5986 5351 5260 5260
q19 1134 973 603 603
q20 543 507 380 380
q21 4366 1838 1397 1397
q22 341 309 254 254
Total cold run time: 94862 ms
Total hot run time: 26494 ms
----- Round 2, with runtime_filter_mode=off -----
orders Doris NULL NULL 150000000 42 6422171781 NULL 22778155 NULL NULL 2023-12-26 18:27:23 2023-12-26 18:42:55 NULL utf-8 NULL NULL
============================================
q1 4982 4765 4572 4572
q2 q3 3916 4311 3863 3863
q4 881 1208 793 793
q5 4068 4374 4337 4337
q6 198 173 144 144
q7 1748 1665 1546 1546
q8 2463 2738 2569 2569
q9 7634 7342 7579 7342
q10 3797 3956 3676 3676
q11 518 424 416 416
q12 488 591 448 448
q13 2414 2936 2018 2018
q14 280 295 305 295
q15 q16 767 779 735 735
q17 1145 1338 1334 1334
q18 7038 6738 6633 6633
q19 910 900 924 900
q20 2123 2190 2039 2039
q21 3945 3471 3502 3471
q22 502 432 385 385
Total cold run time: 49817 ms
Total hot run time: 47516 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4123027711
<details>
<summary>TPC-H: <b>Total hot run time: 26763 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpch-tools
Tpch sf100 test result on commit 98824a06516d3dd396c5fbd6cbba50448c6baa8d, data reload: false
------ Round 1 ----------------------------------
orders Doris NULL NULL 0 0 0 NULL 0 NULL NULL 2023-12-26 18:27:23 2023-12-26 18:42:55 NULL utf-8 NULL NULL
============================================
q1 17607 4617 4311 4311
q2 q3 10651 794 516 516
q4 4678 353 250 250
q5 7562 1212 1012 1012
q6 171 175 145 145
q7 796 880 694 694
q8 9310 1558 1324 1324
q9 4989 4757 4769 4757
q10 6302 1954 1682 1682
q11 464 263 248 248
q12 724 586 463 463
q13 18027 2763 1937 1937
q14 226 238 217 217
q15 q16 750 739 666 666
q17 733 834 463 463
q18 6157 5538 5310 5310
q19 1258 1009 605 605
q20 542 508 370 370
q21 4538 1842 1516 1516
q22 471 363 277 277
Total cold run time: 95956 ms
Total hot run time: 26763 ms
----- Round 2, with runtime_filter_mode=off -----
orders Doris NULL NULL 150000000 42 6422171781 NULL 22778155 NULL NULL 2023-12-26 18:27:23 2023-12-26 18:42:55 NULL utf-8 NULL NULL
============================================
q1 4802 5080 4659 4659
q2 q3 3931 4370 3826 3826
q4 868 1208 797 797
q5 4105 4483 4351 4351
q6 196 192 142 142
q7 1783 1666 1523 1523
q8 2505 2725 2598 2598
q9 7717 7570 7440 7440
q10 3804 4008 3593 3593
q11 511 436 448 436
q12 504 615 451 451
q13 2527 2876 2049 2049
q14 278 321 286 286
q15 q16 742 770 706 706
q17 1179 1337 1332 1332
q18 7047 6850 6699 6699
q19 904 884 933 884
q20 2086 2245 2025 2025
q21 4164 3501 3326 3326
q22 460 430 382 382
Total cold run time: 50113 ms
Total hot run time: 47505 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4124245143
OpenCode automated review failed and did not complete.
Error: Review step was failure (possibly timeout or cancelled)
Workflow run: https://github.com/apache/doris/actions/runs/23527366973
Please inspect the workflow logs and rerun the review after the underlying issue is resolved.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4270050990
OpenCode automated review failed and did not complete.
Error: Review step was failure (possibly timeout or cancelled)
Workflow run: https://github.com/apache/doris/actions/runs/24573506998
Please inspect the workflow logs and rerun the review after the underlying issue is resolved.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "hello-stephen (via GitHub)" <gi...@apache.org>.
hello-stephen commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4293468787
# FE UT Coverage Report
Increment line coverage ` 85.82% (1362/1587)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/61146_31779cc4e6272bd5610fc479f80978dbc0311307/fe_increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/61146_31779cc4e6272bd5610fc479f80978dbc0311307/fe_report/index.html)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4311727558
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "hello-stephen (via GitHub)" <gi...@apache.org>.
hello-stephen commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4272996210
# FE Regression Coverage Report
Increment line coverage ` 69.75% (1107/1587)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/61146_569a044e7b418241c7ed06bde37fd8629c3941fa_merge_fe/increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/61146_569a044e7b418241c7ed06bde37fd8629c3941fa_merge_fe/report/index.html)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "hello-stephen (via GitHub)" <gi...@apache.org>.
hello-stephen commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4038179331
# FE UT Coverage Report
Increment line coverage ` 85.47% (1371/1604)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/61146_48bc77792381e05a7eece5abe21cbd000382ddb8/fe_increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/61146_48bc77792381e05a7eece5abe21cbd000382ddb8/fe_report/index.html)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4066089955
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "hello-stephen (via GitHub)" <gi...@apache.org>.
hello-stephen commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4068433338
# FE UT Coverage Report
Increment line coverage ` 84.44% (1357/1607)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/61146_707151bd57c310c21b891070e8fa39bdfa8bed76/fe_increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/61146_707151bd57c310c21b891070e8fa39bdfa8bed76/fe_report/index.html)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "doris-robot (via GitHub)" <gi...@apache.org>.
doris-robot commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4066763467
<details>
<summary>TPC-H: <b>Total hot run time: 26865 ms</b></summary>
```
machine: 'aliyun_ecs.c7a.8xlarge_32C64G'
scripts: https://github.com/apache/doris/tree/master/tools/tpch-tools
Tpch sf100 test result on commit 707151bd57c310c21b891070e8fa39bdfa8bed76, data reload: false
------ Round 1 ----------------------------------
orders Doris NULL NULL 0 0 0 NULL 0 NULL NULL 2023-12-26 18:27:23 2023-12-26 18:42:55 NULL utf-8 NULL NULL
============================================
q1 17577 4449 4298 4298
q2 q3 10644 788 521 521
q4 4682 359 251 251
q5 7562 1217 1013 1013
q6 177 176 146 146
q7 815 839 692 692
q8 9294 1454 1358 1358
q9 4911 4814 4729 4729
q10 6271 1923 1649 1649
q11 454 253 259 253
q12 712 581 464 464
q13 18036 2930 2193 2193
q14 234 222 211 211
q15 q16 731 745 670 670
q17 706 851 432 432
q18 6092 5437 5192 5192
q19 1111 994 615 615
q20 555 495 376 376
q21 4415 1865 1504 1504
q22 378 483 298 298
Total cold run time: 95357 ms
Total hot run time: 26865 ms
----- Round 2, with runtime_filter_mode=off -----
orders Doris NULL NULL 150000000 42 6422171781 NULL 22778155 NULL NULL 2023-12-26 18:27:23 2023-12-26 18:42:55 NULL utf-8 NULL NULL
============================================
q1 4772 4634 4592 4592
q2 q3 3875 4358 3830 3830
q4 886 1218 773 773
q5 4075 4463 4350 4350
q6 194 180 152 152
q7 1758 1684 1559 1559
q8 2507 2734 2598 2598
q9 7814 7462 7489 7462
q10 3799 3933 3615 3615
q11 510 432 413 413
q12 484 608 452 452
q13 2796 3172 2297 2297
q14 285 317 297 297
q15 q16 756 773 754 754
q17 1171 1328 1357 1328
q18 7269 6750 6788 6750
q19 928 880 881 880
q20 2040 2170 2165 2165
q21 4103 3475 3343 3343
q22 474 459 379 379
Total cold run time: 50496 ms
Total hot run time: 47989 ms
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "hello-stephen (via GitHub)" <gi...@apache.org>.
hello-stephen commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4066607496
# FE UT Coverage Report
Increment line coverage ` 84.26% (1354/1607)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/61146_707151bd57c310c21b891070e8fa39bdfa8bed76/fe_increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/61146_707151bd57c310c21b891070e8fa39bdfa8bed76/fe_report/index.html)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4124030605
/review
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "morrySnow (via GitHub)" <gi...@apache.org>.
morrySnow commented on code in PR #61146:
URL: https://github.com/apache/doris/pull/61146#discussion_r2992993155
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/GraphSimplifier.java:
##########
@@ -0,0 +1,694 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.nereids.jobs.joinorder.hypergraphv2;
+
+import org.apache.doris.common.Pair;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.bitmap.LongBitmap;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.edge.Edge;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node.AbstractNode;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node.DPhyperNode;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.receiver.Counter;
+import org.apache.doris.nereids.stats.JoinEstimation;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.JoinUtils;
+import org.apache.doris.statistics.Statistics;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.Collection;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.List;
+import java.util.PriorityQueue;
+import java.util.stream.Collectors;
+import javax.annotation.Nullable;
+
+/**
+ * GraphSimplifier is used to simplify HyperGraph {@link HyperGraph}.
+ * <p>
+ * Related paper:
+ * - [Neu09] Neumann: βQuery Simplification: Graceful Degradation for Join-Order Optimizationβ.
+ * - [Rad19] Radke and Neumann: βLinDP++: Generalizing Linearized DP to Crossproducts and Non-Inner Joinsβ.
+ */
+public class GraphSimplifier {
+
+ private static int MAX_SIMPLIFICATION_STEPS = 1000000;
+ // It cached the plan stats in simplification. we don't store it in hyper graph,
+ // because it's just used for simulating join. In fact, the graph simplifier
+ // just generate the partial order of join operator.
+ private final HashMap<Long, Statistics> cacheStats = new HashMap<>();
+ private final HashMap<Long, Double> cacheCost = new HashMap<>();
+ private Deque<SimplificationStep> appliedSteps = new ArrayDeque<>();
+ private Deque<SimplificationStep> unAppliedSteps = new ArrayDeque<>();
+ private HyperGraph graph;
+ private CircleDetector cycles;
+ private List<BestSimplification> simplifications;
+ private PriorityQueue<BestSimplification> priorityQueue = new PriorityQueue<>();
+
+ /**
+ * Initializes the GraphSimplifier with the given hypergraph.
+ * Sets up join dependencies, simplifications, and caches.
+ *
+ * @param graph The hypergraph to simplify.
+ */
+ public GraphSimplifier(HyperGraph graph) {
+ this.graph = graph;
+ int edgeCount = graph.getJoinEdges().size();
+
+ // init join dependency
+ this.cycles = new CircleDetector(edgeCount);
+ extractJoinDependencies(cycles);
+
+ // init simplifications with empty values
+ this.simplifications = new ArrayList<>(edgeCount);
+ for (int i = 0; i < edgeCount; i++) {
+ simplifications.add(new BestSimplification());
+ }
+
+ // init cacheStats and cacheCost
+ for (AbstractNode node : graph.getNodes()) {
+ DPhyperNode dPhyperNode = (DPhyperNode) node;
+ cacheStats.put(node.getNodeMap(), dPhyperNode.getGroup().getStatistics());
+ cacheCost.put(node.getNodeMap(), dPhyperNode.getRowCount());
+ }
+
+ //
+ for (int edgeIdx = 0; edgeIdx < edgeCount; edgeIdx++) {
+ recalculateNeighbors(edgeIdx, edgeIdx + 1, edgeCount);
+ }
+ }
+
+ /**
+ * Checks if the hypergraph is joinable, ensuring all tables are connected via joins.
+ *
+ * @param graph The hypergraph to check.
+ * @param cycles The cycle detector for the graph.
+ * @return True if the graph is joinable, false otherwise.
+ */
+ private static boolean graphIsJoinable(HyperGraph graph, CircleDetector cycles) {
+ int nodeCount = graph.getNodes().size();
+ long[] components = new long[nodeCount];
+ int[] inComponent = new int[nodeCount];
+
+ for (int nodeIdx = 0; nodeIdx < nodeCount; nodeIdx++) {
+ components[nodeIdx] = LongBitmap.newBitmap(nodeIdx);
+ inComponent[nodeIdx] = nodeIdx;
+ }
+ return connectComponentsThroughJoins(graph, cycles, components, inComponent) == nodeCount;
+ }
+
+ /**
+ * Connects components in the hypergraph through join edges.
+ *
+ * @param graph The hypergraph to process.
+ * @param cycles The cycle detector for the graph.
+ * @param components Array representing connected components.
+ * @param inComponent Array mapping nodes to their components.
+ * @return The number of connected components.
+ */
+ private static int connectComponentsThroughJoins(
+ HyperGraph graph,
+ CircleDetector cycles,
+ long[] components,
+ int[] inComponent) {
+ int nodeCount = graph.getNodes().size();
+ int numInComponent = 1;
+ boolean didAnything;
+ int usedEdges = 0;
+ int edgeCount = cycles.getOrder().length;
+ do {
+ didAnything = false;
+ for (int edgeIdx : cycles.getOrder()) {
+ Edge e = graph.getJoinEdge(edgeIdx);
+ long rightNodes = e.getRightExtendedNodes();
+ int leftComponent = getComponent(components, inComponent, e.getLeftExtendedNodes());
+ if (leftComponent == -1) {
+ continue;
+ }
+ if (LongBitmap.isOverlap(rightNodes, components[leftComponent])) {
+ return -1;
+ }
+ int rightComponent = getComponent(components, inComponent, e.getRightExtendedNodes());
+ if (rightComponent == -1
+ || combiningWouldViolateConflictRules(e.getConflictRules(), inComponent, leftComponent,
+ rightComponent)) {
+ continue;
+ }
+
+ if (rightComponent < leftComponent) {
+ int tmp = leftComponent;
+ leftComponent = rightComponent;
+ rightComponent = tmp;
+ }
+ int numChanged = 0;
+ for (int tableIdx : LongBitmap.getIterator(components[rightComponent])) {
+ inComponent[tableIdx] = leftComponent;
+ ++numChanged;
+ }
+
+ long combinedNodes = components[leftComponent] | components[rightComponent];
+ components[leftComponent] = combinedNodes;
+ usedEdges++;
+ if (leftComponent == 0) {
+ numInComponent += numChanged;
+ if (numInComponent == nodeCount && usedEdges == edgeCount) {
+ return numInComponent;
+ }
+ }
+ didAnything = true;
+ }
+ } while (didAnything);
+ return numInComponent;
+ }
+
+ private static int getComponent(long[] components, int[] inComponent, long tables) {
+ if (tables == 0) {
+ return -1;
+ }
+ int idx = Long.numberOfTrailingZeros(tables);
+ int component = inComponent[idx];
+ if (component >= 0 && (tables & ~components[component]) == 0) {
+ return component;
+ }
+ return -1;
+ }
+
+ private static boolean combiningWouldViolateConflictRules(
+ List<Pair<Long, Long>> conflictRules,
+ int[] inComponent,
+ int leftComponent,
+ int rightComponent) {
+ for (Pair<Long, Long> cr : conflictRules) {
+ boolean applies = false;
+ for (int nodeIdx : LongBitmap.getIterator(cr.first)) {
+ if (inComponent[nodeIdx] == leftComponent
+ || inComponent[nodeIdx] == rightComponent) {
+ applies = true;
+ break;
+ }
+ }
+ if (applies) {
+ for (int nodeIdx : LongBitmap.getIterator(cr.second)) {
+ if (inComponent[nodeIdx] != leftComponent
+ && inComponent[nodeIdx] != rightComponent) {
+ return true;
+ }
+ }
+ }
+ }
+ return false;
+ }
+
+ private void extractJoinDependencies(CircleDetector circleDetector) {
+ int edgeCount = graph.getJoinEdges().size();
+ for (int i = 0; i < edgeCount; i++) {
+ Edge edge1 = graph.getJoinEdge(i);
+ for (int j = i + 1; j < edgeCount; j++) {
+ Edge edge2 = graph.getJoinEdge(j);
+ if (edge1.isSub(edge2)) {
+ Preconditions.checkArgument(circleDetector.addEdge(i, j),
+ "Edge %s violates Edge %s", edge1, edge2);
+ } else if (edge2.isSub(edge1)) {
+ Preconditions.checkArgument(circleDetector.addEdge(j, i),
+ "Edge %s violates Edge %s", edge2, edge1);
+ }
+ }
+ }
+ }
+
+ /**
+ * simplifyGraph
+ */
+ public boolean simplifyGraph(int limit) {
+ Preconditions.checkArgument(limit >= 1);
+ int lowerBound = 0;
+ int upperBound = 1;
+
+ // Try to probe the largest number of steps to satisfy the limit
+ Counter counter = new Counter(limit);
+ SubgraphEnumerator enumerator = new SubgraphEnumerator(counter, graph);
+ while (true) {
+ boolean hitUpperLimit = false;
+ while (numStepsDone() < upperBound) {
+ if (applySimplificationStep() == SimplificationResult.NO_SIMPLIFICATION_POSSIBLE) {
+ // If we have done all steps but still has more sub graphs
+ // Just return
+ if (!enumerator.enumerate()) {
+ return false;
+ }
+ upperBound = numStepsDone();
+ hitUpperLimit = true;
+ break;
+ }
+ }
+ if (hitUpperLimit) {
+ break;
+ }
+ if (enumerator.enumerate()) {
+ break;
+ }
+ lowerBound = upperBound;
+ upperBound *= 2;
+ if (upperBound > MAX_SIMPLIFICATION_STEPS) {
+ return false;
+ }
+ }
+
+ // Try to search the lowest number of steps to satisfy the limit
+ while (upperBound - lowerBound > 1) {
+ int mid = (upperBound + lowerBound) / 2;
+ applyStepsWithNum(mid);
+ if (enumerator.enumerate()) {
+ upperBound = mid;
+ } else {
+ lowerBound = mid;
+ }
+ }
+ applyStepsWithNum(upperBound);
+ if (!isTotalOrder()) {
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * Check whether all edge has been ordered
+ *
+ * @return if true, all edges has a total order
+ */
+ public boolean isTotalOrder() {
+ return cycles.getOrder().length == graph.getJoinEdges().size() && graphIsJoinable(graph, cycles);
+ }
+
+ private boolean unApplySimplificationStep() {
+ Preconditions.checkArgument(!appliedSteps.isEmpty(),
+ "try to unapply a simplification step but there is no step applied");
+ SimplificationStep bestStep = appliedSteps.poll();
+ unAppliedSteps.push(bestStep);
+ graph.modifyEdge(bestStep.afterEdgeIdx, bestStep.oldEdgeLeft, bestStep.oldEdgeRight);
+ // Note we don't need to delete this edge in circleDetector, because we don't need to
+ // recalculate neighbors until all steps applied
+ return true;
+ }
+
+ private void applyStepsWithNum(int num) {
+ while (appliedSteps.size() < num) {
+ SimplificationResult result = applySimplificationStep();
+ Preconditions.checkState(result != SimplificationResult.NO_SIMPLIFICATION_POSSIBLE);
+ }
+ while (appliedSteps.size() > num) {
+ unApplySimplificationStep();
+ }
+ }
+
+ public @Nullable Pair<Long, Long> getLastAppliedSteps() {
+ if (appliedSteps.isEmpty()) {
+ return null;
+ }
+ return Pair.of(appliedSteps.peek().newEdgeLeft, appliedSteps.peek().newEdgeRight);
+ }
+
+ public int numStepsDone() {
+ return appliedSteps.size();
+ }
+
+ public int numStepsUndone() {
+ return unAppliedSteps.size();
+ }
+
+ @VisibleForTesting
+ protected SimplificationResult applySimplificationStep() {
+ if (!unAppliedSteps.isEmpty()) {
+ SimplificationStep step = unAppliedSteps.poll();
+ graph.modifyEdge(step.afterEdgeIdx, step.newEdgeLeft, step.newEdgeRight);
+ appliedSteps.push(step);
+ return SimplificationResult.APPLIED_REDO_STEP;
+ }
+
+ BestSimplification cacheNode = priorityQueue.peek();
+ if (cacheNode == null) {
+ return SimplificationResult.NO_SIMPLIFICATION_POSSIBLE;
+ }
+ ProposedSimplificationStep bestStep = cacheNode.bestStep;
+ boolean forced = false;
+ if (cycles.edgeWouldCreateCycle(bestStep.beforeEdgeIdx, bestStep.afterEdgeIdx)) {
+ int tmp = bestStep.beforeEdgeIdx;
+ bestStep.beforeEdgeIdx = bestStep.afterEdgeIdx;
+ bestStep.afterEdgeIdx = tmp;
+ forced = true;
+ }
+
+ SimplificationStep fullStep = concretizeSimplificationStep(bestStep);
+
+ boolean added = cycles.addEdge(bestStep.beforeEdgeIdx, bestStep.afterEdgeIdx);
+ Preconditions.checkState(added, "Cycle detected");
+ graph.modifyEdge(bestStep.afterEdgeIdx, fullStep.newEdgeLeft, fullStep.newEdgeRight);
+
+ if (!graphIsJoinable(graph, cycles)) {
+ // Undo change
+ cycles.deleteEdge(bestStep.beforeEdgeIdx, bestStep.afterEdgeIdx);
+ graph.modifyEdge(bestStep.afterEdgeIdx, fullStep.oldEdgeLeft, fullStep.oldEdgeRight);
+
+ // Insert opposite constraint and try again
+ if (!cycles.addEdge(fullStep.afterEdgeIdx, fullStep.beforeEdgeIdx)) {
+ priorityQueue.poll();
+ cacheNode.isInPriorityQueue = false;
+ }
+ return applySimplificationStep();
+ }
+ recalculateNeighbors(bestStep.afterEdgeIdx, 0, graph.getJoinEdges().size());
+ appliedSteps.push(fullStep);
+ return forced ? SimplificationResult.APPLIED_NOOP : SimplificationResult.APPLIED_SIMPLIFICATION;
+ }
+
+ private void updatePQ(int edgeIdx) {
+ BestSimplification cacheNode = simplifications.get(edgeIdx);
+ Preconditions.checkState(!Double.isNaN(cacheNode.bestStep.benefit), "bestStep has invalid benefit value");
+ if (!cacheNode.isInPriorityQueue) {
+ if (cacheNode.bestNeighbor != -1) {
+ priorityQueue.add(cacheNode);
+ cacheNode.isInPriorityQueue = true;
+ }
+ } else {
+ if (cacheNode.bestNeighbor == -1) {
+ priorityQueue.remove(cacheNode);
Review Comment:
π΄ **Bug #2: PriorityQueue not re-heapified when benefit changes**
When `cacheNode` is already queued and its `bestStep.benefit` changes (but `bestNeighbor != -1`), the heap order is not updated. Java `PriorityQueue` doesn't auto-reorder on in-place mutations. The old `hypergraph/GraphSimplifier.updatePriorityQueue()` correctly does `remove()+add()` for all queued updates.
Fix: always `remove()` first when in queue, then re-add if still valid:
```java
} else {
priorityQueue.remove(cacheNode);
if (cacheNode.bestNeighbor == -1) {
cacheNode.isInPriorityQueue = false;
} else {
priorityQueue.add(cacheNode);
}
}
```
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/GraphSimplifier.java:
##########
@@ -0,0 +1,694 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.nereids.jobs.joinorder.hypergraphv2;
+
+import org.apache.doris.common.Pair;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.bitmap.LongBitmap;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.edge.Edge;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node.AbstractNode;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node.DPhyperNode;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.receiver.Counter;
+import org.apache.doris.nereids.stats.JoinEstimation;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.JoinUtils;
+import org.apache.doris.statistics.Statistics;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.Collection;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.List;
+import java.util.PriorityQueue;
+import java.util.stream.Collectors;
+import javax.annotation.Nullable;
+
+/**
+ * GraphSimplifier is used to simplify HyperGraph {@link HyperGraph}.
+ * <p>
+ * Related paper:
+ * - [Neu09] Neumann: βQuery Simplification: Graceful Degradation for Join-Order Optimizationβ.
+ * - [Rad19] Radke and Neumann: βLinDP++: Generalizing Linearized DP to Crossproducts and Non-Inner Joinsβ.
+ */
+public class GraphSimplifier {
+
+ private static int MAX_SIMPLIFICATION_STEPS = 1000000;
+ // It cached the plan stats in simplification. we don't store it in hyper graph,
+ // because it's just used for simulating join. In fact, the graph simplifier
+ // just generate the partial order of join operator.
+ private final HashMap<Long, Statistics> cacheStats = new HashMap<>();
+ private final HashMap<Long, Double> cacheCost = new HashMap<>();
+ private Deque<SimplificationStep> appliedSteps = new ArrayDeque<>();
+ private Deque<SimplificationStep> unAppliedSteps = new ArrayDeque<>();
+ private HyperGraph graph;
+ private CircleDetector cycles;
+ private List<BestSimplification> simplifications;
+ private PriorityQueue<BestSimplification> priorityQueue = new PriorityQueue<>();
+
+ /**
+ * Initializes the GraphSimplifier with the given hypergraph.
+ * Sets up join dependencies, simplifications, and caches.
+ *
+ * @param graph The hypergraph to simplify.
+ */
+ public GraphSimplifier(HyperGraph graph) {
+ this.graph = graph;
+ int edgeCount = graph.getJoinEdges().size();
+
+ // init join dependency
+ this.cycles = new CircleDetector(edgeCount);
+ extractJoinDependencies(cycles);
+
+ // init simplifications with empty values
+ this.simplifications = new ArrayList<>(edgeCount);
+ for (int i = 0; i < edgeCount; i++) {
+ simplifications.add(new BestSimplification());
+ }
+
+ // init cacheStats and cacheCost
+ for (AbstractNode node : graph.getNodes()) {
+ DPhyperNode dPhyperNode = (DPhyperNode) node;
+ cacheStats.put(node.getNodeMap(), dPhyperNode.getGroup().getStatistics());
+ cacheCost.put(node.getNodeMap(), dPhyperNode.getRowCount());
+ }
+
+ //
+ for (int edgeIdx = 0; edgeIdx < edgeCount; edgeIdx++) {
+ recalculateNeighbors(edgeIdx, edgeIdx + 1, edgeCount);
+ }
+ }
+
+ /**
+ * Checks if the hypergraph is joinable, ensuring all tables are connected via joins.
+ *
+ * @param graph The hypergraph to check.
+ * @param cycles The cycle detector for the graph.
+ * @return True if the graph is joinable, false otherwise.
+ */
+ private static boolean graphIsJoinable(HyperGraph graph, CircleDetector cycles) {
+ int nodeCount = graph.getNodes().size();
+ long[] components = new long[nodeCount];
+ int[] inComponent = new int[nodeCount];
+
+ for (int nodeIdx = 0; nodeIdx < nodeCount; nodeIdx++) {
+ components[nodeIdx] = LongBitmap.newBitmap(nodeIdx);
+ inComponent[nodeIdx] = nodeIdx;
+ }
+ return connectComponentsThroughJoins(graph, cycles, components, inComponent) == nodeCount;
+ }
+
+ /**
+ * Connects components in the hypergraph through join edges.
+ *
+ * @param graph The hypergraph to process.
+ * @param cycles The cycle detector for the graph.
+ * @param components Array representing connected components.
+ * @param inComponent Array mapping nodes to their components.
+ * @return The number of connected components.
+ */
+ private static int connectComponentsThroughJoins(
+ HyperGraph graph,
+ CircleDetector cycles,
+ long[] components,
+ int[] inComponent) {
+ int nodeCount = graph.getNodes().size();
+ int numInComponent = 1;
+ boolean didAnything;
+ int usedEdges = 0;
+ int edgeCount = cycles.getOrder().length;
+ do {
+ didAnything = false;
+ for (int edgeIdx : cycles.getOrder()) {
+ Edge e = graph.getJoinEdge(edgeIdx);
+ long rightNodes = e.getRightExtendedNodes();
+ int leftComponent = getComponent(components, inComponent, e.getLeftExtendedNodes());
+ if (leftComponent == -1) {
+ continue;
+ }
+ if (LongBitmap.isOverlap(rightNodes, components[leftComponent])) {
+ return -1;
+ }
+ int rightComponent = getComponent(components, inComponent, e.getRightExtendedNodes());
+ if (rightComponent == -1
+ || combiningWouldViolateConflictRules(e.getConflictRules(), inComponent, leftComponent,
+ rightComponent)) {
+ continue;
+ }
+
+ if (rightComponent < leftComponent) {
+ int tmp = leftComponent;
+ leftComponent = rightComponent;
+ rightComponent = tmp;
+ }
+ int numChanged = 0;
+ for (int tableIdx : LongBitmap.getIterator(components[rightComponent])) {
+ inComponent[tableIdx] = leftComponent;
+ ++numChanged;
+ }
+
+ long combinedNodes = components[leftComponent] | components[rightComponent];
+ components[leftComponent] = combinedNodes;
+ usedEdges++;
+ if (leftComponent == 0) {
+ numInComponent += numChanged;
+ if (numInComponent == nodeCount && usedEdges == edgeCount) {
+ return numInComponent;
+ }
+ }
+ didAnything = true;
+ }
+ } while (didAnything);
+ return numInComponent;
+ }
+
+ private static int getComponent(long[] components, int[] inComponent, long tables) {
+ if (tables == 0) {
+ return -1;
+ }
+ int idx = Long.numberOfTrailingZeros(tables);
+ int component = inComponent[idx];
+ if (component >= 0 && (tables & ~components[component]) == 0) {
+ return component;
+ }
+ return -1;
+ }
+
+ private static boolean combiningWouldViolateConflictRules(
+ List<Pair<Long, Long>> conflictRules,
+ int[] inComponent,
+ int leftComponent,
+ int rightComponent) {
+ for (Pair<Long, Long> cr : conflictRules) {
+ boolean applies = false;
+ for (int nodeIdx : LongBitmap.getIterator(cr.first)) {
+ if (inComponent[nodeIdx] == leftComponent
+ || inComponent[nodeIdx] == rightComponent) {
+ applies = true;
+ break;
+ }
+ }
+ if (applies) {
+ for (int nodeIdx : LongBitmap.getIterator(cr.second)) {
+ if (inComponent[nodeIdx] != leftComponent
+ && inComponent[nodeIdx] != rightComponent) {
+ return true;
+ }
+ }
+ }
+ }
+ return false;
+ }
+
+ private void extractJoinDependencies(CircleDetector circleDetector) {
+ int edgeCount = graph.getJoinEdges().size();
+ for (int i = 0; i < edgeCount; i++) {
+ Edge edge1 = graph.getJoinEdge(i);
+ for (int j = i + 1; j < edgeCount; j++) {
+ Edge edge2 = graph.getJoinEdge(j);
+ if (edge1.isSub(edge2)) {
+ Preconditions.checkArgument(circleDetector.addEdge(i, j),
+ "Edge %s violates Edge %s", edge1, edge2);
+ } else if (edge2.isSub(edge1)) {
+ Preconditions.checkArgument(circleDetector.addEdge(j, i),
+ "Edge %s violates Edge %s", edge2, edge1);
+ }
+ }
+ }
+ }
+
+ /**
+ * simplifyGraph
+ */
+ public boolean simplifyGraph(int limit) {
+ Preconditions.checkArgument(limit >= 1);
+ int lowerBound = 0;
+ int upperBound = 1;
+
+ // Try to probe the largest number of steps to satisfy the limit
+ Counter counter = new Counter(limit);
+ SubgraphEnumerator enumerator = new SubgraphEnumerator(counter, graph);
+ while (true) {
+ boolean hitUpperLimit = false;
+ while (numStepsDone() < upperBound) {
+ if (applySimplificationStep() == SimplificationResult.NO_SIMPLIFICATION_POSSIBLE) {
+ // If we have done all steps but still has more sub graphs
+ // Just return
+ if (!enumerator.enumerate()) {
+ return false;
+ }
+ upperBound = numStepsDone();
+ hitUpperLimit = true;
+ break;
+ }
+ }
+ if (hitUpperLimit) {
+ break;
+ }
+ if (enumerator.enumerate()) {
+ break;
+ }
+ lowerBound = upperBound;
+ upperBound *= 2;
+ if (upperBound > MAX_SIMPLIFICATION_STEPS) {
+ return false;
+ }
+ }
+
+ // Try to search the lowest number of steps to satisfy the limit
+ while (upperBound - lowerBound > 1) {
+ int mid = (upperBound + lowerBound) / 2;
+ applyStepsWithNum(mid);
+ if (enumerator.enumerate()) {
+ upperBound = mid;
+ } else {
+ lowerBound = mid;
+ }
+ }
+ applyStepsWithNum(upperBound);
+ if (!isTotalOrder()) {
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * Check whether all edge has been ordered
+ *
+ * @return if true, all edges has a total order
+ */
+ public boolean isTotalOrder() {
+ return cycles.getOrder().length == graph.getJoinEdges().size() && graphIsJoinable(graph, cycles);
+ }
+
+ private boolean unApplySimplificationStep() {
+ Preconditions.checkArgument(!appliedSteps.isEmpty(),
+ "try to unapply a simplification step but there is no step applied");
+ SimplificationStep bestStep = appliedSteps.poll();
+ unAppliedSteps.push(bestStep);
+ graph.modifyEdge(bestStep.afterEdgeIdx, bestStep.oldEdgeLeft, bestStep.oldEdgeRight);
+ // Note we don't need to delete this edge in circleDetector, because we don't need to
+ // recalculate neighbors until all steps applied
+ return true;
+ }
+
+ private void applyStepsWithNum(int num) {
+ while (appliedSteps.size() < num) {
+ SimplificationResult result = applySimplificationStep();
+ Preconditions.checkState(result != SimplificationResult.NO_SIMPLIFICATION_POSSIBLE);
+ }
+ while (appliedSteps.size() > num) {
+ unApplySimplificationStep();
+ }
+ }
+
+ public @Nullable Pair<Long, Long> getLastAppliedSteps() {
+ if (appliedSteps.isEmpty()) {
+ return null;
+ }
+ return Pair.of(appliedSteps.peek().newEdgeLeft, appliedSteps.peek().newEdgeRight);
+ }
+
+ public int numStepsDone() {
+ return appliedSteps.size();
+ }
+
+ public int numStepsUndone() {
+ return unAppliedSteps.size();
+ }
+
+ @VisibleForTesting
+ protected SimplificationResult applySimplificationStep() {
+ if (!unAppliedSteps.isEmpty()) {
+ SimplificationStep step = unAppliedSteps.poll();
+ graph.modifyEdge(step.afterEdgeIdx, step.newEdgeLeft, step.newEdgeRight);
+ appliedSteps.push(step);
+ return SimplificationResult.APPLIED_REDO_STEP;
+ }
+
+ BestSimplification cacheNode = priorityQueue.peek();
+ if (cacheNode == null) {
+ return SimplificationResult.NO_SIMPLIFICATION_POSSIBLE;
+ }
+ ProposedSimplificationStep bestStep = cacheNode.bestStep;
+ boolean forced = false;
+ if (cycles.edgeWouldCreateCycle(bestStep.beforeEdgeIdx, bestStep.afterEdgeIdx)) {
+ int tmp = bestStep.beforeEdgeIdx;
+ bestStep.beforeEdgeIdx = bestStep.afterEdgeIdx;
+ bestStep.afterEdgeIdx = tmp;
+ forced = true;
+ }
+
+ SimplificationStep fullStep = concretizeSimplificationStep(bestStep);
+
+ boolean added = cycles.addEdge(bestStep.beforeEdgeIdx, bestStep.afterEdgeIdx);
+ Preconditions.checkState(added, "Cycle detected");
+ graph.modifyEdge(bestStep.afterEdgeIdx, fullStep.newEdgeLeft, fullStep.newEdgeRight);
+
+ if (!graphIsJoinable(graph, cycles)) {
+ // Undo change
+ cycles.deleteEdge(bestStep.beforeEdgeIdx, bestStep.afterEdgeIdx);
+ graph.modifyEdge(bestStep.afterEdgeIdx, fullStep.oldEdgeLeft, fullStep.oldEdgeRight);
+
+ // Insert opposite constraint and try again
+ if (!cycles.addEdge(fullStep.afterEdgeIdx, fullStep.beforeEdgeIdx)) {
+ priorityQueue.poll();
+ cacheNode.isInPriorityQueue = false;
+ }
+ return applySimplificationStep();
+ }
+ recalculateNeighbors(bestStep.afterEdgeIdx, 0, graph.getJoinEdges().size());
+ appliedSteps.push(fullStep);
+ return forced ? SimplificationResult.APPLIED_NOOP : SimplificationResult.APPLIED_SIMPLIFICATION;
+ }
+
+ private void updatePQ(int edgeIdx) {
+ BestSimplification cacheNode = simplifications.get(edgeIdx);
+ Preconditions.checkState(!Double.isNaN(cacheNode.bestStep.benefit), "bestStep has invalid benefit value");
+ if (!cacheNode.isInPriorityQueue) {
+ if (cacheNode.bestNeighbor != -1) {
+ priorityQueue.add(cacheNode);
+ cacheNode.isInPriorityQueue = true;
+ }
+ } else {
+ if (cacheNode.bestNeighbor == -1) {
+ priorityQueue.remove(cacheNode);
+ cacheNode.isInPriorityQueue = false;
+ }
+ }
+ }
+
+ private void recalculateNeighbors(int edge1Idx, int begin, int end) {
+ for (int edge2Idx = begin; edge2Idx < Math.min(edge1Idx, end); edge2Idx++) {
+ BestSimplification otherCache = simplifications.get(edge2Idx);
+ ProposedSimplificationStep step = new ProposedSimplificationStep();
+ if (edgesAreNeighboring(edge2Idx, edge1Idx, step)) {
+ if (otherCache.bestNeighbor == -1 || step.benefit >= otherCache.bestStep.benefit) {
+ otherCache.bestNeighbor = edge1Idx;
+ otherCache.bestStep = step;
+ updatePQ(edge2Idx);
+ continue;
+ }
+ }
+ if (otherCache.bestNeighbor == edge1Idx) {
+ recalculateNeighbors(edge2Idx, 0, graph.getJoinEdges().size());
+ }
+ }
+ BestSimplification cacheNode = simplifications.get(edge1Idx);
+ cacheNode.bestNeighbor = -1;
+ cacheNode.bestStep.benefit = Double.NEGATIVE_INFINITY;
+ for (int edge2Idx = Math.max(begin, edge1Idx + 1); edge2Idx < end; edge2Idx++) {
+ ProposedSimplificationStep step = new ProposedSimplificationStep();
+ if (edgesAreNeighboring(edge1Idx, edge2Idx, step)) {
+ if (cacheNode.bestNeighbor == -1 || step.benefit > cacheNode.bestStep.benefit) {
+ cacheNode.bestNeighbor = edge2Idx;
+ cacheNode.bestStep = step;
+ }
+ }
+ }
+ updatePQ(edge1Idx);
+ }
+
+ private boolean edgesAreNeighboring(int edge1Idx, int edge2Idx, ProposedSimplificationStep step) {
+ Edge edge1 = graph.getJoinEdge(edge1Idx);
+ Edge edge2 = graph.getJoinEdge(edge2Idx);
+ if (edge1.isSub(edge2) || edge2.isSub(edge1)) {
+ return false;
+ }
+ long left1 = edge1.getLeftExtendedNodes();
+ long right1 = edge1.getRightExtendedNodes();
+ long left2 = edge2.getLeftExtendedNodes();
+ long right2 = edge2.getRightExtendedNodes();
+ if (!cacheStats.containsKey(left1) || !cacheStats.containsKey(right1)
+ || !cacheStats.containsKey(left2) || !cacheStats.containsKey(right2)) {
+ return false;
+ }
+ Edge edge1Before2;
+ Edge edge2Before1;
+ List<Long> superBitset = new ArrayList<>();
+ if (tryGetSuperset(left1, left2, superBitset)) {
+ // (common Join1 right1) Join2 right2
+ edge1Before2 = threeLeftJoin(superBitset.get(0), edge1, right1, edge2, right2);
+ // (common Join2 right2) Join1 right1
+ edge2Before1 = threeLeftJoin(superBitset.get(0), edge2, right2, edge1, right1);
+ } else if (tryGetSuperset(left1, right2, superBitset)) {
+ // left2 Join2 (common Join1 right1)
+ edge1Before2 = threeRightJoin(left2, edge2, superBitset.get(0), edge1, right1);
+ // (left2 Join2 common) join1 right1
+ edge2Before1 = threeLeftJoin(left2, edge2, superBitset.get(0), edge1, right1);
+ } else if (tryGetSuperset(right1, left2, superBitset)) {
+ // (left1 Join1 common) Join2 right2
+ edge1Before2 = threeLeftJoin(left1, edge1, superBitset.get(0), edge2, right2);
+ // left1 Join1 (common Join2 right2)
+ edge2Before1 = threeRightJoin(left1, edge1, superBitset.get(0), edge2, right2);
+ } else if (tryGetSuperset(right1, right2, superBitset)) {
+ // left2 Join2 (left1 Join1 common)
+ edge1Before2 = threeRightJoin(left2, edge2, left1, edge1, superBitset.get(0));
+ // left1 Join1 (left2 Join2 common)
+ edge2Before1 = threeRightJoin(left1, edge1, left2, edge2, superBitset.get(0));
+ } else {
+ return false;
+ }
+
+ if (edge1Before2 == null || edge2Before1 == null) {
+ return false;
+ }
+
+ double cost1Before2 = calCost(edge1Before2,
+ edge1Before2.getLeftExtendedNodes(), edge1Before2.getRightExtendedNodes());
+ double cost2Before1 = calCost(edge2Before1,
+ edge2Before1.getLeftExtendedNodes(), edge2Before1.getRightExtendedNodes());
+ double benefit = Double.MAX_VALUE;
+ // Choose the plan with smaller cost and make the simplification step to replace the old edge by it.
+ if (cost1Before2 < cost2Before1) {
+ if (cost1Before2 != 0) {
+ benefit = cost2Before1 / cost1Before2;
+ }
+ // choose edge1Before2
+ step.benefit = benefit;
+ step.beforeEdgeIdx = edge1Idx;
+ step.afterEdgeIdx = edge2Idx;
+ } else {
+ if (cost2Before1 != 0) {
+ benefit = cost1Before2 / cost2Before1;
+ }
+ // choose edge2Before1
+ step.benefit = benefit;
+ step.beforeEdgeIdx = edge2Idx;
+ step.afterEdgeIdx = edge1Idx;
+ }
+ return true;
+ }
+
+ private boolean tryGetSuperset(long bitmap1, long bitmap2, List<Long> superset) {
+ if (LongBitmap.isSubset(bitmap1, bitmap2)) {
+ superset.add(bitmap2);
+ return true;
+ } else if (LongBitmap.isSubset(bitmap2, bitmap1)) {
+ superset.add(bitmap1);
+ return true;
+ }
+ return false;
+ }
+
+ private Edge constructEdge(long leftNodes, Edge edge, long rightNodes) {
+ LogicalJoin<? extends Plan, ? extends Plan> join;
+ if (graph.getJoinEdges().size() > 64 * 63 / 8) {
+ // If there are too many edges, it is advisable to return the "edge" directly
+ // to avoid lengthy enumeration time.
+ join = edge.getJoin();
+ } else {
+ BitSet connectionEdges = graph.findConnectionEdges(leftNodes, rightNodes);
+ List<Expression> hashConditions = connectionEdges.stream()
+ .mapToObj(i -> graph.getJoinEdge(i).getJoin().getHashJoinConjuncts())
+ .flatMap(Collection::stream)
+ .collect(Collectors.toList());
+ List<Expression> otherConditions = connectionEdges.stream()
+ .mapToObj(i -> graph.getJoinEdge(i).getJoin().getHashJoinConjuncts())
+ .flatMap(Collection::stream)
Review Comment:
π΄ **Bug #1: Copy-paste error β should be `getOtherJoinConjuncts()`**
This line is identical to line 529 above. `otherConditions` should collect non-equi predicates, not duplicate hash predicates. Current code silently drops all non-equi join conditions and duplicates hash conditions.
```suggestion
.mapToObj(i -> graph.getJoinEdge(i).getJoin().getOtherJoinConjuncts())
```
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/GraphSimplifier.java:
##########
@@ -0,0 +1,694 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.nereids.jobs.joinorder.hypergraphv2;
+
+import org.apache.doris.common.Pair;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.bitmap.LongBitmap;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.edge.Edge;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node.AbstractNode;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node.DPhyperNode;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.receiver.Counter;
+import org.apache.doris.nereids.stats.JoinEstimation;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.JoinUtils;
+import org.apache.doris.statistics.Statistics;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.Collection;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.List;
+import java.util.PriorityQueue;
+import java.util.stream.Collectors;
+import javax.annotation.Nullable;
+
+/**
+ * GraphSimplifier is used to simplify HyperGraph {@link HyperGraph}.
+ * <p>
+ * Related paper:
+ * - [Neu09] Neumann: βQuery Simplification: Graceful Degradation for Join-Order Optimizationβ.
+ * - [Rad19] Radke and Neumann: βLinDP++: Generalizing Linearized DP to Crossproducts and Non-Inner Joinsβ.
+ */
+public class GraphSimplifier {
+
+ private static int MAX_SIMPLIFICATION_STEPS = 1000000;
+ // It cached the plan stats in simplification. we don't store it in hyper graph,
+ // because it's just used for simulating join. In fact, the graph simplifier
+ // just generate the partial order of join operator.
+ private final HashMap<Long, Statistics> cacheStats = new HashMap<>();
+ private final HashMap<Long, Double> cacheCost = new HashMap<>();
+ private Deque<SimplificationStep> appliedSteps = new ArrayDeque<>();
+ private Deque<SimplificationStep> unAppliedSteps = new ArrayDeque<>();
+ private HyperGraph graph;
+ private CircleDetector cycles;
+ private List<BestSimplification> simplifications;
+ private PriorityQueue<BestSimplification> priorityQueue = new PriorityQueue<>();
+
+ /**
+ * Initializes the GraphSimplifier with the given hypergraph.
+ * Sets up join dependencies, simplifications, and caches.
+ *
+ * @param graph The hypergraph to simplify.
+ */
+ public GraphSimplifier(HyperGraph graph) {
+ this.graph = graph;
+ int edgeCount = graph.getJoinEdges().size();
+
+ // init join dependency
+ this.cycles = new CircleDetector(edgeCount);
+ extractJoinDependencies(cycles);
+
+ // init simplifications with empty values
+ this.simplifications = new ArrayList<>(edgeCount);
+ for (int i = 0; i < edgeCount; i++) {
+ simplifications.add(new BestSimplification());
+ }
+
+ // init cacheStats and cacheCost
+ for (AbstractNode node : graph.getNodes()) {
+ DPhyperNode dPhyperNode = (DPhyperNode) node;
+ cacheStats.put(node.getNodeMap(), dPhyperNode.getGroup().getStatistics());
+ cacheCost.put(node.getNodeMap(), dPhyperNode.getRowCount());
+ }
+
+ //
+ for (int edgeIdx = 0; edgeIdx < edgeCount; edgeIdx++) {
+ recalculateNeighbors(edgeIdx, edgeIdx + 1, edgeCount);
+ }
+ }
+
+ /**
+ * Checks if the hypergraph is joinable, ensuring all tables are connected via joins.
+ *
+ * @param graph The hypergraph to check.
+ * @param cycles The cycle detector for the graph.
+ * @return True if the graph is joinable, false otherwise.
+ */
+ private static boolean graphIsJoinable(HyperGraph graph, CircleDetector cycles) {
+ int nodeCount = graph.getNodes().size();
+ long[] components = new long[nodeCount];
+ int[] inComponent = new int[nodeCount];
+
+ for (int nodeIdx = 0; nodeIdx < nodeCount; nodeIdx++) {
+ components[nodeIdx] = LongBitmap.newBitmap(nodeIdx);
+ inComponent[nodeIdx] = nodeIdx;
+ }
+ return connectComponentsThroughJoins(graph, cycles, components, inComponent) == nodeCount;
+ }
+
+ /**
+ * Connects components in the hypergraph through join edges.
+ *
+ * @param graph The hypergraph to process.
+ * @param cycles The cycle detector for the graph.
+ * @param components Array representing connected components.
+ * @param inComponent Array mapping nodes to their components.
+ * @return The number of connected components.
+ */
+ private static int connectComponentsThroughJoins(
+ HyperGraph graph,
+ CircleDetector cycles,
+ long[] components,
+ int[] inComponent) {
+ int nodeCount = graph.getNodes().size();
+ int numInComponent = 1;
+ boolean didAnything;
+ int usedEdges = 0;
+ int edgeCount = cycles.getOrder().length;
+ do {
+ didAnything = false;
+ for (int edgeIdx : cycles.getOrder()) {
+ Edge e = graph.getJoinEdge(edgeIdx);
+ long rightNodes = e.getRightExtendedNodes();
+ int leftComponent = getComponent(components, inComponent, e.getLeftExtendedNodes());
+ if (leftComponent == -1) {
+ continue;
+ }
+ if (LongBitmap.isOverlap(rightNodes, components[leftComponent])) {
+ return -1;
+ }
+ int rightComponent = getComponent(components, inComponent, e.getRightExtendedNodes());
+ if (rightComponent == -1
+ || combiningWouldViolateConflictRules(e.getConflictRules(), inComponent, leftComponent,
+ rightComponent)) {
+ continue;
+ }
+
+ if (rightComponent < leftComponent) {
+ int tmp = leftComponent;
+ leftComponent = rightComponent;
+ rightComponent = tmp;
+ }
+ int numChanged = 0;
+ for (int tableIdx : LongBitmap.getIterator(components[rightComponent])) {
+ inComponent[tableIdx] = leftComponent;
+ ++numChanged;
+ }
+
+ long combinedNodes = components[leftComponent] | components[rightComponent];
+ components[leftComponent] = combinedNodes;
+ usedEdges++;
+ if (leftComponent == 0) {
+ numInComponent += numChanged;
+ if (numInComponent == nodeCount && usedEdges == edgeCount) {
+ return numInComponent;
+ }
+ }
+ didAnything = true;
+ }
+ } while (didAnything);
+ return numInComponent;
+ }
+
+ private static int getComponent(long[] components, int[] inComponent, long tables) {
+ if (tables == 0) {
+ return -1;
+ }
+ int idx = Long.numberOfTrailingZeros(tables);
+ int component = inComponent[idx];
+ if (component >= 0 && (tables & ~components[component]) == 0) {
+ return component;
+ }
+ return -1;
+ }
+
+ private static boolean combiningWouldViolateConflictRules(
+ List<Pair<Long, Long>> conflictRules,
+ int[] inComponent,
+ int leftComponent,
+ int rightComponent) {
+ for (Pair<Long, Long> cr : conflictRules) {
+ boolean applies = false;
+ for (int nodeIdx : LongBitmap.getIterator(cr.first)) {
+ if (inComponent[nodeIdx] == leftComponent
+ || inComponent[nodeIdx] == rightComponent) {
+ applies = true;
+ break;
+ }
+ }
+ if (applies) {
+ for (int nodeIdx : LongBitmap.getIterator(cr.second)) {
+ if (inComponent[nodeIdx] != leftComponent
+ && inComponent[nodeIdx] != rightComponent) {
+ return true;
+ }
+ }
+ }
+ }
+ return false;
+ }
+
+ private void extractJoinDependencies(CircleDetector circleDetector) {
+ int edgeCount = graph.getJoinEdges().size();
+ for (int i = 0; i < edgeCount; i++) {
+ Edge edge1 = graph.getJoinEdge(i);
+ for (int j = i + 1; j < edgeCount; j++) {
+ Edge edge2 = graph.getJoinEdge(j);
+ if (edge1.isSub(edge2)) {
+ Preconditions.checkArgument(circleDetector.addEdge(i, j),
+ "Edge %s violates Edge %s", edge1, edge2);
+ } else if (edge2.isSub(edge1)) {
+ Preconditions.checkArgument(circleDetector.addEdge(j, i),
+ "Edge %s violates Edge %s", edge2, edge1);
+ }
+ }
+ }
+ }
+
+ /**
+ * simplifyGraph
+ */
+ public boolean simplifyGraph(int limit) {
+ Preconditions.checkArgument(limit >= 1);
+ int lowerBound = 0;
+ int upperBound = 1;
+
+ // Try to probe the largest number of steps to satisfy the limit
+ Counter counter = new Counter(limit);
+ SubgraphEnumerator enumerator = new SubgraphEnumerator(counter, graph);
+ while (true) {
+ boolean hitUpperLimit = false;
+ while (numStepsDone() < upperBound) {
+ if (applySimplificationStep() == SimplificationResult.NO_SIMPLIFICATION_POSSIBLE) {
+ // If we have done all steps but still has more sub graphs
+ // Just return
+ if (!enumerator.enumerate()) {
+ return false;
+ }
+ upperBound = numStepsDone();
+ hitUpperLimit = true;
+ break;
+ }
+ }
+ if (hitUpperLimit) {
+ break;
+ }
+ if (enumerator.enumerate()) {
+ break;
+ }
+ lowerBound = upperBound;
+ upperBound *= 2;
+ if (upperBound > MAX_SIMPLIFICATION_STEPS) {
+ return false;
+ }
+ }
+
+ // Try to search the lowest number of steps to satisfy the limit
+ while (upperBound - lowerBound > 1) {
+ int mid = (upperBound + lowerBound) / 2;
+ applyStepsWithNum(mid);
+ if (enumerator.enumerate()) {
+ upperBound = mid;
+ } else {
+ lowerBound = mid;
+ }
+ }
+ applyStepsWithNum(upperBound);
+ if (!isTotalOrder()) {
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * Check whether all edge has been ordered
+ *
+ * @return if true, all edges has a total order
+ */
+ public boolean isTotalOrder() {
+ return cycles.getOrder().length == graph.getJoinEdges().size() && graphIsJoinable(graph, cycles);
+ }
+
+ private boolean unApplySimplificationStep() {
+ Preconditions.checkArgument(!appliedSteps.isEmpty(),
+ "try to unapply a simplification step but there is no step applied");
+ SimplificationStep bestStep = appliedSteps.poll();
+ unAppliedSteps.push(bestStep);
+ graph.modifyEdge(bestStep.afterEdgeIdx, bestStep.oldEdgeLeft, bestStep.oldEdgeRight);
+ // Note we don't need to delete this edge in circleDetector, because we don't need to
+ // recalculate neighbors until all steps applied
+ return true;
+ }
+
+ private void applyStepsWithNum(int num) {
+ while (appliedSteps.size() < num) {
+ SimplificationResult result = applySimplificationStep();
+ Preconditions.checkState(result != SimplificationResult.NO_SIMPLIFICATION_POSSIBLE);
+ }
+ while (appliedSteps.size() > num) {
+ unApplySimplificationStep();
+ }
+ }
+
+ public @Nullable Pair<Long, Long> getLastAppliedSteps() {
+ if (appliedSteps.isEmpty()) {
+ return null;
+ }
+ return Pair.of(appliedSteps.peek().newEdgeLeft, appliedSteps.peek().newEdgeRight);
+ }
+
+ public int numStepsDone() {
+ return appliedSteps.size();
+ }
+
+ public int numStepsUndone() {
+ return unAppliedSteps.size();
+ }
+
+ @VisibleForTesting
+ protected SimplificationResult applySimplificationStep() {
+ if (!unAppliedSteps.isEmpty()) {
+ SimplificationStep step = unAppliedSteps.poll();
+ graph.modifyEdge(step.afterEdgeIdx, step.newEdgeLeft, step.newEdgeRight);
+ appliedSteps.push(step);
+ return SimplificationResult.APPLIED_REDO_STEP;
+ }
+
+ BestSimplification cacheNode = priorityQueue.peek();
+ if (cacheNode == null) {
+ return SimplificationResult.NO_SIMPLIFICATION_POSSIBLE;
+ }
+ ProposedSimplificationStep bestStep = cacheNode.bestStep;
+ boolean forced = false;
+ if (cycles.edgeWouldCreateCycle(bestStep.beforeEdgeIdx, bestStep.afterEdgeIdx)) {
+ int tmp = bestStep.beforeEdgeIdx;
+ bestStep.beforeEdgeIdx = bestStep.afterEdgeIdx;
+ bestStep.afterEdgeIdx = tmp;
+ forced = true;
+ }
+
+ SimplificationStep fullStep = concretizeSimplificationStep(bestStep);
+
+ boolean added = cycles.addEdge(bestStep.beforeEdgeIdx, bestStep.afterEdgeIdx);
+ Preconditions.checkState(added, "Cycle detected");
+ graph.modifyEdge(bestStep.afterEdgeIdx, fullStep.newEdgeLeft, fullStep.newEdgeRight);
+
+ if (!graphIsJoinable(graph, cycles)) {
+ // Undo change
+ cycles.deleteEdge(bestStep.beforeEdgeIdx, bestStep.afterEdgeIdx);
+ graph.modifyEdge(bestStep.afterEdgeIdx, fullStep.oldEdgeLeft, fullStep.oldEdgeRight);
+
+ // Insert opposite constraint and try again
+ if (!cycles.addEdge(fullStep.afterEdgeIdx, fullStep.beforeEdgeIdx)) {
+ priorityQueue.poll();
+ cacheNode.isInPriorityQueue = false;
+ }
+ return applySimplificationStep();
+ }
+ recalculateNeighbors(bestStep.afterEdgeIdx, 0, graph.getJoinEdges().size());
+ appliedSteps.push(fullStep);
+ return forced ? SimplificationResult.APPLIED_NOOP : SimplificationResult.APPLIED_SIMPLIFICATION;
+ }
+
+ private void updatePQ(int edgeIdx) {
+ BestSimplification cacheNode = simplifications.get(edgeIdx);
+ Preconditions.checkState(!Double.isNaN(cacheNode.bestStep.benefit), "bestStep has invalid benefit value");
+ if (!cacheNode.isInPriorityQueue) {
+ if (cacheNode.bestNeighbor != -1) {
+ priorityQueue.add(cacheNode);
+ cacheNode.isInPriorityQueue = true;
+ }
+ } else {
+ if (cacheNode.bestNeighbor == -1) {
+ priorityQueue.remove(cacheNode);
+ cacheNode.isInPriorityQueue = false;
+ }
+ }
+ }
+
+ private void recalculateNeighbors(int edge1Idx, int begin, int end) {
+ for (int edge2Idx = begin; edge2Idx < Math.min(edge1Idx, end); edge2Idx++) {
+ BestSimplification otherCache = simplifications.get(edge2Idx);
+ ProposedSimplificationStep step = new ProposedSimplificationStep();
+ if (edgesAreNeighboring(edge2Idx, edge1Idx, step)) {
+ if (otherCache.bestNeighbor == -1 || step.benefit >= otherCache.bestStep.benefit) {
+ otherCache.bestNeighbor = edge1Idx;
+ otherCache.bestStep = step;
+ updatePQ(edge2Idx);
+ continue;
+ }
+ }
+ if (otherCache.bestNeighbor == edge1Idx) {
+ recalculateNeighbors(edge2Idx, 0, graph.getJoinEdges().size());
+ }
+ }
+ BestSimplification cacheNode = simplifications.get(edge1Idx);
+ cacheNode.bestNeighbor = -1;
+ cacheNode.bestStep.benefit = Double.NEGATIVE_INFINITY;
+ for (int edge2Idx = Math.max(begin, edge1Idx + 1); edge2Idx < end; edge2Idx++) {
+ ProposedSimplificationStep step = new ProposedSimplificationStep();
+ if (edgesAreNeighboring(edge1Idx, edge2Idx, step)) {
+ if (cacheNode.bestNeighbor == -1 || step.benefit > cacheNode.bestStep.benefit) {
+ cacheNode.bestNeighbor = edge2Idx;
+ cacheNode.bestStep = step;
+ }
+ }
+ }
+ updatePQ(edge1Idx);
+ }
+
+ private boolean edgesAreNeighboring(int edge1Idx, int edge2Idx, ProposedSimplificationStep step) {
+ Edge edge1 = graph.getJoinEdge(edge1Idx);
+ Edge edge2 = graph.getJoinEdge(edge2Idx);
+ if (edge1.isSub(edge2) || edge2.isSub(edge1)) {
+ return false;
+ }
+ long left1 = edge1.getLeftExtendedNodes();
+ long right1 = edge1.getRightExtendedNodes();
+ long left2 = edge2.getLeftExtendedNodes();
+ long right2 = edge2.getRightExtendedNodes();
+ if (!cacheStats.containsKey(left1) || !cacheStats.containsKey(right1)
+ || !cacheStats.containsKey(left2) || !cacheStats.containsKey(right2)) {
+ return false;
+ }
+ Edge edge1Before2;
+ Edge edge2Before1;
+ List<Long> superBitset = new ArrayList<>();
+ if (tryGetSuperset(left1, left2, superBitset)) {
+ // (common Join1 right1) Join2 right2
+ edge1Before2 = threeLeftJoin(superBitset.get(0), edge1, right1, edge2, right2);
+ // (common Join2 right2) Join1 right1
+ edge2Before1 = threeLeftJoin(superBitset.get(0), edge2, right2, edge1, right1);
+ } else if (tryGetSuperset(left1, right2, superBitset)) {
+ // left2 Join2 (common Join1 right1)
+ edge1Before2 = threeRightJoin(left2, edge2, superBitset.get(0), edge1, right1);
+ // (left2 Join2 common) join1 right1
+ edge2Before1 = threeLeftJoin(left2, edge2, superBitset.get(0), edge1, right1);
+ } else if (tryGetSuperset(right1, left2, superBitset)) {
+ // (left1 Join1 common) Join2 right2
+ edge1Before2 = threeLeftJoin(left1, edge1, superBitset.get(0), edge2, right2);
+ // left1 Join1 (common Join2 right2)
+ edge2Before1 = threeRightJoin(left1, edge1, superBitset.get(0), edge2, right2);
+ } else if (tryGetSuperset(right1, right2, superBitset)) {
+ // left2 Join2 (left1 Join1 common)
+ edge1Before2 = threeRightJoin(left2, edge2, left1, edge1, superBitset.get(0));
+ // left1 Join1 (left2 Join2 common)
+ edge2Before1 = threeRightJoin(left1, edge1, left2, edge2, superBitset.get(0));
+ } else {
+ return false;
+ }
+
+ if (edge1Before2 == null || edge2Before1 == null) {
+ return false;
+ }
+
+ double cost1Before2 = calCost(edge1Before2,
+ edge1Before2.getLeftExtendedNodes(), edge1Before2.getRightExtendedNodes());
+ double cost2Before1 = calCost(edge2Before1,
+ edge2Before1.getLeftExtendedNodes(), edge2Before1.getRightExtendedNodes());
+ double benefit = Double.MAX_VALUE;
+ // Choose the plan with smaller cost and make the simplification step to replace the old edge by it.
+ if (cost1Before2 < cost2Before1) {
+ if (cost1Before2 != 0) {
+ benefit = cost2Before1 / cost1Before2;
+ }
+ // choose edge1Before2
+ step.benefit = benefit;
+ step.beforeEdgeIdx = edge1Idx;
+ step.afterEdgeIdx = edge2Idx;
+ } else {
+ if (cost2Before1 != 0) {
+ benefit = cost1Before2 / cost2Before1;
+ }
+ // choose edge2Before1
+ step.benefit = benefit;
+ step.beforeEdgeIdx = edge2Idx;
+ step.afterEdgeIdx = edge1Idx;
+ }
+ return true;
+ }
+
+ private boolean tryGetSuperset(long bitmap1, long bitmap2, List<Long> superset) {
+ if (LongBitmap.isSubset(bitmap1, bitmap2)) {
+ superset.add(bitmap2);
+ return true;
+ } else if (LongBitmap.isSubset(bitmap2, bitmap1)) {
+ superset.add(bitmap1);
+ return true;
+ }
+ return false;
+ }
+
+ private Edge constructEdge(long leftNodes, Edge edge, long rightNodes) {
+ LogicalJoin<? extends Plan, ? extends Plan> join;
+ if (graph.getJoinEdges().size() > 64 * 63 / 8) {
+ // If there are too many edges, it is advisable to return the "edge" directly
+ // to avoid lengthy enumeration time.
+ join = edge.getJoin();
+ } else {
+ BitSet connectionEdges = graph.findConnectionEdges(leftNodes, rightNodes);
+ List<Expression> hashConditions = connectionEdges.stream()
+ .mapToObj(i -> graph.getJoinEdge(i).getJoin().getHashJoinConjuncts())
+ .flatMap(Collection::stream)
+ .collect(Collectors.toList());
+ List<Expression> otherConditions = connectionEdges.stream()
+ .mapToObj(i -> graph.getJoinEdge(i).getJoin().getHashJoinConjuncts())
+ .flatMap(Collection::stream)
+ .collect(Collectors.toList());
+ join = edge.getJoin().withJoinConjuncts(hashConditions, otherConditions, null);
+ }
+
+ Edge newEdge = new Edge(join, edge.getIndex(), edge.getLeftChildEdges(), edge.getRightChildEdges(),
+ edge.getLeftSubtreeNodes(), edge.getRightSubtreeNodes(),
+ edge.getLeftRequiredNodes(), edge.getRightRequiredNodes());
+ newEdge.addLeftExtendNode(leftNodes);
+ newEdge.addRightExtendNode(rightNodes);
+ return newEdge;
+ }
+
+ private void deriveStats(Edge edge, long leftBitmap, long rightBitmap) {
+ // The bitmap may differ from the edge's reference slots.
+ // Taking into account the order: edge1<{1} - {2}> edge2<{1,3} - {4}>.
+ // Actually, we are considering the sequence {1,3} - {2} - {4}
+ long bitmap = LongBitmap.newBitmapUnion(leftBitmap, rightBitmap);
+ if (cacheStats.containsKey(bitmap)) {
+ return;
+ }
+ // Note the edge in graphSimplifier contains all tree nodes
+ Statistics joinStats = JoinEstimation
+ .estimate(cacheStats.get(leftBitmap),
+ cacheStats.get(rightBitmap), edge.getJoin());
+ cacheStats.put(bitmap, joinStats);
+ }
+
+ private double calCost(Edge edge, long leftBitmap, long rightBitmap) {
+ long bitmap = LongBitmap.newBitmapUnion(leftBitmap, rightBitmap);
+ Preconditions.checkArgument(cacheStats.containsKey(leftBitmap) && cacheStats.containsKey(rightBitmap)
+ && cacheStats.containsKey(bitmap),
+ "graph simplifier meet an edge %s that have not been derived stats", edge);
+ LogicalJoin<? extends Plan, ? extends Plan> join = edge.getJoin();
+ Statistics leftStats = cacheStats.get(leftBitmap);
+ Statistics rightStats = cacheStats.get(rightBitmap);
+ // Ensure base costs exist for left and right bitmaps. If missing, initialize
+ // with a default cost derived from row count to avoid null lookups.
+ if (!cacheCost.containsKey(leftBitmap) && leftStats != null) {
+ cacheCost.put(leftBitmap, Math.max(1.0, leftStats.getRowCount()));
+ }
+ if (!cacheCost.containsKey(rightBitmap) && rightStats != null) {
+ cacheCost.put(rightBitmap, Math.max(1.0, rightStats.getRowCount()));
+ }
+ double cost;
+ if (JoinUtils.shouldNestedLoopJoin(join)) {
+ cost = cacheCost.get(leftBitmap) + cacheCost.get(rightBitmap)
+ + rightStats.getRowCount() + 1 / leftStats.getRowCount();
+ } else {
+ cost = cacheCost.get(leftBitmap) + cacheCost.get(rightBitmap)
+ + (rightStats.getRowCount() + 1 / leftStats.getRowCount()) * 1.2;
+ }
+
+ if (!cacheCost.containsKey(bitmap) || cacheCost.get(bitmap) > cost) {
+ cacheCost.put(bitmap, cost);
+ }
+ return cost;
+ }
+
+ // --- Supporting classes ---
+
+ private @Nullable Edge threeLeftJoin(long bitmap1, Edge edge1, long bitmap2, Edge edge2, long bitmap3) {
+ // (plan1 edge1 plan2) edge2 plan3
+ // if the left and right is overlapping, just return null.
+ Preconditions.checkArgument(
+ cacheStats.containsKey(bitmap1) && cacheStats.containsKey(bitmap2) && cacheStats.containsKey(bitmap3));
+ // construct new Edge
+ long newLeft = LongBitmap.newBitmapUnion(bitmap1, bitmap2);
+ if (LongBitmap.isOverlap(newLeft, bitmap3)) {
+ return null;
+ }
+ Edge newEdge = constructEdge(newLeft, edge2, bitmap3);
+
+ deriveStats(edge1, bitmap1, bitmap2);
+ deriveStats(newEdge, newLeft, bitmap3);
+
+ calCost(edge1, bitmap1, bitmap2);
+
+ return newEdge;
+ }
+
+ private @Nullable Edge threeRightJoin(long bitmap1, Edge edge1, long bitmap2,
+ Edge edge2, long bitmap3) {
+ Preconditions.checkArgument(cacheStats.containsKey(bitmap1)
+ && cacheStats.containsKey(bitmap2) && cacheStats.containsKey(bitmap3));
+ // plan1 edge1 (plan2 edge2 plan3)
+ long newRight = LongBitmap.newBitmapUnion(bitmap2, bitmap3);
+ if (LongBitmap.isOverlap(bitmap1, newRight)) {
+ return null;
+ }
+ Edge newEdge = constructEdge(bitmap1, edge1, newRight);
+
+ deriveStats(edge2, bitmap2, bitmap3);
+ deriveStats(newEdge, bitmap1, newRight);
+
+ calCost(edge1, bitmap2, bitmap3);
+ return newEdge;
Review Comment:
π΄ **Bug #3: Wrong edge used for cost caching**
`threeRightJoin` computes `bitmap1 βedge1 (bitmap2 βedge2 bitmap3)`. The inner sub-join `(bitmap2 β bitmap3)` uses `edge2`, but cost is cached with `edge1`. Compare with `threeLeftJoin` which correctly uses the matching edge.
```suggestion
calCost(edge2, bitmap2, bitmap3);
```
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/HyperGraph.java:
##########
@@ -0,0 +1,549 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.nereids.jobs.joinorder.hypergraphv2;
+
+import org.apache.doris.common.Pair;
+import org.apache.doris.nereids.CascadesContext;
+import org.apache.doris.nereids.hint.DistributeHint;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.bitmap.LongBitmap;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.edge.Edge;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node.AbstractNode;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node.DPhyperNode;
+import org.apache.doris.nereids.memo.Group;
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.rules.expression.ExpressionRewriteContext;
+import org.apache.doris.nereids.trees.expressions.Alias;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.NamedExpression;
+import org.apache.doris.nereids.trees.expressions.Slot;
+import org.apache.doris.nereids.trees.plans.DistributeType;
+import org.apache.doris.nereids.trees.plans.JoinType;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
+import org.apache.doris.nereids.util.ExpressionUtils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Lists;
+import com.google.common.collect.Sets;
+
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.HashMap;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * The graph is a join graph, whose node is the leaf plan and edge is a join operator.
+ * It's used for join ordering
+ */
+public class HyperGraph {
+ // Long-> nodes collection; BitSet-> its containing edges. containing edges mean the edge's reference nodes
+ // is subset of nodes collection
+ private final Map<Long, BitSet> treeEdgesCache = new LinkedHashMap<>();
+ private final List<Edge> joinEdges;
+ private final List<AbstractNode> nodes;
+ private final List<NamedExpression> finalProjects;
+ private final Map<Long, List<NamedExpression>> nodeToLiteralAlias;
+ private final CascadesContext ctx;
+
+ HyperGraph(List<NamedExpression> finalProjects, List<Edge> joinEdges, List<AbstractNode> nodes,
+ Map<Long, List<NamedExpression>> nodeToLiteralAlias, CascadesContext ctx) {
+ this.finalProjects = ImmutableList.copyOf(finalProjects);
+ this.joinEdges = ImmutableList.copyOf(joinEdges);
+ this.nodes = ImmutableList.copyOf(nodes);
+ this.nodeToLiteralAlias = nodeToLiteralAlias;
+ this.ctx = ctx;
+ }
+
+ /**
+ * the project with alias and slot
+ */
+ public static boolean isValidProject(Plan plan) {
+ if (!(plan instanceof LogicalProject)) {
+ return false;
+ }
+ return ((LogicalProject<? extends Plan>) plan).getProjects().stream()
+ .allMatch(e -> e instanceof Slot || e instanceof Alias);
+ }
+
+ /**
+ * inner join group without mark slot
+ */
+ public static boolean isValidJoin(Plan plan) {
+ if (!(plan instanceof LogicalJoin)) {
+ return false;
+ }
+ LogicalJoin<?, ?> join = (LogicalJoin<?, ?>) plan;
+ return !join.isMarkJoin() && !join.isLeadingJoin() && !join.hasDistributeHint()
+ && !join.getJoinType().isAsofJoin();
+ }
+
+ public static Builder builderForDPhyper(Group group, CascadesContext ctx) {
+ return new Builder().buildHyperGraphForDPhyper(group, ctx);
+ }
+
+ public CascadesContext getCtx() {
+ return ctx;
+ }
+
+ public List<NamedExpression> getFinalProjects() {
+ return finalProjects;
+ }
+
+ public List<Edge> getJoinEdges() {
+ return joinEdges;
+ }
+
+ public List<AbstractNode> getNodes() {
+ return nodes;
+ }
+
+ public long getNodesMap() {
+ return LongBitmap.newBitmapBetween(0, nodes.size());
+ }
+
+ public Edge getJoinEdge(int index) {
+ return joinEdges.get(index);
+ }
+
+ public boolean hasLiteralAlias() {
+ return !nodeToLiteralAlias.isEmpty();
+ }
+
+ /**
+ * find all literal alias should be projected after left join right
+ */
+ public List<NamedExpression> getLiteralAlias(long left, long right) {
+ ImmutableList.Builder<NamedExpression> aliasList = ImmutableList.builder();
+ if (left == right) {
+ List<NamedExpression> namedExpressions = nodeToLiteralAlias.get(left);
+ if (namedExpressions != null) {
+ aliasList.addAll(namedExpressions);
+ nodeToLiteralAlias.remove(left);
+ }
Review Comment:
π΄ **Bug #4: Destructive removal breaks enumeration retry**
`nodeToLiteralAlias.remove(left)` permanently destroys this entry. When `JoinOrderJob.tryEnumerateJoin()` retries enumeration after `simplifyGraph()`, `PlanReceiver.reset()` clears DP tables but NOT this map. The second enumeration pass will miss literal alias projections.
Fix: read without mutating:
```suggestion
// Do not remove β map is reused across enumeration retries
```
Or make `getLiteralAlias` non-destructive by only using `get()` here.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/GraphSimplifier.java:
##########
@@ -0,0 +1,694 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.nereids.jobs.joinorder.hypergraphv2;
+
+import org.apache.doris.common.Pair;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.bitmap.LongBitmap;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.edge.Edge;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node.AbstractNode;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node.DPhyperNode;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.receiver.Counter;
+import org.apache.doris.nereids.stats.JoinEstimation;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.util.JoinUtils;
+import org.apache.doris.statistics.Statistics;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.Collection;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.List;
+import java.util.PriorityQueue;
+import java.util.stream.Collectors;
+import javax.annotation.Nullable;
+
+/**
+ * GraphSimplifier is used to simplify HyperGraph {@link HyperGraph}.
+ * <p>
+ * Related paper:
+ * - [Neu09] Neumann: βQuery Simplification: Graceful Degradation for Join-Order Optimizationβ.
+ * - [Rad19] Radke and Neumann: βLinDP++: Generalizing Linearized DP to Crossproducts and Non-Inner Joinsβ.
+ */
+public class GraphSimplifier {
+
+ private static int MAX_SIMPLIFICATION_STEPS = 1000000;
+ // It cached the plan stats in simplification. we don't store it in hyper graph,
+ // because it's just used for simulating join. In fact, the graph simplifier
+ // just generate the partial order of join operator.
+ private final HashMap<Long, Statistics> cacheStats = new HashMap<>();
+ private final HashMap<Long, Double> cacheCost = new HashMap<>();
+ private Deque<SimplificationStep> appliedSteps = new ArrayDeque<>();
+ private Deque<SimplificationStep> unAppliedSteps = new ArrayDeque<>();
+ private HyperGraph graph;
+ private CircleDetector cycles;
+ private List<BestSimplification> simplifications;
+ private PriorityQueue<BestSimplification> priorityQueue = new PriorityQueue<>();
+
+ /**
+ * Initializes the GraphSimplifier with the given hypergraph.
+ * Sets up join dependencies, simplifications, and caches.
+ *
+ * @param graph The hypergraph to simplify.
+ */
+ public GraphSimplifier(HyperGraph graph) {
+ this.graph = graph;
+ int edgeCount = graph.getJoinEdges().size();
+
+ // init join dependency
+ this.cycles = new CircleDetector(edgeCount);
+ extractJoinDependencies(cycles);
+
+ // init simplifications with empty values
+ this.simplifications = new ArrayList<>(edgeCount);
+ for (int i = 0; i < edgeCount; i++) {
+ simplifications.add(new BestSimplification());
+ }
+
+ // init cacheStats and cacheCost
+ for (AbstractNode node : graph.getNodes()) {
+ DPhyperNode dPhyperNode = (DPhyperNode) node;
+ cacheStats.put(node.getNodeMap(), dPhyperNode.getGroup().getStatistics());
+ cacheCost.put(node.getNodeMap(), dPhyperNode.getRowCount());
+ }
+
+ //
+ for (int edgeIdx = 0; edgeIdx < edgeCount; edgeIdx++) {
+ recalculateNeighbors(edgeIdx, edgeIdx + 1, edgeCount);
+ }
+ }
+
+ /**
+ * Checks if the hypergraph is joinable, ensuring all tables are connected via joins.
+ *
+ * @param graph The hypergraph to check.
+ * @param cycles The cycle detector for the graph.
+ * @return True if the graph is joinable, false otherwise.
+ */
+ private static boolean graphIsJoinable(HyperGraph graph, CircleDetector cycles) {
+ int nodeCount = graph.getNodes().size();
+ long[] components = new long[nodeCount];
+ int[] inComponent = new int[nodeCount];
+
+ for (int nodeIdx = 0; nodeIdx < nodeCount; nodeIdx++) {
+ components[nodeIdx] = LongBitmap.newBitmap(nodeIdx);
+ inComponent[nodeIdx] = nodeIdx;
+ }
+ return connectComponentsThroughJoins(graph, cycles, components, inComponent) == nodeCount;
+ }
+
+ /**
+ * Connects components in the hypergraph through join edges.
+ *
+ * @param graph The hypergraph to process.
+ * @param cycles The cycle detector for the graph.
+ * @param components Array representing connected components.
+ * @param inComponent Array mapping nodes to their components.
+ * @return The number of connected components.
+ */
+ private static int connectComponentsThroughJoins(
+ HyperGraph graph,
+ CircleDetector cycles,
+ long[] components,
+ int[] inComponent) {
+ int nodeCount = graph.getNodes().size();
+ int numInComponent = 1;
+ boolean didAnything;
+ int usedEdges = 0;
+ int edgeCount = cycles.getOrder().length;
+ do {
+ didAnything = false;
+ for (int edgeIdx : cycles.getOrder()) {
+ Edge e = graph.getJoinEdge(edgeIdx);
+ long rightNodes = e.getRightExtendedNodes();
+ int leftComponent = getComponent(components, inComponent, e.getLeftExtendedNodes());
+ if (leftComponent == -1) {
+ continue;
+ }
+ if (LongBitmap.isOverlap(rightNodes, components[leftComponent])) {
+ return -1;
+ }
+ int rightComponent = getComponent(components, inComponent, e.getRightExtendedNodes());
+ if (rightComponent == -1
+ || combiningWouldViolateConflictRules(e.getConflictRules(), inComponent, leftComponent,
+ rightComponent)) {
+ continue;
+ }
+
+ if (rightComponent < leftComponent) {
+ int tmp = leftComponent;
+ leftComponent = rightComponent;
+ rightComponent = tmp;
+ }
+ int numChanged = 0;
+ for (int tableIdx : LongBitmap.getIterator(components[rightComponent])) {
+ inComponent[tableIdx] = leftComponent;
+ ++numChanged;
+ }
+
+ long combinedNodes = components[leftComponent] | components[rightComponent];
+ components[leftComponent] = combinedNodes;
+ usedEdges++;
+ if (leftComponent == 0) {
+ numInComponent += numChanged;
+ if (numInComponent == nodeCount && usedEdges == edgeCount) {
+ return numInComponent;
+ }
+ }
+ didAnything = true;
+ }
+ } while (didAnything);
+ return numInComponent;
+ }
+
+ private static int getComponent(long[] components, int[] inComponent, long tables) {
+ if (tables == 0) {
+ return -1;
+ }
+ int idx = Long.numberOfTrailingZeros(tables);
+ int component = inComponent[idx];
+ if (component >= 0 && (tables & ~components[component]) == 0) {
+ return component;
+ }
+ return -1;
+ }
+
+ private static boolean combiningWouldViolateConflictRules(
+ List<Pair<Long, Long>> conflictRules,
+ int[] inComponent,
+ int leftComponent,
+ int rightComponent) {
+ for (Pair<Long, Long> cr : conflictRules) {
+ boolean applies = false;
+ for (int nodeIdx : LongBitmap.getIterator(cr.first)) {
+ if (inComponent[nodeIdx] == leftComponent
+ || inComponent[nodeIdx] == rightComponent) {
+ applies = true;
+ break;
+ }
+ }
+ if (applies) {
+ for (int nodeIdx : LongBitmap.getIterator(cr.second)) {
+ if (inComponent[nodeIdx] != leftComponent
+ && inComponent[nodeIdx] != rightComponent) {
+ return true;
+ }
+ }
+ }
+ }
+ return false;
+ }
+
+ private void extractJoinDependencies(CircleDetector circleDetector) {
+ int edgeCount = graph.getJoinEdges().size();
+ for (int i = 0; i < edgeCount; i++) {
+ Edge edge1 = graph.getJoinEdge(i);
+ for (int j = i + 1; j < edgeCount; j++) {
+ Edge edge2 = graph.getJoinEdge(j);
+ if (edge1.isSub(edge2)) {
+ Preconditions.checkArgument(circleDetector.addEdge(i, j),
+ "Edge %s violates Edge %s", edge1, edge2);
+ } else if (edge2.isSub(edge1)) {
+ Preconditions.checkArgument(circleDetector.addEdge(j, i),
+ "Edge %s violates Edge %s", edge2, edge1);
+ }
+ }
+ }
+ }
+
+ /**
+ * simplifyGraph
+ */
+ public boolean simplifyGraph(int limit) {
+ Preconditions.checkArgument(limit >= 1);
+ int lowerBound = 0;
+ int upperBound = 1;
+
+ // Try to probe the largest number of steps to satisfy the limit
+ Counter counter = new Counter(limit);
+ SubgraphEnumerator enumerator = new SubgraphEnumerator(counter, graph);
+ while (true) {
+ boolean hitUpperLimit = false;
+ while (numStepsDone() < upperBound) {
+ if (applySimplificationStep() == SimplificationResult.NO_SIMPLIFICATION_POSSIBLE) {
+ // If we have done all steps but still has more sub graphs
+ // Just return
+ if (!enumerator.enumerate()) {
+ return false;
+ }
+ upperBound = numStepsDone();
+ hitUpperLimit = true;
+ break;
+ }
+ }
+ if (hitUpperLimit) {
+ break;
+ }
+ if (enumerator.enumerate()) {
+ break;
+ }
+ lowerBound = upperBound;
+ upperBound *= 2;
+ if (upperBound > MAX_SIMPLIFICATION_STEPS) {
+ return false;
+ }
+ }
+
+ // Try to search the lowest number of steps to satisfy the limit
+ while (upperBound - lowerBound > 1) {
+ int mid = (upperBound + lowerBound) / 2;
+ applyStepsWithNum(mid);
+ if (enumerator.enumerate()) {
+ upperBound = mid;
+ } else {
+ lowerBound = mid;
+ }
+ }
+ applyStepsWithNum(upperBound);
+ if (!isTotalOrder()) {
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * Check whether all edge has been ordered
+ *
+ * @return if true, all edges has a total order
+ */
+ public boolean isTotalOrder() {
+ return cycles.getOrder().length == graph.getJoinEdges().size() && graphIsJoinable(graph, cycles);
+ }
+
+ private boolean unApplySimplificationStep() {
+ Preconditions.checkArgument(!appliedSteps.isEmpty(),
+ "try to unapply a simplification step but there is no step applied");
+ SimplificationStep bestStep = appliedSteps.poll();
+ unAppliedSteps.push(bestStep);
+ graph.modifyEdge(bestStep.afterEdgeIdx, bestStep.oldEdgeLeft, bestStep.oldEdgeRight);
+ // Note we don't need to delete this edge in circleDetector, because we don't need to
+ // recalculate neighbors until all steps applied
+ return true;
+ }
+
+ private void applyStepsWithNum(int num) {
+ while (appliedSteps.size() < num) {
+ SimplificationResult result = applySimplificationStep();
+ Preconditions.checkState(result != SimplificationResult.NO_SIMPLIFICATION_POSSIBLE);
+ }
+ while (appliedSteps.size() > num) {
+ unApplySimplificationStep();
+ }
+ }
+
+ public @Nullable Pair<Long, Long> getLastAppliedSteps() {
+ if (appliedSteps.isEmpty()) {
+ return null;
+ }
+ return Pair.of(appliedSteps.peek().newEdgeLeft, appliedSteps.peek().newEdgeRight);
+ }
+
+ public int numStepsDone() {
+ return appliedSteps.size();
+ }
+
+ public int numStepsUndone() {
+ return unAppliedSteps.size();
+ }
+
+ @VisibleForTesting
+ protected SimplificationResult applySimplificationStep() {
+ if (!unAppliedSteps.isEmpty()) {
+ SimplificationStep step = unAppliedSteps.poll();
+ graph.modifyEdge(step.afterEdgeIdx, step.newEdgeLeft, step.newEdgeRight);
+ appliedSteps.push(step);
+ return SimplificationResult.APPLIED_REDO_STEP;
+ }
+
+ BestSimplification cacheNode = priorityQueue.peek();
+ if (cacheNode == null) {
+ return SimplificationResult.NO_SIMPLIFICATION_POSSIBLE;
+ }
+ ProposedSimplificationStep bestStep = cacheNode.bestStep;
+ boolean forced = false;
+ if (cycles.edgeWouldCreateCycle(bestStep.beforeEdgeIdx, bestStep.afterEdgeIdx)) {
+ int tmp = bestStep.beforeEdgeIdx;
+ bestStep.beforeEdgeIdx = bestStep.afterEdgeIdx;
+ bestStep.afterEdgeIdx = tmp;
+ forced = true;
+ }
+
+ SimplificationStep fullStep = concretizeSimplificationStep(bestStep);
+
+ boolean added = cycles.addEdge(bestStep.beforeEdgeIdx, bestStep.afterEdgeIdx);
+ Preconditions.checkState(added, "Cycle detected");
+ graph.modifyEdge(bestStep.afterEdgeIdx, fullStep.newEdgeLeft, fullStep.newEdgeRight);
+
+ if (!graphIsJoinable(graph, cycles)) {
+ // Undo change
+ cycles.deleteEdge(bestStep.beforeEdgeIdx, bestStep.afterEdgeIdx);
+ graph.modifyEdge(bestStep.afterEdgeIdx, fullStep.oldEdgeLeft, fullStep.oldEdgeRight);
+
+ // Insert opposite constraint and try again
+ if (!cycles.addEdge(fullStep.afterEdgeIdx, fullStep.beforeEdgeIdx)) {
+ priorityQueue.poll();
+ cacheNode.isInPriorityQueue = false;
+ }
+ return applySimplificationStep();
+ }
+ recalculateNeighbors(bestStep.afterEdgeIdx, 0, graph.getJoinEdges().size());
+ appliedSteps.push(fullStep);
+ return forced ? SimplificationResult.APPLIED_NOOP : SimplificationResult.APPLIED_SIMPLIFICATION;
+ }
+
+ private void updatePQ(int edgeIdx) {
+ BestSimplification cacheNode = simplifications.get(edgeIdx);
+ Preconditions.checkState(!Double.isNaN(cacheNode.bestStep.benefit), "bestStep has invalid benefit value");
+ if (!cacheNode.isInPriorityQueue) {
+ if (cacheNode.bestNeighbor != -1) {
+ priorityQueue.add(cacheNode);
+ cacheNode.isInPriorityQueue = true;
+ }
+ } else {
+ if (cacheNode.bestNeighbor == -1) {
+ priorityQueue.remove(cacheNode);
+ cacheNode.isInPriorityQueue = false;
+ }
+ }
+ }
+
+ private void recalculateNeighbors(int edge1Idx, int begin, int end) {
+ for (int edge2Idx = begin; edge2Idx < Math.min(edge1Idx, end); edge2Idx++) {
+ BestSimplification otherCache = simplifications.get(edge2Idx);
+ ProposedSimplificationStep step = new ProposedSimplificationStep();
+ if (edgesAreNeighboring(edge2Idx, edge1Idx, step)) {
+ if (otherCache.bestNeighbor == -1 || step.benefit >= otherCache.bestStep.benefit) {
+ otherCache.bestNeighbor = edge1Idx;
+ otherCache.bestStep = step;
+ updatePQ(edge2Idx);
+ continue;
+ }
+ }
+ if (otherCache.bestNeighbor == edge1Idx) {
+ recalculateNeighbors(edge2Idx, 0, graph.getJoinEdges().size());
+ }
+ }
+ BestSimplification cacheNode = simplifications.get(edge1Idx);
+ cacheNode.bestNeighbor = -1;
+ cacheNode.bestStep.benefit = Double.NEGATIVE_INFINITY;
+ for (int edge2Idx = Math.max(begin, edge1Idx + 1); edge2Idx < end; edge2Idx++) {
+ ProposedSimplificationStep step = new ProposedSimplificationStep();
+ if (edgesAreNeighboring(edge1Idx, edge2Idx, step)) {
+ if (cacheNode.bestNeighbor == -1 || step.benefit > cacheNode.bestStep.benefit) {
+ cacheNode.bestNeighbor = edge2Idx;
+ cacheNode.bestStep = step;
+ }
+ }
+ }
+ updatePQ(edge1Idx);
+ }
+
+ private boolean edgesAreNeighboring(int edge1Idx, int edge2Idx, ProposedSimplificationStep step) {
+ Edge edge1 = graph.getJoinEdge(edge1Idx);
+ Edge edge2 = graph.getJoinEdge(edge2Idx);
+ if (edge1.isSub(edge2) || edge2.isSub(edge1)) {
+ return false;
+ }
+ long left1 = edge1.getLeftExtendedNodes();
+ long right1 = edge1.getRightExtendedNodes();
+ long left2 = edge2.getLeftExtendedNodes();
+ long right2 = edge2.getRightExtendedNodes();
+ if (!cacheStats.containsKey(left1) || !cacheStats.containsKey(right1)
+ || !cacheStats.containsKey(left2) || !cacheStats.containsKey(right2)) {
+ return false;
+ }
+ Edge edge1Before2;
+ Edge edge2Before1;
+ List<Long> superBitset = new ArrayList<>();
+ if (tryGetSuperset(left1, left2, superBitset)) {
+ // (common Join1 right1) Join2 right2
+ edge1Before2 = threeLeftJoin(superBitset.get(0), edge1, right1, edge2, right2);
+ // (common Join2 right2) Join1 right1
+ edge2Before1 = threeLeftJoin(superBitset.get(0), edge2, right2, edge1, right1);
+ } else if (tryGetSuperset(left1, right2, superBitset)) {
+ // left2 Join2 (common Join1 right1)
+ edge1Before2 = threeRightJoin(left2, edge2, superBitset.get(0), edge1, right1);
+ // (left2 Join2 common) join1 right1
+ edge2Before1 = threeLeftJoin(left2, edge2, superBitset.get(0), edge1, right1);
+ } else if (tryGetSuperset(right1, left2, superBitset)) {
+ // (left1 Join1 common) Join2 right2
+ edge1Before2 = threeLeftJoin(left1, edge1, superBitset.get(0), edge2, right2);
+ // left1 Join1 (common Join2 right2)
+ edge2Before1 = threeRightJoin(left1, edge1, superBitset.get(0), edge2, right2);
+ } else if (tryGetSuperset(right1, right2, superBitset)) {
+ // left2 Join2 (left1 Join1 common)
+ edge1Before2 = threeRightJoin(left2, edge2, left1, edge1, superBitset.get(0));
+ // left1 Join1 (left2 Join2 common)
+ edge2Before1 = threeRightJoin(left1, edge1, left2, edge2, superBitset.get(0));
+ } else {
+ return false;
+ }
+
+ if (edge1Before2 == null || edge2Before1 == null) {
+ return false;
+ }
+
+ double cost1Before2 = calCost(edge1Before2,
+ edge1Before2.getLeftExtendedNodes(), edge1Before2.getRightExtendedNodes());
+ double cost2Before1 = calCost(edge2Before1,
+ edge2Before1.getLeftExtendedNodes(), edge2Before1.getRightExtendedNodes());
+ double benefit = Double.MAX_VALUE;
+ // Choose the plan with smaller cost and make the simplification step to replace the old edge by it.
+ if (cost1Before2 < cost2Before1) {
+ if (cost1Before2 != 0) {
+ benefit = cost2Before1 / cost1Before2;
+ }
+ // choose edge1Before2
+ step.benefit = benefit;
+ step.beforeEdgeIdx = edge1Idx;
+ step.afterEdgeIdx = edge2Idx;
+ } else {
+ if (cost2Before1 != 0) {
+ benefit = cost1Before2 / cost2Before1;
+ }
+ // choose edge2Before1
+ step.benefit = benefit;
+ step.beforeEdgeIdx = edge2Idx;
+ step.afterEdgeIdx = edge1Idx;
+ }
+ return true;
+ }
+
+ private boolean tryGetSuperset(long bitmap1, long bitmap2, List<Long> superset) {
+ if (LongBitmap.isSubset(bitmap1, bitmap2)) {
+ superset.add(bitmap2);
+ return true;
+ } else if (LongBitmap.isSubset(bitmap2, bitmap1)) {
+ superset.add(bitmap1);
+ return true;
+ }
+ return false;
+ }
+
+ private Edge constructEdge(long leftNodes, Edge edge, long rightNodes) {
+ LogicalJoin<? extends Plan, ? extends Plan> join;
+ if (graph.getJoinEdges().size() > 64 * 63 / 8) {
+ // If there are too many edges, it is advisable to return the "edge" directly
+ // to avoid lengthy enumeration time.
+ join = edge.getJoin();
+ } else {
+ BitSet connectionEdges = graph.findConnectionEdges(leftNodes, rightNodes);
+ List<Expression> hashConditions = connectionEdges.stream()
+ .mapToObj(i -> graph.getJoinEdge(i).getJoin().getHashJoinConjuncts())
+ .flatMap(Collection::stream)
+ .collect(Collectors.toList());
+ List<Expression> otherConditions = connectionEdges.stream()
+ .mapToObj(i -> graph.getJoinEdge(i).getJoin().getHashJoinConjuncts())
+ .flatMap(Collection::stream)
+ .collect(Collectors.toList());
+ join = edge.getJoin().withJoinConjuncts(hashConditions, otherConditions, null);
+ }
+
+ Edge newEdge = new Edge(join, edge.getIndex(), edge.getLeftChildEdges(), edge.getRightChildEdges(),
+ edge.getLeftSubtreeNodes(), edge.getRightSubtreeNodes(),
+ edge.getLeftRequiredNodes(), edge.getRightRequiredNodes());
+ newEdge.addLeftExtendNode(leftNodes);
+ newEdge.addRightExtendNode(rightNodes);
+ return newEdge;
+ }
+
+ private void deriveStats(Edge edge, long leftBitmap, long rightBitmap) {
+ // The bitmap may differ from the edge's reference slots.
+ // Taking into account the order: edge1<{1} - {2}> edge2<{1,3} - {4}>.
+ // Actually, we are considering the sequence {1,3} - {2} - {4}
+ long bitmap = LongBitmap.newBitmapUnion(leftBitmap, rightBitmap);
+ if (cacheStats.containsKey(bitmap)) {
+ return;
+ }
+ // Note the edge in graphSimplifier contains all tree nodes
+ Statistics joinStats = JoinEstimation
+ .estimate(cacheStats.get(leftBitmap),
+ cacheStats.get(rightBitmap), edge.getJoin());
+ cacheStats.put(bitmap, joinStats);
+ }
+
+ private double calCost(Edge edge, long leftBitmap, long rightBitmap) {
+ long bitmap = LongBitmap.newBitmapUnion(leftBitmap, rightBitmap);
+ Preconditions.checkArgument(cacheStats.containsKey(leftBitmap) && cacheStats.containsKey(rightBitmap)
+ && cacheStats.containsKey(bitmap),
+ "graph simplifier meet an edge %s that have not been derived stats", edge);
+ LogicalJoin<? extends Plan, ? extends Plan> join = edge.getJoin();
+ Statistics leftStats = cacheStats.get(leftBitmap);
+ Statistics rightStats = cacheStats.get(rightBitmap);
+ // Ensure base costs exist for left and right bitmaps. If missing, initialize
+ // with a default cost derived from row count to avoid null lookups.
+ if (!cacheCost.containsKey(leftBitmap) && leftStats != null) {
+ cacheCost.put(leftBitmap, Math.max(1.0, leftStats.getRowCount()));
+ }
+ if (!cacheCost.containsKey(rightBitmap) && rightStats != null) {
+ cacheCost.put(rightBitmap, Math.max(1.0, rightStats.getRowCount()));
+ }
+ double cost;
+ if (JoinUtils.shouldNestedLoopJoin(join)) {
+ cost = cacheCost.get(leftBitmap) + cacheCost.get(rightBitmap)
+ + rightStats.getRowCount() + 1 / leftStats.getRowCount();
+ } else {
Review Comment:
π‘ **Bug #8: Operator precedence + potential NPE/Infinity**
1. `1 / leftStats.getRowCount()` evaluates as the reciprocal due to operator precedence. Likely intended: `(rightRows + 1) / leftRows` or `rightRows + leftRows`.
2. If `leftStats.getRowCount() == 0`, this produces `Infinity`.
3. If `cacheCost.get(leftBitmap)` returns `null` (stats were null during init), auto-unboxing throws NPE.
Consider using `getOrDefault` and clarifying the formula:
```java
double leftCost = cacheCost.getOrDefault(leftBitmap, 1.0);
double rightCost = cacheCost.getOrDefault(rightBitmap, 1.0);
cost = leftCost + rightCost + rightRows + leftRows;
```
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/HyperGraph.java:
##########
@@ -0,0 +1,549 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.nereids.jobs.joinorder.hypergraphv2;
+
+import org.apache.doris.common.Pair;
+import org.apache.doris.nereids.CascadesContext;
+import org.apache.doris.nereids.hint.DistributeHint;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.bitmap.LongBitmap;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.edge.Edge;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node.AbstractNode;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node.DPhyperNode;
+import org.apache.doris.nereids.memo.Group;
+import org.apache.doris.nereids.memo.GroupExpression;
+import org.apache.doris.nereids.rules.expression.ExpressionRewriteContext;
+import org.apache.doris.nereids.trees.expressions.Alias;
+import org.apache.doris.nereids.trees.expressions.Expression;
+import org.apache.doris.nereids.trees.expressions.NamedExpression;
+import org.apache.doris.nereids.trees.expressions.Slot;
+import org.apache.doris.nereids.trees.plans.DistributeType;
+import org.apache.doris.nereids.trees.plans.JoinType;
+import org.apache.doris.nereids.trees.plans.Plan;
+import org.apache.doris.nereids.trees.plans.logical.LogicalJoin;
+import org.apache.doris.nereids.trees.plans.logical.LogicalProject;
+import org.apache.doris.nereids.util.ExpressionUtils;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Lists;
+import com.google.common.collect.Sets;
+
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.HashMap;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * The graph is a join graph, whose node is the leaf plan and edge is a join operator.
+ * It's used for join ordering
+ */
+public class HyperGraph {
+ // Long-> nodes collection; BitSet-> its containing edges. containing edges mean the edge's reference nodes
+ // is subset of nodes collection
+ private final Map<Long, BitSet> treeEdgesCache = new LinkedHashMap<>();
+ private final List<Edge> joinEdges;
+ private final List<AbstractNode> nodes;
+ private final List<NamedExpression> finalProjects;
+ private final Map<Long, List<NamedExpression>> nodeToLiteralAlias;
+ private final CascadesContext ctx;
+
+ HyperGraph(List<NamedExpression> finalProjects, List<Edge> joinEdges, List<AbstractNode> nodes,
+ Map<Long, List<NamedExpression>> nodeToLiteralAlias, CascadesContext ctx) {
+ this.finalProjects = ImmutableList.copyOf(finalProjects);
+ this.joinEdges = ImmutableList.copyOf(joinEdges);
+ this.nodes = ImmutableList.copyOf(nodes);
+ this.nodeToLiteralAlias = nodeToLiteralAlias;
+ this.ctx = ctx;
+ }
+
+ /**
+ * the project with alias and slot
+ */
+ public static boolean isValidProject(Plan plan) {
+ if (!(plan instanceof LogicalProject)) {
+ return false;
+ }
+ return ((LogicalProject<? extends Plan>) plan).getProjects().stream()
+ .allMatch(e -> e instanceof Slot || e instanceof Alias);
+ }
+
+ /**
+ * inner join group without mark slot
+ */
+ public static boolean isValidJoin(Plan plan) {
+ if (!(plan instanceof LogicalJoin)) {
+ return false;
+ }
+ LogicalJoin<?, ?> join = (LogicalJoin<?, ?>) plan;
+ return !join.isMarkJoin() && !join.isLeadingJoin() && !join.hasDistributeHint()
+ && !join.getJoinType().isAsofJoin();
+ }
+
+ public static Builder builderForDPhyper(Group group, CascadesContext ctx) {
+ return new Builder().buildHyperGraphForDPhyper(group, ctx);
+ }
+
+ public CascadesContext getCtx() {
+ return ctx;
+ }
+
+ public List<NamedExpression> getFinalProjects() {
+ return finalProjects;
+ }
+
+ public List<Edge> getJoinEdges() {
+ return joinEdges;
+ }
+
+ public List<AbstractNode> getNodes() {
+ return nodes;
+ }
+
+ public long getNodesMap() {
+ return LongBitmap.newBitmapBetween(0, nodes.size());
+ }
+
+ public Edge getJoinEdge(int index) {
+ return joinEdges.get(index);
+ }
+
+ public boolean hasLiteralAlias() {
+ return !nodeToLiteralAlias.isEmpty();
+ }
+
+ /**
+ * find all literal alias should be projected after left join right
+ */
+ public List<NamedExpression> getLiteralAlias(long left, long right) {
+ ImmutableList.Builder<NamedExpression> aliasList = ImmutableList.builder();
+ if (left == right) {
+ List<NamedExpression> namedExpressions = nodeToLiteralAlias.get(left);
+ if (namedExpressions != null) {
+ aliasList.addAll(namedExpressions);
+ nodeToLiteralAlias.remove(left);
+ }
+ } else {
+ long nodes = LongBitmap.newBitmapUnion(left, right);
+ for (Map.Entry<Long, List<NamedExpression>> entry : nodeToLiteralAlias.entrySet()) {
+ if (!LongBitmap.isSubset(entry.getKey(), left) && !LongBitmap.isSubset(entry.getKey(), right)
+ && LongBitmap.isSubset(entry.getKey(), nodes)) {
+ aliasList.addAll(entry.getValue());
+ }
+ }
+ }
+ return aliasList.build();
+ }
+
+ // find edges to connect left and right node
+ public BitSet findConnectionEdges(long left, long right) {
+ BitSet operatorEdgesMap = new BitSet();
+ operatorEdgesMap.or(getEdgesInTree(LongBitmap.or(left, right)));
+ operatorEdgesMap.andNot(getEdgesInTree(left));
+ operatorEdgesMap.andNot(getEdgesInTree(right));
+ return operatorEdgesMap;
+ }
+
+ /**
+ * Returns all edges in the tree
+ */
+ private BitSet getEdgesInTree(long treeNodesMap) {
+ if (!treeEdgesCache.containsKey(treeNodesMap)) {
+ BitSet edgesMap = new BitSet();
+ for (Edge edge : joinEdges) {
+ if (LongBitmap.isSubset(edge.getReferenceNodes(), treeNodesMap)) {
+ edgesMap.set(edge.getIndex());
+ }
+ }
+ treeEdgesCache.put(treeNodesMap, edgesMap);
+ }
+ return treeEdgesCache.get(treeNodesMap);
+ }
+
+ /**
+ * Graph simplifier need to update the edge for join ordering
+ *
+ * @param edgeIndex The index of updated edge
+ * @param newLeft The new left of updated edge
+ * @param newRight The new right of update edge
+ */
+ public void modifyEdge(int edgeIndex, long newLeft, long newRight) {
+ // When modify an edge in hyper graph, we need to update the left and right nodes
+ // For these nodes that are only in the old edge, we need remove the edge from them
+ // For these nodes that are only in the new edge, we need to add the edge to them
+ Edge edge = joinEdges.get(edgeIndex);
+ if (treeEdgesCache.containsKey(edge.getReferenceNodes())) {
+ treeEdgesCache.get(edge.getReferenceNodes()).set(edgeIndex, false);
+ }
+ joinEdges.get(edgeIndex).setLeftExtendedNodes(newLeft);
+ joinEdges.get(edgeIndex).setRightExtendedNodes(newRight);
+ if (treeEdgesCache.containsKey(edge.getReferenceNodes())) {
+ treeEdgesCache.get(edge.getReferenceNodes()).set(edgeIndex, true);
+ }
+ }
+
+ /**
+ * For the given hyperGraph, make a textual representation in the form
+ * of a dotty graph. You can save this to a file and then use Graphviz
+ * to render this it a graphical representation of the hyperGraph for
+ * easier debugging, e.g. like this:
+ * <p>
+ * dot -Tps graph.dot > graph.ps
+ * display graph.ps
+ */
+ public String toDottyHyperGraph() {
+ StringBuilder builder = new StringBuilder();
+ builder.append(String.format("digraph G { # %d edges%n", joinEdges.size()));
+ List<String> graphvisNodes = new ArrayList<>();
+ for (AbstractNode node : nodes) {
+ String nodeName = node.getName();
+ // nodeID is used to identify the node with the same name
+ String nodeID = nodeName;
+ while (graphvisNodes.contains(nodeID)) {
+ nodeID += "_";
+ }
+ double rowCount = (node instanceof DPhyperNode) ? ((DPhyperNode) node).getRowCount() : -1;
+ builder.append(String.format(" %s [label=\"%s %n rowCount=%.2f\"];%n", nodeID, nodeName, rowCount));
+ graphvisNodes.add(nodeName);
+ }
+ for (int i = 0; i < joinEdges.size(); i += 1) {
+ Edge edge = joinEdges.get(i);
+ // TODO: add cardinality to label
+ String label = String.format("%.2f", edge.getSelectivity());
+ if (joinEdges.get(i).isSimple()) {
+ String arrowHead = "";
+ if (edge.getJoin().getJoinType() == JoinType.INNER_JOIN) {
+ arrowHead = ",arrowhead=none";
+ }
+
+ int leftIndex = LongBitmap.lowestOneIndex(edge.getLeftExtendedNodes());
+ int rightIndex = LongBitmap.lowestOneIndex(edge.getRightExtendedNodes());
+ builder.append(String.format("%s -> %s [label=\"%s\"%s]%n", graphvisNodes.get(leftIndex),
+ graphvisNodes.get(rightIndex), label, arrowHead));
+ } else {
+ // Hyper edge is considered as a tiny virtual node
+ builder.append(String.format("e%d [shape=circle, width=.001, label=\"\"]%n", i));
+
+ String leftLabel = "";
+ String rightLabel = "";
+ if (LongBitmap.getCardinality(edge.getLeftExtendedNodes()) == 1) {
+ rightLabel = label;
+ } else {
+ leftLabel = label;
+ }
+
+ String finalLeftLabel = leftLabel;
+ for (int nodeIndex : LongBitmap.getIterator(edge.getLeftExtendedNodes())) {
+ builder.append(
+ String.format("%s -> e%d [arrowhead=none, label=\"%s\"]%n", graphvisNodes.get(nodeIndex), i,
+ finalLeftLabel));
+ }
+
+ String finalRightLabel = rightLabel;
+ for (int nodeIndex : LongBitmap.getIterator(edge.getRightExtendedNodes())) {
+ builder.append(
+ String.format("%s -> e%d [arrowhead=none, label=\"%s\"]%n", graphvisNodes.get(nodeIndex), i,
+ finalRightLabel));
+ }
+ }
+ }
+ builder.append("}\n");
+ return builder.toString();
+ }
+
+ /**
+ * Builder of HyperGraph
+ */
+ public static class Builder {
+ private final List<Edge> joinEdges = new ArrayList<>();
+ private final List<AbstractNode> nodes = new ArrayList<>();
+ // Key: hyper node's output slots, the slots come from simple slotReference or Alias
+ // value: the long bitmap value representing hyper node(simple node or joined nodes)
+ // addDPHyperNode method add slots from simple node
+ // addAlias method add slots from both simple node and joined nodes, depending on the alias's input slots
+ private final HashMap<Slot, Long> slotToHyperNodeMap = new LinkedHashMap<>();
+
+ private final Map<Long, List<NamedExpression>> nodeToLiteralAlias = new LinkedHashMap<>();
+
+ private Set<Slot> finalOutputs;
+
+ private CascadesContext ctx;
+
+ private ExpressionRewriteContext expressionRewriteCtx;
+
+ private Map<Slot, Expression> aliasReplaceMap = new LinkedHashMap<>();
+
+ private List<NamedExpression> finalProjects = new ArrayList<>();
+
+ private long nonInnerJoinedNodes = 0;
+
+ public List<AbstractNode> getNodes() {
+ return nodes;
+ }
+
+ private Builder buildHyperGraphForDPhyper(Group group, CascadesContext ctx) {
+ this.ctx = ctx;
+ this.expressionRewriteCtx = new ExpressionRewriteContext(ctx);
+ finalOutputs = group.getLogicalProperties().getOutputSet();
+ this.buildForDPhyper(group.getLogicalExpression());
+ for (Slot slot : finalOutputs) {
+ Expression expression = aliasReplaceMap.get(slot);
+ if (expression != null) {
+ finalProjects.add(new Alias(slot.getExprId(), expression, slot.getName()));
+ } else {
+ finalProjects.add(slot);
+ }
+ }
+ return this;
+ }
+
+ public HyperGraph build() {
+ return new HyperGraph(finalProjects, joinEdges, nodes, nodeToLiteralAlias, ctx);
+ }
+
+ public void updateNode(int idx, Group group) {
+ Preconditions.checkArgument(nodes.get(idx) instanceof DPhyperNode);
+ nodes.set(idx, ((DPhyperNode) nodes.get(idx)).withGroup(group));
+ }
+
+ /**
+ * Build Graph for DPhyper in bottom-up way, it means build node first, then edges
+ *
+ * @param groupExpression the groupExpression contains root plan node of this join cluster
+ * @return BitSet is the latest join edges' index in joinEdges, Long is all the subtree nodes of the
+ * latest join edges index
+ */
+ private Pair<BitSet, Long> buildForDPhyper(GroupExpression groupExpression) {
+ // process Project
+ if (isValidProject(groupExpression.getPlan())) {
+ LogicalProject<?> project = (LogicalProject<?>) groupExpression.getPlan();
+ Pair<BitSet, Long> res = buildForDPhyper(groupExpression.child(0).getLogicalExpressions().get(0));
+ for (NamedExpression expr : project.getProjects()) {
+ if (expr instanceof Alias) {
+ this.addAlias((Alias) expr, res.second);
+ }
+ }
+ return res;
+ }
+
+ // process Join
+ if (isValidJoin(groupExpression.getPlan())) {
+ LogicalJoin<?, ?> join = (LogicalJoin<?, ?>) groupExpression.getPlan();
+ Pair<BitSet, Long> left = buildForDPhyper(groupExpression.child(0).getLogicalExpressions().get(0));
+ Pair<BitSet, Long> right = buildForDPhyper(groupExpression.child(1).getLogicalExpressions().get(0));
+ return Pair.of(this.addJoin(join, left, right), LongBitmap.or(left.second, right.second));
+ }
+
+ // process Other Node
+ int idx = this.addDPHyperNode(groupExpression.getOwnerGroup());
+ return Pair.of(new BitSet(), LongBitmap.newBitmap(idx));
+ }
+
+ /**
+ * Store the relation between Alias Slot and Original Slot and its expression
+ * e.g.,
+ * a = b
+ * |--- project((c + d) as b)
+ * <p>
+ * a = b
+ * |--- project((c + 1) as b)
+ *
+ * @param alias The alias Expression in project Operator
+ */
+ public boolean addAlias(Alias alias, long subTreeNodes) {
+ Slot aliasSlot = alias.toSlot();
+ if (slotToHyperNodeMap.containsKey(aliasSlot)) {
+ return true;
+ }
+ long bitmap = LongBitmap.newBitmap();
+ // find the nodes produce the input slots, the nodes is subset of subTreeNodes
+ for (Slot slot : alias.getInputSlots()) {
+ bitmap = LongBitmap.or(bitmap, slotToHyperNodeMap.get(slot));
+ }
+ // The case hit when there are some constant aliases such as:
+ // select * from t1 join (
+ // select *, 1 as b1 from t2)
+ // on t1.b = b1
+ // just reference them all for this slot
+ boolean addToReplaceMap = true;
+ if (bitmap == 0) {
+ bitmap = subTreeNodes;
+ addToReplaceMap = false;
+ List<NamedExpression> aliasList = nodeToLiteralAlias.get(bitmap);
+ if (aliasList == null) {
+ aliasList = new ArrayList<>(1);
+ nodeToLiteralAlias.put(bitmap, aliasList);
+ }
+ aliasList.add(alias);
+ }
+ Preconditions.checkArgument(bitmap > 0, "slot must belong to some table");
+ slotToHyperNodeMap.put(aliasSlot, bitmap);
+ alias = (Alias) ExpressionUtils.replaceNameExpression(alias, aliasReplaceMap);
+ if (addToReplaceMap) {
+ aliasReplaceMap.put(aliasSlot, alias.child());
+ }
+ return true;
+ }
+
+ /**
+ * add end node to HyperGraph
+ *
+ * @param group The group that is the end node in graph
+ * @return return the node index
+ */
+ private int addDPHyperNode(Group group) {
+ for (Slot slot : group.getLogicalExpression().getPlan().getOutput()) {
+ slotToHyperNodeMap.put(slot, LongBitmap.newBitmap(nodes.size()));
+ }
+ nodes.add(new DPhyperNode(nodes.size(), group));
+ return nodes.size() - 1;
+ }
+
+ private long calReferencedNodesBySlots(Set<Slot> slots) {
+ long bitmap = LongBitmap.newBitmap();
+ for (Slot slot : slots) {
+ Preconditions.checkArgument(slotToHyperNodeMap.containsKey(slot));
+ bitmap = LongBitmap.or(bitmap, slotToHyperNodeMap.get(slot));
+ }
+ return bitmap;
+ }
+
+ /**
+ * try to add edge for join group ( only works for inner join!!! )
+ * 1. consider original join node's conjuncts:
+ * inner join conjuncts: t1.a = t2.a and t1.b = t3.b
+ * 2. extract join conjuncts:
+ * nodeToConjuncts contains 2 elements : (t1 and t2, t1.a = t2.a), (t1 and t3, t1.b = t3.b)
+ * 3. based on nodeToConjuncts, create 2 new join node and edge:
+ * inner join1 : t1.a = t2.a
+ * inner join2 : t1.b = t3.b
+ *
+ * @param join The join plan
+ * @param leftChildEdgeNodes first level left child edges and all nodes in the left tree
+ * @param rightChildEdgeNodes first level right child edges and all nodes in the right tree
+ * @return BitSet indicate the join edges' index in joinEdges produced by @param join
+ */
+ private BitSet addJoin(LogicalJoin<?, ?> join, Pair<BitSet, Long> leftChildEdgeNodes,
+ Pair<BitSet, Long> rightChildEdgeNodes) {
+ // the join conjuncts may only use subset of leftNodes and rightNodes
+ // extract inner join conjuncts to requiredNodesToConjuncts map
+ // requiredNodesToConjuncts:
+ // Pair<Long, Long> -> [leftNodes, rightNodes] only contains conjuncts' input slots referenced nodes
+ // Pair<List<Expression>, List<Expression>> -> [hashConjuncts, otherConjuncts]
+ long leftSubtreeNodes = leftChildEdgeNodes.second;
+ long rightSubtreeNodes = rightChildEdgeNodes.second;
+ Map<Pair<Long, Long>, Pair<List<Expression>, List<Expression>>> requiredNodesToConjuncts =
+ new LinkedHashMap<>();
+ if (join.getExpressions().isEmpty()) {
+ return addCrossJoin(join, leftChildEdgeNodes, rightChildEdgeNodes);
+ } else {
+ Pair<Long, Long> ends = calculateEndsBySlots(join.getInputSlots(), leftSubtreeNodes, rightSubtreeNodes);
+ if (join.getJoinType().isInnerJoin()) {
+ // we split inner join conjuncts if the ends touch no nonInnerJoinedNodes;
+ if (LongBitmap.isOverlap(nonInnerJoinedNodes, ends.first) || LongBitmap.isOverlap(
+ nonInnerJoinedNodes, ends.second)) {
+ requiredNodesToConjuncts.put(ends,
+ Pair.of(join.getHashJoinConjuncts(), join.getOtherJoinConjuncts()));
+ } else {
+ // split join conjuncts to edges
+ for (Expression expression : join.getHashJoinConjuncts()) {
+ ends = calculateEndsBySlots(expression.getInputSlots(), leftSubtreeNodes,
+ rightSubtreeNodes);
+ if (!requiredNodesToConjuncts.containsKey(ends)) {
+ requiredNodesToConjuncts.put(ends, Pair.of(new ArrayList<>(), new ArrayList<>()));
+ }
+ requiredNodesToConjuncts.get(ends).first.add(expression);
+ }
+ for (Expression expression : join.getOtherJoinConjuncts()) {
+ ends = calculateEndsBySlots(expression.getInputSlots(), leftSubtreeNodes,
+ rightSubtreeNodes);
+ if (!requiredNodesToConjuncts.containsKey(ends)) {
+ requiredNodesToConjuncts.put(ends, Pair.of(new ArrayList<>(), new ArrayList<>()));
+ }
+ requiredNodesToConjuncts.get(ends).second.add(expression);
+ }
+ }
+ } else {
+ nonInnerJoinedNodes = LongBitmap.or(leftSubtreeNodes, rightSubtreeNodes);
+ requiredNodesToConjuncts.put(ends,
Review Comment:
π‘ **Bug #10: Overwrites instead of accumulates**
Should use `|=` to accumulate non-inner-joined nodes across sibling subtrees. E.g., for `INNER(LEFT(T1,T2), LEFT(T3,T4))`, processing the second LEFT loses T1,T2 tracking.
```suggestion
nonInnerJoinedNodes |= LongBitmap.or(leftSubtreeNodes, rightSubtreeNodes);
```
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/SubgraphEnumerator.java:
##########
@@ -0,0 +1,559 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.nereids.jobs.joinorder.hypergraphv2;
+
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.bitmap.LongBitmap;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.bitmap.LongBitmapSubsetIterator;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.edge.Edge;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node.AbstractNode;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node.DPhyperNode;
+import org.apache.doris.nereids.jobs.joinorder.hypergraphv2.receiver.AbstractReceiver;
+import org.apache.doris.qe.ConnectContext;
+
+import com.google.common.base.Preconditions;
+import org.apache.logging.log4j.LogManager;
+import org.apache.logging.log4j.Logger;
+
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.stream.Collectors;
+
+/**
+ * HyperGraph Join Reorder Enumerator.
+ * <p>
+ * This class implements a join reordering algorithm based on HyperGraph, inspired by the papers:
+ * <ul>
+ * <li>"Dynamic Programming Strikes Back"</li>
+ * <li>"Build Query Optimizer"</li>
+ * </ul>
+ * The core idea is to model tables and join relationships in a query as a hypergraph, then enumerate all
+ * possible join orders by recursively generating all connected subgraphs (CSG) and their complements (CMP),
+ * and recording/pruning them using a DP table (receiver).
+ * <br>
+ * Key concepts:
+ * <ul>
+ * <li><b>CSG (Connected SubGraph):</b> A connected subgraph in the hypergraph, representing a set of tables
+ * that can be joined together.</li>
+ * <li><b>CMP (Complement SubGraph):</b> The complement of a CSG, representing the remaining tables that can
+ * be joined with the current CSG.</li>
+ * <li><b>EdgeCalculator:</b> Caches the relationship between subgraphs and edges to improve enumeration
+ * efficiency.</li>
+ * <li><b>NeighborhoodCalculator:</b> Calculates the neighborhood nodes of a subgraph for expansion.</li>
+ * <li><b>receiver:</b> The DP table, responsible for recording enumerated subgraphs and their join plans.</li>
+ * </ul>
+ * <br>
+ * Main workflow:
+ * <ol>
+ * <li>Initialize the receiver, EdgeCalculator, and NeighborhoodCalculator.</li>
+ * <li>For each node, recursively enumerate all connected subgraphs (CSG), and for each CSG, enumerate all
+ * possible CMPs.</li>
+ * <li>Record and prune using the receiver to avoid redundant or invalid enumerations.</li>
+ * <li>All feasible join plans are finally stored in the receiver.</li>
+ * </ol>
+ * This implementation supports trace debugging and can output detailed enumeration steps.
+ */
+public class SubgraphEnumerator {
+ public static final Logger LOG = LogManager.getLogger(SubgraphEnumerator.class);
+ // Whether to enable trace for detailed enumeration steps
+ private final boolean enableTrace = ConnectContext.get().getSessionVariable().enableDpHypTrace;
+ // Trace information collector
+ private final StringBuilder traceBuilder = new StringBuilder();
+ // DP table, records all enumerated CSG/CMP and their join plans
+ private AbstractReceiver receiver;
+ // The HyperGraph being enumerated
+ private HyperGraph hyperGraph;
+ // Edge relationship cache to avoid redundant computation
+ private EdgeCalculator edgeCalculator;
+ // Neighborhood node calculator
+ private NeighborhoodCalculator neighborhoodCalculator;
+
+ /**
+ * Constructor.
+ *
+ * @param receiver DP table to record join plans
+ * @param hyperGraph The query's hypergraph
+ */
+ public SubgraphEnumerator(AbstractReceiver receiver, HyperGraph hyperGraph) {
+ this.receiver = receiver;
+ this.hyperGraph = hyperGraph;
+ }
+
+ /**
+ * Main entry for hypergraph enumeration.
+ * <p>
+ * 1. Initializes the DP table (receiver), edge cache (edgeCalculator), and neighborhood calculator
+ * (neighborhoodCalculator).
+ * 2. For each node, recursively enumerates all connected subgraphs (CSG), and for each CSG, enumerates all
+ * possible CMPs.
+ * 3. Records all feasible join plans in the receiver.
+ *
+ * @return true if enumeration succeeds, false otherwise
+ */
+ public boolean enumerate() {
+ if (enableTrace) {
+ traceBuilder.append("Query Graph Graphviz: ").append(hyperGraph.toDottyHyperGraph()).append("\n");
+ }
+ receiver.reset();
+ List<AbstractNode> nodes = hyperGraph.getNodes();
+ // Init all nodes in Receiver
+ // in hyper graph, there are two kinds of elements, join edge and hyper node
+ // in plan tree, the LogicalJoin node is translated to join edge in hyper graph
+ // and other kind of node is translated to hyper node.
+ // so in a join cluster, all hyper nodes may be a simple table or the root node of sub-plan tree
+ for (AbstractNode node : nodes) {
+ DPhyperNode dPhyperNode = (DPhyperNode) node;
+ receiver.addGroup(node.getNodeMap(), dPhyperNode.getGroup());
+ }
+ int size = nodes.size();
+
+ // Init edgeCalculator
+ edgeCalculator = new EdgeCalculator(hyperGraph.getJoinEdges());
+ for (AbstractNode node : nodes) {
+ edgeCalculator.initSubgraph(node.getNodeMap());
+ }
+
+ // Init neighborhoodCalculator
+ neighborhoodCalculator = new NeighborhoodCalculator();
+
+ // We skip the last element because it can't generate valid csg-cmp pair
+ long forbiddenNodes = LongBitmap.newBitmapBetween(0, size - 1);
+ for (int i = size - 1; i >= 0; i--) {
+ if (enableTrace) {
+ traceBuilder.append("Starting main iteration at node[").append(i).append("]\n");
+ }
+ long csg = LongBitmap.newBitmap(i);
+ forbiddenNodes = LongBitmap.unset(forbiddenNodes, i);
+ if (!emitCsg(csg) || !enumerateCsgRec(csg, LongBitmap.clone(forbiddenNodes))) {
+ return false;
+ }
+ }
+ if (enableTrace) {
+ LOG.info(traceBuilder.toString());
+ }
+ return true;
+ }
+
+ /**
+ * Recursively expands the current connected subgraph (CSG), enumerating all larger connected subgraphs
+ * containing the current CSG.
+ *
+ * @param csg The current connected subgraph as a bitmap
+ * @param forbiddenNodes The set of nodes that cannot be expanded (bitmap)
+ * @return true if successful, false otherwise
+ */
+ private boolean enumerateCsgRec(long csg, long forbiddenNodes) {
+ long neighborhood = neighborhoodCalculator.calcNeighborhood(csg, forbiddenNodes, edgeCalculator);
+ LongBitmapSubsetIterator subsetIterator = LongBitmap.getSubsetIterator(neighborhood);
+ if (enableTrace) {
+ traceBuilder.append("Expanding connected subgraph, subgraph=[").append(LongBitmap.toString(csg))
+ .append("], neighborhood=[").append(LongBitmap.toString(neighborhood)).append("], forbidden=[")
+ .append(LongBitmap.toString(forbiddenNodes)).append("]\n");
+ }
+ for (long subset : subsetIterator) {
+ long newCsg = LongBitmap.newBitmapUnion(csg, subset);
+ if (receiver.contain(newCsg)) {
+ if (!emitCsg(newCsg)) {
+ return false;
+ }
+ }
+ }
+ forbiddenNodes = LongBitmap.or(forbiddenNodes, neighborhood);
+ subsetIterator.reset();
+ for (long subset : subsetIterator) {
+ long newCsg = LongBitmap.newBitmapUnion(csg, subset);
+ edgeCalculator.unionSubGraphs(csg, subset);
+ if (!enumerateCsgRec(newCsg, LongBitmap.clone(forbiddenNodes))) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Recursively expands the current complement subgraph (CMP), enumerating all larger complements containing
+ * the current CMP.
+ *
+ * @param csg The current CSG
+ * @param cmp The current CMP
+ * @param forbiddenNodes The set of nodes that cannot be expanded
+ * @return true if successful, false otherwise
+ */
+ private boolean enumerateCmpRec(long csg, long cmp, long forbiddenNodes) {
+ long neighborhood = neighborhoodCalculator.calcNeighborhood(cmp, forbiddenNodes, edgeCalculator);
+ LongBitmapSubsetIterator subsetIterator = new LongBitmapSubsetIterator(neighborhood);
+ if (enableTrace) {
+ traceBuilder.append("Expanding complement subgraph, subgraph=[").append(LongBitmap.toString(cmp))
+ .append("], neighborhood=[").append(LongBitmap.toString(neighborhood)).append("], forbidden=[")
+ .append(LongBitmap.toString(forbiddenNodes)).append("]\n");
+ }
+ for (long subset : subsetIterator) {
+ long newCmp = LongBitmap.newBitmapUnion(cmp, subset);
+ // We need to check whether Cmp is connected and then try to find hyper edge
+ if (receiver.contain(newCmp)) {
+ // We check all edges for finding an edge.
+ List<Edge> edges = edgeCalculator.connectCsgCmp(csg, newCmp);
+ if (!edges.isEmpty()) {
+ AbstractReceiver.EmitState emitState = receiver.emitCsgCmp(csg, newCmp, edges);
+ if (emitState == AbstractReceiver.EmitState.SUCCESS) {
+ edgeCalculator.unionSubGraphs(csg, newCmp);
+ } else if (emitState == AbstractReceiver.EmitState.FAIL) {
+ return false;
+ }
+ }
+ }
+ }
+ forbiddenNodes = LongBitmap.or(forbiddenNodes, neighborhood);
+ subsetIterator.reset();
+ for (long subset : subsetIterator) {
+ long newCmp = LongBitmap.newBitmapUnion(cmp, subset);
+ edgeCalculator.unionSubGraphs(cmp, subset);
+ if (!enumerateCmpRec(csg, newCmp, LongBitmap.clone(forbiddenNodes))) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * For a given connected subgraph (CSG), enumerate all possible complements (CMP) and generate all feasible
+ * csg-cmp pairs.
+ *
+ * @param csg The current connected subgraph
+ * @return true if successful, false otherwise
+ */
+ private boolean emitCsg(long csg) {
+ long forbiddenNodes = LongBitmap.newBitmapBetween(0, LongBitmap.nextSetBit(csg, 0));
+ forbiddenNodes = LongBitmap.or(forbiddenNodes, csg);
+ long neighborhoods = neighborhoodCalculator.calcNeighborhood(csg, LongBitmap.clone(forbiddenNodes),
+ edgeCalculator);
+ if (enableTrace && LongBitmap.getCardinality(csg) == 1) {
+ traceBuilder.append("Emitting connected subgraph, subgraph=[").append(LongBitmap.toString(csg))
+ .append("], neighborhood=[").append(LongBitmap.toString(neighborhoods)).append("], forbidden=[")
+ .append(LongBitmap.toString(forbiddenNodes)).append("]\n");
+ }
+ for (int nodeIndex : LongBitmap.getReverseIterator(neighborhoods)) {
+ long cmp = LongBitmap.newBitmap(nodeIndex);
+ // whether there is an edge between csg and cmp
+ List<Edge> edges = edgeCalculator.connectCsgCmp(csg, cmp);
+ if (!edges.isEmpty()) {
+ AbstractReceiver.EmitState emitState = receiver.emitCsgCmp(csg, cmp, edges);
+ if (emitState == AbstractReceiver.EmitState.SUCCESS) {
+ edgeCalculator.unionSubGraphs(csg, cmp);
+ } else if (emitState == AbstractReceiver.EmitState.FAIL) {
+ return false;
+ }
+ }
+
+ // In order to avoid enumerate repeated cmp, e.g.,
+ // t1 (csg)
+ // / \
+ // t2 - t3
+ // for csg {t1}, we can get neighborhoods {t2, t3}
+ // 1. The cmp is {t3} and expanded from {t3} to {t2, t3}
+ // 2. The cmp is {t2} and expanded from {t2} to {t2, t3}
+ // We don't want get {t2, t3} twice. So In first enumeration, we
+ // can exclude {t2}
+ long newForbiddenNodes = LongBitmap.newBitmapBetween(0, nodeIndex);
+ newForbiddenNodes = LongBitmap.and(newForbiddenNodes, neighborhoods);
+ newForbiddenNodes = LongBitmap.or(newForbiddenNodes, forbiddenNodes);
+ if (!enumerateCmpRec(csg, cmp, newForbiddenNodes)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Neighborhood node calculator.
+ * <p>
+ * Used to calculate the neighborhood node set of a given subgraph (i.e., nodes that can be used to expand
+ * the subgraph). Only the minimal set of nodes needed to expand all subgraphs is selected, to avoid redundant
+ * expansion.
+ */
+ static class NeighborhoodCalculator {
+ /**
+ * Calculate the neighborhood nodes for a given subgraph.
+ *
+ * @param subgraph The current subgraph
+ * @param forbiddenNodes Nodes that cannot be expanded
+ * @param edgeCalculator Edge cache
+ * @return Neighborhood node set (bitmap)
+ */
+ public long calcNeighborhood(long subgraph, long forbiddenNodes, EdgeCalculator edgeCalculator) {
+ long neighborhoods = LongBitmap.newBitmap();
+ for (Edge edge : edgeCalculator.foundSimpleEdgesContain(subgraph)) {
+ // neighborhoods = LongBitmap.or(neighborhoods, edge.getReferenceNodes());
+ neighborhoods = LongBitmap.or(neighborhoods, edge.getReferenceNodes());
+ }
+ forbiddenNodes = LongBitmap.or(forbiddenNodes, subgraph);
+ for (Edge edge : edgeCalculator.foundComplexEdgesContain(subgraph)) {
+ long left = edge.getLeftExtendedNodes();
+ long right = edge.getRightExtendedNodes();
+ if (LongBitmap.isSubset(left, subgraph) && !LongBitmap.isOverlap(right, forbiddenNodes)) {
+ neighborhoods = LongBitmap.set(neighborhoods, LongBitmap.lowestOneIndex(right));
+ } else if (LongBitmap.isSubset(right, subgraph) && !LongBitmap.isOverlap(left, forbiddenNodes)) {
+ neighborhoods = LongBitmap.set(neighborhoods, LongBitmap.lowestOneIndex(left));
+ }
+ }
+ neighborhoods = LongBitmap.andNot(neighborhoods, forbiddenNodes);
+ return neighborhoods;
+ }
+ }
+
+ /**
+ * Edge relationship cache and calculator.
+ * <p>
+ * 1. Caches all edges in the hypergraph.
+ * 2. Caches, for each subgraph, the edges it contains (split into simple/complex), and the edges connecting
+ * to its complement.
+ * 3. Supports efficient merging of subgraphs, finding connecting edges, and determining edge-subgraph
+ * relationships.
+ * <ul>
+ * <li><b>containSimpleEdges/containComplexEdges:</b> Edges where one endpoint is fully contained in the
+ * subgraph.</li>
+ * <li><b>overlapEdges:</b> Edges where one endpoint partially overlaps with the subgraph.</li>
+ * </ul>
+ * These caches greatly improve join enumeration efficiency.
+ */
+ static class EdgeCalculator {
+ // all edges are unchanged during enumerate phase
+ final List<Edge> edges;
+ // It cached all edges that contained by this subgraph, Note we always
+ // use bitset store edge map because the number of edges can be very large
+ // We split these into simple edges (only one node on each side) and complex edges (others)
+ // because we can often quickly discard all simple edges by testing the set of interesting nodes
+ // against the βsimple_neighborhoodβ bitmap. These data will be calculated before enumerate.
+
+ // HashMap<Long, BitSet>: sub-graph to it's edges
+ // Long : sub graph nodes' indexes LongBitmap, the index is 0 based, but in LongBitmap, minimal is 1st bit: 1
+ // BitSet : edge's index in all join edges, 0 based
+ // for each sub graph, we cache its containSimpleEdges and containComplexEdges for neighbor calculation
+ // contains means the sub graph contains one whole side end of edge
+ HashMap<Long, BitSet> containSimpleEdges = new HashMap<>();
+ HashMap<Long, BitSet> containComplexEdges = new HashMap<>();
+ // It cached all edges that overlap by this subgraph. All overlap edges must be
+ // complex edges, overlap means the sub graph contains part of one side end of edge
+ // the overlapEdges are NOT used to connect the sub graph, but used make union two sub-graph faster
+ // only overlapEdges may be turned in to containEdges
+ HashMap<Long, BitSet> overlapEdges = new HashMap<>();
+
+ EdgeCalculator(List<Edge> edges) {
+ this.edges = edges;
+ }
+
+ /**
+ * Initialize the edge cache for a subgraph.
+ *
+ * @param subgraph Subgraph node set
+ */
+ public void initSubgraph(long subgraph) {
+ BitSet simpleContains = new BitSet();
+ BitSet complexContains = new BitSet();
+ BitSet overlaps = new BitSet();
+ for (Edge edge : edges) {
+ if (isContainEdge(subgraph, edge)) {
+ if (edge.isSimple()) {
+ simpleContains.set(edge.getIndex());
+ } else {
+ complexContains.set(edge.getIndex());
+ }
+ } else if (isOverlapEdge(subgraph, edge)) {
+ overlaps.set(edge.getIndex());
+ }
+ }
+ if (containSimpleEdges.containsKey(subgraph)) {
+ complexContains.or(containComplexEdges.get(subgraph));
+ simpleContains.or(containSimpleEdges.get(subgraph));
+ }
+ if (overlapEdges.containsKey(subgraph)) {
+ overlaps.or(overlapEdges.get(subgraph));
+ }
+ overlapEdges.put(subgraph, overlaps);
+ containSimpleEdges.put(subgraph, simpleContains);
+ containComplexEdges.put(subgraph, complexContains);
+ }
+
+ /**
+ * Merge the edge caches of two subgraphs.
+ * <p>
+ * Used to quickly merge edge information when expanding subgraphs.
+ *
+ * @param subgraph1 Subgraph 1
+ * @param subgraph2 Subgraph 2
+ */
+ public void unionSubGraphs(long subgraph1, long subgraph2) {
+ // When union two sub graphs, we only need to check overlap edges.
+ // However, if all reference nodes are contained by the subgraph,
+ // we should remove it.
+ if (!containSimpleEdges.containsKey(subgraph1)) {
+ initSubgraph(subgraph1);
+ }
+ if (!containSimpleEdges.containsKey(subgraph2)) {
+ initSubgraph(subgraph2);
+ }
+ long subgraph = LongBitmap.newBitmapUnion(subgraph1, subgraph2);
+ if (containSimpleEdges.containsKey(subgraph)) {
+ return;
+ }
+ BitSet simpleContains = new BitSet();
+ simpleContains.or(containSimpleEdges.get(subgraph1));
+ simpleContains.or(containSimpleEdges.get(subgraph2));
+ BitSet complexContains = new BitSet();
+ complexContains.or(containComplexEdges.get(subgraph1));
+ complexContains.or(containComplexEdges.get(subgraph2));
+ BitSet overlaps = new BitSet();
+ overlaps.or(overlapEdges.get(subgraph1));
+ overlaps.or(overlapEdges.get(subgraph2));
+ for (int index : overlaps.stream().toArray()) {
+ Edge edge = edges.get(index);
+ // some overlap edges may become contains edges
+ if (isContainEdge(subgraph, edge)) {
+ overlaps.set(index, false);
+ if (edge.isSimple()) {
+ simpleContains.set(index);
+ } else {
+ complexContains.set(index);
+ }
+ }
+ }
+ simpleContains = removeInvalidEdges(subgraph, simpleContains);
+ complexContains = removeInvalidEdges(subgraph, complexContains);
+ containSimpleEdges.put(subgraph, simpleContains);
+ containComplexEdges.put(subgraph, complexContains);
+ overlapEdges.put(subgraph, overlaps);
+ }
+
+ /**
+ * Find join edges that connect csg and cmp.
+ * <p>
+ * Only returns join edges that can connect csg and cmp.
+ *
+ * @param csg Connected subgraph
+ * @param cmp Complement subgraph
+ * @return List of connecting edges, or empty if not connected
+ */
+ public List<Edge> connectCsgCmp(long csg, long cmp) {
+ Preconditions.checkArgument(
+ containSimpleEdges.containsKey(csg) && containSimpleEdges.containsKey(cmp));
+ List<Edge> foundEdges = new ArrayList<>();
+ // find all edges contained both by csg and cmp, we use these edges as join condition later
+ BitSet edgeMap = new BitSet();
+ edgeMap.or(containSimpleEdges.get(csg));
+ edgeMap.and(containSimpleEdges.get(cmp));
+ BitSet complexes = new BitSet();
+ complexes.or(containComplexEdges.get(csg));
+ complexes.and(containComplexEdges.get(cmp));
+ edgeMap.or(complexes);
+ edgeMap.stream().forEach(index -> foundEdges.add(edges.get(index)));
+ return foundEdges;
+ }
+
+ /**
+ * Get all edges (simple + complex) contained in a subgraph.
+ *
+ * @param subgraph Subgraph
+ * @return List of edges
+ */
+ public List<Edge> foundEdgesContain(long subgraph) {
+ BitSet edgeMap = containSimpleEdges.get(subgraph);
+ Preconditions.checkState(edgeMap != null);
+ edgeMap.or(containComplexEdges.get(subgraph));
+ return edgeMap.stream().mapToObj(edges::get).collect(Collectors.toList());
Review Comment:
π΄ **Bug #5: Mutates cached BitSet by reference**
`containSimpleEdges.get(subgraph)` returns a reference. The `.or()` permanently corrupts the cached entry by merging complex edges into the simple-edges cache. Any subsequent `foundSimpleEdgesContain()` for this subgraph returns wrong results.
Fix: clone before mutating:
```java
BitSet edgeMap = (BitSet) containSimpleEdges.get(subgraph).clone();
```
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/joinorder/hypergraphv2/node/DPhyperNode.java:
##########
@@ -0,0 +1,47 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+package org.apache.doris.nereids.jobs.joinorder.hypergraphv2.node;
+
+import org.apache.doris.nereids.memo.Group;
+
+import com.google.common.base.Preconditions;
+
+/**
+ * HyperGraph Node.
+ */
+public class DPhyperNode extends AbstractNode {
+ private final Group group;
+
+ public DPhyperNode(int index, Group group) {
+ super(group.getLogicalExpression().getPlan(), index);
+ Preconditions.checkArgument(group != null, "DPhyper requires Group is not null");
+ this.group = group;
Review Comment:
π‘ **Issue #11: Dead code β null check after dereference**
This `Preconditions.checkArgument` is unreachable because `super(group.getLogicalExpression()...)` on the previous line already dereferences `group`. If `group` is null, NPE fires before this check.
Fix: either use `Objects.requireNonNull(group)` before super, or remove this dead check.
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/jobs/executor/Optimizer.java:
##########
@@ -95,10 +105,51 @@ public static boolean isDpHyp(CascadesContext cascadesContext) {
}
private void dpHypOptimize() {
+ Plan oldRewrittenPlan = cascadesContext.getRewritePlan();
Group root = cascadesContext.getMemo().getRoot();
// Due to EnsureProjectOnTopJoin, root group can't be Join Group, so DPHyp doesn't change the root group
cascadesContext.pushJob(new JoinOrderJob(root, cascadesContext.getCurrentJobContext()));
cascadesContext.getJobScheduler().executeJobPool(cascadesContext);
+
+ // 1) copy out logical plan from memo
+ Plan plan = cascadesContext.getMemo().copyOutBestLogicalPlan();
+
+ // 2) run PushDownExpressionsInHashCondition as a plan rewrite on a temporary context
+ org.apache.doris.nereids.CascadesContext tempCtx = CascadesContext.newCurrentTreeContext(cascadesContext);
+ tempCtx.setRewritePlan(plan);
+ RewriteJob pushDownRewrite = AbstractBatchJobExecutor.topDown(new PushDownExpressionsInHashCondition(),
+ new MergeProjectable());
+ RewriteJob columnPrune = AbstractBatchJobExecutor.custom(RuleType.COLUMN_PRUNING, ColumnPruning::new);
+ RewriteJob adjustNullable = AbstractBatchJobExecutor.custom(RuleType.ADJUST_NULLABLE,
+ () -> new AdjustNullable(false));
+ RewriteJob checkAfterRewrite = AbstractBatchJobExecutor.bottomUp(new CheckAfterRewrite());
+ AbstractBatchJobExecutor executor = new AbstractBatchJobExecutor(tempCtx) {
+ @Override
+ public java.util.List<org.apache.doris.nereids.jobs.rewrite.RewriteJob> getJobs() {
+ return com.google.common.collect.ImmutableList.of(pushDownRewrite, columnPrune, adjustNullable,
+ checkAfterRewrite);
+ }
+ };
+ boolean oldFeDebugValue = tempCtx.getStatementContext().getConnectContext().getSessionVariable().feDebug;
+ try {
+ tempCtx.getStatementContext().getConnectContext().getSessionVariable().feDebug = false;
+ executor.execute();
+ } finally {
+ tempCtx.getStatementContext().getConnectContext().getSessionVariable().feDebug = oldFeDebugValue;
+ }
+
+ // 3) copy rewritten plan into the main cascades context and rebuild memo
+ Plan rewritten = tempCtx.getRewritePlan();
+ cascadesContext.releaseMemo();
+ cascadesContext.setRewritePlan(rewritten);
+ // init memo
+ cascadesContext.toMemo();
+ cascadesContext.setRewritePlan(oldRewrittenPlan);
+
Review Comment:
π΄ **Bug #6: Restoring stale rewritePlan after memo rebuild**
After `toMemo()` builds a new memo from `rewritten`, this line restores the pre-DPhyper plan. Now `getRewritePlan()` returns a plan that doesn't match the memo. If any downstream code reads `getRewritePlan()` (e.g., error reporting, fallback), it sees stale topology.
Consider keeping them aligned or documenting the intentional divergence.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "hello-stephen (via GitHub)" <gi...@apache.org>.
hello-stephen commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4181473425
# FE UT Coverage Report
Increment line coverage ` 86.22% (1370/1589)` :tada:
[Increment coverage report](http://coverage.selectdb-in.cc/coverage/61146_7086d3bb0b0e5412c4bedfa4391c31029de24d8f/fe_increment_report/index.html)
[Complete coverage report](http://coverage.selectdb-in.cc/coverage/61146_7086d3bb0b0e5412c4bedfa4391c31029de24d8f/fe_report/index.html)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
Re: [PR] [feat](join) support outer join reorder in dphyper [doris]
Posted by "starocean999 (via GitHub)" <gi...@apache.org>.
starocean999 commented on PR #61146:
URL: https://github.com/apache/doris/pull/61146#issuecomment-4272581456
run buildall
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org