Support date_bin / date_trunc satisfaction for multi-key Range partitioning #24644

Is your feature request related to a problem?

Child of epic #22395 and leftover work from #23569 / #24501.

#23569 asked that both of these layouts skip a hash shuffle for

SELECT a, date_bin(INTERVAL '1 hour', timestamp) AS binned, SUM(x)
FROM t
GROUP BY a, binned

1. Range([timestamp]) with splits aligned to the bin — done in feat: skip hash shuffle for date_bin/date_trunc on Range([timestamp]) #24501. Extra GROUP BY keys (a, …) are a superset of the transformed range key, so range_monotonic_fn_satisfies_keys can use .any().
2. Range on timestamp and a (compound / multi-key range) — not done.

#24501 fail-closes on compound range:

// datafusion/physical-expr/src/partitioning.rs
if range.ordering().len() != 1 {
    return false;
}

A unit test asserts Range([key, timestamp]) does not satisfy GROUP BY (key, date_bin(timestamp)) via that path.

Jayant asked on #24501 whether this expands in a follow-up:
#24501 (comment)

Why this is not “drop the len() != 1 check”

Range([key, timestamp]) with a lex split (k2, 01:00) is not the same as Range([timestamp]).

• Partition 0: rows < (k2, 01:00), including (k1, 02:00)
• Partition 1: rows >= (k2, 01:00)

The same date_bin(timestamp) can appear on both sides if key is not in the GROUP BY. Example: (k1, 02:00) and (k2, 02:00) share hour 02:00 but sit in different partitions.

So this is unsafe:

required.iter().any(|e| {
    check_monotonic_transform(e, some_range_key) && disjoint_on_that_component(...)
})

GROUP BY (key, date_bin(timestamp)) is partition-disjoint on that layout: key is the lex prefix, and an aligned date_bin is disjoint on the timestamp component of the split. GROUP BY date_bin(timestamp) alone is not.

Proposed rule

A group-key set G is partition-disjoint for a multi-key range only if no group can appear on both sides of every lex split.

For each split, either:

• the full lex prefix of the range key is in G, and the remaining key has a disjoint monotonic transform in G, or
• the first differing range key has a disjoint monotonic transform in G.

Compound split-point “predecessor” is not “predecessor of column i only.” Adjacent partitions are defined by the full lex compare.

RangePartitioning::project can already rewrite Range([key, timestamp]) → Range([key, time_bin]) when the projection keeps key and date_bin(timestamp). That only preserves output metadata. It does not skip the shuffle. Satisfaction is the missing piece.

Describe the solution you'd like

• Implement the lex-prefix + disjoint-transform check in range_monotonic_fn_satisfies_keys (or a dedicated helper).
• Tests:
  • Range([key, timestamp]) + GROUP BY (key, date_bin(aligned)) → satisfied (no shuffle).
  • Range([key, timestamp]) + GROUP BY date_bin(...) only → not satisfied.
  • Unaligned / straddling bin (e.g. date_trunc('day') or date_bin(70 minutes) on an hour split) → not satisfied.
• Optional SLT table that declares compound range metadata (today’s listing fixtures are single-key).

Describe alternatives you've considered

• Leave the len() != 1 guard forever. Fine if nobody declares Range([key, timestamp]). Support functions date_bin and date_trunc in range partition satisfaction #23569 still lists case (2).
• Treat any extra group key as enough. Incorrect for GROUP BY date_bin only on a compound range.

Additional context

• PR: feat: skip hash shuffle for date_bin/date_trunc on Range([timestamp]) #24501
• Epic: [EPIC] Implement Range Partitioning #22395
• Parent: Support functions date_bin and date_trunc in range partition satisfaction #23569 (item 2)