opt: extend SplitScanIntoUnionScans to handle longer keys by DrewKimball · Pull Request #58085 · cockroachdb/cockroach

DrewKimball · 2020-12-18T23:31:40Z

Previously, SplitScanIntoUnionScans only handled Scan constraints
where all the start and end keys of the spans were of the exact same
length keyLength, and the first keyLength columns of the index
formed a prefix for the limit ordering columns. The following is an
example of a case that can be handled under these conditions:

/1/2/3: [/US_WEST/0 - /US_WEST/1]
=>
/1/2/3: [/US_WEST/0 - /US_WEST/0], [/US_WEST/1 - /US_WEST/1]
keyLength: 2
limit ordering: +3

However, a case like this one could not be handled, even though
the transformation shown is a valid (and desirable) one:

/1/2/3: [/US_WEST/0/postfix - /US_WEST/1]
=>
/1/2/3: [/US_WEST/0/postfix - /US_WEST/0], [/US_WEST/1 - /US_WEST/1]
keyLength: -
limit ordering: +3

This patch extends SplitScanIntoUnionScans to handle cases like the
above. This is accomplished by modifying the keyCount() and span.split()
code to require a prefix length as input. Examples:

[/ASIA/0/postfix - /ASIA/4].keyCount(prefixLength=1) = 1
[/ASIA/0/postfix - /ASIA/4].keyCount(prefixLength=2) = 5
[/ASIA/0/postfix - /ASIA/4].keyCount(prefixLength=3) = undefined

In this case, the prefix length used is the number of index columns that
precede the limit ordering columns (which must either be in order or in
reverse order):

index: /1/2/-3/4
limit ordering: /3/-4
prefix length: 2

In addition, SplitScanIntoUnionScans can now support cases where one span
from the Scan's constraint can be split and used to generate limited Scans,
but the other cannot.

Fixes #55156

Release note: None

cockroach-teamcity · 2020-12-18T23:31:46Z

This change is

rytaft

Welcome back, @DrewKimball!

This is great!

In the PR/commit message, you say that the following transformation is valid:

/1/2/3: [/US_WEST/0/postfix - /US_WEST/1]
=>
/1/2/3: [/US_WEST/0/postfix - /US_WEST/0], [/US_WEST/1/postfix - /US_WEST/1]

I'm not sure that's technically correct, since the first constraint contains more keys than the second one.

But looking at the code and comments, it looks like you would actually perform this transformation:

/1/2/3: [/US_WEST/0/postfix - /US_WEST/1]
=>
/1/2/3: [/US_WEST/0/postfix - /US_WEST/0], [/US_WEST/1 - /US_WEST/1]

So maybe you just need to update the PR/commit message?

Reviewed 7 of 7 files at r1.
Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @DrewKimball)

pkg/sql/opt/constraint/span.go, line 335 at r1 (raw file):

// removed:
//
//    ['ASIA'/1 - /'ASIA'/2]/KeyCount(keyCtx, length=2) => 2, true

[nit] /KeyCount -> .KeyCount

pkg/sql/opt/xform/limit_funcs.go, line 162 at r1 (raw file):

// SplitScanIntoUnionScans returns a Union of Scan operators with hard limits
// that each Scan over a single key from the original scan's constraints. This

[nit] each Scan -> each scan ... original scan's -> original Scan's

DrewKimball

Thanks @rytaft, it's good to be (sort of) back. And you're right, I'll change the commit message.

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

pkg/sql/opt/constraint/span.go, line 335 at r1 (raw file):

Previously, rytaft (Rebecca Taft) wrote…

[nit] /KeyCount -> .KeyCount

Done.

pkg/sql/opt/xform/limit_funcs.go, line 162 at r1 (raw file):

Previously, rytaft (Rebecca Taft) wrote…

[nit] each Scan -> each scan ... original scan's -> original Scan's

Done.

DrewKimball · 2020-12-22T10:49:56Z

TFTR!

rytaft

[super nit] in the commit/PR message you're using +3 for the ordering at the top, and /3 for the ordering further down

Also, don't forget to update the PR message to include the fixes you made to the commit message!

Reviewed 2 of 2 files at r2.
Reviewable status: complete! 1 of 0 LGTMs obtained

RaduBerinde

I tried the example in #55156 with this change, but I see no change. Here's the execbuilder test I used: https://gist.github.com/RaduBerinde/0a5286cc3352944726ee588ba7650fc5

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale)

RaduBerinde

In this case, we don't even need to split any of the spans.. We just need to separate them in their own scans, so that each can be limited.

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale)

DrewKimball · 2020-12-24T22:01:08Z

@RaduBerinde that's because the logic at line 233 in limit_funcs prevents the plan from being generated when the new plan isn't expected to decrease the number of rows scanned by a decent margin. Do you think we should be generating the plan in this case?

If you just want to see the plan being generated from those constraints, you can just increase the rowcount of the table.

RaduBerinde · 2020-12-26T19:14:08Z

Ah, that's great! Could you add an execbuilder or xform test with the case from the issue? You can inject stats as needed.

blathers-crl · 2020-12-26T20:35:24Z

Thank you for updating your pull request.

My owl senses detect your PR is good for review. Please keep an eye out for any test failures in CI.

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

DrewKimball · 2020-12-28T21:26:06Z

@RaduBerinde any chance you could bors this? I'm just an external contributor right now:)

RaduBerinde

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

pkg/sql/opt/exec/execbuilder/testdata/limit, line 393 at r3 (raw file):

# Expect a scan over each shard.
query T
EXPLAIN (OPT, VERBOSE)

[nit] Could you make this a regular EXPLAIN? (the tests are meant to cover what the execbuilder does as well) It doesn't have to be verbose, we're just looking for some unions.

Previously, `SplitScanIntoUnionScans` only handled Scan constraints where all the start and end keys of the spans were of the exact same length `keyLength`, and the first `keyLength` columns of the index formed a prefix for the limit ordering columns. The following is an example of a case that can be handled under these conditions: ``` /1/2/3: [/US_WEST/0 - /US_WEST/1] => /1/2/3: [/US_WEST/0 - /US_WEST/0], [/US_WEST/1 - /US_WEST/1] keyLength: 2 limit ordering: +3 ``` However, a case like this one could not be handled, even though the transformation shown is a valid (and desirable) one: ``` /1/2/3: [/US_WEST/0/postfix - /US_WEST/1] => /1/2/3: [/US_WEST/0/postfix - /US_WEST/0], [/US_WEST/1 - /US_WEST/1] keyLength: - limit ordering: +3 ``` This patch extends `SplitScanIntoUnionScans` to handle cases like the above. This is accomplished by modifying the `keyCount()` and `span.split()` code to require a prefix length as input. Examples: ``` [/ASIA/0/postfix - /ASIA/4].keyCount(prefixLength=1) = 1 [/ASIA/0/postfix - /ASIA/4].keyCount(prefixLength=2) = 5 [/ASIA/0/postfix - /ASIA/4].keyCount(prefixLength=3) = undefined ``` In this case, the prefix length used is the number of index columns that precede the limit ordering columns (which must either be in order or in reverse order): ``` index: /1/2/-3/4 limit ordering: /3/-4 prefix length: 2 ``` In addition, `SplitScanIntoUnionScans` can now support cases where one span from the Scan's constraint can be split and used to generate limited Scans, but the other cannot. Fixes cockroachdb#55156 Release note: None

DrewKimball · 2020-12-28T23:02:45Z

Done.

RaduBerinde · 2020-12-29T00:42:46Z

Thanks!

bors r+

craig · 2020-12-29T01:25:03Z

Build succeeded:

GitHub CI (Cockroach)

DrewKimball requested a review from a team as a code owner December 18, 2020 23:31

rytaft approved these changes Dec 21, 2020

View reviewed changes

DrewKimball force-pushed the split_scan branch from 44da2a0 to c91cf80 Compare December 22, 2020 03:46

DrewKimball commented Dec 22, 2020

View reviewed changes

DrewKimball force-pushed the split_scan branch 2 times, most recently from d3325ff to e28b372 Compare December 22, 2020 09:09

rytaft approved these changes Dec 22, 2020

View reviewed changes

DrewKimball force-pushed the split_scan branch from e28b372 to ccfb151 Compare December 22, 2020 20:45

RaduBerinde approved these changes Dec 24, 2020

View reviewed changes

DrewKimball force-pushed the split_scan branch from ccfb151 to 2795425 Compare December 26, 2020 20:35

blathers-crl bot added the O-community Originated from the community label Dec 26, 2020

RaduBerinde reviewed Dec 28, 2020

View reviewed changes

DrewKimball force-pushed the split_scan branch from 2795425 to c8152db Compare December 28, 2020 23:02

craig bot merged commit 6f63d85 into cockroachdb:master Dec 29, 2020

DrewKimball deleted the split_scan branch December 29, 2020 01:44

Conversation

DrewKimball commented Dec 18, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

cockroach-teamcity commented Dec 18, 2020

Uh oh!

rytaft left a comment

Choose a reason for hiding this comment

Uh oh!

DrewKimball left a comment

Choose a reason for hiding this comment

Uh oh!

DrewKimball commented Dec 22, 2020

Uh oh!

rytaft left a comment

Choose a reason for hiding this comment

Uh oh!

RaduBerinde left a comment

Choose a reason for hiding this comment

Uh oh!

RaduBerinde left a comment

Choose a reason for hiding this comment

Uh oh!

DrewKimball commented Dec 24, 2020

Uh oh!

RaduBerinde commented Dec 26, 2020

Uh oh!

blathers-crl bot commented Dec 26, 2020

Uh oh!

DrewKimball commented Dec 28, 2020

Uh oh!

RaduBerinde left a comment

Choose a reason for hiding this comment

Uh oh!

DrewKimball commented Dec 28, 2020

Uh oh!

RaduBerinde commented Dec 29, 2020

Uh oh!

craig bot commented Dec 29, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

DrewKimball commented Dec 18, 2020 •

edited

Loading