On Fri, Feb 7, 2014 at 4:28 PM, Jeremy Harris <jgh@wizmail.org> wrote:
> On 06/02/14 22:12, Jeremy Harris wrote:
>>> Did you try sorting already-sorted, reverse
>>> sorted, or pipe-organ shaped data sets?
>
> Summary (low numbers better):
>
> Random ints: 83% compares, level on time.
> Sorted ints: level compares, 70% time.
> Reverse-sorted ints: 10% compares, 15% time (!)
> Constant ints: 200% compares, 360% time (ouch, and not O(n))
> Pipe-organ ints: 80% compares, 107% time
> Random text: 83% compares, 106% time
This is kind of what I expected to happen. The problem is that it's
hard to make some cases better without making other cases worse. I
suspect (hope?) there's some simple fix for the constant-int case.
But the last two cases are trickier. It seems intuitively that
reducing comparisons ought to reduce runtime, but if I'm reading the
results, the runtime actually went up even though the number of
comparisons went down. This is hard to account for, but we probably
need to at least understand why that's happening. I feel like this
algorithm ought to be a win, but these data don't provide a compelling
case for change.
I wonder if it would be worth trying this test with text data as well.Text comparisons are much more expensive than
integercomparisons, so
the effect of saving comparisons ought to be more visible there.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company