Try to find sort order that satisfies multiple windows #19779
Description
When calculating window functions, we can merge sort steps for windows, if their required orders are suffixes of some common order. E.g. in query like this we should sort once by p, o asc:
EXPLAIN
SELECT
min(number) OVER (PARTITION BY p),
max(number) OVER (PARTITION BY p ORDER BY o ASC)
FROM
(
SELECT
number,
intDiv(number, 3) AS p,
mod(number, 5) AS o
FROM numbers(10)
)
┌─explain─────────────────────────────────────────────────────────────────────────────────────┐
│ Expression (Projection + Before ORDER BY) │
│ Window (Window step for window 'PARTITION BY p') │
│ MergingSorted (Merge sorted streams for window 'PARTITION BY p') │
│ MergeSorting (Merge sorted blocks for window 'PARTITION BY p') │
│ PartialSorting (Sort each block for window 'PARTITION BY p') │
│ Window (Window step for window 'PARTITION BY p ORDER BY o ASC') │
│ MergingSorted (Merge sorted streams for window 'PARTITION BY p ORDER BY o ASC') │
│ MergeSorting (Merge sorted blocks for window 'PARTITION BY p ORDER BY o ASC') │
│ PartialSorting (Sort each block for window 'PARTITION BY p ORDER BY o ASC') │
│ Expression (Before window functions + Projection + Before ORDER BY) │
│ SettingQuotaAndLimits (Set limits and quota after reading from storage) │
│ ReadFromStorage (SystemNumbers) │
└─────────────────────────────────────────────────────────────────────────────────────────────┘
To do this, it is enough to sort the windows by their PARTITION BY + ORDER BY clauses, and then start with the strongest sorting required.
This is also required for correctness, see this comment: https://github.com/postgres/postgres/blob/ca3b37487be333a1d241dab1bbdd17a211a88f43/src/backend/optimizer/plan/planner.c#L5516