Skip site navigation (1) Skip section navigation (2)

Remove hacks for old bad qsort() implementations?

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: pgsql-hackers(at)postgreSQL(dot)org
Subject: Remove hacks for old bad qsort() implementations?
Date: 2008-03-17 03:59:41
Message-ID: (view raw, whole thread or download thread mbox)
Lists: pgsql-hackers
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.


			regards, tom lane


pgsql-hackers by date

Next:From: Kohei KaiGaiDate: 2008-03-17 04:25:40
Subject: [0/4] Proposal of SE-PostgreSQL patches
Previous:From: Greg SmithDate: 2008-03-17 03:45:56
Subject: Re: Commit fest?

Privacy Policy | About PostgreSQL
Copyright © 1996-2017 The PostgreSQL Global Development Group