pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedRe: [HACKERS] qsort again (was Re: Strange Create Index
6+ messages / 4 participants
[nested] [flat]
* Re: [HACKERS] qsort again (was Re: Strange Create Index
@ 2006-02-16 11:06 ` Gary Doades <gpd@gpdnet.co.uk>
2006-02-16 15:42 ` Re: [HACKERS] qsort again (was Re: Strange Create Index Gary Doades <gpd@gpdnet.co.uk>
1 sibling, 1 reply; 6+ messages in thread
From: Gary Doades @ 2006-02-16 11:06 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-performance
Tom Lane wrote:
> I increased the size of the test case by 10x (basically s/100000/1000000/)
> which is enough to push it into the external-sort regime. I get
> amazingly stable runtimes now --- I didn't have the patience to run 100
> trials, but in 30 trials I have slowest 11538 msec and fastest 11144 msec.
> So this code path is definitely not very sensitive to this data
> distribution.
>
> While these numbers aren't glittering in comparison to the best-case
> qsort times (~450 msec to sort 10% as much data), they are sure a lot
> better than the worst-case times. So maybe a workaround for you is
> to decrease maintenance_work_mem, counterintuitive though that be.
> (Now, if you *weren't* using maintenance_work_mem of 100MB or more
> for your problem restore, then I'm not sure I know what's going on...)
>
Good call. I basically reversed your test by keeping the number of rows
the same (200000), but reducing maintenance_work_mem. Reducing to 8192
made no real difference. Reducing to 4096 flattened out all the times
nicely. Slower overall, but at least predictable. Hopefully only a
temporary solution until qsort is fixed.
My restore now takes 22 minutes :)
I think the reason I wasn't seeing performance issues with normal sort
operations is because they use work_mem not maintenance_work_mem which was
only set to 2048 anyway. Does that sound right?
Regards,
Gary.
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: [HACKERS] qsort again (was Re: Strange Create Index
2006-02-16 11:06 ` Re: [HACKERS] qsort again (was Re: Strange Create Index Gary Doades <gpd@gpdnet.co.uk>
@ 2006-02-16 15:42 ` Gary Doades <gpd@gpdnet.co.uk>
0 siblings, 0 replies; 6+ messages in thread
From: Gary Doades @ 2006-02-16 15:42 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-performance
> "Gary Doades" <gpd@gpdnet.co.uk> writes:
>> I think the reason I wasn't seeing performance issues with normal sort
>> operations is because they use work_mem not maintenance_work_mem which
>> was
>> only set to 2048 anyway. Does that sound right?
>
> Very probable. Do you want to test the theory by jacking that up? ;-)
Hmm, played around a bit. I have managed to get it to do a sort on one of
the "bad" columns using a select of two whole tables that results in a
sequntial scan, sort and merge join. I also tried a simple select column
order by column for a bad column.
I tried varying maintenance_work_mem and work_mem up and down between 2048
and 65536 but I always get similar results. The sort phase always takes 4
to 5 seconds which seems about right for 900,000 rows.
This was on a colunm that took 12 minutes to create an index on.
I've no idea why it should behave this way, but probably explains why I
(and others) may not have noticed it before.
Regards,
Gary.
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: qsort again (was Re: Strange Create Index
@ 2006-02-16 11:35 ` Steinar H. Gunderson <sgunderson@bigfoot.com>
2006-02-16 23:05 ` Re: [HACKERS] qsort again (was Re: Strange Create Index PFC <lists@peufeu.com>
1 sibling, 1 reply; 6+ messages in thread
From: Steinar H. Gunderson @ 2006-02-16 11:35 UTC (permalink / raw)
To: pgsql-performance
On Wed, Feb 15, 2006 at 11:30:54PM -0500, Ron wrote:
> Even better (and more easily scaled as the number of GPR's in the CPU
> changes) is to use
> the set {L; L+1; L+2; t>>1; R-2; R-1; R}
> This means that instead of 7 random memory accesses, we have 3; two
> of which result in a
> burst access for three elements each.
Isn't that improvement going to disappear competely if you choose a bad
pivot?
> SIDE NOTE: IIRC glibc's qsort is actually merge sort. Merge sort
> performance is insensitive to all inputs, and there are way to
> optimize it as well.
glibc-2.3.5/stdlib/qsort.c:
/* Order size using quicksort. This implementation incorporates
four optimizations discussed in Sedgewick:
I can't see any references to merge sort in there at all.
/* Steinar */
--
Homepage: http://www.sesse.net/
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: [HACKERS] qsort again (was Re: Strange Create Index
2006-02-16 11:35 ` Re: qsort again (was Re: Strange Create Index Steinar H. Gunderson <sgunderson@bigfoot.com>
@ 2006-02-16 23:05 ` PFC <lists@peufeu.com>
2006-02-17 00:18 ` Re: [HACKERS] qsort again (was Re: Strange Create Index Markus Schaber <schabi@logix-tt.com>
2006-02-17 02:02 ` Re: [HACKERS] qsort again (was Re: Strange Create Index Steinar H. Gunderson <sgunderson@bigfoot.com>
0 siblings, 2 replies; 6+ messages in thread
From: PFC @ 2006-02-16 23:05 UTC (permalink / raw)
To: pgsql-performance
> It seems that instead of maintaining a different sorting code path for
> each data type, you could get away with one generic path and one
> (hopefully faster) path if you allowed data types to optionally support
> a 'sortKey' interface by providing a function f which maps inputs to 32-
> bit int outputs, such that the following two properties hold:
Looks like the decorate-sort-undecorate pattern, which works quite well.
Good idea.
I would have said a 64 bit int, but it's the same idea. However it won't
work for floats, which is a pity, because floats fit in 64 bits. Unless
more types creep in the code path (which would not necessarily make it
that slower).
As for text, the worst case is when all strings start with the same 8
letters, but a good case pops up when a few-letter code is used as a key
in a table. Think about a zipcode, for instance. If a merge join needs to
sort on zipcodes, it might as well sort on 64-bits integers...
By the way, I'd like to declare my zipcode columns as SQL_ASCII while the
rest of my database is in UNICODE, so they are faster to index and sort.
Come on, MySQL does it...
Keep up !
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: [HACKERS] qsort again (was Re: Strange Create Index
2006-02-16 11:35 ` Re: qsort again (was Re: Strange Create Index Steinar H. Gunderson <sgunderson@bigfoot.com>
2006-02-16 23:05 ` Re: [HACKERS] qsort again (was Re: Strange Create Index PFC <lists@peufeu.com>
@ 2006-02-17 00:18 ` Markus Schaber <schabi@logix-tt.com>
1 sibling, 0 replies; 6+ messages in thread
From: Markus Schaber @ 2006-02-17 00:18 UTC (permalink / raw)
To: PFC <lists@peufeu.com>; +Cc: pgsql-performance
Hi, PFC,
PFC schrieb:
> By the way, I'd like to declare my zipcode columns as SQL_ASCII
> while the rest of my database is in UNICODE, so they are faster to
> index and sort. Come on, MySQL does it...
Another use case for parametric column definitions - charset definitions
- and the first one that cannot be emulated via constraints.
Other use cases I remember were range definitions for numbers or PostGIS
dimension, subtype and SRID, but those cann all be emulated via checks /
constraints.
Markus
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: [HACKERS] qsort again (was Re: Strange Create Index
2006-02-16 11:35 ` Re: qsort again (was Re: Strange Create Index Steinar H. Gunderson <sgunderson@bigfoot.com>
2006-02-16 23:05 ` Re: [HACKERS] qsort again (was Re: Strange Create Index PFC <lists@peufeu.com>
@ 2006-02-17 02:02 ` Steinar H. Gunderson <sgunderson@bigfoot.com>
1 sibling, 0 replies; 6+ messages in thread
From: Steinar H. Gunderson @ 2006-02-17 02:02 UTC (permalink / raw)
To: pgsql-performance
On Fri, Feb 17, 2006 at 12:05:23AM +0100, PFC wrote:
> I would have said a 64 bit int, but it's the same idea. However it
> won't work for floats, which is a pity, because floats fit in 64 bits.
Actually, you can compare IEEE floats directly as ints, as long as they're
positive. (If they can be both positive and negative, you need to take
special care of the sign bit first, but it's still doable.)
/* Steinar */
--
Homepage: http://www.sesse.net/
^ permalink raw reply [nested|flat] 6+ messages in thread
end of thread, other threads:[~2006-02-17 02:02 UTC | newest]
Thread overview: 6+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2006-02-16 11:06 ` Gary Doades <gpd@gpdnet.co.uk>
2006-02-16 15:42 ` Gary Doades <gpd@gpdnet.co.uk>
2006-02-16 11:35 ` Steinar H. Gunderson <sgunderson@bigfoot.com>
2006-02-16 23:05 ` PFC <lists@peufeu.com>
2006-02-17 00:18 ` Markus Schaber <schabi@logix-tt.com>
2006-02-17 02:02 ` Steinar H. Gunderson <sgunderson@bigfoot.com>
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