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

Hello

related to

https://commitfest.postgresql.org/action/patch_view?id=1130
http://www.postgresql.org/message-id/CABwTF4V9rsjiBWE+87pK83Mmm7ACdrG7sZ08RQ-4qYMe8jvhbw@mail.gmail.com

* motivation: remove recursive procession of AND/OR list (hangs with
10062 and more subexpressions)

* patch is short, clean and respect postgresql source code requirements
* patch was applied cleanly without warnings
* all regression tests was passed
* I successfully evaluated expression with 100000 subexpressions
* there is no significant slowdown

possible improvements

a = (A_Expr*) list_nth(pending, 0);

a = (A_Expr*) linitial(pending);

not well comment

should be -- "If the right branch is also an SAME condition, append it to the"

+ /*
+ * If the right branch is also an AND condition, append it to the
+ * pending list, to be processed later. This allows us to walk even
+ * bushy trees, not just left-deep trees.
+ */
+ if (IsA(a->rexpr, A_Expr) && ((A_Expr*)a->rexpr)->kind == root_kind)
+ {
+ pending = lappend(pending, a->rexpr);
+ }
+ else
+ {
+ expr = transformExprRecurse(pstate, a->rexpr);
+ expr = coerce_to_boolean(pstate, expr, root_kind == AEXPR_AND ?
"AND" : "OR");
+ exprs = lcons(expr, exprs);
+ }

I don't see any other issues, so after fixing comments this patch is
ready for commit

Regards

Pavel Stehule

Thanks for the review Pavel.

On Tue, Jun 18, 2013 at 3:01 PM, Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com>wrote:

> Hello
>
> related to
>
> https://commitfest.postgresql.org/action/patch_view?id=1130
>
> http://www.postgresql.org/message-id/CABwTF4V9rsjiBWE+87pK83Mmm7ACdrG7sZ08RQ-4qYMe8jvhbw@mail.gmail.com
>
>
> * motivation: remove recursive procession of AND/OR list (hangs with
> 10062 and more subexpressions)
>
> * patch is short, clean and respect postgresql source code requirements
> * patch was applied cleanly without warnings
> * all regression tests was passed
> * I successfully evaluated expression with 100000 subexpressions
> * there is no significant slowdown
>
> possible improvements
>
> a = (A_Expr*) list_nth(pending, 0);
>
> a = (A_Expr*) linitial(pending);
>
> not well comment
>
> should be -- "If the right branch is also an SAME condition, append it to
> the"
>
> + /*
> + * If the right branch is also an AND condition,
> append it to the
> + * pending list, to be processed later. This
> allows us to walk even
> + * bushy trees, not just left-deep trees.
> + */
> + if (IsA(a->rexpr, A_Expr) &&
> ((A_Expr*)a->rexpr)->kind == root_kind)
> + {
> + pending = lappend(pending, a->rexpr);
> + }
> + else
> + {
> + expr = transformExprRecurse(pstate,
> a->rexpr);
> + expr = coerce_to_boolean(pstate, expr,
> root_kind == AEXPR_AND ?
> "AND" : "OR");
> + exprs = lcons(expr, exprs);
> + }
>
> I don't see any other issues, so after fixing comments this patch is
> ready for commit
>
> Regards
>
> Pavel Stehule
>

--
Gurjeet Singh

http://gurjeet.singh.im/

EnterpriseDB Inc.

On Tue, Jun 18, 2013 at 3:01 PM, Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com>wrote:

>
> related to
>
> https://commitfest.postgresql.org/action/patch_view?id=1130
>
> http://www.postgresql.org/message-id/CABwTF4V9rsjiBWE+87pK83Mmm7ACdrG7sZ08RQ-4qYMe8jvhbw@mail.gmail.com
>
>
> * motivation: remove recursive procession of AND/OR list (hangs with
> 10062 and more subexpressions)
>
> * patch is short, clean and respect postgresql source code requirements
> * patch was applied cleanly without warnings
> * all regression tests was passed
> * I successfully evaluated expression with 100000 subexpressions
> * there is no significant slowdown
>
> possible improvements
>
> a = (A_Expr*) list_nth(pending, 0);
>
> a = (A_Expr*) linitial(pending);
>

I made that change, hesitantly. The comments above definition of linitial()
macro describe the confusion that API causes. I wanted to avoid that
confusion for new code, so I used the newer API which makes the intention
quite clear. But looking at that code closely, list_nth() causes at least 2
function calls, and that's pretty heavy compared to the linitiali() macro.

>
> not well comment
>
> should be -- "If the right branch is also an SAME condition, append it to
> the"
>

I moved that comment above the outer bock, so that the intention of the
whole do-while code block is described in one place.

I don't see any other issues, so after fixing comments this patch is
> ready for commit
>

Thanks for the review Pavel.

Attached is the updated patch, v4. It has the above edits, and a few code
improvements, like not repeating the (root_kind == AEPR_AND ? .. : ..)
ternary expression.

Best regards,
--
Gurjeet Singh

http://gurjeet.singh.im/

EnterpriseDB Inc.

Hello

just one small notices

I dislike a name "root_bool_expr", because, there is not a expression,
but expression type. Can you use "root_bool_expr_type" instead? It is
little bit longer, but more correct. Same not best name is
"root_char", maybe "root_bool_op_name"

or root_expr_type and root_op_name ???

Have no other comments

Regards

Pavel

2013/6/30 Gurjeet Singh <gurjeet(at)singh(dot)im>:
> On Tue, Jun 18, 2013 at 3:01 PM, Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com>
> wrote:
>>
>>
>> related to
>>
>> https://commitfest.postgresql.org/action/patch_view?id=1130
>>
>> http://www.postgresql.org/message-id/CABwTF4V9rsjiBWE+87pK83Mmm7ACdrG7sZ08RQ-4qYMe8jvhbw@mail.gmail.com
>>
>>
>> * motivation: remove recursive procession of AND/OR list (hangs with
>> 10062 and more subexpressions)
>>
>> * patch is short, clean and respect postgresql source code requirements
>> * patch was applied cleanly without warnings
>> * all regression tests was passed
>> * I successfully evaluated expression with 100000 subexpressions
>> * there is no significant slowdown
>>
>> possible improvements
>>
>> a = (A_Expr*) list_nth(pending, 0);
>>
>> a = (A_Expr*) linitial(pending);
>
>
> I made that change, hesitantly. The comments above definition of linitial()
> macro describe the confusion that API causes. I wanted to avoid that
> confusion for new code, so I used the newer API which makes the intention
> quite clear. But looking at that code closely, list_nth() causes at least 2
> function calls, and that's pretty heavy compared to the linitiali() macro.
>
>>
>>
>> not well comment
>>
>> should be -- "If the right branch is also an SAME condition, append it to
>> the"
>
>
> I moved that comment above the outer bock, so that the intention of the
> whole do-while code block is described in one place.
>
>> I don't see any other issues, so after fixing comments this patch is
>> ready for commit
>
>
> Thanks for the review Pavel.
>
> Attached is the updated patch, v4. It has the above edits, and a few code
> improvements, like not repeating the (root_kind == AEPR_AND ? .. : ..)
> ternary expression.
>
> Best regards,
> --
> Gurjeet Singh
>
> http://gurjeet.singh.im/
>
> EnterpriseDB Inc.

On Sun, Jun 30, 2013 at 11:13 AM, Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com>wrote:

> Hello
>
> just one small notices
>
> I dislike a name "root_bool_expr", because, there is not a expression,
> but expression type. Can you use "root_bool_expr_type" instead? It is
> little bit longer, but more correct. Same not best name is
> "root_char", maybe "root_bool_op_name"
>
> or root_expr_type and root_op_name ???
>

How about naming those 3 variables as follows:

root_expr_kind
root_expr_name
root_bool_expr_type

--
Gurjeet Singh

http://gurjeet.singh.im/

EnterpriseDB Inc.

2013/6/30 Gurjeet Singh <gurjeet(at)singh(dot)im>:
> On Sun, Jun 30, 2013 at 11:13 AM, Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com>
> wrote:
>>
>> Hello
>>
>> just one small notices
>>
>> I dislike a name "root_bool_expr", because, there is not a expression,
>> but expression type. Can you use "root_bool_expr_type" instead? It is
>> little bit longer, but more correct. Same not best name is
>> "root_char", maybe "root_bool_op_name"
>>
>> or root_expr_type and root_op_name ???
>
>
> How about naming those 3 variables as follows:
>
> root_expr_kind
> root_expr_name
> root_bool_expr_type

+1

Pavel

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

On Sun, Jun 30, 2013 at 11:46 AM, Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com>wrote:

> 2013/6/30 Gurjeet Singh <gurjeet(at)singh(dot)im>:
> > On Sun, Jun 30, 2013 at 11:13 AM, Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com
> >
> > wrote:
> >
> > How about naming those 3 variables as follows:
> >
> > root_expr_kind
> > root_expr_name
> > root_bool_expr_type
>
> +1

Thanks. Attached is the patch with that change. I'll update the commitfest
entry with a link to this email.

--
Gurjeet Singh

http://gurjeet.singh.im/

EnterpriseDB Inc.

On Sun, Jun 30, 2013 at 11:46 AM, Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com>wrote:

> 2013/6/30 Gurjeet Singh <gurjeet(at)singh(dot)im>:
> > On Sun, Jun 30, 2013 at 11:13 AM, Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com
> >
> > wrote:
> >
> > How about naming those 3 variables as follows:
> >
> > root_expr_kind
> > root_expr_name
> > root_bool_expr_type
>
> +1

Thanks. Attached is the patch with that change. I'll update the commitfest
entry with a link to this email.

--
Gurjeet Singh

http://gurjeet.singh.im/

EnterpriseDB Inc.

--
Gurjeet Singh

http://gurjeet.singh.im/

EnterpriseDB Inc.

2013/6/30 Gurjeet Singh <gurjeet(at)singh(dot)im>:
> On Sun, Jun 30, 2013 at 11:46 AM, Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com>
> wrote:
>>
>> 2013/6/30 Gurjeet Singh <gurjeet(at)singh(dot)im>:
>> > On Sun, Jun 30, 2013 at 11:13 AM, Pavel Stehule
>> > <pavel(dot)stehule(at)gmail(dot)com>
>> > wrote:
>> >
>> > How about naming those 3 variables as follows:
>> >
>> > root_expr_kind
>> > root_expr_name
>> > root_bool_expr_type
>>
>> +1
>
>
> Thanks. Attached is the patch with that change. I'll update the commitfest
> entry with a link to this email.

ok

I chechecked it - patched without warnings, all tests passed

It is ready for commit

Regards

Pavel

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

On Sun, Jun 30, 2013 at 1:08 PM, Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com> wrote:
> 2013/6/30 Gurjeet Singh <gurjeet(at)singh(dot)im>:
>> On Sun, Jun 30, 2013 at 11:46 AM, Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com>
>> wrote:
>>>
>>> 2013/6/30 Gurjeet Singh <gurjeet(at)singh(dot)im>:
>>> > On Sun, Jun 30, 2013 at 11:13 AM, Pavel Stehule
>>> > <pavel(dot)stehule(at)gmail(dot)com>
>>> > wrote:
>>> >
>>> > How about naming those 3 variables as follows:
>>> >
>>> > root_expr_kind
>>> > root_expr_name
>>> > root_bool_expr_type
>>>
>>> +1
>>
>>
>> Thanks. Attached is the patch with that change. I'll update the commitfest
>> entry with a link to this email.
>
> ok
>
> I chechecked it - patched without warnings, all tests passed
>
> It is ready for commit

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.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

> 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.

Is there going to be further discussion of this patch, or do I return it?

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

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.
>
> 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.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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.

Best regards,
--
Gurjeet Singh

http://gurjeet.singh.im/

EnterpriseDB Inc.

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.

On Tue, Jul 16, 2013 at 4:04 PM, Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com>wrote:

> 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
>

Thanks Pavel.

The difference in average seems negligible, but stddev is interesting
because v6 does less work than v5 in common cases and in the test that I
had shared.

The current commitfest (2013-06) is marked as 'In Progress', so is it okay
to just mark the patch as 'Ready for Committer' or should I move it to the
next commitfest (2013-09).

What's the procedure of moving a patch to the next commitfest? Do I make a
fresh submission there with a link to current submission, or is the move
doable somehow in the application itself.

Best regards,
--
Gurjeet Singh

http://gurjeet.singh.im/

EnterpriseDB Inc.

On Wed, Jul 17, 2013 at 8:21 AM, Gurjeet Singh <gurjeet(at)singh(dot)im> wrote:

>
> What's the procedure of moving a patch to the next commitfest?
>

Never mind, I see an email from Josh B. regarding this on my corporate
account.

Best regards,
--
Gurjeet Singh

http://gurjeet.singh.im/

EnterpriseDB Inc.

On 07/17/2013 05:21 AM, Gurjeet Singh wrote:
> On Tue, Jul 16, 2013 at 4:04 PM, Pavel Stehule <pavel(dot)stehule(at)gmail(dot)com>wrote:
>
>> 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
>>
>
> Thanks Pavel.
>
> The difference in average seems negligible, but stddev is interesting
> because v6 does less work than v5 in common cases and in the test that I
> had shared.
>
> The current commitfest (2013-06) is marked as 'In Progress', so is it okay
> to just mark the patch as 'Ready for Committer' or should I move it to the
> next commitfest (2013-09).

If this is actually "ready for committer", I'll mark it as such.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

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.

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.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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.

On Wed, Jul 17, 2013 at 2:03 PM, Gurjeet Singh <gurjeet(at)singh(dot)im> wrote:
> 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.

Because simpler code is less likely to have bugs and is easier to
maintain. It's worth noting that the change you're proposing is in
fact user-visible, as demonstrated by the fact that you had to update
the regression test output:

- | WHERE (((rsl.sl_color =
rsh.slcolor) AND (rsl.sl_len_cm >= rsh.slminlen_cm)) AND
(rsl.sl_len_cm <= rsh.slmaxlen_cm));
+ | WHERE ((rsl.sl_color =
rsh.slcolor) AND (rsl.sl_len_cm >= rsh.slminlen_cm) AND (rsl.sl_len_cm
<= rsh.slmaxlen_cm));

Now, I think that change is actually an improvement, because here's
what that WHERE clause looked like when it was entered:

WHERE rsl.sl_color = rsh.slcolor
AND rsl.sl_len_cm >= rsh.slminlen_cm
AND rsl.sl_len_cm <= rsh.slmaxlen_cm;

But flattening a = 1 AND (b = 1 AND c = 1 AND d = 1) AND e = 1 to a
flat list doesn't have any of the same advantages.

At the end of the day, this is a judgement call, and I'm giving you
mine. If somebody else wants to weigh in, that's fine. I can't think
of anything that would actually be outright broken under your proposed
approach, but my personal feeling is that it's better to only add the
amount of code that we know is needed to solve the problem actually
observed in practice, and no more.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> On Wed, Jul 17, 2013 at 2:03 PM, Gurjeet Singh <gurjeet(at)singh(dot)im> wrote:
>> 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.

> Because simpler code is less likely to have bugs and is easier to
> maintain.

I agree with that point, but one should also remember Polya's Inventor's
Paradox: the more general problem may be easier to solve. That is, if
done right, code that fully flattens an AND tree might actually be
simpler than code that does just a subset of the transformation. The
current patch fails to meet this expectation, but maybe you just haven't
thought about it the right way.

My concerns about this patch have little to do with that, though, and
much more to do with the likelihood that it breaks some other piece of
code that is expecting AND/OR to be strictly binary operators, which
is what they've always been in parsetrees that haven't reached the
planner. It doesn't appear to me that you've done any research on that
point whatsoever --- you have not even updated the comment for BoolExpr
(in primnodes.h) that this patch falsifies.

> It's worth noting that the change you're proposing is in
> fact user-visible, as demonstrated by the fact that you had to update
> the regression test output:

The point to worry about here is whether rule dump and reload is still
safe. In particular, the logic in ruleutils.c for deciding whether it's
safe to omit parentheses has only really been thought about/tested for
the binary AND/OR case. Although that code can dump N-way AND/OR
because it's also used to print post-planner expression trees in EXPLAIN,
that case has never been held to the standard of "is the parser
guaranteed to interpret this expression the same as before?". Perhaps
it's fine, but has anyone looked at that issue?

regards, tom lane

On Thu, Jul 18, 2013 at 10:19 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

>
> > Because simpler code is less likely to have bugs and is easier to
> > maintain.
>
> I agree with that point, but one should also remember Polya's Inventor's
> Paradox: the more general problem may be easier to solve. That is, if
> done right, code that fully flattens an AND tree might actually be
> simpler than code that does just a subset of the transformation. The
> current patch fails to meet this expectation,

The current patch does completely flatten any type of tree (left/right-deep
or bushy) without recursing, and right-deep and bushy tree processing is
what Robert is recommending to defer to recursive processing. Maybe I
haven't considered a case where it doesn't flatten the tree; do you have an
example in mind.

> but maybe you just haven't
> thought about it the right way.
>
> My concerns about this patch have little to do with that, though, and
> much more to do with the likelihood that it breaks some other piece of
> code that is expecting AND/OR to be strictly binary operators, which
> is what they've always been in parsetrees that haven't reached the
> planner. It doesn't appear to me that you've done any research on that
> point whatsoever

No, I haven't, and I might not be able to research it for a few more weeks.

> you have not even updated the comment for BoolExpr
> (in primnodes.h) that this patch falsifies.
>

I will fix that.

Best regards,
--
Gurjeet Singh

http://gurjeet.singh.im/

EnterpriseDB Inc.

On Thu, Jul 18, 2013 at 1:54 PM, Gurjeet Singh <gurjeet(at)singh(dot)im> wrote:

> On Thu, Jul 18, 2013 at 10:19 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
>>
>> > Because simpler code is less likely to have bugs and is easier to
>> > maintain.
>>
>> I agree with that point, but one should also remember Polya's Inventor's
>> Paradox: the more general problem may be easier to solve. That is, if
>> done right, code that fully flattens an AND tree might actually be
>> simpler than code that does just a subset of the transformation. The
>> current patch fails to meet this expectation,
>
>
> The current patch does completely flatten any type of tree
> (left/right-deep or bushy) without recursing, and right-deep and bushy tree
> processing is what Robert is recommending to defer to recursive processing.
> Maybe I haven't considered a case where it doesn't flatten the tree; do you
> have an example in mind.
>
>
>> but maybe you just haven't
>> thought about it the right way.
>>
>
I tried to eliminate the 'pending' list, but I don't see a way around it.
We need temporary storage somewhere to store the branches encountered on
the right; in recursion case the call stack was serving that purpose.

>
>> My concerns about this patch have little to do with that, though, and
>> much more to do with the likelihood that it breaks some other piece of
>> code that is expecting AND/OR to be strictly binary operators, which
>> is what they've always been in parsetrees that haven't reached the
>> planner. It doesn't appear to me that you've done any research on that
>> point whatsoever
>
>
> No, I haven't, and I might not be able to research it for a few more weeks.
>

There are about 30 files (including optimizer and executor) that match
case-insensitive search for BoolExpr, and I scanned those for the usage of
the member 'args'. All the instances where BoolExpr.args is being accessed,
it's being treated as a null-terminated list. There's one exception that I
could find, and it was in context of NOT expression: not_clause() in
clauses.c.

>
>
>> you have not even updated the comment for BoolExpr
>> (in primnodes.h) that this patch falsifies.
>>
>
> I will fix that.
>

I think this line in that comment already covers the fact that in some
"special" cases a BoolExpr may have more than 2 arguments.

"There are also a few special cases where more arguments can appear before
optimization."

I have updated the comment nevertheless, and removed another comment in
parse_expr.c that claimed to be the only place where a BoolExpr with more
than 2 args is generated.

I have isolated the code for right-deep and bushy tree processing via the
macro PROCESS_BUSHY_TREES. Also, I have shortened some variable names while
retaining their meaning.

Please find the updated patch attached (based on master).

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

EDB www.EnterpriseDB.com <http://www.enterprisedb.com>

Gurjeet Singh <gurjeet(at)singh(dot)im> writes:
> I tried to eliminate the 'pending' list, but I don't see a way around it.
> We need temporary storage somewhere to store the branches encountered on
> the right; in recursion case the call stack was serving that purpose.

I still think we should fix this in the grammar, rather than introducing
complicated logic to try to get rid of the recursion later. For example,
as attached.

The existing A_Expr representation of raw AND/OR nodes isn't conducive to
this, but it's not that hard to change it. The attached patch chooses to
use BoolExpr as both the raw and transformed representation of AND/OR/NOT;
we could alternatively invent some new raw-parsetree node type, but I
don't see any advantage in that.

I continue to think that more thought is needed about downstream
processing. For instance, at least the comment at the head of prepqual.c
is wrong now, and it's worth wondering whether the planner still needs to
worry about AND/OR flattening at all. (It probably does, to deal with
view-flattening cases for example; but it's worth considering whether
anything could be saved if we stopped doing that.)

regards, tom lane

I wrote:
> Gurjeet Singh <gurjeet(at)singh(dot)im> writes:
>> I tried to eliminate the 'pending' list, but I don't see a way around it.
>> We need temporary storage somewhere to store the branches encountered on
>> the right; in recursion case the call stack was serving that purpose.

> I still think we should fix this in the grammar, rather than introducing
> complicated logic to try to get rid of the recursion later. For example,
> as attached.

I went looking for (and found) some additional obsoleted comments, and
convinced myself that ruleutils.c is okay as-is, and pushed this.

regards, tom lane

Thanks!

On Mon, Jun 16, 2014 at 3:58 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> I wrote:
>> Gurjeet Singh <gurjeet(at)singh(dot)im> writes:
>>> I tried to eliminate the 'pending' list, but I don't see a way around it.
>>> We need temporary storage somewhere to store the branches encountered on
>>> the right; in recursion case the call stack was serving that purpose.
>
>> I still think we should fix this in the grammar, rather than introducing
>> complicated logic to try to get rid of the recursion later. For example,
>> as attached.
>
> I went looking for (and found) some additional obsoleted comments, and
> convinced myself that ruleutils.c is okay as-is, and pushed this.
>
> regards, tom lane

--
Gurjeet Singh http://gurjeet.singh.im/

EDB www.EnterpriseDB.com