Repository navigation
Commit 408527a
authored
fix: prevent DISTINCT ORDER BY LIMIT from returning too few rows (apache#24932)
## Which issue does this PR close?
- Closes apache#24927.
## Rationale for this change
With multiple partitions, `SELECT DISTINCT ... ORDER BY ... LIMIT` can
return fewer rows than requested even when enough distinct values exist.
`DISTINCT` runs in partial and final stages. Sort pushdown was moving
the final TopK `fetch` (the sort's row limit) below the final
aggregation, while duplicate partial results still existed:
```text
SortPreservingMergeExec: fetch=3
AggregateExec: final DISTINCT
SortExec: TopK(fetch=3) <-- limit is applied too early
AggregateExec: partial DISTINCT
```
Duplicates could fill the limit and discard another value before the
final `DISTINCT` had a chance to remove them.
The corrected plan keeps the limit above the final `DISTINCT`:
```text
SortPreservingMergeExec: fetch=3 <-- limit is applied after DISTINCT
AggregateExec: final DISTINCT
SortExec <-- ordering only; no limit
AggregateExec: partial DISTINCT
```
I bisected this regression to
[`450c861a8c`](apache@450c861)
(apache#14821), first released in 47.0.0. That refactor made the
ordering-satisfied fast path forward `fetch` to the current plan's
children. It correctly established that the current plan preserved the
requested ordering, but preserving order does not mean that moving a
limit is safe. The shortcut consequently bypassed the existing
limit-pushdown and cardinality checks: the parent of that commit returns
`0`, `1`, and `2`, while the commit itself returns only `0` and `2`.
## What changes are included in this PR?
When a plan already satisfies the requested ordering, sort pushdown
first tries to keep a pending `fetch` on that plan through the generic
`ExecutionPlan::with_fetch` capability. It forwards the fetch to
children only when the plan explicitly supports limit pushdown and
produces exactly one output row for every input row.
If an already ordered plan can neither retain nor safely forward the
fetch, the optimizer keeps the limit above it with a `LocalLimitExec` or
`GlobalLimitExec`, adding a sort-preserving merge when a single output
partition is required. This carries the limit without introducing a
redundant sort and gives subsequent optimizer runs the same canonical
plan shape.
## What is the testing strategy for this PR?
An SQLLogicTest in `limit.slt` uses the exact two-partition query from
apache#24927 and verifies that it returns `0`, `1`, and `2`. Focused physical
optimizer tests verify the stable limit-carrier plan across another
optimizer pass and verify that fetch is still forwarded through a safe
equal-cardinality plan.
## Are there any user-facing changes?
Yes. Affected queries now return all requested distinct rows. There are
no API or configuration changes.1 parent 9442d88 commit 408527a
3 files changed
Lines changed: 237 additions & 19 deletions
File tree
- datafusion
- core/tests/physical_optimizer
- physical-optimizer/src/ensure_requirements/enforce_sorting
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
30 | 30 | | |
31 | 31 | | |
32 | 32 | | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
33 | 36 | | |
34 | 37 | | |
35 | 38 | | |
| |||
41 | 44 | | |
42 | 45 | | |
43 | 46 | | |
44 | | - | |
| 47 | + | |
45 | 48 | | |
46 | 49 | | |
47 | 50 | | |
| |||
835 | 838 | | |
836 | 839 | | |
837 | 840 | | |
| 841 | + | |
| 842 | + | |
| 843 | + | |
| 844 | + | |
| 845 | + | |
| 846 | + | |
| 847 | + | |
| 848 | + | |
| 849 | + | |
| 850 | + | |
| 851 | + | |
| 852 | + | |
| 853 | + | |
| 854 | + | |
| 855 | + | |
| 856 | + | |
| 857 | + | |
| 858 | + | |
| 859 | + | |
| 860 | + | |
| 861 | + | |
| 862 | + | |
| 863 | + | |
| 864 | + | |
| 865 | + | |
| 866 | + | |
| 867 | + | |
| 868 | + | |
| 869 | + | |
| 870 | + | |
| 871 | + | |
| 872 | + | |
| 873 | + | |
| 874 | + | |
| 875 | + | |
| 876 | + | |
| 877 | + | |
| 878 | + | |
| 879 | + | |
| 880 | + | |
| 881 | + | |
| 882 | + | |
| 883 | + | |
| 884 | + | |
| 885 | + | |
| 886 | + | |
| 887 | + | |
| 888 | + | |
| 889 | + | |
| 890 | + | |
| 891 | + | |
| 892 | + | |
| 893 | + | |
| 894 | + | |
| 895 | + | |
| 896 | + | |
| 897 | + | |
| 898 | + | |
| 899 | + | |
| 900 | + | |
| 901 | + | |
| 902 | + | |
| 903 | + | |
| 904 | + | |
| 905 | + | |
| 906 | + | |
| 907 | + | |
| 908 | + | |
| 909 | + | |
| 910 | + | |
| 911 | + | |
| 912 | + | |
| 913 | + | |
| 914 | + | |
| 915 | + | |
| 916 | + | |
| 917 | + | |
| 918 | + | |
| 919 | + | |
| 920 | + | |
| 921 | + | |
| 922 | + | |
| 923 | + | |
| 924 | + | |
| 925 | + | |
| 926 | + | |
| 927 | + | |
| 928 | + | |
| 929 | + | |
| 930 | + | |
| 931 | + | |
| 932 | + | |
| 933 | + | |
| 934 | + | |
| 935 | + | |
| 936 | + | |
838 | 937 | | |
839 | 938 | | |
840 | 939 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
43 | 43 | | |
44 | 44 | | |
45 | 45 | | |
| 46 | + | |
46 | 47 | | |
47 | 48 | | |
48 | 49 | | |
| 50 | + | |
49 | 51 | | |
50 | 52 | | |
51 | 53 | | |
| |||
114 | 116 | | |
115 | 117 | | |
116 | 118 | | |
| 119 | + | |
| 120 | + | |
| 121 | + | |
| 122 | + | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
| 126 | + | |
| 127 | + | |
| 128 | + | |
| 129 | + | |
| 130 | + | |
| 131 | + | |
| 132 | + | |
| 133 | + | |
| 134 | + | |
| 135 | + | |
| 136 | + | |
| 137 | + | |
| 138 | + | |
| 139 | + | |
| 140 | + | |
| 141 | + | |
| 142 | + | |
| 143 | + | |
| 144 | + | |
| 145 | + | |
| 146 | + | |
| 147 | + | |
| 148 | + | |
| 149 | + | |
| 150 | + | |
| 151 | + | |
| 152 | + | |
| 153 | + | |
| 154 | + | |
| 155 | + | |
| 156 | + | |
| 157 | + | |
| 158 | + | |
| 159 | + | |
| 160 | + | |
| 161 | + | |
| 162 | + | |
| 163 | + | |
| 164 | + | |
| 165 | + | |
| 166 | + | |
| 167 | + | |
| 168 | + | |
| 169 | + | |
| 170 | + | |
| 171 | + | |
| 172 | + | |
| 173 | + | |
| 174 | + | |
| 175 | + | |
| 176 | + | |
| 177 | + | |
| 178 | + | |
| 179 | + | |
| 180 | + | |
| 181 | + | |
| 182 | + | |
| 183 | + | |
| 184 | + | |
117 | 185 | | |
118 | 186 | | |
119 | 187 | | |
| |||
244 | 312 | | |
245 | 313 | | |
246 | 314 | | |
| 315 | + | |
247 | 316 | | |
248 | | - | |
| 317 | + | |
| 318 | + | |
| 319 | + | |
| 320 | + | |
| 321 | + | |
| 322 | + | |
| 323 | + | |
249 | 324 | | |
250 | 325 | | |
251 | 326 | | |
| |||
261 | 336 | | |
262 | 337 | | |
263 | 338 | | |
| 339 | + | |
| 340 | + | |
| 341 | + | |
| 342 | + | |
| 343 | + | |
| 344 | + | |
| 345 | + | |
264 | 346 | | |
265 | 347 | | |
266 | 348 | | |
267 | 349 | | |
268 | 350 | | |
269 | | - | |
| 351 | + | |
270 | 352 | | |
271 | 353 | | |
272 | 354 | | |
| |||
306 | 388 | | |
307 | 389 | | |
308 | 390 | | |
| 391 | + | |
| 392 | + | |
| 393 | + | |
| 394 | + | |
| 395 | + | |
| 396 | + | |
| 397 | + | |
| 398 | + | |
| 399 | + | |
| 400 | + | |
| 401 | + | |
| 402 | + | |
| 403 | + | |
| 404 | + | |
| 405 | + | |
| 406 | + | |
309 | 407 | | |
310 | 408 | | |
311 | 409 | | |
| |||
326 | 424 | | |
327 | 425 | | |
328 | 426 | | |
329 | | - | |
330 | | - | |
331 | | - | |
332 | | - | |
333 | | - | |
334 | | - | |
335 | | - | |
336 | | - | |
| 427 | + | |
| 428 | + | |
| 429 | + | |
| 430 | + | |
| 431 | + | |
| 432 | + | |
| 433 | + | |
337 | 434 | | |
338 | 435 | | |
339 | 436 | | |
| |||
347 | 444 | | |
348 | 445 | | |
349 | 446 | | |
350 | | - | |
| 447 | + | |
351 | 448 | | |
352 | 449 | | |
353 | | - | |
354 | | - | |
355 | | - | |
356 | | - | |
357 | | - | |
358 | | - | |
359 | | - | |
| 450 | + | |
| 451 | + | |
360 | 452 | | |
361 | 453 | | |
362 | 454 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
444 | 444 | | |
445 | 445 | | |
446 | 446 | | |
| 447 | + | |
| 448 | + | |
| 449 | + | |
| 450 | + | |
| 451 | + | |
| 452 | + | |
| 453 | + | |
| 454 | + | |
| 455 | + | |
| 456 | + | |
| 457 | + | |
| 458 | + | |
| 459 | + | |
| 460 | + | |
| 461 | + | |
| 462 | + | |
| 463 | + | |
| 464 | + | |
| 465 | + | |
| 466 | + | |
| 467 | + | |
| 468 | + | |
| 469 | + | |
| 470 | + | |
| 471 | + | |
| 472 | + | |
| 473 | + | |
447 | 474 | | |
448 | 475 | | |
449 | 476 | | |
| |||
0 commit comments