While working on [1] to make improvements in the query planner around
the speed to find EquivalenceMembers in an EquivalenceClass, because
that patch does have a large impact in terms of performance
improvements, some performance tests with that patch started to
highlight some other places that bottleneck the planner's performance.
One of those places is in generate_orderedappend_paths() when we find
that the required sort order is the same as the reverse of the
partition order. In this case, we build a list of paths for each
partition using the lcons() function. Since Lists are now arrays in
PostgreSQL, lcons() isn't as efficient as it once was and it must
memmove the entire existing contents of the list up one element to
make way to prepend the new element. This is effectively quadratic and
becomes noticeable with a large number of partitions.
One way we could solve that is to just lappend() the new item and then
just reverse the order of the list only when we need to. This has the
added advantage of removing a bunch of semi-duplicated code from
generate_orderedappend_paths(). It also has a noticeable impact on the
planner's performance.
I did a quick test with:
create table lp (a int, b int) partition by list(a);
select 'create table lp'||x::text||' partition of lp for values
in('||x::text||');' from generate_Series(1,10000)x;
\gexec
create index on lp(a);
Using: psql -c "explain (analyze, timing off) select * from lp order
by a desc" postgres | grep "Planning Time"
master:
Planning Time: 6034.765 ms
Planning Time: 5919.914 ms
Planning Time: 5720.529 ms
master + eclass idx (from [1]) (yes, it really is this much faster)
Planning Time: 549.262 ms
Planning Time: 489.023 ms
Planning Time: 497.803 ms
master + eclass idx + list_reverse (attached)
Planning Time: 517.067 ms
Planning Time: 463.613 ms
Planning Time: 463.036 ms
I suspect there won't be much controversy here and there's certainly
not much complexity, so in absence of anyone voicing an opinion here,
I'm inclined to not waste too much time on this one and just get it
done. I'll leave it for a few days.
David
[1]
https://postgr.es/m/flat/caj2pmkzncgoukse+_5lthd+kbxkvq6h2hqn8esxpxd+cxmg...@mail.gmail.com
diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index a709d23ef1..5f1f675e44 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -1654,6 +1654,37 @@ list_copy_deep(const List *oldlist)
return newlist;
}
+/*
+ * Reverses the order of 'list' elements in place and returns the input list
+ */
+List *
+list_reverse(List *list)
+{
+ ListCell *head;
+ ListCell *tail;
+
+ if (list == NIL)
+ return NIL;
+
+ head = &list->elements[0];
+ tail = &list->elements[list->length - 1];
+
+ while (head < tail)
+ {
+ ListCell tmp;
+
+ /* Swap data at the head and tail position */
+ memcpy(&tmp, head, sizeof(ListCell));
+ memcpy(head, tail, sizeof(ListCell));
+ memcpy(tail, &tmp, sizeof(ListCell));
+
+ head++;
+ tail--;
+ }
+
+ return list;
+}
+
/*
* Sort a list according to the specified comparator function.
*
diff --git a/src/backend/optimizer/path/allpaths.c
b/src/backend/optimizer/path/allpaths.c
index ae0f9bdc8a..4356102399 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -1801,7 +1801,7 @@ generate_orderedappend_paths(PlannerInfo *root,
RelOptInfo *rel,
* Collect the appropriate child paths. The required
logic varies
* for the Append and MergeAppend cases.
*/
- if (match_partition_order)
+ if (match_partition_order || match_partition_order_desc)
{
/*
* We're going to make a plain Append path. We
don't need
@@ -1822,25 +1822,6 @@ generate_orderedappend_paths(PlannerInfo *root,
RelOptInfo *rel,
fractional_subpaths =
lappend(fractional_subpaths, cheapest_fractional);
}
}
- else if (match_partition_order_desc)
- {
- /*
- * As above, but we need to reverse the order
of the children,
- * because nodeAppend.c doesn't know anything
about reverse
- * ordering and will scan the children in the
order presented.
- */
- cheapest_startup =
get_singleton_append_subpath(cheapest_startup);
- cheapest_total =
get_singleton_append_subpath(cheapest_total);
-
- startup_subpaths = lcons(cheapest_startup,
startup_subpaths);
- total_subpaths = lcons(cheapest_total,
total_subpaths);
-
- if (cheapest_fractional)
- {
- cheapest_fractional =
get_singleton_append_subpath(cheapest_fractional);
- fractional_subpaths =
lcons(cheapest_fractional, fractional_subpaths);
- }
- }
else
{
/*
@@ -1861,6 +1842,13 @@ generate_orderedappend_paths(PlannerInfo *root,
RelOptInfo *rel,
/* ... and build the Append or MergeAppend paths */
if (match_partition_order || match_partition_order_desc)
{
+ /*
+ * When in DESC partition order, reverse the order of
the list
+ * so that we scan the partitions in reverse order
+ */
+ if (match_partition_order_desc)
+ startup_subpaths =
list_reverse(startup_subpaths);
+
/* We only need Append */
add_path(rel, (Path *) create_append_path(root,
rel,
@@ -1872,6 +1860,11 @@ generate_orderedappend_paths(PlannerInfo *root,
RelOptInfo *rel,
false,
-1));
if (startup_neq_total)
+ {
+ /* reverse order of path list when in partition
DESC order */
+ if (match_partition_order_desc)
+ total_subpaths =
list_reverse(total_subpaths);
+
add_path(rel, (Path *) create_append_path(root,
rel,
total_subpaths,
@@ -1881,8 +1874,13 @@ generate_orderedappend_paths(PlannerInfo *root,
RelOptInfo *rel,
0,
false,
-1));
-
+ }
if (fractional_subpaths)
+ {
+ /* reverse order of path list when in partition
DESC order */
+ if (match_partition_order_desc)
+ fractional_subpaths =
list_reverse(fractional_subpaths);
+
add_path(rel, (Path *) create_append_path(root,
rel,
fractional_subpaths,
@@ -1892,6 +1890,7 @@ generate_orderedappend_paths(PlannerInfo *root,
RelOptInfo *rel,
0,
false,
-1));
+ }
}
else
{
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 529a382d28..5a2cc38f78 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -626,6 +626,8 @@ extern pg_nodiscard List *list_copy_head(const List
*oldlist, int len);
extern pg_nodiscard List *list_copy_tail(const List *oldlist, int nskip);
extern pg_nodiscard List *list_copy_deep(const List *oldlist);
+extern List *list_reverse(List *list);
+
typedef int (*list_sort_comparator) (const ListCell *a, const ListCell *b);
extern void list_sort(List *list, list_sort_comparator cmp);
