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

Hello

2013/7/15 Gurjeet Singh <gurjeet@singh.im>:
> On Sun, Jul 14, 2013 at 8:27 PM, Robert Haas <robertmhaas@gmail.com> wrote:
>>
>> On Wed, Jul 10, 2013 at 9:02 PM, Josh Berkus <josh@agliodbs.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.686 | 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.