From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: James Coleman <jtc331@gmail.com>
Cc: Simon Riggs <simon@2ndquadrant.com>
Cc: Rafia Sabih <rafia.pghackers@gmail.com>
Cc: Shaun Thomas <shaun.thomas@2ndquadrant.com>
Cc: Dmitry Dolgov <9erthalion6@gmail.com>
Cc: Alexander Korotkov <a.korotkov@postgrespro.ru>
Cc: Tom Lane <tgl@sss.pgh.pa.us>
Cc: PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>
Subject: Re: [PATCH] Incremental sort (was: PoC: Partial sort)
Date: Tue, 25 Jun 2019 18:02:35 +0200
Message-ID: <20190625160235.6ctryjzvw5je7cet@development> (raw)
In-Reply-To: <CAAaqYe9pzNZnF328bFZfzR8zJK9Mvft3i6TN0NjxjCkWeVm1iQ@mail.gmail.com>
References: <20190602211753.rxor4apm7zfiltt3@development>
<CAAaqYe_a7Umxn6J+GGXGu00f+Jwmcq83gh3dj6tC4RR75+yjAw@mail.gmail.com>
<CA+FpmFffDyU_FTf8c3a9+GWqMmsQ9xy6Dibc0Ja9v4BeYzjXow@mail.gmail.com>
<20190614181135.tdj7aq4iffy5ghl2@development>
<CAAaqYe9mifZ9wv-Jm=+J3FWEOrXM-6SgY7z_YJhObfiG7dcxnA@mail.gmail.com>
<CAAaqYe_PXXHnOavS_X+C+yJnWesQzWeCv80jsp33SW4osGRUWg@mail.gmail.com>
<CANP8+jJaGHCQb8aBuywkz8Ev9WJwSZrMkmtr2WciCFazhtsgcw@mail.gmail.com>
<CAAaqYe9N=BZDJ2U9FsRX1-foJu-a8u1t1KGYtvf=zJdUAO9JdA@mail.gmail.com>
<20190624201601.iqy3ddig72l5lvbz@development>
<CAAaqYe9pzNZnF328bFZfzR8zJK9Mvft3i6TN0NjxjCkWeVm1iQ@mail.gmail.com>
On Mon, Jun 24, 2019 at 07:34:19PM -0400, James Coleman wrote:
>On Mon, Jun 24, 2019 at 4:16 PM Tomas Vondra
><tomas.vondra@2ndquadrant.com> wrote:
>>
>> On Mon, Jun 24, 2019 at 01:00:50PM -0400, James Coleman wrote:
>> >On Mon, Jun 24, 2019 at 12:56 PM Simon Riggs <simon@2ndquadrant.com> wrote:
>> >>
>> >> On Mon, 24 Jun 2019 at 16:10, James Coleman <jtc331@gmail.com> wrote:
>> >>>
>> >>> On Thu, Jun 13, 2019 at 11:38:12PM -0400, James Coleman wrote:
>...
>> >>> As I see it the two most significant concerning cases right now are:
>> >>> 1. Very large batches (in particular where the batch is effectively
>> >>> all of the matching rows such that we're really just doing a standard
>> >>> sort).
>> >>> 2. Many very small batches.
>> >>
>> >>
>> >> What is the specific use case for this? This sounds quite general case.
>> >
>> >They are both general cases in some sense, but the concerns lie mostly
>> >with what happens when they're unexpectedly encountered. For example,
>> >if the expected row count or group size is off by a good bit and we
>> >effectively have to perform a sort of all (or most) possible rows.
>> >
>> >If we can get the performance to a point where that misestimated row
>> >count or group size doesn't much matter, then ISTM including the patch
>> >becomes a much more obvious total win.
>> >
>>
>> Yes, that seems like a reasonable approach. Essentially, we're trying to
>> construct plausible worst case examples, and then minimize the overhead
>> compared to regular sort. If we get sufficiently close, then it's fine
>> to rely on somewhat shaky stats - like group size estimates.
>
>I have a bit of a mystery in my performance testing. I've been setting
>up a table like so:
>
>create table foo(pk serial primary key, owner_fk integer, created_at timestamp);
>insert into foo(owner_fk, created_at)
>select fk_t.i, now() - (time_t.i::text || ' minutes')::interval
>from generate_series(1, 10000) time_t(i)
>cross join generate_series(1, 1000) fk_t(i);
>-- double up on one set to guarantee matching prefixes
>insert into foo (owner_fk, created_at) select owner_fk, created_at
>from foo where owner_fk = 23;
>create index idx_foo_on_owner_and_created_at on foo(owner_fk, created_at);
>analyze foo;
>
>and then I have the following query:
>
>select *
>from foo
>where owner_fk = 23
>order by created_at desc, pk desc
>limit 20000;
>
>The idea here is to force a bit of a worst case for small groups: we
>have 10,000 batches (i.e., equal prefix groups) of 2 tuples each and
>then query with a limit matching the actual number of rows we know
>will match the query -- so even though there's a limit we're forcing a
>total sort (and also guaranteeing both plans have to touch the same
>number of rows). Note: I know that batches of size is actually the
>worst case, but I chose batches of two because I've also been testing
>a change that would skip the sort entirely for single tuple batches.
>
>On master (really the commit right before the current revision of the
>patch), I get:
>latency average = 14.271 ms
>tps = 70.075243 (excluding connections establishing)
>
>With the patch (and incremental sort enabled):
>latency average = 11.975 ms
>tps = 83.512090 (excluding connections establishing)
>
>With the patch (but incremental sort disabled):
>latency average = 11.884 ms
>tps = 84.149834 (excluding connections establishing)
>
>All of those are 60 seconds runs on pgbench with a single thread.
>
>So we have a very substantial speedup with patch *even if the new
>feature isn't enabled*. I've confirmed the plan looks the same on
>patched with incremental sort disabled and master. The only changes
>that would seem to really effect execution time would be the changes
>to tuplesort.c, but looking through them I don't see anything I'd
>expect to change things so dramatically.
>
>Any thoughts on this?
>
I can reproduce the same thing, so it's not just you. On my machine, I see
these tps numbers (average of 10 runs, 60 seconds each):
master: 65.177
patched (on): 80.368
patched (off): 80.750
The numbers are very consistent (within 1 tps).
I've done a bit of CPU profiling, and on master I see this:
13.84% postgres postgres [.] comparetup_heap
4.83% postgres postgres [.] qsort_tuple
3.87% postgres postgres [.] pg_ltostr_zeropad
3.55% postgres postgres [.] pg_ltoa
3.19% postgres postgres [.] AllocSetAlloc
2.68% postgres libc-2.28.so [.] __GI___strlen_sse2
2.38% postgres postgres [.] LWLockRelease
2.38% postgres postgres [.] AppendSeconds.constprop.9
2.22% postgres libc-2.28.so [.] __memmove_sse2_unaligned_erms
2.17% postgres postgres [.] GetPrivateRefCountEntry
2.03% postgres postgres [.] j2date
...
while on patched versions I see this:
4.60% postgres postgres [.] pg_ltostr_zeropad
4.51% postgres postgres [.] pg_ltoa
3.50% postgres postgres [.] AllocSetAlloc
3.34% postgres libc-2.28.so [.] __GI___strlen_sse2
2.99% postgres postgres [.] LWLockRelease
2.84% postgres postgres [.] AppendSeconds.constprop.9
2.65% postgres postgres [.] GetPrivateRefCountEntry
2.64% postgres postgres [.] j2date
2.60% postgres postgres [.] printtup
2.56% postgres postgres [.] heap_hot_search_buffer
...
1.35% postgres postgres [.] comparetup_heap
...
So either we're calling comparetup_heap less often, or it's cheaper.
But it seems to be very dependent on the data set. If you do this:
create table foo_2 as select * from foo order by random();
alter table foo_2 add primary key (pk);
create index idx_foo_2_on_owner_and_created_at on foo_2 (owner_fk, created_at);
and then run the test against this table, there's no difference.
So my guess is this particular data set triggers slightly different
behavior in tuplesort, reducing the cost of comparetup_heap. The speedup
is quite significant (~20% on my system), the question is how widely
applicable can it be.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
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: pgsql-hackers@postgresql.org
Cc: tomas.vondra@2ndquadrant.com, jtc331@gmail.com, simon@2ndquadrant.com, rafia.pghackers@gmail.com, shaun.thomas@2ndquadrant.com, 9erthalion6@gmail.com, a.korotkov@postgrespro.ru, tgl@sss.pgh.pa.us, pgsql-hackers@lists.postgresql.org
Subject: Re: [PATCH] Incremental sort (was: PoC: Partial sort)
In-Reply-To: <20190625160235.6ctryjzvw5je7cet@development>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox