Repository navigation
Commit 28cefb7
authored
fix: match functional dependencies by column position, not by name (apache#26150)
## Which issue does this PR close?
- None yet. The bug and its repro are below.
## Rationale for this change
If `x` is a primary key, the optimizer treats `CAST(x AS ...)` as `x`.
It then drops the other ORDER BY or GROUP BY keys that `x` determines,
so the query returns wrong results:
```sql
CREATE TABLE t (x DOUBLE, y VARCHAR, PRIMARY KEY (x))
AS VALUES (1.1, 'b'), (1.2, 'a'), (2.1, 'c');
SELECT x, y FROM t ORDER BY CAST(x AS INT), y;
-- main: 1.1 b / 1.2 a / 2.1 c (`y` is dropped from the sort)
-- expected: 1.2 a / 1.1 b / 2.1 c
SELECT CAST(x AS INT) k, count(*) n FROM t GROUP BY CAST(x AS INT), y;
-- main: (1, 2) / (2, 1) (`y` is dropped from the grouping)
-- expected: (1, 1) / (1, 1) / (2, 1)
SELECT y, count(*) FROM t GROUP BY CAST(x AS INT);
-- main: accepted
-- expected: Error: Column in SELECT must be in GROUP BY or an aggregate function
```
`CAST(x AS INT)` is named `t.x`, because casts are left out of
expression names. The functional dependency helpers matched GROUP BY and
ORDER BY expressions to key columns by comparing names, so the cast
matched the key `t.x`.
The same happens with `TRY_CAST`, with a `UNIQUE NOT NULL` key, and with
a key that comes from an inner GROUP BY. The ORDER BY case comes from
the sort key pruning added in apache#21362 (54.0.0).
## What changes are included in this PR?
- **Index-based helpers.** The four helpers in
`functional_dependencies.rs` now take, for each GROUP BY or ORDER BY
expression, the index of the input field it references (`Option<usize>`)
instead of its name. A computed expression has no index, so it never
matches a key. The new `datafusion_expr::utils::passthrough_field_index`
returns the index for a column reference, aliased or not.
- **One GROUP BY list.** The dependencies of an `Aggregate`'s output use
the GROUP BY list that its schema is built from
(`grouping_set_to_exprlist`). Before, they used a list de-duplicated by
name, which merged `CAST(x AS INT)` and `x`.
- **Projections resolve columns.** A projection now finds each input
column with `DFSchema::index_of_column_by_name` instead of comparing
`"qualifier.name"` strings. The unit test
`projection_duplicate_flattened_name_uses_first_input_index` asserted
the old string behaviour: a column named `"orders.id"` got the
dependency of the different field `orders.id`. It is renamed and now
asserts that each column keeps its own dependency.
## What is the testing strategy for this PR?
- **New tests.** Section 6 of `functional_dependencies.slt` has one
query for each user of the helpers:
- ORDER BY pruning;
- GROUP BY pruning;
- `Aggregate` output dependencies;
- GROUP BY expansion.
On `main`, each of these returns a wrong result or accepts an invalid
query. The same queries also run over `TRY_CAST` on a `UNIQUE NOT NULL`
key and over a key from an inner GROUP BY. One more query pins that a
widening cast (`INT` to `BIGINT`) of a key does not carry its
dependencies.
- **New unit tests.** `passthrough_field_index` resolves an ambiguous
unqualified column to nothing. A key that is in the GROUP BY list two
times (`id, id AS k`, builder API only) still determines the row.
- **Existing tests** are unchanged, apart from the rewritten unit test.
- **Planning time.** Planning is not slower. The `sql_planner` TPC-H and
TPC-DS benchmarks, whose tables have primary keys, are about 5% faster,
because the new code no longer renders expression names.
<details><summary>Benchmark numbers (3 interleaved runs per
side)</summary>
| Benchmark | `main` | This PR |
|---|---|---|
| `physical_plan_tpch_all` | 17.3 / 17.8 / 18.0 ms | 16.1 / 17.0 / 17.2
ms |
| `physical_plan_tpcds_all` | 291 / 300 / 301 ms | 276 / 280 / 282 ms |
</details>
## Are there any user-facing changes?
- **Results.** The queries above return correct results.
- **Rejected queries.** Only a column reference to a key carries its
dependencies. A query that selects other columns while grouping by an
expression over the key is now rejected, even when the expression keeps
distinct values distinct, like `GROUP BY CAST(x AS BIGINT)` over an
`INT` key. `main` accepts it and its result is correct. PostgreSQL and
DuckDB reject it too. Group by the key column itself instead.
- **API change.** Four `pub` functions in `datafusion_common` take
`&[Option<usize>]` instead of `&[String]`:
- `aggregate_functional_dependencies`
- `get_target_functional_dependencies`
- `get_required_group_by_exprs_indices`
- `get_required_sort_exprs_indices`
The upgrade guide has a migration note.1 parent 6023600 commit 28cefb7
8 files changed
Lines changed: 307 additions & 103 deletions
File tree
- datafusion
- common/src
- expr/src
- logical_plan
- optimizer/src
- optimize_projections
- sqllogictest/test_files
- docs/source/library-user-guide/upgrading
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
452 | 452 | | |
453 | 453 | | |
454 | 454 | | |
| 455 | + | |
| 456 | + | |
| 457 | + | |
| 458 | + | |
| 459 | + | |
| 460 | + | |
455 | 461 | | |
456 | 462 | | |
457 | | - | |
| 463 | + | |
458 | 464 | | |
459 | 465 | | |
460 | 466 | | |
| |||
466 | 472 | | |
467 | 473 | | |
468 | 474 | | |
469 | | - | |
470 | 475 | | |
471 | 476 | | |
472 | | - | |
| 477 | + | |
473 | 478 | | |
474 | 479 | | |
475 | 480 | | |
| |||
480 | 485 | | |
481 | 486 | | |
482 | 487 | | |
483 | | - | |
484 | | - | |
485 | | - | |
486 | | - | |
487 | | - | |
488 | | - | |
489 | | - | |
490 | | - | |
491 | | - | |
492 | | - | |
493 | | - | |
| 488 | + | |
| 489 | + | |
| 490 | + | |
| 491 | + | |
| 492 | + | |
| 493 | + | |
| 494 | + | |
| 495 | + | |
| 496 | + | |
| 497 | + | |
| 498 | + | |
494 | 499 | | |
495 | | - | |
| 500 | + | |
496 | 501 | | |
497 | 502 | | |
498 | 503 | | |
499 | 504 | | |
500 | | - | |
| 505 | + | |
501 | 506 | | |
502 | 507 | | |
503 | 508 | | |
| |||
513 | 518 | | |
514 | 519 | | |
515 | 520 | | |
516 | | - | |
| 521 | + | |
517 | 522 | | |
518 | 523 | | |
519 | 524 | | |
| |||
533 | 538 | | |
534 | 539 | | |
535 | 540 | | |
536 | | - | |
537 | | - | |
| 541 | + | |
| 542 | + | |
538 | 543 | | |
539 | 544 | | |
540 | 545 | | |
| |||
566 | 571 | | |
567 | 572 | | |
568 | 573 | | |
| 574 | + | |
| 575 | + | |
| 576 | + | |
569 | 577 | | |
570 | 578 | | |
571 | | - | |
| 579 | + | |
572 | 580 | | |
573 | 581 | | |
574 | 582 | | |
575 | 583 | | |
576 | 584 | | |
577 | 585 | | |
578 | | - | |
579 | 586 | | |
580 | 587 | | |
581 | 588 | | |
582 | 589 | | |
583 | 590 | | |
584 | 591 | | |
585 | | - | |
586 | | - | |
587 | | - | |
588 | | - | |
589 | 592 | | |
590 | 593 | | |
591 | 594 | | |
592 | | - | |
| 595 | + | |
593 | 596 | | |
594 | | - | |
| 597 | + | |
595 | 598 | | |
596 | 599 | | |
597 | 600 | | |
| |||
605 | 608 | | |
606 | 609 | | |
607 | 610 | | |
| 611 | + | |
| 612 | + | |
| 613 | + | |
| 614 | + | |
608 | 615 | | |
609 | 616 | | |
610 | | - | |
| 617 | + | |
611 | 618 | | |
612 | 619 | | |
613 | | - | |
614 | | - | |
| 620 | + | |
615 | 621 | | |
616 | | - | |
617 | | - | |
618 | | - | |
619 | | - | |
620 | | - | |
| 622 | + | |
621 | 623 | | |
622 | 624 | | |
623 | 625 | | |
| |||
642 | 644 | | |
643 | 645 | | |
644 | 646 | | |
645 | | - | |
| 647 | + | |
646 | 648 | | |
647 | | - | |
| 649 | + | |
648 | 650 | | |
649 | 651 | | |
650 | 652 | | |
651 | 653 | | |
652 | 654 | | |
653 | 655 | | |
| 656 | + | |
| 657 | + | |
| 658 | + | |
654 | 659 | | |
655 | 660 | | |
656 | | - | |
| 661 | + | |
657 | 662 | | |
658 | 663 | | |
659 | | - | |
660 | 664 | | |
661 | | - | |
662 | | - | |
| 665 | + | |
| 666 | + | |
663 | 667 | | |
664 | | - | |
665 | | - | |
666 | | - | |
| 668 | + | |
| 669 | + | |
| 670 | + | |
667 | 671 | | |
668 | | - | |
669 | | - | |
670 | | - | |
671 | | - | |
| 672 | + | |
672 | 673 | | |
673 | 674 | | |
674 | 675 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
41 | 41 | | |
42 | 42 | | |
43 | 43 | | |
44 | | - | |
| 44 | + | |
45 | 45 | | |
46 | 46 | | |
47 | 47 | | |
| |||
1988 | 1988 | | |
1989 | 1989 | | |
1990 | 1990 | | |
1991 | | - | |
1992 | | - | |
1993 | | - | |
| 1991 | + | |
| 1992 | + | |
| 1993 | + | |
1994 | 1994 | | |
1995 | | - | |
| 1995 | + | |
1996 | 1996 | | |
1997 | 1997 | | |
1998 | 1998 | | |
1999 | | - | |
| 1999 | + | |
2000 | 2000 | | |
2001 | 2001 | | |
2002 | | - | |
2003 | | - | |
2004 | | - | |
2005 | | - | |
2006 | | - | |
| 2002 | + | |
| 2003 | + | |
| 2004 | + | |
2007 | 2005 | | |
2008 | 2006 | | |
2009 | 2007 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
44 | 44 | | |
45 | 45 | | |
46 | 46 | | |
47 | | - | |
| 47 | + | |
48 | 48 | | |
49 | 49 | | |
50 | 50 | | |
| |||
69 | 69 | | |
70 | 70 | | |
71 | 71 | | |
72 | | - | |
73 | 72 | | |
74 | 73 | | |
75 | 74 | | |
| |||
4386 | 4385 | | |
4387 | 4386 | | |
4388 | 4387 | | |
4389 | | - | |
4390 | | - | |
4391 | | - | |
4392 | | - | |
| 4388 | + | |
| 4389 | + | |
4393 | 4390 | | |
| 4391 | + | |
4394 | 4392 | | |
4395 | 4393 | | |
4396 | 4394 | | |
4397 | | - | |
| 4395 | + | |
4398 | 4396 | | |
4399 | 4397 | | |
4400 | 4398 | | |
| |||
4420 | 4418 | | |
4421 | 4419 | | |
4422 | 4420 | | |
4423 | | - | |
4424 | | - | |
4425 | | - | |
4426 | | - | |
4427 | | - | |
4428 | | - | |
4429 | | - | |
4430 | | - | |
4431 | | - | |
4432 | | - | |
4433 | | - | |
4434 | | - | |
4435 | | - | |
| 4421 | + | |
| 4422 | + | |
| 4423 | + | |
4436 | 4424 | | |
4437 | 4425 | | |
4438 | 4426 | | |
| |||
4453 | 4441 | | |
4454 | 4442 | | |
4455 | 4443 | | |
4456 | | - | |
4457 | | - | |
4458 | | - | |
4459 | | - | |
| 4444 | + | |
| 4445 | + | |
| 4446 | + | |
4460 | 4447 | | |
4461 | 4448 | | |
4462 | 4449 | | |
4463 | 4450 | | |
4464 | | - | |
4465 | | - | |
| 4451 | + | |
4466 | 4452 | | |
4467 | 4453 | | |
4468 | 4454 | | |
| |||
5565 | 5551 | | |
5566 | 5552 | | |
5567 | 5553 | | |
5568 | | - | |
| 5554 | + | |
| 5555 | + | |
| 5556 | + | |
| 5557 | + | |
| 5558 | + | |
| 5559 | + | |
| 5560 | + | |
| 5561 | + | |
| 5562 | + | |
| 5563 | + | |
| 5564 | + | |
| 5565 | + | |
| 5566 | + | |
| 5567 | + | |
| 5568 | + | |
| 5569 | + | |
| 5570 | + | |
| 5571 | + | |
| 5572 | + | |
| 5573 | + | |
| 5574 | + | |
| 5575 | + | |
| 5576 | + | |
| 5577 | + | |
| 5578 | + | |
| 5579 | + | |
5569 | 5580 | | |
5570 | | - | |
5571 | | - | |
5572 | | - | |
5573 | | - | |
5574 | | - | |
5575 | | - | |
5576 | | - | |
5577 | | - | |
| 5581 | + | |
| 5582 | + | |
| 5583 | + | |
| 5584 | + | |
5578 | 5585 | | |
5579 | 5586 | | |
5580 | 5587 | | |
| |||
5597 | 5604 | | |
5598 | 5605 | | |
5599 | 5606 | | |
5600 | | - | |
5601 | | - | |
| 5607 | + | |
5602 | 5608 | | |
5603 | 5609 | | |
| 5610 | + | |
5604 | 5611 | | |
| 5612 | + | |
| 5613 | + | |
| 5614 | + | |
5605 | 5615 | | |
5606 | 5616 | | |
5607 | 5617 | | |
| |||
0 commit comments