Skip to content

Commit 61a4cc6

Browse files
author
Alexander Korotkov
committed
Sorting optimization when first pathkey matches partition column.
1 parent b592bd4 commit 61a4cc6

File tree

3 files changed

+206
-18
lines changed

3 files changed

+206
-18
lines changed

‎contrib/pg_pathman/expected/pg_pathman.out

Lines changed: 78 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -340,6 +340,26 @@ EXPLAIN (COSTS OFF) SELECT * FROM test.num_range_rel WHERE (id >= 500 AND id < 1
340340
-> Seq Scan on num_range_rel_4
341341
(8 rows)
342342

343+
EXPLAIN (COSTS OFF) SELECT * FROM test.num_range_rel ORDER BY id;
344+
QUERY PLAN
345+
----------------------------------------------------------------
346+
Append
347+
-> Index Scan using num_range_rel_1_pkey on num_range_rel_1
348+
-> Index Scan using num_range_rel_2_pkey on num_range_rel_2
349+
-> Index Scan using num_range_rel_3_pkey on num_range_rel_3
350+
-> Index Scan using num_range_rel_4_pkey on num_range_rel_4
351+
(5 rows)
352+
353+
EXPLAIN (COSTS OFF) SELECT * FROM test.num_range_rel WHERE id <= 2500 ORDER BY id;
354+
QUERY PLAN
355+
----------------------------------------------------------------
356+
Append
357+
-> Index Scan using num_range_rel_1_pkey on num_range_rel_1
358+
-> Index Scan using num_range_rel_2_pkey on num_range_rel_2
359+
-> Index Scan using num_range_rel_3_pkey on num_range_rel_3
360+
Index Cond: (id <= 2500)
361+
(5 rows)
362+
343363
EXPLAIN (COSTS OFF) SELECT * FROM test.range_rel WHERE dt > '2015-02-15';
344364
QUERY PLAN
345365
------------------------------------------------------------------------------------
@@ -380,6 +400,27 @@ EXPLAIN (COSTS OFF) SELECT * FROM test.range_rel WHERE (dt >= '2015-01-15' AND d
380400
-> Seq Scan on range_rel_4
381401
(8 rows)
382402

403+
EXPLAIN (COSTS OFF) SELECT * FROM test.range_rel ORDER BY dt;
404+
QUERY PLAN
405+
----------------------------------------------------------
406+
Append
407+
-> Index Scan using range_rel_1_dt_idx on range_rel_1
408+
-> Index Scan using range_rel_2_dt_idx on range_rel_2
409+
-> Index Scan using range_rel_3_dt_idx on range_rel_3
410+
-> Index Scan using range_rel_4_dt_idx on range_rel_4
411+
(5 rows)
412+
413+
EXPLAIN (COSTS OFF) SELECT * FROM test.range_rel WHERE dt >= '2015-01-15' ORDER BY dt DESC;
414+
QUERY PLAN
415+
-------------------------------------------------------------------------------------
416+
Append
417+
-> Index Scan Backward using range_rel_4_dt_idx on range_rel_4
418+
-> Index Scan Backward using range_rel_3_dt_idx on range_rel_3
419+
-> Index Scan Backward using range_rel_2_dt_idx on range_rel_2
420+
-> Index Scan Backward using range_rel_1_dt_idx on range_rel_1
421+
Index Cond: (dt >= 'Thu Jan 15 00:00:00 2015'::timestamp without time zone)
422+
(6 rows)
423+
383424
/*
384425
* Sorting
385426
*/
@@ -410,11 +451,10 @@ SET enable_seqscan = OFF;
410451
EXPLAIN (COSTS OFF) SELECT * FROM test.range_rel WHERE dt < '2015-03-01' ORDER BY dt;
411452
QUERY PLAN
412453
----------------------------------------------------------
413-
Merge Append
414-
Sort Key: range_rel_1.dt
454+
Append
415455
-> Index Scan using range_rel_1_dt_idx on range_rel_1
416456
-> Index Scan using range_rel_2_dt_idx on range_rel_2
417-
(4 rows)
457+
(3 rows)
418458

419459
EXPLAIN (COSTS OFF) SELECT * FROM test.range_rel_1 UNION ALL SELECT * FROM test.range_rel_2 ORDER BY dt;
420460
QUERY PLAN
@@ -428,6 +468,41 @@ EXPLAIN (COSTS OFF) SELECT * FROM test.range_rel_1 UNION ALL SELECT * FROM test.
428468
/*
429469
* Join
430470
*/
471+
SET enable_hashjoin = OFF;
472+
SET enable_mergejoin = ON;
473+
EXPLAIN (COSTS OFF)
474+
SELECT * FROM test.range_rel j1
475+
JOIN test.range_rel j2 on j2.id = j1.id
476+
JOIN test.num_range_rel j3 on j3.id = j1.id
477+
WHERE j1.dt < '2015-03-01' AND j2.dt >= '2015-02-01' ORDER BY j2.dt;
478+
QUERY PLAN
479+
-------------------------------------------------------------------------------------------
480+
Sort
481+
Sort Key: j2.dt
482+
-> Merge Join
483+
Merge Cond: (j3.id = j2.id)
484+
-> Append
485+
-> Index Scan using num_range_rel_1_pkey on num_range_rel_1 j3
486+
-> Index Scan using num_range_rel_2_pkey on num_range_rel_2 j3_1
487+
-> Index Scan using num_range_rel_3_pkey on num_range_rel_3 j3_2
488+
-> Index Scan using num_range_rel_4_pkey on num_range_rel_4 j3_3
489+
-> Materialize
490+
-> Merge Join
491+
Merge Cond: (j1.id = j2.id)
492+
-> Merge Append
493+
Sort Key: j1.id
494+
-> Index Scan using range_rel_1_pkey on range_rel_1 j1
495+
-> Index Scan using range_rel_2_pkey on range_rel_2 j1_1
496+
-> Materialize
497+
-> Merge Append
498+
Sort Key: j2.id
499+
-> Index Scan using range_rel_2_pkey on range_rel_2 j2
500+
-> Index Scan using range_rel_3_pkey on range_rel_3 j2_1
501+
-> Index Scan using range_rel_4_pkey on range_rel_4 j2_2
502+
(22 rows)
503+
504+
SET enable_hashjoin = ON;
505+
SET enable_mergejoin = OFF;
431506
EXPLAIN (COSTS OFF)
432507
SELECT * FROM test.range_rel j1
433508
JOIN test.range_rel j2 on j2.id = j1.id

‎contrib/pg_pathman/pg_pathman.c

Lines changed: 115 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,7 @@
1212
#include "postgres.h"
1313
#include "fmgr.h"
1414
#include "miscadmin.h"
15+
#include "nodes/makefuncs.h"
1516
#include "nodes/nodeFuncs.h"
1617
#include "nodes/pg_list.h"
1718
#include "nodes/relation.h"
@@ -95,11 +96,13 @@ static void set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel,
9596
static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte);
9697
static void set_append_rel_size(PlannerInfo *root, RelOptInfo *rel,
9798
Index rti, RangeTblEntry *rte);
98-
static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte);
99+
static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte, PathKey *pathkeyAsc, PathKey *pathkeyDesc);
99100
static List *accumulate_append_subpath(List *subpaths, Path *path);
100101
static void generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
101102
List *live_childrels,
102-
List *all_child_pathkeys);
103+
List *all_child_pathkeys,
104+
PathKey *pathkeyAsc,
105+
PathKey *pathkeyDesc);
103106

104107

105108
char *
@@ -407,6 +410,41 @@ pathman_set_rel_pathlist_hook(PlannerInfo *root, RelOptInfo *rel, Index rti, Ran
407410
Oid *dsm_arr;
408411
List *ranges,
409412
*wrappers;
413+
PathKey *pathkeyAsc = NULL,
414+
*pathkeyDesc = NULL;
415+
416+
if (prel->parttype == PT_RANGE)
417+
{
418+
/*
419+
* Get pathkeys for ascending and descending sort by patition
420+
* column.
421+
*/
422+
List *pathkeys;
423+
Var *var;
424+
Oid vartypeid,
425+
varcollid;
426+
int32 type_mod;
427+
TypeCacheEntry *tce;
428+
429+
/* Make Var from patition column */
430+
get_rte_attribute_type(rte, prel->attnum,
431+
&vartypeid, &type_mod, &varcollid);
432+
var = makeVar(rti, prel->attnum, vartypeid, type_mod, varcollid, 0);
433+
var->location = -1;
434+
435+
/* Determine operator type */
436+
tce = lookup_type_cache(var->vartype, TYPECACHE_LT_OPR | TYPECACHE_GT_OPR);
437+
438+
/* Make pathkeys */
439+
pathkeys = build_expression_pathkey(root, (Expr *)var, NULL,
440+
tce->lt_opr, NULL, false);
441+
if (pathkeys)
442+
pathkeyAsc = (PathKey *) linitial(pathkeys);
443+
pathkeys = build_expression_pathkey(root, (Expr *)var, NULL,
444+
tce->gt_opr, NULL, false);
445+
if (pathkeys)
446+
pathkeyDesc = (PathKey *) linitial(pathkeys);
447+
}
410448

411449
rte->inh = true;
412450
dsm_arr = (Oid *) dsm_array_get_pointer(&prel->children);
@@ -491,9 +529,8 @@ pathman_set_rel_pathlist_hook(PlannerInfo *root, RelOptInfo *rel, Index rti, Ran
491529
}
492530

493531
rel->pathlist = NIL;
494-
set_append_rel_pathlist(root, rel, rti, rte);
532+
set_append_rel_pathlist(root, rel, rti, rte, pathkeyAsc, pathkeyDesc);
495533
set_append_rel_size(root, rel, rti, rte);
496-
497534
}
498535

499536
/* Invoke original hook if needed */
@@ -1387,7 +1424,8 @@ set_foreign_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
13871424
*/
13881425
static void
13891426
set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
1390-
Index rti, RangeTblEntry *rte)
1427+
Index rti, RangeTblEntry *rte,
1428+
PathKey *pathkeyAsc, PathKey *pathkeyDesc)
13911429
{
13921430
int parentRTindex = rti;
13931431
List *live_childrels = NIL;
@@ -1536,7 +1574,8 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
15361574
*/
15371575
if (subpaths_valid)
15381576
generate_mergeappend_paths(root, rel, live_childrels,
1539-
all_child_pathkeys);
1577+
all_child_pathkeys, pathkeyAsc,
1578+
pathkeyDesc);
15401579
}
15411580

15421581
static List *
@@ -1550,7 +1589,21 @@ accumulate_append_subpath(List *subpaths, Path *path)
15501589

15511590
//---------------------------------------------------------------
15521591

1592+
/*
1593+
* Returns the same list in reversed order.
1594+
*/
1595+
static List *
1596+
list_reverse(List *l)
1597+
{
1598+
List *result = NIL;
1599+
ListCell *lc;
15531600

1601+
foreach (lc, l)
1602+
{
1603+
result = lcons(lfirst(lc), result);
1604+
}
1605+
return result;
1606+
}
15541607

15551608
/*
15561609
* generate_mergeappend_paths
@@ -1578,7 +1631,8 @@ accumulate_append_subpath(List *subpaths, Path *path)
15781631
static void
15791632
generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
15801633
List *live_childrels,
1581-
List *all_child_pathkeys)
1634+
List *all_child_pathkeys,
1635+
PathKey *pathkeyAsc, PathKey *pathkeyDesc)
15821636
{
15831637
ListCell *lcp;
15841638

@@ -1588,6 +1642,7 @@ generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
15881642
List *startup_subpaths = NIL;
15891643
List *total_subpaths = NIL;
15901644
bool startup_neq_total = false;
1645+
bool presorted = true;
15911646
ListCell *lcr;
15921647

15931648
/* Select the child paths for this ordering... */
@@ -1619,6 +1674,7 @@ generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
16191674
childrel->cheapest_total_path;
16201675
/* Assert we do have an unparameterized path for this child */
16211676
Assert(cheapest_total->param_info == NULL);
1677+
presorted = false;
16221678
}
16231679

16241680
/*
@@ -1635,17 +1691,61 @@ generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
16351691
accumulate_append_subpath(total_subpaths, cheapest_total);
16361692
}
16371693

1638-
/* ... and build the MergeAppend paths */
1639-
add_path(rel, (Path *) create_merge_append_path(root,
1640-
rel,
1641-
startup_subpaths,
1642-
pathkeys,
1643-
NULL));
1644-
if (startup_neq_total)
1694+
/*
1695+
* When first pathkey matching ascending/descending sort by partition
1696+
* column then build path with Append node, because MergeAppend is not
1697+
* required in this case.
1698+
*/
1699+
if ((PathKey *) linitial(pathkeys) == pathkeyAsc && presorted)
1700+
{
1701+
Path *path;
1702+
1703+
path = (Path *) create_append_path(rel, startup_subpaths, NULL);
1704+
path->pathkeys = pathkeys;
1705+
add_path(rel, path);
1706+
1707+
if (startup_neq_total)
1708+
{
1709+
path = (Path *) create_append_path(rel, total_subpaths, NULL);
1710+
path->pathkeys = pathkeys;
1711+
add_path(rel, path);
1712+
}
1713+
}
1714+
else if ((PathKey *) linitial(pathkeys) == pathkeyDesc && presorted)
1715+
{
1716+
/*
1717+
* When pathkey is descending sort by partition column then we
1718+
* need to scan partitions in reversed order.
1719+
*/
1720+
Path *path;
1721+
1722+
path = (Path *) create_append_path(rel,
1723+
list_reverse(startup_subpaths), NULL);
1724+
path->pathkeys = pathkeys;
1725+
add_path(rel, path);
1726+
1727+
if (startup_neq_total)
1728+
{
1729+
path = (Path *) create_append_path(rel,
1730+
list_reverse(total_subpaths), NULL);
1731+
path->pathkeys = pathkeys;
1732+
add_path(rel, path);
1733+
}
1734+
}
1735+
else
1736+
{
1737+
/* ... and build the MergeAppend paths */
16451738
add_path(rel, (Path *) create_merge_append_path(root,
16461739
rel,
1647-
total_subpaths,
1740+
startup_subpaths,
16481741
pathkeys,
16491742
NULL));
1743+
if (startup_neq_total)
1744+
add_path(rel, (Path *) create_merge_append_path(root,
1745+
rel,
1746+
total_subpaths,
1747+
pathkeys,
1748+
NULL));
1749+
}
16501750
}
16511751
}

‎contrib/pg_pathman/sql/pg_pathman.sql

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -87,10 +87,14 @@ EXPLAIN (COSTS OFF) SELECT * FROM test.num_range_rel WHERE id > 2500;
8787
EXPLAIN (COSTS OFF) SELECT * FROM test.num_range_rel WHERE id >= 1000 AND id < 3000;
8888
EXPLAIN (COSTS OFF) SELECT * FROM test.num_range_rel WHERE id >= 1500 AND id < 2500;
8989
EXPLAIN (COSTS OFF) SELECT * FROM test.num_range_rel WHERE (id >= 500 AND id < 1500) OR (id > 2500);
90+
EXPLAIN (COSTS OFF) SELECT * FROM test.num_range_rel ORDER BY id;
91+
EXPLAIN (COSTS OFF) SELECT * FROM test.num_range_rel WHERE id <= 2500 ORDER BY id;
9092
EXPLAIN (COSTS OFF) SELECT * FROM test.range_rel WHERE dt > '2015-02-15';
9193
EXPLAIN (COSTS OFF) SELECT * FROM test.range_rel WHERE dt >= '2015-02-01' AND dt < '2015-03-01';
9294
EXPLAIN (COSTS OFF) SELECT * FROM test.range_rel WHERE dt >= '2015-02-15' AND dt < '2015-03-15';
9395
EXPLAIN (COSTS OFF) SELECT * FROM test.range_rel WHERE (dt >= '2015-01-15' AND dt < '2015-02-15') OR (dt > '2015-03-15');
96+
EXPLAIN (COSTS OFF) SELECT * FROM test.range_rel ORDER BY dt;
97+
EXPLAIN (COSTS OFF) SELECT * FROM test.range_rel WHERE dt >= '2015-01-15' ORDER BY dt DESC;
9498

9599
/*
96100
* Sorting
@@ -107,6 +111,15 @@ EXPLAIN (COSTS OFF) SELECT * FROM test.range_rel_1 UNION ALL SELECT * FROM test.
107111
/*
108112
* Join
109113
*/
114+
SET enable_hashjoin = OFF;
115+
SET enable_mergejoin = ON;
116+
EXPLAIN (COSTS OFF)
117+
SELECT * FROM test.range_rel j1
118+
JOIN test.range_rel j2 on j2.id = j1.id
119+
JOIN test.num_range_rel j3 on j3.id = j1.id
120+
WHERE j1.dt < '2015-03-01' AND j2.dt >= '2015-02-01' ORDER BY j2.dt;
121+
SET enable_hashjoin = ON;
122+
SET enable_mergejoin = OFF;
110123
EXPLAIN (COSTS OFF)
111124
SELECT * FROM test.range_rel j1
112125
JOIN test.range_rel j2 on j2.id = j1.id

0 commit comments

Comments
 (0)