apache / apache/datafusion

Classify more operators as swappable / commutative

Open
#22,456 1 comment 0 reactions 1 assignee Claimed by @neilconway View on GitHub
enhancement
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

### Is your feature request related to a problem or challenge?

In `Operator::swap()`, the following operators are currently not considered commutative: `Plus`, `Multiply`, `And`, `Or`, `BitwiseAnd`, `BitwiseOr`, `BitwiseXor`. In principle they are perfectly commutative and should be classified as such.

Fixing this is slightly involved, because it breaks other optimizations. For example, from `order.slt`:

```
CREATE EXTERNAL TABLE ordered_table(a, b, ...)
STORED AS CSV ...
WITH ORDER (a + b ASC);

SELECT a + b AS sum1
FROM ordered_table
ORDER BY a + b ASC LIMIT 1;
```

If we say that `Plus` is swappable, expression simplification will rewrite the query `ORDER BY` as `b + a`, but we do *not* apply expression simplification / canonicalization to the `WITH ORDER` clause on the table. That means we'd do a redundant sort.

The current situation is not optimal either: we'll insert redundant sorts on `ORDER BY b + a`, for example. So the proper fix is something like:

1. (A) _Either_ teach the physical planner to use commutativity when assessing if two expressions are equivalent (right now it basically just uses equality)
1. (B) _or_ make sure that we canonicalize every `Expr` that makes its way into the optimizer, including those derived from DDL and other places
2. Mark the missing operators as commutative / swappable

Offhand 1(b) seems simpler to me.

### Describe the solution you'd like

_No response_

### Describe alternatives you've considered

_No response_

### Additional context

_No response_

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.