Re: [HACKERS] Remove hacks for old bad qsort() implementations?
Added to TODO:
* Consider whether duplicate keys should be sorted by block/offset
http://archives.postgresql.org/pgsql-hackers/2008-03/msg00558.php
---
Tom Lane wrote:
There are several places in tuplesort.c (and perhaps elsewhere) where
we explicitly work around limitations of various platforms' qsort()
functions. Notably, there's this bit in comparetup_index_btree
/*
* If key values are equal, we sort on ItemPointer. This does not affect
* validity of the finished index, but it offers cheap insurance against
* performance problems with bad qsort implementations that have trouble
* with large numbers of equal keys.
*/
which I unquestioningly copied into comparetup_index_hash yesterday.
However, oprofile is telling me that doing this is costing
*significantly* more than just returning zero would do:
9081 0.3050 :tuple1 = (IndexTuple) a-tuple;
3759 0.1263 :tuple2 = (IndexTuple) b-tuple;
:
:{
130409 4.3800 :BlockNumber blk1 =
ItemPointerGetBlockNumber(tuple1-t_tid);
34539 1.1601 :BlockNumber blk2 =
ItemPointerGetBlockNumber(tuple2-t_tid);
:
3281 0.1102 :if (blk1 != blk2)
812 0.0273 :return (blk1 blk2) ? -1 : 1;
:}
:{
28 9.4e-04 :OffsetNumber pos1 =
ItemPointerGetOffsetNumber(tuple1-t_tid);
1 3.4e-05 :OffsetNumber pos2 =
ItemPointerGetOffsetNumber(tuple2-t_tid);
:
1 3.4e-05 :if (pos1 != pos2)
48757 1.6376 :return (pos1 pos2) ? -1 : 1;
:}
:
:return 0;
56705 1.9045 :}
Looks to me like we're eating more than seven percent of the total
runtime to do this :-(
Now as far as I can see, the original motivation for this (as stated in
the comment) is entirely dead anymore, since we always use our own qsort
implementation in preference to whatever bogus version a given libc
might supply. What do people think of removing this bit of code in
favor of just returning 0?
I can see a couple of possible objections:
1. Someday we might go back to using platform qsort. (But surely we
could insist on qsort behaving sanely for equal keys.)
2. If you've got lots of equal keys, it's conceivable that having the
index entries sorted by TID offers some advantage in indexscan speed.
I'm dubious that that's useful, mainly because the planner should prefer
a bitmap scan in such a case; and anyway the ordering is unlikely to
be preserved for long. But it's something to think about.
Comments?
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
--
Bruce Momjian [EMAIL PROTECTED]http://momjian.us
EnterpriseDB http://enterprisedb.com
+ If your life is a hard drive, Christ can be your backup. +
--
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] Remove hacks for old bad qsort() implementations?
Bruce Momjian [EMAIL PROTECTED] writes: Tom, are you intending to remove this part of the sort code? http://archives.postgresql.org/message-id/[EMAIL PROTECTED] Well, I got some push-back on the proposal, so I'd kind of dropped it. But AFAIR the objections were purely hypothetical, whereas the cost of the existing code is measurable; so maybe we should do it anyway. 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] Remove hacks for old bad qsort() implementations?
Tom Lane wrote: Bruce Momjian [EMAIL PROTECTED] writes: Tom, are you intending to remove this part of the sort code? http://archives.postgresql.org/message-id/[EMAIL PROTECTED] Well, I got some push-back on the proposal, so I'd kind of dropped it. But AFAIR the objections were purely hypothetical, whereas the cost of the existing code is measurable; so maybe we should do it anyway. Yea, that's what I was thinking. Your measurements were significant. -- Bruce Momjian [EMAIL PROTECTED]http://momjian.us EnterpriseDB http://enterprisedb.com + If your life is a hard drive, Christ can be your backup. + -- 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] Remove hacks for old bad qsort() implementations?
Tom, are you intending to remove this part of the sort code?
---
Tom Lane wrote:
There are several places in tuplesort.c (and perhaps elsewhere) where
we explicitly work around limitations of various platforms' qsort()
functions. Notably, there's this bit in comparetup_index_btree
/*
* If key values are equal, we sort on ItemPointer. This does not affect
* validity of the finished index, but it offers cheap insurance against
* performance problems with bad qsort implementations that have trouble
* with large numbers of equal keys.
*/
which I unquestioningly copied into comparetup_index_hash yesterday.
However, oprofile is telling me that doing this is costing
*significantly* more than just returning zero would do:
9081 0.3050 :tuple1 = (IndexTuple) a-tuple;
3759 0.1263 :tuple2 = (IndexTuple) b-tuple;
:
:{
130409 4.3800 :BlockNumber blk1 =
ItemPointerGetBlockNumber(tuple1-t_tid);
34539 1.1601 :BlockNumber blk2 =
ItemPointerGetBlockNumber(tuple2-t_tid);
:
3281 0.1102 :if (blk1 != blk2)
812 0.0273 :return (blk1 blk2) ? -1 : 1;
:}
:{
28 9.4e-04 :OffsetNumber pos1 =
ItemPointerGetOffsetNumber(tuple1-t_tid);
1 3.4e-05 :OffsetNumber pos2 =
ItemPointerGetOffsetNumber(tuple2-t_tid);
:
1 3.4e-05 :if (pos1 != pos2)
48757 1.6376 :return (pos1 pos2) ? -1 : 1;
:}
:
:return 0;
56705 1.9045 :}
Looks to me like we're eating more than seven percent of the total
runtime to do this :-(
Now as far as I can see, the original motivation for this (as stated in
the comment) is entirely dead anymore, since we always use our own qsort
implementation in preference to whatever bogus version a given libc
might supply. What do people think of removing this bit of code in
favor of just returning 0?
I can see a couple of possible objections:
1. Someday we might go back to using platform qsort. (But surely we
could insist on qsort behaving sanely for equal keys.)
2. If you've got lots of equal keys, it's conceivable that having the
index entries sorted by TID offers some advantage in indexscan speed.
I'm dubious that that's useful, mainly because the planner should prefer
a bitmap scan in such a case; and anyway the ordering is unlikely to
be preserved for long. But it's something to think about.
Comments?
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
--
Bruce Momjian [EMAIL PROTECTED]http://momjian.us
EnterpriseDB http://enterprisedb.com
+ If your life is a hard drive, Christ can be your backup. +
--
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] Remove hacks for old bad qsort() implementations?
How about always adding the TID as last key when using qsort for
create
index ?
I think you misunderstood: that's what we do now. I'm proposing
removing it because I think it's probably useless.
Ah, sorry, I did not look at the code, and interpreted your comment as
some exceptional handling.
I think really randomly (regarding TID) ordering highly duplicate keys
is not such a good idea.
But the point is, it does not need to be exact. Basically sorted with a
few exceptions
and jumps, or sorted by blockid only would be ok. How random does our
qsort really return those tids ?
You wrote:
However, oprofile is telling me that doing this is costing
*significantly* more than just returning zero would do:
9081 0.3050 :tuple1 = (IndexTuple) a-tuple;
3759 0.1263 :tuple2 = (IndexTuple) b-tuple;
:
:{
130409 4.3800 :BlockNumber blk1 =
ItemPointerGetBlockNumber(tuple1-t_tid);
So why is this ItemPointerGetBlockNumber so expensive ?
34539 1.1601 :BlockNumber blk2 =
ItemPointerGetBlockNumber(tuple2-t_tid);
Is it not correctly inlined ? Are the shifts for BlockNumber so
expensive ?
Or is this simply some oprofile overhead that is not real at all ?
Andreas
--
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] Remove hacks for old bad qsort() implementations?
2. If you've got lots of equal keys, it's conceivable that having the index entries sorted by TID offers some advantage in indexscan speed. I'm dubious that that's useful, mainly because the planner should prefer a bitmap scan in such a case; and anyway the ordering is unlikely to be preserved for long. But it's something to think about. How about always adding the TID as last key when using qsort for create index ? Andreas -- 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] Remove hacks for old bad qsort() implementations?
Tom Lane wrote: There are several places in tuplesort.c (and perhaps elsewhere) where we explicitly work around limitations of various platforms' qsort() functions. Notably, there's this bit in comparetup_index_btree /* * If key values are equal, we sort on ItemPointer. This does not affect * validity of the finished index, but it offers cheap insurance against * performance problems with bad qsort implementations that have trouble * with large numbers of equal keys. */ Hmm, wasn't this supposed to be there to fix a problem with Lehman Yao's btree definition, that required all keys to be distinct? [ checks the README ] Okay, it seems I'm wrong; it has nothing to do with what we pass to qsort. The requirement that all btree keys be unique is too onerous, but the algorithm won't work correctly without it. Fortunately, it is only necessary that keys be unique on a single tree level, because LY only use the assumption of key uniqueness when re-finding a key in a parent page (to determine where to insert the key for a split page). Therefore, we can use the link field to disambiguate multiple occurrences of the same user key: only one entry in the parent level will be pointing at the page we had split. -- Alvaro Herrerahttp://www.CommandPrompt.com/ PostgreSQL Replication, Consulting, Custom Development, 24x7 support -- 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] Remove hacks for old bad qsort() implementations?
Zeugswetter Andreas OSB SD [EMAIL PROTECTED] writes: How about always adding the TID as last key when using qsort for create index ? I think you misunderstood: that's what we do now. I'm proposing removing it because I think it's probably useless. 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
[HACKERS] Remove hacks for old bad qsort() implementations?
There are several places in tuplesort.c (and perhaps elsewhere) where
we explicitly work around limitations of various platforms' qsort()
functions. Notably, there's this bit in comparetup_index_btree
/*
* If key values are equal, we sort on ItemPointer. This does not affect
* validity of the finished index, but it offers cheap insurance against
* performance problems with bad qsort implementations that have trouble
* with large numbers of equal keys.
*/
which I unquestioningly copied into comparetup_index_hash yesterday.
However, oprofile is telling me that doing this is costing
*significantly* more than just returning zero would do:
9081 0.3050 :tuple1 = (IndexTuple) a-tuple;
3759 0.1263 :tuple2 = (IndexTuple) b-tuple;
:
:{
130409 4.3800 :BlockNumber blk1 =
ItemPointerGetBlockNumber(tuple1-t_tid);
34539 1.1601 :BlockNumber blk2 =
ItemPointerGetBlockNumber(tuple2-t_tid);
:
3281 0.1102 :if (blk1 != blk2)
812 0.0273 :return (blk1 blk2) ? -1 : 1;
:}
:{
28 9.4e-04 :OffsetNumber pos1 =
ItemPointerGetOffsetNumber(tuple1-t_tid);
1 3.4e-05 :OffsetNumber pos2 =
ItemPointerGetOffsetNumber(tuple2-t_tid);
:
1 3.4e-05 :if (pos1 != pos2)
48757 1.6376 :return (pos1 pos2) ? -1 : 1;
:}
:
:return 0;
56705 1.9045 :}
Looks to me like we're eating more than seven percent of the total
runtime to do this :-(
Now as far as I can see, the original motivation for this (as stated in
the comment) is entirely dead anymore, since we always use our own qsort
implementation in preference to whatever bogus version a given libc
might supply. What do people think of removing this bit of code in
favor of just returning 0?
I can see a couple of possible objections:
1. Someday we might go back to using platform qsort. (But surely we
could insist on qsort behaving sanely for equal keys.)
2. If you've got lots of equal keys, it's conceivable that having the
index entries sorted by TID offers some advantage in indexscan speed.
I'm dubious that that's useful, mainly because the planner should prefer
a bitmap scan in such a case; and anyway the ordering is unlikely to
be preserved for long. But it's something to think about.
Comments?
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
