opt: Locality optimized search

[nvanbenschoten]

In #41535, we introduced the concept of partitioned uniqueness checks, coupled with partitioned unique indexes. This ensures that all data for a given row in a REGIONAL table is stored in a single region while continuing to allow the use of UNIQUE constraints.

Partitioned unique indexes have the interesting property that if a value is found in one partition of the index, it is known that no others exist in any other partition. This presents an opportunity to optimize lookups on these indexes. By default, we would expect that lookups would have to fanout to each partition when searching for a match to the unique column(s) – this is how hash-sharded index lookups work. But this naive fanout doesn't acknowledge the disparity of lookup cost between different partitions of the index. In the case of REGIONAL tables, one partition is local and all others are across a WAN hop. It also doesn't acknowledge that given a workload with some degree of access locality, the partition stored in the local region is more likely to hold the matching row than any other partition.

For these reasons, we would be well served to optimize these lookups for cases where the matching row is in the local partition. So instead of fanning out to all partitions immediately, we should search for the row in the local partition first, and only fan out to all other partitions if that initial lookup missed.

Example:

Picture a schema that looks like the following, using a partitioned unique index.

CREATE TABLE data (
    _region STRING NOT NULL CHECK (_region IN ('us-east', 'us-west', 'eu-west', 'asia-south')),
    id UUID UNIQUE NOT NULL,
    PRIMARY KEY (_region, id)
)

This would map to a single index on (_region, id), because a separate index on id would not be necessary with partitioned uniqueness checks.

The question becomes: "how do we execute the following query from a us-east gateway"?

SELECT * FROM data WHERE id = '0123-4567-89ab-cdef'

The naive approach would be to evaluate it like:

-- query all four regions in parallel
SELECT * FROM data WHERE id = '0123-4567-89ab-cdef' AND _region IN ('us-east', 'us-west', 'eu-west', 'asia-south')

A better approach using a locality optimized search algorithm would evaluate it like:

--- query the local region first
SELECT * FROM data WHERE id = '0123-4567-89ab-cdef' AND _region = 'us-east'
--- if this returns a row, return that single row and short circuit
--- if not, proceed with the following query of the remaining three regions
SELECT * FROM data WHERE id = '0123-4567-89ab-cdef' AND _region IN ('us-west', 'eu-west', 'asia-south')

Extension: Stale Read Hints

The approach listed above is a huge improvement. It's optimal for a local region search hit and correct for a remote region search hit or a miss. However, we can do better for remote region search hits by trying to avoid immediately fanning out to all remote regions on a local search miss. In REGIONAL tables, we expect that each region will have at least a non-voting replica of all data. That means that each region has fast access to a stale copy of the entire dataset. We can use this stale data as a hint for where to look if a row is not in the local region. Note that because this is stale, we still need a fallback plan in case the row has been "re-homed" recently.

Using this approach, the locality optimized search algorithm would become:

--- query the local region first
SELECT * FROM data WHERE id = '0123-4567-89ab-cdef' AND _region = 'us-east'
--- if this returns a row, return that single row and short circuit
--- if not, perform a stale read on the local copy of this data to locate the expected home region
SELECT * FROM data AS OF SYSTEM TIME follower_read_timestamp() WHERE id = '0123-4567-89ab-cdef' AND _region IN ('us-west', 'eu-west', 'asia-south')
--- if this returns a row, query only that remote region next
--- otherwise, perform the same fanout query transactionally and return
SELECT * FROM data WHERE id = '0123-4567-89ab-cdef' AND _region = 'us-west'
--- if this returns a row, return that single row and short circuit
--- if not, proceed with the following query of the remaining two regions
SELECT * FROM data WHERE id = '0123-4567-89ab-cdef' AND _region IN ('eu-west', 'asia-south')

This extension draws some parallels to the asynchronously updated "Lookup Master" index present in SLOG. With the proposed approach here, we avoid the need for a new index maintained on the side in a specialized manner at the expense of a local fanout during the stale lookup. That seems like a very reasonable trade-off.

Extension: Ignore Empty Regions

With the current proposal, adding a new region alternative to a table (broadening the CHECK constraint) immediately increases the fan-out factor of queries that miss the current region. This is mildly undesirable because users might want to add a new region to a database for replication purposes without homing any data in that region, at least for some tables.

To alleviate this problem, we could maintain some form of consistent table statistics (probably on the schema object itself because existing table stats are stale and therefore unsuitable) denoting which regions are empty and can be ignored for the purposes of queries to the table. This marker would need to be updated on the first time that a row is inserted into the empty region to instruct queries to begin searching in it.

This would allow users to more effectively "pay for what they use". They would avoid searching in regions that don't contain rows. The most important instance of this is that when all rows are homed in a single region and a query hits a gateway in that region, there would be no remote fan out at all.

Epic CRDB-2528

[nvanbenschoten]

One thing that I didn't mention above but that deserves a callout here is that we'll want this search behavior to apply even when the lookup is only a part of a larger query plan. For instance, the initial row scan of a DELETE statement (e.g. DELETE FROM data WHERE id = '0123-4567-89ab-cdef') or an UPDATE statement (e.g. UPDATE data SET ... WHERE id = '0123-4567-89ab-cdef') should benefit from this optimization as well. This will ensure that these operations are local if the row they reference is homed in the gateway's region.

Given the design of the SQL optimizer, I expect that we'll get this for free, but we should make sure to keep this in mind when building this out.

[nvanbenschoten]

Two other notes:

• this lookup approach should be used for foreign key checks. As in the previous comment, I expect that we'll get this for free now that fk checks have been pulled into the optimizer, but we should ensure that.
• this lookup approach should apply to other forms of point lookups. For instance, it should apply to multi-point lookups like SELECT * FROM data WHERE id IN ('0123-4567-89ab-cdef', '1123-4567-89ab-cdef', '2123-4567-89ab-cdef'). I'm less confident that this will come for free without any additional work. If this needs more then it can be viewed as an extension.

[awoods187]

Can we close this now cc @rytaft @ajstorm ?

[rytaft]

Not yet -- we still need to support locality optimized inner, left and semi lookup joins (currently only anti is supported), and we need to support locality optimized scans with more than a single row.

[nvanbenschoten]

If we do, let's make sure we open issues for any extensions that we still may want to do in the future. For instance, we'll eventually want to support this for multi-point reads (e.g. WHERE id IN (...)). Anything other query plans? Also, I think the "Extension: Stale Read Hints" part is very cool and worthy of its own issue.

[awoods187]

I'm a plus one to breaking this up into smaller issues. It will also make it easier to track progress internally.

[ajstorm]

Splitting it up works for me too. It should make it easier to track that way.

…

On Wed, May 5, 2021 at 10:17 AM Andy Woods ***@***.***> wrote: I'm a plus one to breaking this up into smaller issues. It will also make it easier to track progress internally. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#55185 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AEMXVOTISHFS42Q7ATDCPO3TMFHRHANCNFSM4SCCH37A> .

[rytaft]

Done. Opened #64862, #64870, #64872, and #64874, so I'll close this now.