On Wed, Jul 17, 2013 at 1:25 PM, Robert Haas
<robertmhaas@gmail.com> wrote:
On Mon, Jul 15, 2013 at 12:45 AM, Gurjeet Singh <
gurjeet@singh.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.
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,
--