Generating partitioning tuple conversion maps faster
Hi,
The code in convert_tuples_by_name_map() could be made a bit smarter
to speed up the search for the column with the same name by first
looking at the same attnum in the other relation rather than starting
the search from the first attnum each time.
I imagine most people are going to create partitions with columns in
the same order as they are in the partitioned table. This will happen
automatically if the CREATE TABLE .. PARTITION OF syntax is used, so
it makes sense to exploit that knowledge.
I've attached a patch which modifies convert_tuples_by_name_map() to
have it just start the inner loop search in the same position as we
are currently in the outer loop. Best case, this takes the function
from being O(N^2) to O(N). It quite possible that the partition or,
more likely, the partitioned table has had some columns dropped
(likely this lives longer than a partition), in which case we don't
want to miss the target column by 1, so I've coded the patch to count
the non-dropped columns and start the search after having ignored
dropped columns.
This patch is just a few lines of code. I do think there's much more
room to improve this whole area. For example, build child->parent map
from the parent->child map instead of searching again later with the
inputs reversed. Although, that's more than a handful of lines of
code. The change I'm proposing here seems worthwhile to me. FWIW,
something similar is done in make_inh_translation_list(), although I
think my way might have a slightly better chance of not hitting the
worst cases search.
Benchmark: (Uses tables with 1000 columns, each with a name 11 chars in length.)
Setup:
select 'create table listp (' || string_agg('c' ||
left(md5(x::Text),10) || ' int',',') || ') partition by list (c' ||
left(md5('1'),10) || ');' from generate_Series(1,1000) x;
\gexec
create table listp0 partition of listp for values in(0);
create table listp1 partition of listp for values in(1);
select 'create table listpd (' || string_agg('c' ||
left(md5(x::Text),10) || ' int',',') || ') partition by list (c' ||
left(md5('1'),10) || ');' from generate_Series(0,1000) x;
\gexec
select 'alter table listpd drop column c' || left(md5(0::text),10) || ';';
\gexec
create table listpd0 partition of listpd for values in(0);
create table listpd1 partition of listpd for values in(1);
select 'create table list (' || string_agg('c' ||
left(md5(x::Text),10) || ' int',',') || ');' from
generate_Series(1,1000) x;
\gexec
\q
psql -t -c "select 'insert into listp values(' || string_Agg('1',',')
|| ');' from generate_Series(1,1000) x;" postgres > insertp.sql
psql -t -c "select 'insert into listpd values(' || string_Agg('1',',')
|| ');' from generate_Series(1,1000) x;" postgres > insertpd.sql
psql -t -c "select 'insert into list values(' || string_Agg('1',',')
|| ');' from generate_Series(1,1000) x;" postgres > insert.sql
psql -t -c "select 'update list set c' || left(md5('1'),10) || ' = (c'
|| left(md5('1'),10) || ' + 1) & 1;'" postgres > update.sql
psql -t -c "select 'update listp set c' || left(md5('1'),10) || ' =
(c' || left(md5('1'),10) || ' + 1) & 1;'" postgres > updatep.sql
psql -t -c "select 'update listpd set c' || left(md5('1'),10) || ' =
(c' || left(md5('1'),10) || ' + 1) & 1;'" postgres > updatepd.sql
Tests:
# Test 1: INSERT control test for non-partitioned table.
pgbench -n -T 60 -f insert.sql postgres
# Test 2: INSERT perfect match
pgbench -n -T 60 -f insertp.sql postgres
# Test 3: INSERT dropped first column from parent
pgbench -n -T 60 -f insertpd.sql postgres
# Test 4: UPDATE control test for non-partitioned table.
psql -c "truncate list;" postgres
psql -f insert.sql postgres
pgbench -n -T 60 -f update.sql postgres
# Test 5: UPDATE perfect match
psql -c "truncate listp;" postgres
psql -f insertp.sql postgres
pgbench -n -T 60 -f updatep.sql postgres
# Test 6: UPDATE dropped first column from parent
psql -c "truncate listpd;" postgres
psql -f insertpd.sql postgres
pgbench -n -T 60 -f updatepd.sql postgres
Results:
AWS m5d (fsync off)
Unpatched:
Test 1:
tps = 1055.527253 (excluding connections establishing)
Test 2:
tps = 355.308869 (excluding connections establishing)
Test 3:
tps = 361.465022 (excluding connections establishing)
Test 4:
tps = 1107.483236 (excluding connections establishing)
Test 5:
tps = 132.805775 (excluding connections establishing)
Test 6:
tps = 86.303093 (excluding connections establishing)
Patched:
Test 1:
tps = 1055.831144 (excluding connections establishing)
Test 2:
tps = 1014.282634 (excluding connections establishing)
Test 3:
tps = 982.258274 (excluding connections establishing)
Test 4:
tps = 625.429778 (excluding connections establishing)
Test 5:
tps = 525.667826 (excluding connections establishing)
Test 6:
tps = 173.529296 (excluding connections establishing)
I'd have expected Test 6 to do about 480-500tps. Adding debug to check
why it's not revealed that the search is doing what's expected. I'm
unsure why it has not improved more.
Given the small size of this patch. I think it's a good candidate for
the July 'fest.
--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
Attachments:
v1-0001-Improve-best-case-speed-of-tuple-conversion-map-g.patchapplication/octet-stream; name=v1-0001-Improve-best-case-speed-of-tuple-conversion-map-g.patchDownload
From 0b9be8e526335686d2a4eeba5a62313b5018a5c4 Mon Sep 17 00:00:00 2001
From: "dgrowley@gmail.com" <dgrowley@gmail.com>
Date: Mon, 25 Jun 2018 16:31:47 +1200
Subject: [PATCH v1] Improve best case speed of tuple conversion map generation
Previously convert_tuples_by_name_map naively performed a search of all
inner loop columns for each loop done in the outer loop. When partitioned
tables had many columns this could result in slow generation of the tuple
conversion maps. For INSERT and UPDATE statements that touched few rows,
this could mean a very large overhead indeed.
We can do a bit better with this loop. It's quite likely that the columns
in partitioned tables and their partitions are in the same order, so it
makes sense to start searching in the inner loop at the same position that
we're on in the outer loop. This makes the best case search O(N) (N being
the number of columns). The worst case is still O(N^2), but it seems
unlikely that would happen, although we must take some protection against
starting the search one column too late due to a dropped column. Without
this protection the worst case could be easy to hit.
---
src/backend/access/common/tupconvert.c | 21 +++++++++++++++++++--
1 file changed, 19 insertions(+), 2 deletions(-)
diff --git a/src/backend/access/common/tupconvert.c b/src/backend/access/common/tupconvert.c
index 2d0d2f4b32..578bf7f2ba 100644
--- a/src/backend/access/common/tupconvert.c
+++ b/src/backend/access/common/tupconvert.c
@@ -297,6 +297,7 @@ convert_tuples_by_name_map(TupleDesc indesc,
AttrNumber *attrMap;
int n;
int i;
+ int outnondropped = 0;
n = outdesc->natts;
attrMap = (AttrNumber *) palloc0(n * sizeof(AttrNumber));
@@ -313,9 +314,22 @@ convert_tuples_by_name_map(TupleDesc indesc,
attname = NameStr(outatt->attname);
atttypid = outatt->atttypid;
atttypmod = outatt->atttypmod;
+
+ /*
+ * Now search for an attribute with the same name in the indesc. It
+ * seems likely that a partitioned table will have the attributes in
+ * the same order as the partition, so we optimistically start our
+ * search at the same attnum (minus the so-far counted number of
+ * dropped columns in outdesc). If a column were dropped in outdesc
+ * and not indesc then if we didn't account for the dropped column, it
+ * could mean we end up starting our search one column after the one
+ * we want to find, resulting in only finding our target on the final
+ * column we check.
+ */
for (j = 0; j < indesc->natts; j++)
{
- Form_pg_attribute inatt = TupleDescAttr(indesc, j);
+ int k = (outnondropped + j) % indesc->natts;
+ Form_pg_attribute inatt = TupleDescAttr(indesc, k);
if (inatt->attisdropped)
continue;
@@ -330,7 +344,7 @@ convert_tuples_by_name_map(TupleDesc indesc,
attname,
format_type_be(outdesc->tdtypeid),
format_type_be(indesc->tdtypeid))));
- attrMap[i] = (AttrNumber) (j + 1);
+ attrMap[i] = inatt->attnum;
break;
}
}
@@ -342,6 +356,9 @@ convert_tuples_by_name_map(TupleDesc indesc,
attname,
format_type_be(outdesc->tdtypeid),
format_type_be(indesc->tdtypeid))));
+
+ /* keep track of number of non-dropped outdesc columns */
+ outnondropped++;
}
return attrMap;
--
2.16.2.windows.1
On Mon, Jun 25, 2018 at 10:30 AM David Rowley
<david.rowley@2ndquadrant.com> wrote:
[...]
Given the small size of this patch. I think it's a good candidate for
the July 'fest.
Just a different thought, how about having flag array something like
needed_tuple_conv?
While loading partdesc, we could calculate that the columns of partition table
are aligned with the parent or not?
Regards,
Amul
On 2018/06/25 14:12, amul sul wrote:
On Mon, Jun 25, 2018 at 10:30 AM David Rowley
<david.rowley@2ndquadrant.com> wrote:[...]
Given the small size of this patch. I think it's a good candidate for
the July 'fest.Just a different thought, how about having flag array something like
needed_tuple_conv?While loading partdesc, we could calculate that the columns of partition table
are aligned with the parent or not?
Yeah maybe, but ISTM, that could be implemented *in addition to* the
tweaks to convert_tuples_by_name_map that David's proposing, which seem
helpful in their own right.
Thanks,
Amit
On Mon, Jun 25, 2018 at 10:57 AM Amit Langote
<Langote_Amit_f8@lab.ntt.co.jp> wrote:
On 2018/06/25 14:12, amul sul wrote:
On Mon, Jun 25, 2018 at 10:30 AM David Rowley
<david.rowley@2ndquadrant.com> wrote:[...]
Given the small size of this patch. I think it's a good candidate for
the July 'fest.Just a different thought, how about having flag array something like
needed_tuple_conv?While loading partdesc, we could calculate that the columns of partition table
are aligned with the parent or not?Yeah maybe, but ISTM, that could be implemented *in addition to* the
tweaks to convert_tuples_by_name_map that David's proposing, which seem
helpful in their own right.
Yes, I agree.
Regards,
Amul
On 06/25/2018 08:00 AM, David Rowley wrote:
I'd have expected Test 6 to do about 480-500tps. Adding debug to check
why it's not revealed that the search is doing what's expected. I'm
unsure why it has not improved more.
I think I found one possible reason for this slowness. Your patch
behaves as expected when there is a dropped output column, but does one
extra comparison when there is a dropped input column. This backwards
conversion is called from ExecInitRoutingInfo. To fix this, I'd just
keep a persistent inner loop counter (see the attached patch).
Still, fixing this doesn't improve the performance. According to perf
report, updatepd.sql spends 25% of time in strcmp, and updatep.sql about
0.5%, but they are comparing the same column names, even with the same
alignment and relative offsets. I'm completely puzzled by this.
As a side thought, we wouldn't have to go through this if we had a hash
table that is easy to use, or perhaps string interning in catcache.
--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Attachments:
persistent-inner.patchtext/x-patch; name=persistent-inner.patchDownload
diff --git a/src/backend/access/common/tupconvert.c b/src/backend/access/common/tupconvert.c
index 2d0d2f4..573ddd82 100644
--- a/src/backend/access/common/tupconvert.c
+++ b/src/backend/access/common/tupconvert.c
@@ -297,6 +297,7 @@ convert_tuples_by_name_map(TupleDesc indesc,
AttrNumber *attrMap;
int n;
int i;
+ int nextInput = -1;
n = outdesc->natts;
attrMap = (AttrNumber *) palloc0(n * sizeof(AttrNumber));
@@ -315,7 +316,13 @@ convert_tuples_by_name_map(TupleDesc indesc,
atttypmod = outatt->atttypmod;
for (j = 0; j < indesc->natts; j++)
{
- Form_pg_attribute inatt = TupleDescAttr(indesc, j);
+ Form_pg_attribute inatt;
+
+ nextInput++;
+ if (nextInput >= indesc->natts)
+ nextInput = 0;
+
+ inatt = TupleDescAttr(indesc, nextInput);
if (inatt->attisdropped)
continue;
@@ -330,7 +337,7 @@ convert_tuples_by_name_map(TupleDesc indesc,
attname,
format_type_be(outdesc->tdtypeid),
format_type_be(indesc->tdtypeid))));
- attrMap[i] = (AttrNumber) (j + 1);
+ attrMap[i] = (AttrNumber) (nextInput + 1);
break;
}
}
On 29 June 2018 at 02:23, Alexander Kuzmenkov
<a.kuzmenkov@postgrespro.ru> wrote:
I think I found one possible reason for this slowness. Your patch behaves as
expected when there is a dropped output column, but does one extra
comparison when there is a dropped input column. This backwards conversion
is called from ExecInitRoutingInfo. To fix this, I'd just keep a persistent
inner loop counter (see the attached patch).
It's just 2000 comparisons vs 1000.
Still, fixing this doesn't improve the performance. According to perf
report, updatepd.sql spends 25% of time in strcmp, and updatep.sql about
0.5%, but they are comparing the same column names, even with the same
alignment and relative offsets. I'm completely puzzled by this.
On further inspection, the slowdown is coming from the planner in
make_inh_translation_list(). The INSERT path does not hit that since
the planner's job is pretty simple for simple INSERTs.
As a side thought, we wouldn't have to go through this if we had a hash
table that is easy to use, or perhaps string interning in catcache.
Maybe it's better to try the direct lookup and fall back on
SearchSysCacheAttName() if the same attnum does not have the same
name.
--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
On 29 June 2018 at 11:10, David Rowley <david.rowley@2ndquadrant.com> wrote:
On further inspection, the slowdown is coming from the planner in
make_inh_translation_list(). The INSERT path does not hit that since
the planner's job is pretty simple for simple INSERTs.
I've attached a patch that uses SearchSysCacheAttName to speed up
these translations in the planner.
This puts test 6 more at the level I'd have expected.
Here are fresh benchmarks results taken with the attached, again on
AWS m5d instance, though probably not the same one as before
(fsync=off).
Unpatched:
Test 1
tps = 922.479156 (excluding connections establishing)
Test 2
tps = 334.701555 (excluding connections establishing)
Test 3
tps = 327.547316 (excluding connections establishing)
Test 4
tps = 1198.924131 (excluding connections establishing)
Test 5
tps = 125.130723 (excluding connections establishing)
Test 6
tps = 81.511072 (excluding connections establishing)
Patched
Test 1
tps = 918.105382 (excluding connections establishing)
Test 2
tps = 913.315387 (excluding connections establishing)
Test 3
tps = 893.578988 (excluding connections establishing)
Test 4
tps = 1213.238177 (excluding connections establishing)
Test 5
tps = 459.022550 (excluding connections establishing)
Test 6
tps = 416.835747 (excluding connections establishing)
--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
Attachments:
v2_speedup_building_tuple_conversion_maps.patchapplication/octet-stream; name=v2_speedup_building_tuple_conversion_maps.patchDownload
diff --git a/src/backend/access/common/tupconvert.c b/src/backend/access/common/tupconvert.c
index 2d0d2f4b32..578bf7f2ba 100644
--- a/src/backend/access/common/tupconvert.c
+++ b/src/backend/access/common/tupconvert.c
@@ -297,6 +297,7 @@ convert_tuples_by_name_map(TupleDesc indesc,
AttrNumber *attrMap;
int n;
int i;
+ int outnondropped = 0;
n = outdesc->natts;
attrMap = (AttrNumber *) palloc0(n * sizeof(AttrNumber));
@@ -313,9 +314,22 @@ convert_tuples_by_name_map(TupleDesc indesc,
attname = NameStr(outatt->attname);
atttypid = outatt->atttypid;
atttypmod = outatt->atttypmod;
+
+ /*
+ * Now search for an attribute with the same name in the indesc. It
+ * seems likely that a partitioned table will have the attributes in
+ * the same order as the partition, so we optimistically start our
+ * search at the same attnum (minus the so-far counted number of
+ * dropped columns in outdesc). If a column were dropped in outdesc
+ * and not indesc then if we didn't account for the dropped column, it
+ * could mean we end up starting our search one column after the one
+ * we want to find, resulting in only finding our target on the final
+ * column we check.
+ */
for (j = 0; j < indesc->natts; j++)
{
- Form_pg_attribute inatt = TupleDescAttr(indesc, j);
+ int k = (outnondropped + j) % indesc->natts;
+ Form_pg_attribute inatt = TupleDescAttr(indesc, k);
if (inatt->attisdropped)
continue;
@@ -330,7 +344,7 @@ convert_tuples_by_name_map(TupleDesc indesc,
attname,
format_type_be(outdesc->tdtypeid),
format_type_be(indesc->tdtypeid))));
- attrMap[i] = (AttrNumber) (j + 1);
+ attrMap[i] = inatt->attnum;
break;
}
}
@@ -342,6 +356,9 @@ convert_tuples_by_name_map(TupleDesc indesc,
attname,
format_type_be(outdesc->tdtypeid),
format_type_be(indesc->tdtypeid))));
+
+ /* keep track of number of non-dropped outdesc columns */
+ outnondropped++;
}
return attrMap;
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index 2d470240d5..5a1e7a12ec 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -51,6 +51,7 @@
#include "utils/lsyscache.h"
#include "utils/rel.h"
#include "utils/selfuncs.h"
+#include "utils/syscache.h"
typedef struct
@@ -1896,6 +1897,7 @@ make_inh_translation_list(Relation oldrelation, Relation newrelation,
List *vars = NIL;
TupleDesc old_tupdesc = RelationGetDescr(oldrelation);
TupleDesc new_tupdesc = RelationGetDescr(newrelation);
+ Oid new_relid = RelationGetRelid(newrelation);
int oldnatts = old_tupdesc->natts;
int newnatts = new_tupdesc->natts;
int old_attno;
@@ -1941,7 +1943,7 @@ make_inh_translation_list(Relation oldrelation, Relation newrelation,
* There's no guarantee it'll have the same column position, because
* of cases like ALTER TABLE ADD COLUMN and multiple inheritance.
* However, in simple cases it will be the same column number, so try
- * that before we go groveling through all the columns.
+ * that before looking for it in syscache.
*
* Note: the test for (att = ...) != NULL cannot fail, it's just a
* notational device to include the assignment into the if-clause.
@@ -1953,16 +1955,16 @@ make_inh_translation_list(Relation oldrelation, Relation newrelation,
new_attno = old_attno;
else
{
- for (new_attno = 0; new_attno < newnatts; new_attno++)
- {
- att = TupleDescAttr(new_tupdesc, new_attno);
- if (!att->attisdropped &&
- strcmp(attname, NameStr(att->attname)) == 0)
- break;
- }
- if (new_attno >= newnatts)
+ HeapTuple newtup = SearchSysCacheAttName(new_relid, attname);
+
+ if (!newtup)
elog(ERROR, "could not find inherited attribute \"%s\" of relation \"%s\"",
attname, RelationGetRelationName(newrelation));
+
+ new_attno = ((Form_pg_attribute) GETSTRUCT(newtup))->attnum - 1;
+ ReleaseSysCache(newtup);
+
+ att = TupleDescAttr(new_tupdesc, new_attno);
}
/* Found it, check type and collation match */
On 06/29/2018 03:25 AM, David Rowley wrote:
I've attached a patch that uses SearchSysCacheAttName to speed up
these translations in the planner.
Good idea. On my desktop, this gives 270 tps dropped vs 610 tps plain
(for updates). If you combine it with persistent inner loop index, it's
probably going to be even faster, because it will only require one
catalog access for each index shift. Now it looks like it goes to
catalog for every column after the dropped one.
What about convert_tuples_by_name_map, do you plan to switch it to
catalog lookups as well?
--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
On 30 June 2018 at 00:22, Alexander Kuzmenkov
<a.kuzmenkov@postgrespro.ru> wrote:
On 06/29/2018 03:25 AM, David Rowley wrote:
I've attached a patch that uses SearchSysCacheAttName to speed up
these translations in the planner.Good idea. On my desktop, this gives 270 tps dropped vs 610 tps plain (for
updates). If you combine it with persistent inner loop index, it's probably
going to be even faster, because it will only require one catalog access for
each index shift. Now it looks like it goes to catalog for every column
after the dropped one.
Thanks for testing.
What about convert_tuples_by_name_map, do you plan to switch it to catalog
lookups as well?
Syscache? I didn't really see an obvious way to get the relids down to
the function. e.g the call through ExecEvalConvertRowtype() ->
convert_tuples_by_name() does not have a Relation to work with, just a
TupleDesc.
I think further work might be diminishing returns. I think your idea
to reduce the loops in test 6 from 2000 down to 1001 should be worth
it. I'll try the idea out next week.
--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
On 30 June 2018 at 05:40, David Rowley <david.rowley@2ndquadrant.com> wrote:
I think your idea
to reduce the loops in test 6 from 2000 down to 1001 should be worth
it. I'll try the idea out next week.
The attached changes things to use your way of picking up the search
for the next column at the column after the last match was found.
I don't think performance will have changed much from the last
version, but here are the performance results (in tps) from my laptop
this time. fsync=off.
Test Unpatched Patched Gain
Test 1 873.837 912.981 104.48%
Test 2 213.004 895.268 420.31%
Test 3 224.810 887.099 394.60%
Test 4 1177.533 1107.767 94.08%
Test 5 97.707 402.258 411.70%
Test 6 72.025 360.702 500.80%
Tests are all the same as the tests done in the initial email on this thread.
Tests 1 and 4 are non-partitioned tests. Any variance there should
just be noise. No code was changed in either of those tests.
--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
Attachments:
v3-0001-Improve-performance-of-tuple-conversion-map-gener.patchapplication/octet-stream; name=v3-0001-Improve-performance-of-tuple-conversion-map-gener.patchDownload
From 01b5e9a1deba60246d816e31e4042ff46a593306 Mon Sep 17 00:00:00 2001
From: "dgrowley@gmail.com" <dgrowley@gmail.com>
Date: Mon, 25 Jun 2018 16:31:47 +1200
Subject: [PATCH v3] Improve performance of tuple conversion map generation
Previously convert_tuples_by_name_map naively performed a search of each
outdesc column starting at the first column in indesc and searched each
indesc column until a match was found. When partitioned tables had many
columns this could result in slow generation of the tuple conversion maps.
For INSERT and UPDATE statements that touched few rows, this could mean a
very large overhead indeed.
We can do a bit better with this loop. It's quite likely that the columns
in partitioned tables and their partitions are in the same order, so it
makes sense to start searching for each column outer column at the inner
column position 1 after where the previous match was found (per idea from
Alexander Kuzmenkov). This makes the best case search O(N) instead of
O(N^2). The worst case is still O(N^2), but it seems unlikely that would
happen.
---
src/backend/access/common/tupconvert.c | 37 ++++++++++++++++++++++++++--------
src/backend/optimizer/prep/prepunion.c | 20 +++++++++---------
2 files changed, 40 insertions(+), 17 deletions(-)
diff --git a/src/backend/access/common/tupconvert.c b/src/backend/access/common/tupconvert.c
index 2d0d2f4b32..11038c69cb 100644
--- a/src/backend/access/common/tupconvert.c
+++ b/src/backend/access/common/tupconvert.c
@@ -295,12 +295,16 @@ convert_tuples_by_name_map(TupleDesc indesc,
const char *msg)
{
AttrNumber *attrMap;
- int n;
+ int outnatts;
+ int innatts;
int i;
+ int nextindesc = -1;
- n = outdesc->natts;
- attrMap = (AttrNumber *) palloc0(n * sizeof(AttrNumber));
- for (i = 0; i < n; i++)
+ outnatts = outdesc->natts;
+ innatts = indesc->natts;
+
+ attrMap = (AttrNumber *) palloc0(outnatts * sizeof(AttrNumber));
+ for (i = 0; i < outnatts; i++)
{
Form_pg_attribute outatt = TupleDescAttr(outdesc, i);
char *attname;
@@ -313,10 +317,28 @@ convert_tuples_by_name_map(TupleDesc indesc,
attname = NameStr(outatt->attname);
atttypid = outatt->atttypid;
atttypmod = outatt->atttypmod;
- for (j = 0; j < indesc->natts; j++)
+
+ /*
+ * Now search for an attribute with the same name in the indesc. It
+ * seems likely that a partitioned table will have the attributes in
+ * the same order as the partition, so the search below is optimized
+ * for that case. It is possible that columns are dropped in one of
+ * the relations, but not the other, so we use the 'nextindesc'
+ * counter to track the starting point of the search. If the inner
+ * loop encounters dropped columns then it will have to skip over
+ * them, but it should leave 'nextindesc' at the correct position for
+ * the next outer loop.
+ */
+ for (j = 0; j < innatts; j++)
{
- Form_pg_attribute inatt = TupleDescAttr(indesc, j);
+ Form_pg_attribute inatt;
+
+ nextindesc++;
+ if (nextindesc >= innatts)
+ nextindesc = 0;
+
+ inatt = TupleDescAttr(indesc, nextindesc);
if (inatt->attisdropped)
continue;
if (strcmp(attname, NameStr(inatt->attname)) == 0)
@@ -330,7 +352,7 @@ convert_tuples_by_name_map(TupleDesc indesc,
attname,
format_type_be(outdesc->tdtypeid),
format_type_be(indesc->tdtypeid))));
- attrMap[i] = (AttrNumber) (j + 1);
+ attrMap[i] = inatt->attnum;
break;
}
}
@@ -343,7 +365,6 @@ convert_tuples_by_name_map(TupleDesc indesc,
format_type_be(outdesc->tdtypeid),
format_type_be(indesc->tdtypeid))));
}
-
return attrMap;
}
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index 7d75e1eda9..95247b4a1c 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -51,6 +51,7 @@
#include "utils/lsyscache.h"
#include "utils/rel.h"
#include "utils/selfuncs.h"
+#include "utils/syscache.h"
typedef struct
@@ -1895,6 +1896,7 @@ make_inh_translation_list(Relation oldrelation, Relation newrelation,
List *vars = NIL;
TupleDesc old_tupdesc = RelationGetDescr(oldrelation);
TupleDesc new_tupdesc = RelationGetDescr(newrelation);
+ Oid new_relid = RelationGetRelid(newrelation);
int oldnatts = old_tupdesc->natts;
int newnatts = new_tupdesc->natts;
int old_attno;
@@ -1940,7 +1942,7 @@ make_inh_translation_list(Relation oldrelation, Relation newrelation,
* There's no guarantee it'll have the same column position, because
* of cases like ALTER TABLE ADD COLUMN and multiple inheritance.
* However, in simple cases it will be the same column number, so try
- * that before we go groveling through all the columns.
+ * that before looking for it in syscache.
*
* Note: the test for (att = ...) != NULL cannot fail, it's just a
* notational device to include the assignment into the if-clause.
@@ -1952,16 +1954,16 @@ make_inh_translation_list(Relation oldrelation, Relation newrelation,
new_attno = old_attno;
else
{
- for (new_attno = 0; new_attno < newnatts; new_attno++)
- {
- att = TupleDescAttr(new_tupdesc, new_attno);
- if (!att->attisdropped &&
- strcmp(attname, NameStr(att->attname)) == 0)
- break;
- }
- if (new_attno >= newnatts)
+ HeapTuple newtup = SearchSysCacheAttName(new_relid, attname);
+
+ if (!newtup)
elog(ERROR, "could not find inherited attribute \"%s\" of relation \"%s\"",
attname, RelationGetRelationName(newrelation));
+
+ new_attno = ((Form_pg_attribute) GETSTRUCT(newtup))->attnum - 1;
+ ReleaseSysCache(newtup);
+
+ att = TupleDescAttr(new_tupdesc, new_attno);
}
/* Found it, check type and collation match */
--
2.17.1
On 07/05/2018 02:52 PM, David Rowley wrote:
On 30 June 2018 at 05:40, David Rowley <david.rowley@2ndquadrant.com> wrote:
I think your idea
to reduce the loops in test 6 from 2000 down to 1001 should be worth
it. I'll try the idea out next week.The attached changes things to use your way of picking up the search
for the next column at the column after the last match was found.
Great. I think we can use the same approach for
make_inh_translation_list, as in the attached patch. It show some
improvement on test 6. I got the following tps, median of 11 runs
(forgot to turn off fsync though):
test master v3 v4
1 414 416 408
2 259 409 404
3 263 400 405
4 417 416 404
5 118 311 305
6 85 280 303
--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Attachments:
v4-0001-Improve-performance-of-tuple-conversion-map-generati.patchtext/x-patch; name=v4-0001-Improve-performance-of-tuple-conversion-map-generati.patchDownload
From a21da8b6e875977eff7b313e37975b39b390a03e Mon Sep 17 00:00:00 2001
From: "dgrowley@gmail.com" <dgrowley@gmail.com>
Date: Mon, 25 Jun 2018 16:31:47 +1200
Subject: [PATCH] Improve performance of tuple conversion map generation
Previously convert_tuples_by_name_map naively performed a search of each
outdesc column starting at the first column in indesc and searched each
indesc column until a match was found. When partitioned tables had many
columns this could result in slow generation of the tuple conversion maps.
For INSERT and UPDATE statements that touched few rows, this could mean a
very large overhead indeed.
We can do a bit better with this loop. It's quite likely that the columns
in partitioned tables and their partitions are in the same order, so it
makes sense to start searching for each column outer column at the inner
column position 1 after where the previous match was found (per idea from
Alexander Kuzmenkov). This makes the best case search O(N) instead of
O(N^2). The worst case is still O(N^2), but it seems unlikely that would
happen.
---
src/backend/access/common/tupconvert.c | 37 ++++++++++++++++++++++++++-------
src/backend/optimizer/prep/prepunion.c | 38 ++++++++++++++++------------------
2 files changed, 47 insertions(+), 28 deletions(-)
diff --git a/src/backend/access/common/tupconvert.c b/src/backend/access/common/tupconvert.c
index 2d0d2f4..11038c6 100644
--- a/src/backend/access/common/tupconvert.c
+++ b/src/backend/access/common/tupconvert.c
@@ -295,12 +295,16 @@ convert_tuples_by_name_map(TupleDesc indesc,
const char *msg)
{
AttrNumber *attrMap;
- int n;
+ int outnatts;
+ int innatts;
int i;
+ int nextindesc = -1;
- n = outdesc->natts;
- attrMap = (AttrNumber *) palloc0(n * sizeof(AttrNumber));
- for (i = 0; i < n; i++)
+ outnatts = outdesc->natts;
+ innatts = indesc->natts;
+
+ attrMap = (AttrNumber *) palloc0(outnatts * sizeof(AttrNumber));
+ for (i = 0; i < outnatts; i++)
{
Form_pg_attribute outatt = TupleDescAttr(outdesc, i);
char *attname;
@@ -313,10 +317,28 @@ convert_tuples_by_name_map(TupleDesc indesc,
attname = NameStr(outatt->attname);
atttypid = outatt->atttypid;
atttypmod = outatt->atttypmod;
- for (j = 0; j < indesc->natts; j++)
+
+ /*
+ * Now search for an attribute with the same name in the indesc. It
+ * seems likely that a partitioned table will have the attributes in
+ * the same order as the partition, so the search below is optimized
+ * for that case. It is possible that columns are dropped in one of
+ * the relations, but not the other, so we use the 'nextindesc'
+ * counter to track the starting point of the search. If the inner
+ * loop encounters dropped columns then it will have to skip over
+ * them, but it should leave 'nextindesc' at the correct position for
+ * the next outer loop.
+ */
+ for (j = 0; j < innatts; j++)
{
- Form_pg_attribute inatt = TupleDescAttr(indesc, j);
+ Form_pg_attribute inatt;
+
+ nextindesc++;
+ if (nextindesc >= innatts)
+ nextindesc = 0;
+
+ inatt = TupleDescAttr(indesc, nextindesc);
if (inatt->attisdropped)
continue;
if (strcmp(attname, NameStr(inatt->attname)) == 0)
@@ -330,7 +352,7 @@ convert_tuples_by_name_map(TupleDesc indesc,
attname,
format_type_be(outdesc->tdtypeid),
format_type_be(indesc->tdtypeid))));
- attrMap[i] = (AttrNumber) (j + 1);
+ attrMap[i] = inatt->attnum;
break;
}
}
@@ -343,7 +365,6 @@ convert_tuples_by_name_map(TupleDesc indesc,
format_type_be(outdesc->tdtypeid),
format_type_be(indesc->tdtypeid))));
}
-
return attrMap;
}
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index 2d47024..7d7517b 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -51,6 +51,7 @@
#include "utils/lsyscache.h"
#include "utils/rel.h"
#include "utils/selfuncs.h"
+#include "utils/syscache.h"
typedef struct
@@ -1896,9 +1897,11 @@ make_inh_translation_list(Relation oldrelation, Relation newrelation,
List *vars = NIL;
TupleDesc old_tupdesc = RelationGetDescr(oldrelation);
TupleDesc new_tupdesc = RelationGetDescr(newrelation);
+ Oid new_relid = RelationGetRelid(newrelation);
int oldnatts = old_tupdesc->natts;
int newnatts = new_tupdesc->natts;
int old_attno;
+ int new_attno = 0;
for (old_attno = 0; old_attno < oldnatts; old_attno++)
{
@@ -1907,7 +1910,6 @@ make_inh_translation_list(Relation oldrelation, Relation newrelation,
Oid atttypid;
int32 atttypmod;
Oid attcollation;
- int new_attno;
att = TupleDescAttr(old_tupdesc, old_attno);
if (att->attisdropped)
@@ -1940,29 +1942,24 @@ make_inh_translation_list(Relation oldrelation, Relation newrelation,
* Otherwise we have to search for the matching column by name.
* There's no guarantee it'll have the same column position, because
* of cases like ALTER TABLE ADD COLUMN and multiple inheritance.
- * However, in simple cases it will be the same column number, so try
- * that before we go groveling through all the columns.
- *
- * Note: the test for (att = ...) != NULL cannot fail, it's just a
- * notational device to include the assignment into the if-clause.
+ * In simple cases, the relative order of columns is mostly the same
+ * in both relations, so try the column of newrelation that is next
+ * to the one we found before, and if that fails, look for it in syscache.
*/
- if (old_attno < newnatts &&
- (att = TupleDescAttr(new_tupdesc, old_attno)) != NULL &&
- !att->attisdropped &&
- strcmp(attname, NameStr(att->attname)) == 0)
- new_attno = old_attno;
- else
+ if (new_attno >= newnatts ||
+ (att = TupleDescAttr(new_tupdesc, new_attno), att->attisdropped) ||
+ strcmp(attname, NameStr(att->attname)) != 0)
{
- for (new_attno = 0; new_attno < newnatts; new_attno++)
- {
- att = TupleDescAttr(new_tupdesc, new_attno);
- if (!att->attisdropped &&
- strcmp(attname, NameStr(att->attname)) == 0)
- break;
- }
- if (new_attno >= newnatts)
+ HeapTuple newtup = SearchSysCacheAttName(new_relid, attname);
+
+ if (!newtup)
elog(ERROR, "could not find inherited attribute \"%s\" of relation \"%s\"",
attname, RelationGetRelationName(newrelation));
+
+ new_attno = ((Form_pg_attribute) GETSTRUCT(newtup))->attnum - 1;
+ ReleaseSysCache(newtup);
+
+ att = TupleDescAttr(new_tupdesc, new_attno);
}
/* Found it, check type and collation match */
@@ -1979,6 +1976,7 @@ make_inh_translation_list(Relation oldrelation, Relation newrelation,
atttypmod,
attcollation,
0));
+ new_attno++;
}
*translated_vars = vars;
--
2.7.4
On 7 July 2018 at 01:08, Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru> wrote:
Great. I think we can use the same approach for make_inh_translation_list,
as in the attached patch. It show some improvement on test 6. I got the
following tps, median of 11 runs (forgot to turn off fsync though):test master v3 v4
1 414 416 408
2 259 409 404
3 263 400 405
4 417 416 404
5 118 311 305
6 85 280 303
Nice. I think that's a good idea. Although, I didn't really like the
use of the comma operator you added. I think since TupleDescAttr can't
be NULL we can just do:
(att = TupleDescAttr(new_tupdesc, new_attno))->attisdropped
There's no shortage of other places that do TupleDescAttr(...)-> so I
think that's perfectly fine.
I also did a slight rewording of the comment above that new code. I've
attached v5.
Please feel free to add yourself as an author of this patch in the
commitfest app. You've probably contributed about as much as I have to
this.
--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
Attachments:
v5-0001-Improve-performance-of-tuple-conversion-map-gener.patchapplication/octet-stream; name=v5-0001-Improve-performance-of-tuple-conversion-map-gener.patchDownload
From da1ada3c7b052d46e4e4162d576484ad67517dd6 Mon Sep 17 00:00:00 2001
From: "dgrowley@gmail.com" <dgrowley@gmail.com>
Date: Mon, 25 Jun 2018 16:31:47 +1200
Subject: [PATCH v5] Improve performance of tuple conversion map generation
Previously convert_tuples_by_name_map naively performed a search of each
outdesc column starting at the first column in indesc and searched each
indesc column until a match was found. When partitioned tables had many
columns this could result in slow generation of the tuple conversion maps.
For INSERT and UPDATE statements that touched few rows, this could mean a
very large overhead indeed.
We can do a bit better with this loop. It's quite likely that the columns
in partitioned tables and their partitions are in the same order, so it
makes sense to start searching for each column outer column at the inner
column position 1 after where the previous match was found (per idea from
Alexander Kuzmenkov). This makes the best case search O(N) instead of
O(N^2). The worst case is still O(N^2), but it seems unlikely that would
happen.
Likewise, in the planner, make_inh_translation_list's search for the
matching column could often end up falling back on an O(N^2) type
search. This commit also improves that by first checking the column that
follows the previous match, instead of the column with the same attnum.
If we fail to match here we fallback on the syscache's hashtable lookup.
---
src/backend/access/common/tupconvert.c | 37 +++++++++++++++++++++++++-------
src/backend/optimizer/prep/prepunion.c | 39 +++++++++++++++++-----------------
2 files changed, 48 insertions(+), 28 deletions(-)
diff --git a/src/backend/access/common/tupconvert.c b/src/backend/access/common/tupconvert.c
index 2d0d2f4b32..11038c69cb 100644
--- a/src/backend/access/common/tupconvert.c
+++ b/src/backend/access/common/tupconvert.c
@@ -295,12 +295,16 @@ convert_tuples_by_name_map(TupleDesc indesc,
const char *msg)
{
AttrNumber *attrMap;
- int n;
+ int outnatts;
+ int innatts;
int i;
+ int nextindesc = -1;
- n = outdesc->natts;
- attrMap = (AttrNumber *) palloc0(n * sizeof(AttrNumber));
- for (i = 0; i < n; i++)
+ outnatts = outdesc->natts;
+ innatts = indesc->natts;
+
+ attrMap = (AttrNumber *) palloc0(outnatts * sizeof(AttrNumber));
+ for (i = 0; i < outnatts; i++)
{
Form_pg_attribute outatt = TupleDescAttr(outdesc, i);
char *attname;
@@ -313,10 +317,28 @@ convert_tuples_by_name_map(TupleDesc indesc,
attname = NameStr(outatt->attname);
atttypid = outatt->atttypid;
atttypmod = outatt->atttypmod;
- for (j = 0; j < indesc->natts; j++)
+
+ /*
+ * Now search for an attribute with the same name in the indesc. It
+ * seems likely that a partitioned table will have the attributes in
+ * the same order as the partition, so the search below is optimized
+ * for that case. It is possible that columns are dropped in one of
+ * the relations, but not the other, so we use the 'nextindesc'
+ * counter to track the starting point of the search. If the inner
+ * loop encounters dropped columns then it will have to skip over
+ * them, but it should leave 'nextindesc' at the correct position for
+ * the next outer loop.
+ */
+ for (j = 0; j < innatts; j++)
{
- Form_pg_attribute inatt = TupleDescAttr(indesc, j);
+ Form_pg_attribute inatt;
+
+ nextindesc++;
+ if (nextindesc >= innatts)
+ nextindesc = 0;
+
+ inatt = TupleDescAttr(indesc, nextindesc);
if (inatt->attisdropped)
continue;
if (strcmp(attname, NameStr(inatt->attname)) == 0)
@@ -330,7 +352,7 @@ convert_tuples_by_name_map(TupleDesc indesc,
attname,
format_type_be(outdesc->tdtypeid),
format_type_be(indesc->tdtypeid))));
- attrMap[i] = (AttrNumber) (j + 1);
+ attrMap[i] = inatt->attnum;
break;
}
}
@@ -343,7 +365,6 @@ convert_tuples_by_name_map(TupleDesc indesc,
format_type_be(outdesc->tdtypeid),
format_type_be(indesc->tdtypeid))));
}
-
return attrMap;
}
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index 7d75e1eda9..c1a1730472 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -51,6 +51,7 @@
#include "utils/lsyscache.h"
#include "utils/rel.h"
#include "utils/selfuncs.h"
+#include "utils/syscache.h"
typedef struct
@@ -1895,9 +1896,11 @@ make_inh_translation_list(Relation oldrelation, Relation newrelation,
List *vars = NIL;
TupleDesc old_tupdesc = RelationGetDescr(oldrelation);
TupleDesc new_tupdesc = RelationGetDescr(newrelation);
+ Oid new_relid = RelationGetRelid(newrelation);
int oldnatts = old_tupdesc->natts;
int newnatts = new_tupdesc->natts;
int old_attno;
+ int new_attno = 0;
for (old_attno = 0; old_attno < oldnatts; old_attno++)
{
@@ -1906,7 +1909,6 @@ make_inh_translation_list(Relation oldrelation, Relation newrelation,
Oid atttypid;
int32 atttypmod;
Oid attcollation;
- int new_attno;
att = TupleDescAttr(old_tupdesc, old_attno);
if (att->attisdropped)
@@ -1939,29 +1941,25 @@ make_inh_translation_list(Relation oldrelation, Relation newrelation,
* Otherwise we have to search for the matching column by name.
* There's no guarantee it'll have the same column position, because
* of cases like ALTER TABLE ADD COLUMN and multiple inheritance.
- * However, in simple cases it will be the same column number, so try
- * that before we go groveling through all the columns.
- *
- * Note: the test for (att = ...) != NULL cannot fail, it's just a
- * notational device to include the assignment into the if-clause.
+ * However, in simple cases, the relative order of columns is mostly
+ * the same in both relations, so try the column of newrelation that
+ * follows immediately after the one that we just found, and if that
+ * fails, let syscache handle it.
*/
- if (old_attno < newnatts &&
- (att = TupleDescAttr(new_tupdesc, old_attno)) != NULL &&
- !att->attisdropped &&
- strcmp(attname, NameStr(att->attname)) == 0)
- new_attno = old_attno;
- else
+ if (new_attno >= newnatts ||
+ (att = TupleDescAttr(new_tupdesc, new_attno))->attisdropped ||
+ strcmp(attname, NameStr(att->attname)) != 0)
{
- for (new_attno = 0; new_attno < newnatts; new_attno++)
- {
- att = TupleDescAttr(new_tupdesc, new_attno);
- if (!att->attisdropped &&
- strcmp(attname, NameStr(att->attname)) == 0)
- break;
- }
- if (new_attno >= newnatts)
+ HeapTuple newtup = SearchSysCacheAttName(new_relid, attname);
+
+ if (!newtup)
elog(ERROR, "could not find inherited attribute \"%s\" of relation \"%s\"",
attname, RelationGetRelationName(newrelation));
+
+ new_attno = ((Form_pg_attribute) GETSTRUCT(newtup))->attnum - 1;
+ ReleaseSysCache(newtup);
+
+ att = TupleDescAttr(new_tupdesc, new_attno);
}
/* Found it, check type and collation match */
@@ -1978,6 +1976,7 @@ make_inh_translation_list(Relation oldrelation, Relation newrelation,
atttypmod,
attcollation,
0));
+ new_attno++;
}
*translated_vars = vars;
--
2.17.1
On 07/09/2018 10:13 AM, David Rowley wrote:
I've attached v5.
v5 looks good to me, I've changed the status to ready.
Please feel free to add yourself as an author of this patch in the
commitfest app. You've probably contributed about as much as I have to
this.
Thanks, I'm fine with being credited as a reviewer.
--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
On 9 July 2018 at 23:28, Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru> wrote:
On 07/09/2018 10:13 AM, David Rowley wrote:
I've attached v5.
v5 looks good to me, I've changed the status to ready.
Many thanks for reviewing this.
--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
On 09/07/18 22:58, David Rowley wrote:
On 9 July 2018 at 23:28, Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru> wrote:
On 07/09/2018 10:13 AM, David Rowley wrote:
I've attached v5.
v5 looks good to me, I've changed the status to ready.
Many thanks for reviewing this.
Pushed, thanks!
- Heikki
On 14 July 2018 at 04:57, Heikki Linnakangas <hlinnaka@iki.fi> wrote:
Pushed, thanks!
Thanks for pushing, and thanks again for reviewing it, Alexander.
--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
Hi,
Any chance for a backport to PG 11?
cherry-pick apply cleanly and with a 100 columns table it improves
performance nicely (20%).
Regards
Didier
On Sat, Jul 14, 2018 at 1:25 AM David Rowley
<david.rowley@2ndquadrant.com> wrote:
Show quoted text
On 14 July 2018 at 04:57, Heikki Linnakangas <hlinnaka@iki.fi> wrote:
Pushed, thanks!
Thanks for pushing, and thanks again for reviewing it, Alexander.
--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
