opt: allow OrderingChoices to imply more orderings#64593
opt: allow OrderingChoices to imply more orderings#64593craig[bot] merged 1 commit intocockroachdb:masterfrom
Conversation
|
This change is |
|
Ignore the first 3 commits -- they are from #64501. |
9023b89 to
d8a54d9
Compare
|
Just copying this from above so it doesn't get lost: ignore the first 3 commits -- they are from #64501. Also, note that this doesn't fix #33023, because the example in that issue still requires a sort. To remove the sort, we'll need to write |
RaduBerinde
left a comment
There was a problem hiding this comment.
Reviewable status:
complete! 1 of 0 LGTMs obtained (waiting on @mgartner and @rytaft)
pkg/sql/opt/ordering/select.go, line 30 at r4 (raw file):
return props.OrderingChoice{} } child := parent.(*memo.SelectExpr).Input
This is a creative way to do it! But it deserves an explanation (and we should point to #33023 as well). What we need to get across is that trimColumnGroups will trim the column groups arbitrarily so we are trying to "guide" it into a good choice by using a more specific ordering.
pkg/sql/opt/ordering/select.go, line 34 at r4 (raw file):
for i := range orders { if orders[i].Implies(required) { order := orders[i].CommonPrefix(required)
If it implies required why do we need to get the common prefix? (as opposed to just using orders[i])?
Also, maybe we should use Intersects and Intersection here instead (it should allow for more cases)
d8a54d9 to
00fbf57
Compare
rytaft
left a comment
There was a problem hiding this comment.
TFTR!
Reviewable status:
pkg/sql/opt/ordering/select.go, line 30 at r4 (raw file):
Previously, RaduBerinde wrote…
This is a creative way to do it! But it deserves an explanation (and we should point to #33023 as well). What we need to get across is that
trimColumnGroupswill trim the column groups arbitrarily so we are trying to "guide" it into a good choice by using a more specific ordering.
Thanks! Done.
pkg/sql/opt/ordering/select.go, line 34 at r4 (raw file):
If it implies required why do we need to get the common prefix? (as opposed to just using orders[i])?
We need to make sure that the required ordering is no stronger than needed. Otherwise, we get errors like this from checkRequired: "panic: provided +7,+8 can be trimmed to +7 (FDs: (6)==(7), (7)==(6))" (added a comment to that effect).
Also, maybe we should use Intersects and Intersection here instead (it should allow for more cases)
If we use Intersects and Intersection, we get those same errors from checkRequired, since Intersection may create a stronger ordering than required.
(I also tried removing that check to see what would happen, and using Intersects and Intersection here doesn't improve many plans -- it actually makes many plans worse).
RaduBerinde
left a comment
There was a problem hiding this comment.
Reviewed 41 of 50 files at r1, 40 of 49 files at r3, 24 of 25 files at r4, 3 of 3 files at r5, 2 of 2 files at r6.
Reviewable status:
pkg/sql/opt/ordering/select.go, line 34 at r4 (raw file):
Previously, rytaft (Rebecca Taft) wrote…
If it implies required why do we need to get the common prefix? (as opposed to just using orders[i])?
We need to make sure that the required ordering is no stronger than needed. Otherwise, we get errors like this from
checkRequired: "panic: provided +7,+8 can be trimmed to +7 (FDs: (6)==(7), (7)==(6))" (added a comment to that effect).Also, maybe we should use Intersects and Intersection here instead (it should allow for more cases)
If we use
IntersectsandIntersection, we get those same errors fromcheckRequired, sinceIntersectionmay create a stronger ordering thanrequired.(I also tried removing that check to see what would happen, and using
IntersectsandIntersectionhere doesn't improve many plans -- it actually makes many plans worse).
Ah, got it, indeed, we need to trim the interesting ordering.
This commit updates the logic for determining whether an OrderingChoice can imply another OrderingChoice. The new logic allows columns in a group to be treated like optional columns after one of the columns is used. For example, "+1,+2,+3" implies "+(1|2),+3" now returns true. Prior to this commit, it returned false, which resulted in unnecessary sort operations in some cases. This commit also updates the corresponding logic for intersecting and finding the common prefix of two OrderingChoices. Furthermore, we now use interesting orderings to inform the required ordering passed down to the children of Select expressions. This makes it more likely that the child will be able to provide the required ordering. Informs cockroachdb#33023 Release note (performance improvement): increased the intelligence of the optimizer around orderings that can be provided by certain relational expressions when there are equalities between columns. This can allow the optimizer to remove unnecessary sort operations in some cases, thus improving performance.
00fbf57 to
970a932
Compare
rytaft
left a comment
There was a problem hiding this comment.
bors r+
Reviewable status:
RaduBerinde
left a comment
There was a problem hiding this comment.
Reviewed 6 of 6 files at r7.
Reviewable status:
|
Build succeeded: |
This commit updates the logic for determining whether an
OrderingChoicecan imply another
OrderingChoice. The new logic allows columns in a group to betreated like optional columns after one of the columns is used. For example,
"+1,+2,+3" implies "+(1|2),+3" now returns true. Prior to this commit, it
returned false, which resulted in unnecessary sort operations in some cases.
This commit also updates the corresponding logic for intersecting and finding
the common prefix of two
OrderingChoices.Furthermore, we now use interesting orderings to inform the required ordering
passed down to the children of
Selectexpressions. This makes it more likelythat the child will be able to provide the required ordering.
Informs #33023
Release note (performance improvement): increased the intelligence
of the optimizer around orderings that can be provided by certain
relational expressions when there are equalities between columns.
This can allow the optimizer to remove unnecessary sort operations in
some cases, thus improving performance.