[
https://issues.apache.org/jira/browse/CALCITE-3118?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Botong Huang updated CALCITE-3118:
----------------------------------
Description:
In VolcanoRuleCall.matchRecurse(), when ascending (child operand is matched,
looking for parent operand match), we want to check that the matched parent
indeed has the previously matched RelNode as a child *with the* *expected child
ordinal*.
However, there is a bug in this child ordinal check:
{noformat}
333 if (ascending && operand.childPolicy !=
RelOptRuleOperandChildPolicy.UNORDERED) {
334 // We know that the previous operand was *a* child of its parent,
335 // but now check that it is the *correct* child.
336 final RelSubset input =
337 (RelSubset) rel.getInput(previousOperand.ordinalInParent);
338 List<RelNode> inputRels = input.set.getRelsFromAllSubsets();
339 if (!inputRels.contains(previous)) {
340 continue;
341 }
342 }
{noformat}
We intend to make sure that "previous" is in Subset "input". However line 338
looked at RelNodes from the entire RelSet, rather than RelNodes only in Subset
"input". As a result, in some cases, incorrect parent is not skipped as
expected and is matched incorrectly.
The unit test case included is a case that triggers this bug, where a second
child RelNode incorrectly get matched as the first child of the parent RelNode.
--------------------------
Here's a detailed explanation of the test case that triggers the bug
We constructed a RelNode structure:
{noformat}
PhysBiRel
/ \
Subset1 Subset2
| |
leftPhy rightPhy
{noformat}
Where PhysBiRel has two inputs: leftPhy and rightPhy, both are logically
equivalent, but with different traits (Convention in this test case), and thus
are in different subsets.
(Two Rels in two subsets in the same RelSet is a necessary condition to
trigger this bug. )
A rule AssertOperandsDifferentRule is constructed as follows:
{noformat}
operand(PhysBiRel.class,
operand(PhysLeafRel.class, any()),
operand(PhysLeafRel.class, any()))
{noformat}
Obviously the correct match would be:
{noformat}
PhysBiRel
/ \
leftPhy rightPhy
{noformat}
However, with the bug, another match is also returned:
{noformat}
PhysBiRel
/ \
rightPhy rightPhy
{noformat}
*This is wrong because rightPhy is not PhysBiRel's first input at all, and
should not match as parent operand's first child.*
----------------------------
Here's how the incorrect match occurs.
1. When rightPhy of class PhysLeafRel is registered, we attempt to match it to
both the left and right child operands of AssertOperandsDifferentRule above.
This is expected.
2. When matched to the right child operand, it eventually leads to the correct
match result above.
3. When matched to the left child operand, it should have skipped/failed
matching the parent operand to PhysBiRel because rightPhy is *NOT* PhysBiRel's
first input. But because of the bug, the match succeeded. After parent is
matched, then it attempt to match the right child operand, and again matched
the rightPhy. As a result, both child operand end up matching the same RelNode
rightPhy.
was:
In VolcanoRuleCall.matchRecurse(), when ascending (child operand is matched,
looking for parent operand match), we want to check that the matched parent
indeed has the previously matched RelNode as a child *with the* *expected child
ordinal*.
However, there is a bug in this child ordinal check:
{noformat}
333 if (ascending && operand.childPolicy !=
RelOptRuleOperandChildPolicy.UNORDERED) {
334 // We know that the previous operand was *a* child of its parent,
335 // but now check that it is the *correct* child.
336 final RelSubset input =
337 (RelSubset) rel.getInput(previousOperand.ordinalInParent);
338 List<RelNode> inputRels = input.set.getRelsFromAllSubsets();
339 if (!inputRels.contains(previous)) {
340 continue;
341 }
342 }
{noformat}
We intend to make sure that "previous" is in Subset "input". However line 338
looked at RelNodes from the entire RelSet, rather than RelNodes only in Subset
"input". As a result, in some cases, incorrect parent is not skipped as
expected and matched incorrectly.
The unit test case included is a case that triggers this bug, where a second
child RelNode incorrectly get matched as the first child of the parent RelNode.
--------------------------
Here's a detailed explanation of the test case that triggers the bug
We constructed a RelNode structure:
{noformat}
PhysBiRel
/ \
Subset1 Subset2
| |
leftPhy rightPhy
{noformat}
Where PhysBiRel has two inputs: leftPhy and rightPhy, both are logically
equivalent, but with different traits (Convention in this test case), and thus
are in different subsets.
(Two Rels in two subsets in the same RelSet is a necessary condition to
trigger this bug. )
A rule AssertOperandsDifferentRule is constructed as follows:
{noformat}
operand(PhysBiRel.class,
operand(PhysLeafRel.class, any()),
operand(PhysLeafRel.class, any()))
{noformat}
Obviously the correct match would be:
{noformat}
PhysBiRel
/ \
leftPhy rightPhy
{noformat}
However, with the bug, another match is also returned:
{noformat}
PhysBiRel
/ \
rightPhy rightPhy
{noformat}
*This is wrong because rightPhy is not PhysBiRel's first input at all, and
should not match as parent operand's first child.*
----------------------------
Here's how the incorrect match occurs.
1. When rightPhy is registered, we attempt to match it to both the left and
right child operand of AssertOperandsDifferentRule above.
2. When matched to the right child operand, it eventually leads to the correct
match result above.
3. When matched to the left child operand, it should have skipped/failed
matching the parent operand to PhysBiRel because rightPhy is !!!!not!!!
PhysBiRel's first input.
But because of the bug, the match succeeded. After parent is matched, then it
attempt to match the right child operand, and again matched the rightPhy as
expected.
As a result, both child operand end up matching the same RelNode rightPhy.
> VolcanoRuleCall match parent child ordinal not properly checked
> ---------------------------------------------------------------
>
> Key: CALCITE-3118
> URL: https://issues.apache.org/jira/browse/CALCITE-3118
> Project: Calcite
> Issue Type: Bug
> Reporter: Botong Huang
> Priority: Major
> Labels: pull-request-available
> Time Spent: 1h 10m
> Remaining Estimate: 0h
>
> In VolcanoRuleCall.matchRecurse(), when ascending (child operand is matched,
> looking for parent operand match), we want to check that the matched parent
> indeed has the previously matched RelNode as a child *with the* *expected
> child ordinal*.
> However, there is a bug in this child ordinal check:
> {noformat}
> 333 if (ascending && operand.childPolicy !=
> RelOptRuleOperandChildPolicy.UNORDERED) {
> 334 // We know that the previous operand was *a* child of its parent,
> 335 // but now check that it is the *correct* child.
> 336 final RelSubset input =
> 337 (RelSubset) rel.getInput(previousOperand.ordinalInParent);
> 338 List<RelNode> inputRels = input.set.getRelsFromAllSubsets();
> 339 if (!inputRels.contains(previous)) {
> 340 continue;
> 341 }
> 342 }
> {noformat}
> We intend to make sure that "previous" is in Subset "input". However line 338
> looked at RelNodes from the entire RelSet, rather than RelNodes only in
> Subset "input". As a result, in some cases, incorrect parent is not skipped
> as expected and is matched incorrectly.
> The unit test case included is a case that triggers this bug, where a second
> child RelNode incorrectly get matched as the first child of the parent
> RelNode.
> --------------------------
> Here's a detailed explanation of the test case that triggers the bug
> We constructed a RelNode structure:
> {noformat}
> PhysBiRel
> / \
> Subset1 Subset2
> | |
> leftPhy rightPhy
> {noformat}
> Where PhysBiRel has two inputs: leftPhy and rightPhy, both are logically
> equivalent, but with different traits (Convention in this test case), and
> thus are in different subsets.
> (Two Rels in two subsets in the same RelSet is a necessary condition to
> trigger this bug. )
> A rule AssertOperandsDifferentRule is constructed as follows:
> {noformat}
> operand(PhysBiRel.class,
> operand(PhysLeafRel.class, any()),
> operand(PhysLeafRel.class, any()))
> {noformat}
> Obviously the correct match would be:
> {noformat}
> PhysBiRel
> / \
> leftPhy rightPhy
> {noformat}
> However, with the bug, another match is also returned:
> {noformat}
> PhysBiRel
> / \
> rightPhy rightPhy
> {noformat}
> *This is wrong because rightPhy is not PhysBiRel's first input at all, and
> should not match as parent operand's first child.*
> ----------------------------
> Here's how the incorrect match occurs.
> 1. When rightPhy of class PhysLeafRel is registered, we attempt to match it
> to both the left and right child operands of AssertOperandsDifferentRule
> above. This is expected.
> 2. When matched to the right child operand, it eventually leads to the
> correct match result above.
> 3. When matched to the left child operand, it should have skipped/failed
> matching the parent operand to PhysBiRel because rightPhy is *NOT*
> PhysBiRel's first input. But because of the bug, the match succeeded. After
> parent is matched, then it attempt to match the right child operand, and
> again matched the rightPhy. As a result, both child operand end up matching
> the same RelNode rightPhy.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
