opt: fix normalization of comparisons with constants by mgartner · Pull Request #90266 · cockroachdb/cockroach

mgartner · 2022-10-19T18:46:03Z

opt: fix normalization of comparisons with constants

A prior commit in #88199 attempted to fix a bug in the
NormalizeCmpPlusConst, NormalizeCmpMinusConst, and
NormalizeCmpConstMinus rules by checking for overflow/underflow in the
addition/subtraction of constants in a comparison expression. This was
insufficient to completely fix the bug because the transformation is
invalid if the non-normalized expression would have overflowed. Consider
an expression:

t::TIME + '-11 hrs'::INTERVAL > '01:00'::TIME

NormalizeCmpPlusConst would successively normalize it to this:

t::TIME > '01:00'::TIME - '-11 hrs'::INTERVAL
=> t::TIME > '12:00'::TIME

This expression is not semantically equivalent to the original
expression. It yields different results when t is a value that would
underflow when eleven hours is subtracted from it. For example, consider
t = '03:00'::TIME:

Original expression:
t::TIME + '-11 hrs'::INTERVAL > '01:00'::TIME
=> '03:00'::TIME + '-11 hrs'::INTERVAL > '01:00'::TIME
=> '16:00'::TIME > '01:00'::TIME
=> true

Normalized expression:
t::TIME > '12:00'::TIME
=> '03:00'::TIME > '12:00'::TIME
=> false

These normalization rules are only valid with types where overflow or
underflow during addition and subtraction results in an error.

This commit restricts these normalization rules to only operate on
integers, floats, and decimals, which will error if there is underflow
or overflow.

Fixes #90053

Release note (bug fix): A bug has been fixed that caused incorrect
evaluation of comparison expressions involving time and interval types,
like col::TIME + '10 hrs'::INTERVAL' > '01:00'::TIME.

opt: replace FoldBinaryCheckOverflow with FoldBinary

Release note: None

cockroach-teamcity · 2022-10-19T18:46:15Z

This change is

mgartner · 2022-10-19T18:46:41Z

I'm planning on backporting only the first commit.

rytaft

great find!

Reviewed 5 of 5 files at r1, 2 of 2 files at r2, all commit messages.
Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @DrewKimball, @mgartner, and @msirek)

pkg/sql/opt/norm/comp_funcs.go line 74 at r1 (raw file):

	// for this NULL check. The NULL check might not be necessary since we no
	// longer use this function on TIME and INTERVAL types, so maybe we can
	// reuse FoldBinary instead.

For the backport, why don't you at least rename this function to FindBinaryCheckNull, since there is no overflow checking.

A prior commit in cockroachdb#88199 attempted to fix a bug in the `NormalizeCmpPlusConst`, `NormalizeCmpMinusConst`, and `NormalizeCmpConstMinus` rules by checking for overflow/underflow in the addition/subtraction of constants in a comparison expression. This was insufficient to completely fix the bug because the transformation is invalid if the non-normalized expression would have overflowed. Consider an expression: t::TIME + '-11 hrs'::INTERVAL > '01:00'::TIME `NormalizeCmpPlusConst` would successively normalize it to this: t::TIME > '01:00'::TIME - '-11 hrs'::INTERVAL => t::TIME > '12:00'::TIME This expression is not semantically equivalent to the original expression. It yields different results when `t` is a value that would underflow when eleven hours is subtracted from it. For example, consider `t = '03:00'::TIME`: Original expression: t::TIME + '-11 hrs'::INTERVAL > '01:00'::TIME => '03:00'::TIME + '-11 hrs'::INTERVAL > '01:00'::TIME => '16:00'::TIME > '01:00'::TIME => true Normalized expression: t::TIME > '12:00'::TIME => '03:00'::TIME > '12:00'::TIME => false These normalization rules are only valid with types where overflow or underflow during addition and subtraction results in an error. This commit restricts these normalization rules to only operate on integers, floats, and decimals, which will error if there is underflow or overflow. Fixes cockroachdb#90053 Release note (bug fix): A bug has been fixed that caused incorrect evaluation of comparison expressions involving time and interval types, like `col::TIME + '10 hrs'::INTERVAL' > '01:00'::TIME`.

Release note: None

mgartner

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @DrewKimball, @msirek, and @rytaft)

pkg/sql/opt/norm/comp_funcs.go line 74 at r1 (raw file):

Previously, rytaft (Rebecca Taft) wrote…

For the backport, why don't you at least rename this function to FindBinaryCheckNull, since there is no overflow checking.

Good catch! Fixed.

msirek

Nice fix!

Reviewable status: complete! 1 of 0 LGTMs obtained (and 1 stale) (waiting on @DrewKimball and @rytaft)

rytaft

Reviewed 2 of 2 files at r3, 2 of 2 files at r4, all commit messages.
Reviewable status: complete! 1 of 0 LGTMs obtained (and 1 stale) (waiting on @DrewKimball)

mgartner · 2022-10-19T20:01:40Z

TFTRs!

bors r+

craig · 2022-10-19T20:47:24Z

Build succeeded:

Bazel Essential CI (Cockroach)

blathers-crl · 2022-10-19T20:47:55Z

Encountered an error creating backports. Some common things that can go wrong:

The backport branch might have already existed.
There was a merge conflict.
The backport branch contained merge commits.

You might need to create your backport manually using the backport tool.

error creating merge commit from 9150586 to blathers/backport-release-21.2-90266: POST https://api.github.com/repos/cockroachdb/cockroach/merges: 409 Merge conflict []

you may need to manually resolve merge conflicts with the backport tool.

Backport to branch 21.2.x failed. See errors above.

error creating merge commit from 3a635c6 to blathers/backport-release-22.1-90266: POST https://api.github.com/repos/cockroachdb/cockroach/merges: 409 Merge conflict []

you may need to manually resolve merge conflicts with the backport tool.

Backport to branch 22.1.x failed. See errors above.

error creating merge commit from 3a635c6 to blathers/backport-release-22.2-90266: POST https://api.github.com/repos/cockroachdb/cockroach/merges: 409 Merge conflict []

you may need to manually resolve merge conflicts with the backport tool.

Backport to branch 22.2.x failed. See errors above.

error creating merge commit from 3a635c6 to blathers/backport-release-22.2.0-90266: POST https://api.github.com/repos/cockroachdb/cockroach/merges: 409 Merge conflict []

you may need to manually resolve merge conflicts with the backport tool.

Backport to branch 22.2.0 failed. See errors above.

_{🦉 Hoot! I am a Blathers, a bot for CockroachDB. My owner is otan.}

This commit lifts some of the limitations placed on comparison normalization rules in cockroachdb#90266. That PR limited algebraic transformations of comparison expressions when the types involved were anything other than integers, decimals, or floats. Other types, like `TIME`, can overflow without error during addition or subtraction, making the transformation incorrect. `TIMESTAMP` and `TIMESTAMPTZ` types will error on overflow when an `INTERVAL` is added to or subtracted from them. So this commit allows the rule to apply for expressions with these types. Specifically, the following transformations are now made: ts + const_interval [cmp] const_ts => ts [cmp] const_ts - const_interval ts - const_interval [cmp] const_ts => ts [cmp] const_ts + const_interval const_ts - ts [cmp] const_interval => const_ts - const_interval [cmp] ts This ultimately allows more rules to match, like GenerateConstrainedScans. Release note (performance improvement): The optimizer now generates more efficient query plans for queries with comparison of timestamp and interval columns, e.g., `timestamp_col - '1 day'::INTERVAL > now()`.

118307: opt: normalize comparison with addition/subtraction of TS and INTERVALs r=mgartner a=mgartner #### opt: add TIMESTAMP, TIMESTAMPTZ, and INTERVAL columns to comp norm tests Release note: None #### opt: normalize comparison with addition/subtraction of TS and INTERVALs This commit lifts some of the limitations placed on comparison normalization rules in #90266. That PR limited algebraic transformations of comparison expressions when the types involved were anything other than integers, decimals, or floats. Other types, like `TIME`, can overflow without error during addition or subtraction, making the transformation incorrect. `TIMESTAMP` and `TIMESTAMPTZ` types will error on overflow when an `INTERVAL` is added to or subtracted from them. So this commit allows the rule to apply for expressions with these types. Specifically, the following transformations are now made: ts + const_interval [cmp] const_ts => ts [cmp] const_ts - const_interval ts - const_interval [cmp] const_ts => ts [cmp] const_ts + const_interval const_ts - ts [cmp] const_interval => const_ts - const_interval [cmp] ts This ultimately allows more rules to match, like GenerateConstrainedScans. Epic: None Release note (performance improvement): The optimizer now generates more efficient query plans for queries with comparison of timestamp and interval columns, e.g., `timestamp_col - '1 day'::INTERVAL > now()`. Co-authored-by: Marcus Gartner <marcus@cockroachlabs.com>

mgartner requested review from a team, DrewKimball and msirek October 19, 2022 18:46

mgartner requested a review from a team as a code owner October 19, 2022 18:46

mgartner added backport-21.2.x labels Oct 19, 2022

rytaft approved these changes Oct 19, 2022

View reviewed changes

mgartner added 2 commits October 19, 2022 15:08

opt: replace FoldBinaryCheckOverflow with FoldBinary

3a635c6

Release note: None

mgartner force-pushed the 90053-normalize-overflow branch from 50143c6 to 3a635c6 Compare October 19, 2022 19:09

mgartner commented Oct 19, 2022

View reviewed changes

msirek approved these changes Oct 19, 2022

View reviewed changes

rytaft approved these changes Oct 19, 2022

View reviewed changes

craig bot merged commit caaf41a into cockroachdb:master Oct 19, 2022

mgartner deleted the 90053-normalize-overflow branch October 20, 2022 14:36

rytaft mentioned this pull request Oct 27, 2022

sql: incorrectly folding interval + timetz constants #88128

Closed

mgartner mentioned this pull request Jan 25, 2024

opt: normalize comparison with addition/subtraction of TS and INTERVALs #118307

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

opt: fix normalization of comparisons with constants#90266

opt: fix normalization of comparisons with constants#90266
craig[bot] merged 2 commits intocockroachdb:masterfrom
mgartner:90053-normalize-overflow

mgartner commented Oct 19, 2022 •

edited

Loading

Uh oh!

cockroach-teamcity commented Oct 19, 2022

Uh oh!

mgartner commented Oct 19, 2022

Uh oh!

rytaft left a comment

Uh oh!

mgartner left a comment

Uh oh!

msirek left a comment

Uh oh!

rytaft left a comment

Uh oh!

mgartner commented Oct 19, 2022

Uh oh!

craig bot commented Oct 19, 2022

Uh oh!

blathers-crl bot commented Oct 19, 2022

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

Conversation

mgartner commented Oct 19, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

opt: fix normalization of comparisons with constants

opt: replace FoldBinaryCheckOverflow with FoldBinary

Uh oh!

cockroach-teamcity commented Oct 19, 2022

Uh oh!

mgartner commented Oct 19, 2022

Uh oh!

rytaft left a comment

Choose a reason for hiding this comment

Uh oh!

mgartner left a comment

Choose a reason for hiding this comment

Uh oh!

msirek left a comment

Choose a reason for hiding this comment

Uh oh!

rytaft left a comment

Choose a reason for hiding this comment

Uh oh!

mgartner commented Oct 19, 2022

Uh oh!

craig bot commented Oct 19, 2022

Uh oh!

blathers-crl bot commented Oct 19, 2022

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

mgartner commented Oct 19, 2022 •

edited

Loading