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

Hello

2013/7/15 Gurjeet Singh <gurjeet(at)singh(dot)im>:
> On Sun, Jul 14, 2013 at 8:27 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>>
>> On Wed, Jul 10, 2013 at 9:02 PM, Josh Berkus <josh(at)agliodbs(dot)com> wrote:
>> >> I think it's a waste of code to try to handle bushy trees. A list is
>> >> not a particularly efficient representation of the pending list; this
>> >> will probably be slower than recusing in the common case. I'd suggest
>> >> keeping the logic to handle left-deep trees, which I find rather
>> >> elegant, but ditching the pending list.
>
>
> Somehow I find it hard to believe that recursing would be more efficient
> than processing the items right there. The recursion is not direct either;
> transformExprRecurse() is going to call this function again, but after a few
> more switch-case comparisons.
>
> 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 by common-case you mean a list of just one logical AND/OR operator, then
> I agree that creating and destroying a list may incur overhead that is
> relatively very expensive. To that end, I have altered the patch, attached,
> to not build a pending list until we encounter a node with root_expr_kind in
> a right branch.
>
> We're getting bushy-tree processing with very little extra code, but if you
> deem it not worthwhile or adding complexity, please feel free to rip it out.
>
>>
>> >
>> > Is there going to be further discussion of this patch, or do I return
>> > it?
>>
>> Considering it's not been updated, nor my comments responded to, in
>> almost two weeks, I think we return it at this point.
>
>
> Sorry, I didn't notice that this patch was put back in 'Waiting on Author'
> state.
>

I did a some performance tests of v5 and v6 version and there v5 is
little bit faster than v6, and v6 has significantly higher stddev

but I am not sure, if my test is correct - I tested a speed of EXPLAIN
statement - result was forwarded to /dev/null

Result of this test is probably related to tested pattern of
expressions - in this case "expr or expr or expr or expr or expr ... "

10 000 exprs (ms)

v | avg | stddev
---+---------+--------
5 | 1839.14 | 13.68
6 | 1871.77 | 48.02

==v5 profile==
209064 43.5354 postgres equal
207849 43.2824 postgres process_equivalence
37453 7.7992 postgres datumIsEqual
3178 0.6618 postgres SearchCatCache
2350 0.4894 postgres AllocSetAlloc

==v6 profile==
193251 45.3998 postgres process_equivalence
178183 41.8599 postgres equal
30430 7.1488 postgres datumIsEqual
2819 0.6623 postgres SearchCatCache
1951 0.4583 postgres AllocSetAlloc

I found so 9.4 planner is about 1% slower (for test that sent by
Gurjeet), that than 9.2 planner, but it is not related to this patch

v6 is clean and all regression tests was passed

Regards

Pavel

> Best regards,
>
> --
> Gurjeet Singh
>
> http://gurjeet.singh.im/
>
> EnterpriseDB Inc.