Re: review: Non-recursive processing of AND/OR lists

On Wed, Jul 17, 2013 at 1:25 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:

> On Mon, Jul 15, 2013 at 12:45 AM, Gurjeet Singh <gurjeet(at)singh(dot)im> wrote:
> > Agreed that there's overhead in allocating list items, but is it more
> > overhead than pushing functions on the call stack? Not sure, so I leave
> it
> > to others who understand such things better than I do.
>
> If you think that a palloc can ever be cheaper that pushing a frame on
> the callstack, you're wrong. palloc is not some kind of an atomic
> primitive. It's implemented by the AllocSetAlloc function, and you're
> going to have to push that function on the call stack, too, in order
> to run it.
>

Agreed. I take my objection back. Even if AllocSetAlloc() reuses memory
that was pfree'd earlier, it'll still be at least as expensive as recursing.

>
> My main point here is that if the user writes a = 1 and b = 1 and c =
> 1 and d = 1, they're not going to end up with a bushy tree. They're
> going to end up with a tree that's only deep in one direction (left, I
> guess) and that's the case we might want to consider optimizing. To
> obtain a bushy tree, they're going to have to write a = 1 and (b = 1
> and c = 1) and d = 1, or something like that, and I don't see why we
> should stress out about that case. It will be rare in practice.
>

In v6 of the patch, I have deferred the 'pending' list initialization to
until we actually hit a candidate right-branch. So in the common case the
pending list will never be populated, and if we find a bushy or right-deep
tree (for some reason an ORM/tool may choose to build AND/OR lists that may
end being right-deep when in Postgres), then the pending list will be used
to process them iteratively.

Does that alleviate your concern about 'pending' list management causing an
overhead.

Agreed that bushy/right-deep trees are a remote corner case, but we are
addressing a remote corner case in the first place (insanely long AND
lists) and why not handle another remote corner case right now if it
doesn't cause an overhead for common case.

Best regards,
--
Gurjeet Singh

http://gurjeet.singh.im/

EnterpriseDB Inc.