On Thu, Jul 16, 2015 at 5:05 PM, Tom Lane <t...@sss.pgh.pa.us> wrote: > It's possible that this issue can only manifest on 9.4 and up where > we have the ability for tuplesort to allocate work arrays approaching > INT_MAX elements. But I don't have a lot of faith in that; I think the > worst-case stack depth for the way we have it now could be as bad as O(N), > so in principle a crash could be possible with significantly smaller input > arrays. I think we'd better back-patch this all the way.
+1. If you want to generate a worst case, McIlroy wrote a program that will generate one [1]. AFAIR, it will generate a series of self-consistent comparisons in the "gas" comparator that produce a worst-case outcome (as opposed to producing a simple worse-case input, which would be more convenient in this kind of scenario). This is known specifically to affect the Bentley & McIlroy implementation, as the paper goes into. [1] http://www.cs.dartmouth.edu/~doug/mdmspe.pdf -- Peter Geoghegan -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers