Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Peter Geoghegan]

On Thu, Dec 17, 2015 at 9:29 AM, Corey Huinker  wrote:
> My apologies to Peter and all the Roberts, I wasn't able to set up a test
> fast enough. Glad it got committed.

I don't use the term "slam-dunk" casually. :-)

This was the first time I ever referred to a patch of mine that way.
It doesn't happen very often, but it does happen.

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Corey Huinker]

On Wed, Dec 16, 2015 at 4:24 PM, Peter Geoghegan  wrote:

> On Wed, Dec 16, 2015 at 12:28 PM, Robert Haas 
> wrote:
> >> I seem to be able to produce these sorting patches at a much greater
> >> rate than they can be committed, in part because Robert is the only
> >> one that ever reviews them, and he is only one person.
> >
> > I object to that vicious slander.  I am at least three people, if not
> more!
>
> I was referring only to the Robert that reviews my sorting patches.  :-)
>
> > Meanwhile, I did some simple benchmarking on your latest patch on my
> > MacBook Pro.  I did pgbench -i -s 100 and then tried:
> >
> > create index x on pgbench_accounts (aid);
> > create index concurrently x on pgbench_accounts (aid);
> >
> > The first took about 6.9 seconds.  The second took about 11.3 seconds
> > patched versus 14.6 seconds unpatched.  That's certainly a healthy
> > improvement.
>
> That seems pretty good. It probably doesn't matter, but FWIW it's
> likely that your numbers are not as good as mine because this ends up
> with a perfect logical/physical correlation, which the quicksort
> precheck [1] does very well on when sorting the TIDs (since input is
> *perfectly* correlated, as opposed to 99.99% correlated, a case that
> does poorly [2]).
>
> > I have also reviewed the code, and it looks OK to me, so committed.
>
> Thanks!
>
> [1] Commit a3f0b3d68f9a5357a3f72b40a45bcc714a9e0649
> [2] http://www.postgresql.org/message-id/54eb580c.2000...@2ndquadrant.com
> --
> Peter Geoghegan
>
>
> --
> Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers
>

My apologies to Peter and all the Roberts, I wasn't able to set up a test
fast enough. Glad it got committed.

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Peter Geoghegan]

On Wed, Dec 16, 2015 at 12:28 PM, Robert Haas  wrote:
>> I seem to be able to produce these sorting patches at a much greater
>> rate than they can be committed, in part because Robert is the only
>> one that ever reviews them, and he is only one person.
>
> I object to that vicious slander.  I am at least three people, if not more!

I was referring only to the Robert that reviews my sorting patches.  :-)

> Meanwhile, I did some simple benchmarking on your latest patch on my
> MacBook Pro.  I did pgbench -i -s 100 and then tried:
>
> create index x on pgbench_accounts (aid);
> create index concurrently x on pgbench_accounts (aid);
>
> The first took about 6.9 seconds.  The second took about 11.3 seconds
> patched versus 14.6 seconds unpatched.  That's certainly a healthy
> improvement.

That seems pretty good. It probably doesn't matter, but FWIW it's
likely that your numbers are not as good as mine because this ends up
with a perfect logical/physical correlation, which the quicksort
precheck [1] does very well on when sorting the TIDs (since input is
*perfectly* correlated, as opposed to 99.99% correlated, a case that
does poorly [2]).

> I have also reviewed the code, and it looks OK to me, so committed.

Thanks!

[1] Commit a3f0b3d68f9a5357a3f72b40a45bcc714a9e0649
[2] http://www.postgresql.org/message-id/54eb580c.2000...@2ndquadrant.com
-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Robert Haas]

On Tue, Nov 17, 2015 at 6:50 PM, Peter Geoghegan  wrote:
> On Tue, Nov 17, 2015 at 12:53 AM, Simon Riggs  wrote:
>> Short and sweet! Looks good.
>
> Thanks.
>
>> I would be inclined to add more comments to explain it, these things have a
>> habit of being forgotten.
>
> I'm not sure what additional detail I can add.
>
> I seem to be able to produce these sorting patches at a much greater
> rate than they can be committed, in part because Robert is the only
> one that ever reviews them, and he is only one person.

I object to that vicious slander.  I am at least three people, if not more!

Meanwhile, I did some simple benchmarking on your latest patch on my
MacBook Pro.  I did pgbench -i -s 100 and then tried:

create index x on pgbench_accounts (aid);
create index concurrently x on pgbench_accounts (aid);

The first took about 6.9 seconds.  The second took about 11.3 seconds
patched versus 14.6 seconds unpatched.  That's certainly a healthy
improvement.

I then rebuilt with --disable-float8-byval, because I was worried that
case might be harmed by this change.  It turns out we win in that case
too, just not by as much.  The time for the first case doesn't change
much, and neither does the unpatched time.  The patched time is about
12.9 seconds.

I have also reviewed the code, and it looks OK to me, so committed.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Jeff Janes]

On Sat, Dec 12, 2015 at 9:48 AM, Corey Huinker  wrote:
>
>
> What, if any, other load should be placed on the underlying table during the
> test?
>
> I ask because CIC statements that run in seconds on our staging machine can
> take many hours on our production machine, when most of the access is just
> reads, though those reads may have been part of a larger transaction that
> did updates elsewhere.

That sounds like the CIC is just blocked waiting for long-lived
transactions to go away.  There isn't much that changes to the sorting
algorithm can do about that.

Cheers,

Jeff


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Peter Geoghegan]

On Fri, Dec 11, 2015 at 9:13 AM, Robert Haas  wrote:
> Also, I'd be in favor of you updating the patch to reflect the
> comments from Tom and Simon on November 17th.

Attached revision:

* Has more worked out comments on encoding, per Simon's request.

* Uses Tom's preferred formulation for encoding TIDs (which involves
unsigned integer casts).

* Sets indexcursor = NULL when the tuplesort is empty, just to be
tidy, per Tom's request.

-- 
Peter Geoghegan
From dd15ae3d0a2bc29fbcefebe2ae08834d2e247070 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan 
Date: Sat, 14 Nov 2015 16:57:20 -0800
Subject: [PATCH] Speed up CREATE INDEX CONCURRENTLY's TID sort

Add a simple TID encoding scheme.  This is used for encoding and
decoding TIDs to and from int8/int64 values, for the benefit of an
expensive, extra tuplesort operation performed by CREATE INDEX
CONCURRENTLY.  The sort now uses the default int8 opclass to sort values
in the ad-hoc encoding, and so benefits from the availability of int8
SortSupport.

Despite the fact that item pointers take up only 6 bytes on disk, the
TID type is always pass-by-reference due to considerations about how
Datums are represented and accessed.  On the other hand, int8 is
usually, in practice, a pass-by-value type.

Testing shows this approach makes CREATE INDEX CONCURRENTLY
significantly faster on platforms where int8 is pass-by-value,
especially when the big saving in memory within tuplesort.c prevents the
sort from being performed externally.  The approach will help to some
degree on all platforms, though.
---
 src/backend/catalog/index.c | 71 ++---
 1 file changed, 67 insertions(+), 4 deletions(-)

diff --git a/src/backend/catalog/index.c b/src/backend/catalog/index.c
index e59b163..c10be3d 100644
--- a/src/backend/catalog/index.c
+++ b/src/backend/catalog/index.c
@@ -109,6 +109,8 @@ static void index_update_stats(Relation rel,
 static void IndexCheckExclusion(Relation heapRelation,
 	Relation indexRelation,
 	IndexInfo *indexInfo);
+static inline int64 itemptr_encode(ItemPointer itemptr);
+static inline void itemptr_decode(ItemPointer itemptr, int64 encoded);
 static bool validate_index_callback(ItemPointer itemptr, void *opaque);
 static void validate_index_heapscan(Relation heapRelation,
 		Relation indexRelation,
@@ -2832,7 +2834,13 @@ validate_index(Oid heapId, Oid indexId, Snapshot snapshot)
 	ivinfo.num_heap_tuples = heapRelation->rd_rel->reltuples;
 	ivinfo.strategy = NULL;
 
-	state.tuplesort = tuplesort_begin_datum(TIDOID, TIDLessOperator,
+	/*
+	 * Encode TIDs as int8 values for the sort, rather than directly sorting
+	 * item pointers.  This can be significantly faster, primarily because TID
+	 * is a pass-by-reference type on all platforms, whereas int8 is
+	 * pass-by-value on most platforms.
+	 */
+	state.tuplesort = tuplesort_begin_datum(INT8OID, Int8LessOperator,
 			InvalidOid, false,
 			maintenance_work_mem,
 			false);
@@ -2872,14 +2880,55 @@ validate_index(Oid heapId, Oid indexId, Snapshot snapshot)
 }
 
 /*
+ * itemptr_encode - Encode ItemPointer as int64/int8
+ *
+ * This representation must produce values encoded as int64 that sort in the
+ * same order as their corresponding original TID values would (using the
+ * default int8 opclass to produce a result equivalent to the default TID
+ * opclass).
+ *
+ * As noted in validate_index(), this can be significantly faster.
+ */
+static inline int64
+itemptr_encode(ItemPointer itemptr)
+{
+	BlockNumber		block = ItemPointerGetBlockNumber(itemptr);
+	OffsetNumber	offset = ItemPointerGetOffsetNumber(itemptr);
+	int64			encoded;
+
+	/*
+	 * Use the 16 least significant bits for the offset.  32 adjacent bits are
+	 * used for the block number.  Since remaining bits are unused, there
+	 * cannot be negative encoded values (We assume a two's complement
+	 * representation).
+	 */
+	encoded = ((uint64) block << 16) | (uint16) offset;
+
+	return encoded;
+}
+
+/*
+ * itemptr_decode - Decode int64/int8 representation back to ItemPointer
+ */
+static inline void
+itemptr_decode(ItemPointer itemptr, int64 encoded)
+{
+	BlockNumber		block = (BlockNumber) (encoded >> 16);
+	OffsetNumber	offset = (OffsetNumber) (encoded & 0x);
+
+	ItemPointerSet(itemptr, block, offset);
+}
+
+/*
  * validate_index_callback - bulkdelete callback to collect the index TIDs
  */
 static bool
 validate_index_callback(ItemPointer itemptr, void *opaque)
 {
 	v_i_state  *state = (v_i_state *) opaque;
+	int64		encoded = itemptr_encode(itemptr);
 
-	tuplesort_putdatum(state->tuplesort, PointerGetDatum(itemptr), false);
+	tuplesort_putdatum(state->tuplesort, Int64GetDatum(encoded), false);
 	state->itups += 1;
 	return false;/* never actually delete anything */
 }
@@ -2911,6 +2960,7 @@ validate_index_heapscan(Relation heapRelation,
 
 	/* state variables for the merge */
 	ItemPointer indexcursor = NULL;
+	ItemPointerData		decoded;
 	bool		tuplesort_empty = false;
 
 	/*

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Peter Geoghegan]

On Sat, Dec 12, 2015 at 9:48 AM, Corey Huinker  wrote:
> I ask because CIC statements that run in seconds on our staging machine can
> take many hours on our production machine, when most of the access is just
> reads, though those reads may have been part of a larger transaction that
> did updates elsewhere.

I don't think it's necessary to simulate any other load.


-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Corey Huinker]

On Fri, Dec 11, 2015 at 5:35 PM, Peter Geoghegan  wrote:

> On Fri, Dec 11, 2015 at 2:26 PM, Corey Huinker 
> wrote:
> > Sure, the machine we called "ninefivealpha", which incidentally, failed
> to
> > find a single bug in alpha2 thru beta2, is currently idle, and concurrent
> > index creation times are a bugbear around these parts. Can somebody,
> either
> > in this thread or privately, outline what sort of a test they'd like to
> see?
>
> Any kind of CREATE INDEX CONCURRENTLY test, before and after.
>
> I looked at a simple, random int4 column. That seems like a good case
> to focus on, since there isn't too much other overhead.  I think I
> performed my test on an unlogged table, to make sure other overhead
> was even further minimized.
>
> --
> Peter Geoghegan
>

What, if any, other load should be placed on the underlying table during
the test?

I ask because CIC statements that run in seconds on our staging machine can
take many hours on our production machine, when most of the access is just
reads, though those reads may have been part of a larger transaction that
did updates elsewhere.

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Peter Geoghegan]

On Fri, Dec 11, 2015 at 2:26 PM, Corey Huinker  wrote:
> Sure, the machine we called "ninefivealpha", which incidentally, failed to
> find a single bug in alpha2 thru beta2, is currently idle, and concurrent
> index creation times are a bugbear around these parts. Can somebody, either
> in this thread or privately, outline what sort of a test they'd like to see?

Any kind of CREATE INDEX CONCURRENTLY test, before and after.

I looked at a simple, random int4 column. That seems like a good case
to focus on, since there isn't too much other overhead.  I think I
performed my test on an unlogged table, to make sure other overhead
was even further minimized.

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Corey Huinker]

On Fri, Dec 11, 2015 at 12:13 PM, Robert Haas  wrote:

> On Wed, Dec 9, 2015 at 8:16 PM, Peter Geoghegan  wrote:
> > On Tue, Nov 17, 2015 at 7:33 PM, Corey Huinker 
> wrote:
> >> I'm willing, but I'm too new to the codebase to be an effective reviewer
> >> (without guidance). The one thing I can offer in the mean time is this:
> my
> >> company/client nearly always has a few spare AWS machines on the largish
> >> side where I can compile uncommitted patches and benchmark stuff for
> y'all.
> >
> > I think that this particular patch is close to being a slam-dunk, so I
> > don't think it's particularly needed here. But thanks.
>
> It never hurts to have a few extra performance test results - I'm all
> in favor of Corey doing some testing.
>
> Also, I'd be in favor of you updating the patch to reflect the
> comments from Tom and Simon on November 17th.
>
> --
> Robert Haas
> EnterpriseDB: http://www.enterprisedb.com
> The Enterprise PostgreSQL Company
>

Sure, the machine we called "ninefivealpha", which incidentally, failed to
find a single bug in alpha2 thru beta2, is currently idle, and concurrent
index creation times are a bugbear around these parts. Can somebody, either
in this thread or privately, outline what sort of a test they'd like to see?

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Robert Haas]

On Wed, Dec 9, 2015 at 8:16 PM, Peter Geoghegan  wrote:
> On Tue, Nov 17, 2015 at 7:33 PM, Corey Huinker  
> wrote:
>> I'm willing, but I'm too new to the codebase to be an effective reviewer
>> (without guidance). The one thing I can offer in the mean time is this: my
>> company/client nearly always has a few spare AWS machines on the largish
>> side where I can compile uncommitted patches and benchmark stuff for y'all.
>
> I think that this particular patch is close to being a slam-dunk, so I
> don't think it's particularly needed here. But thanks.

It never hurts to have a few extra performance test results - I'm all
in favor of Corey doing some testing.

Also, I'd be in favor of you updating the patch to reflect the
comments from Tom and Simon on November 17th.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Peter Geoghegan]

On Tue, Nov 17, 2015 at 7:33 PM, Corey Huinker  wrote:
> I'm willing, but I'm too new to the codebase to be an effective reviewer
> (without guidance). The one thing I can offer in the mean time is this: my
> company/client nearly always has a few spare AWS machines on the largish
> side where I can compile uncommitted patches and benchmark stuff for y'all.

I think that this particular patch is close to being a slam-dunk, so I
don't think it's particularly needed here. But thanks.

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Corey Huinker]

On Tue, Nov 17, 2015 at 7:28 PM, Michael Paquier 
wrote:

> On Wed, Nov 18, 2015 at 8:50 AM, Peter Geoghegan wrote:
> > I seem to be able to produce these sorting patches at a much greater
> > rate than they can be committed, in part because Robert is the only
> > one that ever reviews them, and he is only one person. Since you think
> > the patch is good work, perhaps you can find the time to formally
> > review it.
>
> Finding reviewing volunteers is a good thing, particularly on these
> times where we tend to have more patches than reviews, however I would
> suggest prioritizing the older items by beginning in what is in the
> current CF (47 items waiting for review at I write this message), 3
> patches for the sorting work.
>
> FWIW, I think that this series of patches is interesting and have high
> value because particularly I have seen clear improvements particularly
> with raw dumps on schemas with many indexes (disclaimer: I am the guy
> Peter talked to regarding this patch though this was not on the top
> head nor of my TODOs).
> --
> Michael
>
>
> --
> Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers
>

I'm willing, but I'm too new to the codebase to be an effective reviewer
(without guidance). The one thing I can offer in the mean time is this: my
company/client nearly always has a few spare AWS machines on the largish
side where I can compile uncommitted patches and benchmark stuff for y'all.

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Michael Paquier]

On Wed, Nov 18, 2015 at 8:50 AM, Peter Geoghegan wrote:
> I seem to be able to produce these sorting patches at a much greater
> rate than they can be committed, in part because Robert is the only
> one that ever reviews them, and he is only one person. Since you think
> the patch is good work, perhaps you can find the time to formally
> review it.

Finding reviewing volunteers is a good thing, particularly on these
times where we tend to have more patches than reviews, however I would
suggest prioritizing the older items by beginning in what is in the
current CF (47 items waiting for review at I write this message), 3
patches for the sorting work.

FWIW, I think that this series of patches is interesting and have high
value because particularly I have seen clear improvements particularly
with raw dumps on schemas with many indexes (disclaimer: I am the guy
Peter talked to regarding this patch though this was not on the top
head nor of my TODOs).
-- 
Michael


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Peter Geoghegan]

On Tue, Nov 17, 2015 at 12:53 AM, Simon Riggs  wrote:
> Short and sweet! Looks good.

Thanks.

> I would be inclined to add more comments to explain it, these things have a
> habit of being forgotten.

I'm not sure what additional detail I can add.

I seem to be able to produce these sorting patches at a much greater
rate than they can be committed, in part because Robert is the only
one that ever reviews them, and he is only one person. Since you think
the patch is good work, perhaps you can find the time to formally
review it.

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Peter Geoghegan]

On Tue, Nov 17, 2015 at 7:54 AM, Tom Lane  wrote:
> I think this might do the wrong thing with block numbers above 0x8000
> and/or offset numbers above 0x8000.  I'd be more comfortable about it if
> +   encoded = ((int64) block << 16) | offset;
> were
> +   encoded = ((uint64) block << 16) | (uint16) offset;
> so that there's no risk of the compiler deciding to sign-extend rather
> than zero-fill either input.

I don't have a problem with your alternative, but I don't see any risk
with the original. It is recommended by various coding standards to
only use bitwise operators on unsigned operands, so that's a good
enough reason, I suppose.

> Also, I think it'd be a good idea to explicitly set indexcursor = NULL
> in the tuplesort_empty case; the previous coding was effectively doing
> that.  It's true that the code shouldn't attempt to touch the value,
> but it's better not to have dangling pointers lying around.

The code started that way, but I removed the "indexcursor = NULL"
because the previous coding was *not* doing that. tuplesort_getdatum()
was not setting the passed Datum pointer (which points to indexcursor
here) in the event of returning false. Maybe I should have left in the
code setting indexcursor = NULL all the same.

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Tom Lane]

Peter Geoghegan  writes:
>>> Might be better to hack a special case right there (ie, embed TIDs into
>>> int8s and sort the int8s) rather than try to change the type's SQL
>>> declaration.

> I suggested to someone else that he take a look at this as a project,
> but I guess he was busy too. I decided to just do it myself. Patch is
> attached.

I think this might do the wrong thing with block numbers above 0x8000
and/or offset numbers above 0x8000.  I'd be more comfortable about it if
+   encoded = ((int64) block << 16) | offset;
were
+   encoded = ((uint64) block << 16) | (uint16) offset;
so that there's no risk of the compiler deciding to sign-extend rather
than zero-fill either input.

Also, I think it'd be a good idea to explicitly set indexcursor = NULL
in the tuplesort_empty case; the previous coding was effectively doing
that.  It's true that the code shouldn't attempt to touch the value,
but it's better not to have dangling pointers lying around.

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Simon Riggs]

On 17 November 2015 at 00:52, Peter Geoghegan  wrote:


> This patch does seem like a slam dunk, even if I do say so myself


Short and sweet! Looks good.

I would be inclined to add more comments to explain it, these things have a
habit of being forgotten.

-- 
Simon Riggshttp://www.2ndQuadrant.com/

PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Peter Geoghegan]

On Mon, Sep 7, 2015 at 9:20 PM, Peter Geoghegan  wrote:
>>> This matters because a major cost during CREATE INDEX CONCURRENTLY is
>>> a TID-based datum sort (this is probably most of the cost over and
>>> above a conventional CREATE INDEX).
>>
>> Might be better to hack a special case right there (ie, embed TIDs into
>> int8s and sort the int8s) rather than try to change the type's SQL
>> declaration.
>
> That sounds at least as effective as what I originally sketched.

> I hope someone picks this up soon.

I suggested to someone else that he take a look at this as a project,
but I guess he was busy too. I decided to just do it myself. Patch is
attached. This has the bulkdelete callback that gathers TIDs from the
index during CREATE INDEX CONCURRENTLY encode them as int8 values
ahead of the sort, while sorting the values as int8 values. They're
later decoded as needed.

This turns out to be a relatively simple patch. Testing shows it
removes *most* of the overhead of CREATE INDEX CONCURRENTLY over
CREATE INDEX. In absolute terms, a test case involving a CREATE INDEX
CONCURRENTLY on a single integer column takes about 30% - 40% less
time with the patch applied. The TID sort itself is about 3 times
faster, and that's without the benefit of the patch making the TID
sort an internal sort where it would otherwise have been an external
sort. Sorting item pointers as TIDs naively currently wastes a lot of
memory (not just memory bandwidth) -- a pass-by-value datum sort only
ever allocates memory for SortTuples, avoiding allocating any memory
for a "tuple proper". Clearly just having the sort be pass-by-value is
*much* faster. As comments above process_ordered_aggregate_single()
put it:

 * The one-input case is handled separately from the multi-input case
 * for performance reasons: for single by-value inputs, such as the
 * common case of count(distinct id), the tuplesort_getdatum code path
 * is around 300% faster.  (The speedup for by-reference types is less
 * but still noticeable.)

Another way of stating how things are improved here is: my CREATE
INDEX CONCURRENTLY test case had about a 2.1x overhead over an
equivalent CREATE INDEX on master, but with the patch applied the
CREATE INDEX CONCURRENTLY has an overhead of only about 1.3x. The
extra logical I/O for CONCURRENTLY's second scan, and for the
physical-order index scan (to "bulk delete", to gather TIDs to sort)
is a surprisingly small cost.

I'll add the patch to the open commitfest. Think of all these patches
of mine as giving reviewers a choice of what to review. This patch
does seem like a slam dunk, even if I do say so myself, so at least
it's relatively easy to review. The external sort work remains my most
interesting pending work, though.

-- 
Peter Geoghegan
From 3c7551435394090a4c2d3e7588d018ea9dca2482 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan 
Date: Sat, 14 Nov 2015 16:57:20 -0800
Subject: [PATCH] Speed up CREATE INDEX CONCURRENTLY's TID sort

Add a simple TID encoding scheme.  This is used for encoding and
decoding TIDs to and from int8/int64 values, for the benefit of an
expensive tuplesort operation performed by CREATE INDEX CONCURRENTLY.
The sort now uses the default int8 opclass to sort values in the ad-hoc
encoding, and so benefits from the availability of int8 SortSupport.

Despite the fact that item pointers take up only 6 bytes on disk, the
TID type is always pass-by-reference due to considerations about how
Datums are represented and accessed.  On the other hand, int8 is
usually, in practice, a pass-by-value type.

Testing shows this approach makes CREATE INDEX CONCURRENTLY
significantly faster on platforms where int8 is pass-by-value,
especially when the big saving in memory within tuplesort.c prevents the
sort from being performed externally.  The approach will help to some
degree on all platforms, though.
---
 src/backend/catalog/index.c | 56 +
 1 file changed, 52 insertions(+), 4 deletions(-)

diff --git a/src/backend/catalog/index.c b/src/backend/catalog/index.c
index e59b163..7429f3c 100644
--- a/src/backend/catalog/index.c
+++ b/src/backend/catalog/index.c
@@ -109,6 +109,8 @@ static void index_update_stats(Relation rel,
 static void IndexCheckExclusion(Relation heapRelation,
 	Relation indexRelation,
 	IndexInfo *indexInfo);
+static inline int64 itemptr_encode(ItemPointer itemptr);
+static inline void itemptr_decode(ItemPointer itemptr, int64 encoded);
 static bool validate_index_callback(ItemPointer itemptr, void *opaque);
 static void validate_index_heapscan(Relation heapRelation,
 		Relation indexRelation,
@@ -2832,7 +2834,13 @@ validate_index(Oid heapId, Oid indexId, Snapshot snapshot)
 	ivinfo.num_heap_tuples = heapRelation->rd_rel->reltuples;
 	ivinfo.strategy = NULL;
 
-	state.tuplesort = tuplesort_begin_datum(TIDOID, TIDLessOperator,
+	/*
+	 * Encode TIDs as int8 values for the sort, rather than directly sorting
+	 * item pointers.  This can be significantly

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Peter Geoghegan]

On Mon, Sep 7, 2015 at 9:03 PM, Tom Lane  wrote:
> I'm not sure that it would be just "a little work" --- I suspect that
> the idea that pass-by-val types are 1, 2, 4, or 8 bytes is embedded in
> a fair number of places, including alignment macros in which any added
> complexity would have a large distributed cost.

I didn't immediately consider that.

>> This matters because a major cost during CREATE INDEX CONCURRENTLY is
>> a TID-based datum sort (this is probably most of the cost over and
>> above a conventional CREATE INDEX).
>
> Might be better to hack a special case right there (ie, embed TIDs into
> int8s and sort the int8s) rather than try to change the type's SQL
> declaration.

That sounds at least as effective as what I originally sketched. It
would also be better to have a simple comparator, rather than the more
complex TID comparator. Baking the details into the int8
representation, rather than having the comparator tease it apart will
be faster. Ordinarily, abbreviation does that kind of thing, but there
are upsides to not doing that when tie-breaker comparisons are not
actually required, and this really only needs to happen in one place.

I hope someone picks this up soon.

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Should TIDs be typbyval = FLOAT8PASSBYVAL to speed up CREATE INDEX CONCURRENTLY?

[Tom Lane]

Peter Geoghegan  writes:
> I noticed that the TID type is cataloged as typbyval = f, despite the
> fact that it is 6 bytes, and so could be made typbyval = t on 64-bit
> platforms (i.e. typbyval = FLOAT8PASSBYVAL) with a little work.

I'm not sure that it would be just "a little work" --- I suspect that
the idea that pass-by-val types are 1, 2, 4, or 8 bytes is embedded in
a fair number of places, including alignment macros in which any added
complexity would have a large distributed cost.

> This matters because a major cost during CREATE INDEX CONCURRENTLY is
> a TID-based datum sort (this is probably most of the cost over and
> above a conventional CREATE INDEX).

Might be better to hack a special case right there (ie, embed TIDs into
int8s and sort the int8s) rather than try to change the type's SQL
declaration.

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers