public inbox for [email protected]
help / color / mirror / Atom feedFrom: Andrey V. Lepikhov <[email protected]>
To: Tomas Vondra <[email protected]>
To: Teodor Sigaev <[email protected]>
Cc: Tomas Vondra <[email protected]>
Cc: PostgreSQL Developers <[email protected]>
Subject: Re: POC: GROUP BY optimization
Date: Tue, 1 Feb 2022 14:48:11 +0500
Message-ID: <[email protected]> (raw)
In-Reply-To: <[email protected]>
References: <CA+q6zcVRrd-z4YZ4M43ccst7aGL9==w5r1fionRWhP9ot6mybQ@mail.gmail.com>
<20200514235220.xewrrwjvatxzn3g6@development>
<CALT9ZEFU60nW9TJqHUs9Ex_tqv__7t=jfF4Q=iwwxJTO0PY7Rg@mail.gmail.com>
<20201026085721.g6h5xljxvodnmk34@localhost>
<CALT9ZEF8FUZoijXnFsDXNgqbSHFzaCU2q0cmJFnZ4z2wNZO98w@mail.gmail.com>
<20201026104040.6bigvej6f55vjvgp@localhost>
<20201027201509.jfv6sfhrmxhdwlvk@development>
<20201029145025.tn3tekboot37nkbf@localhost>
<CALT9ZEEqnS+tObVjLWZrUme-PZQ-O0krpFCfQhwG-4ziSeSrBQ@mail.gmail.com>
<CALtqXTdsuDq_dsbE0F0XHd8U2-ceSdvN9wr1zkap=sJypgBJBA@mail.gmail.com>
<CALT9ZEFwfCQAzUVfUxak=fzhgwez3jn=5XcpsU9HbKQ_VjrZ-A@mail.gmail.com>
<[email protected]>
<CALtqXTe4rKXHXxNNGVy0wHVwGYYJpy2QNPTN29qq+ErBJJakrA@mail.gmail.com>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
> On 7/22/21 3:58 AM, Tomas Vondra wrote:
> I've simplified the costing a bit, and the attached version actually
> undoes all the "suspicious" plan changes in postgres_fdw. It changes one
> new plan, but that seems somewhat reasonable, as it pushes sort to the
> remote side.
I tried to justify heap-sort part of the compute_cpu_sort_cost() routine
and realized, that here we may have a mistake.
After a week of efforts, I don't found any research papers on dependence
of bounded heap-sort time compexity on number of duplicates.
So, I suppose self-made formula, based on simple logical constructions:
1. We should base on initial formula: cost ~ N*LOG2(M), where M -
output_tuples.
2. Realize, that full representation of this formula is:
cost ~ N*LOG2(min{N,M})
3. In the case of multicolumn, number of comparisons for each next
column can be estimated by the same formula, but arranged to a number of
tuples per group:
comparisons ~ input * LOG2(min{input,M})
4. Realize, that for the case, when M > input, we should change this
formula a bit:
comparisons ~ max{input,M} * LOG2(min{input,M})
Remember, that in our case M << tuples.
So, general formula for bounded heap sort can be written as:
cost ~ N * sum(max{n_i,M}/N * LOG2(min{n_i,M})), i=1,ncols
where n_1 == N, n_i - number of tuples per group, estimated from
previous iteration.
In attachment - an implementation of this approach.
--
regards,
Andrey Lepikhov
Postgres Professional
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 68a32740d7..2c3cce57aa 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1872,6 +1872,15 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
*
* N * sum( Fk * log(Gk) )
*
+ * For bounded heap sort we haven't such a duplicates-related research. So invent
+ * it based on a simple logic (M - number of output tuples):
+ * For one column we can estimate number of comparisons as:
+ * N * log(min{N,M})
+ * For the case of many columns we can natively estimate number of comparisons by
+ * the formula:
+ * sum(max{n_i,M} * log(min{N,M})),
+ * where n_0 == N, n_i - number of tuples per group, estimated on previous step.
+ *
* Note: We also consider column width, not just the comparator cost.
*
* NOTE: some callers currently pass NIL for pathkeys because they
@@ -1881,7 +1890,7 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
static Cost
compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
Cost comparison_cost, double tuples, double output_tuples,
- bool heapSort)
+ bool bounded_sort)
{
Cost per_tuple_cost = 0.0;
ListCell *lc;
@@ -1907,7 +1916,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
* of this function, but I'm not sure. I suggest we introduce some simple
* constants for that, instead of magic values.
*/
- output_tuples = (heapSort) ? 2.0 * output_tuples : tuples;
+ output_tuples = (bounded_sort) ? 2.0 * output_tuples : tuples;
per_tuple_cost += 2.0 * cpu_operator_cost * LOG2(output_tuples);
/* add cost provided by caller */
@@ -1925,8 +1934,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
{
PathKey *pathkey = (PathKey*) lfirst(lc);
EquivalenceMember *em;
- double nGroups,
- correctedNGroups;
+ double nGroups;
/*
* We believe that equivalence members aren't very different, so, to
@@ -2000,24 +2008,16 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
*/
if (i >= nPresortedKeys)
{
- if (heapSort)
- {
- double heap_tuples;
-
- /* have to keep at least one group, and a multiple of group size */
- heap_tuples = Max(ceil(output_tuples / tuplesPerPrevGroup) * tuplesPerPrevGroup,
- tuplesPerPrevGroup);
-
- /* so how many (whole) groups is that? */
- correctedNGroups = ceil(heap_tuples / tuplesPerPrevGroup);
- }
+ /*
+ * Quick sort and 'top-N' sorting (bounded heap sort) algorithms
+ * have different formulas for time complexity estimation.
+ */
+ if (bounded_sort)
+ per_tuple_cost += totalFuncCost *
+ (Max(tuplesPerPrevGroup, output_tuples) / tuples) *
+ LOG2(2.0 * Min(tuplesPerPrevGroup, output_tuples));
else
- /* all groups in the input */
- correctedNGroups = nGroups;
-
- correctedNGroups = Max(1.0, ceil(correctedNGroups));
-
- per_tuple_cost += totalFuncCost * LOG2(correctedNGroups);
+ per_tuple_cost += totalFuncCost * LOG2(nGroups);
}
i++;
Attachments:
[text/plain] bounded_heap_sort_fix.txt (3.1K, ../[email protected]/2-bounded_heap_sort_fix.txt)
download | inline diff:
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 68a32740d7..2c3cce57aa 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1872,6 +1872,15 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
*
* N * sum( Fk * log(Gk) )
*
+ * For bounded heap sort we haven't such a duplicates-related research. So invent
+ * it based on a simple logic (M - number of output tuples):
+ * For one column we can estimate number of comparisons as:
+ * N * log(min{N,M})
+ * For the case of many columns we can natively estimate number of comparisons by
+ * the formula:
+ * sum(max{n_i,M} * log(min{N,M})),
+ * where n_0 == N, n_i - number of tuples per group, estimated on previous step.
+ *
* Note: We also consider column width, not just the comparator cost.
*
* NOTE: some callers currently pass NIL for pathkeys because they
@@ -1881,7 +1890,7 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr)
static Cost
compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
Cost comparison_cost, double tuples, double output_tuples,
- bool heapSort)
+ bool bounded_sort)
{
Cost per_tuple_cost = 0.0;
ListCell *lc;
@@ -1907,7 +1916,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
* of this function, but I'm not sure. I suggest we introduce some simple
* constants for that, instead of magic values.
*/
- output_tuples = (heapSort) ? 2.0 * output_tuples : tuples;
+ output_tuples = (bounded_sort) ? 2.0 * output_tuples : tuples;
per_tuple_cost += 2.0 * cpu_operator_cost * LOG2(output_tuples);
/* add cost provided by caller */
@@ -1925,8 +1934,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
{
PathKey *pathkey = (PathKey*) lfirst(lc);
EquivalenceMember *em;
- double nGroups,
- correctedNGroups;
+ double nGroups;
/*
* We believe that equivalence members aren't very different, so, to
@@ -2000,24 +2008,16 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys,
*/
if (i >= nPresortedKeys)
{
- if (heapSort)
- {
- double heap_tuples;
-
- /* have to keep at least one group, and a multiple of group size */
- heap_tuples = Max(ceil(output_tuples / tuplesPerPrevGroup) * tuplesPerPrevGroup,
- tuplesPerPrevGroup);
-
- /* so how many (whole) groups is that? */
- correctedNGroups = ceil(heap_tuples / tuplesPerPrevGroup);
- }
+ /*
+ * Quick sort and 'top-N' sorting (bounded heap sort) algorithms
+ * have different formulas for time complexity estimation.
+ */
+ if (bounded_sort)
+ per_tuple_cost += totalFuncCost *
+ (Max(tuplesPerPrevGroup, output_tuples) / tuples) *
+ LOG2(2.0 * Min(tuplesPerPrevGroup, output_tuples));
else
- /* all groups in the input */
- correctedNGroups = nGroups;
-
- correctedNGroups = Max(1.0, ceil(correctedNGroups));
-
- per_tuple_cost += totalFuncCost * LOG2(correctedNGroups);
+ per_tuple_cost += totalFuncCost * LOG2(nGroups);
}
i++;
view thread (2+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected]
Subject: Re: POC: GROUP BY optimization
In-Reply-To: <[email protected]>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox