From 62e221e1c01e3985d2b8e4b68c364f8486c327ab Mon Sep 17 00:00:00 2001 From: David Rowley Date: Tue, 15 Sep 2020 23:44:45 +1200 Subject: [PATCH] Allow incremental sorts for windowing functions This expands on the work done in d2d8a229b and allows incremental sort to be considered during create_window_paths(). Author: David Rowley Reviewed-by: Daniel Gustafsson, Tomas Vondra Discussion: https://postgr.es/m/CAApHDvoOHobiA2x13NtWnWLcTXYj9ddpCkv9PnAJQBMegYf_xw%40mail.gmail.com --- src/backend/optimizer/plan/planner.c | 41 +++++++++++++++++++++----- src/test/regress/expected/window.out | 44 ++++++++++++++++++++++++++++ src/test/regress/sql/window.sql | 22 ++++++++++++++ 3 files changed, 100 insertions(+), 7 deletions(-) diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 139c5e3dc24..8007e205ed7 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -4582,14 +4582,17 @@ create_window_paths(PlannerInfo *root, /* * Consider computing window functions starting from the existing * cheapest-total path (which will likely require a sort) as well as any - * existing paths that satisfy root->window_pathkeys (which won't). + * existing paths that satisfy or partially satisfy root->window_pathkeys. */ foreach(lc, input_rel->pathlist) { Path *path = (Path *) lfirst(lc); + int presorted_keys; if (path == input_rel->cheapest_total_path || - pathkeys_contained_in(root->window_pathkeys, path->pathkeys)) + pathkeys_count_contained_in(root->window_pathkeys, path->pathkeys, + &presorted_keys) || + presorted_keys > 0) create_one_window_path(root, window_rel, path, @@ -4664,18 +4667,42 @@ create_one_window_path(PlannerInfo *root, { WindowClause *wc = lfirst_node(WindowClause, l); List *window_pathkeys; + int presorted_keys; + bool is_sorted; window_pathkeys = make_pathkeys_for_window(root, wc, root->processed_tlist); + is_sorted = pathkeys_count_contained_in(window_pathkeys, + path->pathkeys, + &presorted_keys); + /* Sort if necessary */ - if (!pathkeys_contained_in(window_pathkeys, path->pathkeys)) + if (!is_sorted) { - path = (Path *) create_sort_path(root, window_rel, - path, - window_pathkeys, - -1.0); + /* + * No presorted keys or incremental sort disabled, just perform a + * complete sort. + */ + if (presorted_keys == 0 || !enable_incremental_sort) + path = (Path *) create_sort_path(root, window_rel, + path, + window_pathkeys, + -1.0); + else + { + /* + * Since we have presorted keys and incremental sort is + * enabled, just use incremental sort. + */ + path = (Path *) create_incremental_sort_path(root, + window_rel, + path, + window_pathkeys, + presorted_keys, + -1.0); + } } if (lnext(activeWindows, l)) diff --git a/src/test/regress/expected/window.out b/src/test/regress/expected/window.out index 13c91c9916f..21c6cac491f 100644 --- a/src/test/regress/expected/window.out +++ b/src/test/regress/expected/window.out @@ -3200,6 +3200,50 @@ FROM empsalary; -> Seq Scan on empsalary (5 rows) +-- Test incremental sorting +EXPLAIN (COSTS OFF) +SELECT * FROM + (SELECT depname, + empno, + salary, + enroll_date, + row_number() OVER (PARTITION BY depname ORDER BY enroll_date) AS first_emp, + row_number() OVER (PARTITION BY depname ORDER BY enroll_date DESC) AS last_emp + FROM empsalary) emp +WHERE first_emp = 1 OR last_emp = 1; + QUERY PLAN +----------------------------------------------------------------------------------- + Subquery Scan on emp + Filter: ((emp.first_emp = 1) OR (emp.last_emp = 1)) + -> WindowAgg + -> Incremental Sort + Sort Key: empsalary.depname, empsalary.enroll_date + Presorted Key: empsalary.depname + -> WindowAgg + -> Sort + Sort Key: empsalary.depname, empsalary.enroll_date DESC + -> Seq Scan on empsalary +(10 rows) + +SELECT * FROM + (SELECT depname, + empno, + salary, + enroll_date, + row_number() OVER (PARTITION BY depname ORDER BY enroll_date) AS first_emp, + row_number() OVER (PARTITION BY depname ORDER BY enroll_date DESC) AS last_emp + FROM empsalary) emp +WHERE first_emp = 1 OR last_emp = 1; + depname | empno | salary | enroll_date | first_emp | last_emp +-----------+-------+--------+-------------+-----------+---------- + develop | 8 | 6000 | 10-01-2006 | 1 | 5 + develop | 7 | 4200 | 01-01-2008 | 5 | 1 + personnel | 2 | 3900 | 12-23-2006 | 1 | 2 + personnel | 5 | 3500 | 12-10-2007 | 2 | 1 + sales | 1 | 5000 | 10-01-2006 | 1 | 3 + sales | 4 | 4800 | 08-08-2007 | 3 | 1 +(6 rows) + -- cleanup DROP TABLE empsalary; -- test user-defined window function with named args and default args diff --git a/src/test/regress/sql/window.sql b/src/test/regress/sql/window.sql index af206ca4664..9485aebce85 100644 --- a/src/test/regress/sql/window.sql +++ b/src/test/regress/sql/window.sql @@ -936,6 +936,28 @@ SELECT lag(1) OVER (PARTITION BY depname ORDER BY salary,enroll_date,empno) FROM empsalary; +-- Test incremental sorting +EXPLAIN (COSTS OFF) +SELECT * FROM + (SELECT depname, + empno, + salary, + enroll_date, + row_number() OVER (PARTITION BY depname ORDER BY enroll_date) AS first_emp, + row_number() OVER (PARTITION BY depname ORDER BY enroll_date DESC) AS last_emp + FROM empsalary) emp +WHERE first_emp = 1 OR last_emp = 1; + +SELECT * FROM + (SELECT depname, + empno, + salary, + enroll_date, + row_number() OVER (PARTITION BY depname ORDER BY enroll_date) AS first_emp, + row_number() OVER (PARTITION BY depname ORDER BY enroll_date DESC) AS last_emp + FROM empsalary) emp +WHERE first_emp = 1 OR last_emp = 1; + -- cleanup DROP TABLE empsalary; -- 2.30.2