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