On 2017-02-24 15:18:04 -0800, Andres Freund wrote:
> On 2017-02-24 15:12:37 -0800, Andres Freund wrote:
> > On 2017-02-24 18:04:18 -0500, Tom Lane wrote:
> > > Concretely, something like the attached. This passes regression tests
> > > but I've not pushed on it any harder than that.
> >
> > Heh, I'd just gotten something that didn't immediately crash anymore ;)
> >
> > Running your patch against Jeff's test-case, verified before that I
> > could easily reproduce the O(N^2) cost.
>
> Oh, that didn't take as long as I was afraid (optimized/non-assert build):
>
> postgres[26268][1]=# SET work_mem = '13GB';
> SET
> Time: 2.591 ms
> postgres[26268][1]=# select count(*) from foobar2 where not exists (select 1 from foobar t where
t.titleid=foobar2.titleid);
> Time: 268043.710 ms (04:28.044)
As another datapoint, I measured this patch against the problem from
https://www.postgresql.org/message-id/20170227111732.vrx5v72ighehwpkf@alap3.anarazel.de
(see top post in thread), and it indeed fixes the runtime issue -
there's still considerably higher memory usage and some runtime
overhead, but the quadratic behaviour is gone.
I think we should go forward with something like this patch in all
branches, and only use Tomas' patch in master, because they're
considerably larger.
Regards,
Andres