RFC: optimize join & dml routing for reference tables

[maxenglander]

Introduction

The goal of this RFC is to make reference tables more useful, and to find a solution for some of its current limitations. This RFC is mainly motivated by #11863. However, depending on if/how we solve the problem, it may have a broader impact.

Reference tables are intended to be helpful in situations like:

• You have an unsharded table, like commerce.products.
• You have a sharded table, like customer.customers.
• You sometimes want to be able to join customers to products.
• This query can be very inefficient because of the cross-keyspace join.

Reference tables are designed to solve this by letting you:

• First materialize the unsharded table products table into each shard of the customer keyspace where customers lives.
• Flag the materialized table as being of type reference in the customers VSchema.
• From there, VTGate will route to a shard-local copy of products whenever it is joined to customers.

Problem statement

There are limitations on how helpful VTGate will be with routing.

Let's say you want to have products table have the same name in both the unsharded and sharded keyspace. And then you want to issue keyspace-unqualified queries like this:

INSERT INTO `products` ...
SELECT * FROM `customers` JOIN `products` ON ...

These queries won't work. They will produce this error: https://github.com/vitessio/vitess/blob/4ff02c0f7af35a520bfc90d32e77fc13810dfdd9/go/vt/vtgate/vindexes/vschema.go#L566

Additionally, when the queries are keyspace-qualified, Vitess will make sub-optimal routing decisions:

SELECT * FROM `commerce`.`customers` JOIN `customer`.`products` ON ...

Even though Vitess has all the information it needs to route the entire query to customer, it will route it to both keyspaces.

Use cases

Just to show that this isn't a contrived problem, here is a use case that describes the situation of a customer of PlanetScale:

1. They have a Java application using Spring and Hibernate.
2. Their development and staging environments use an unsharded single keyspace.
3. In production they have mix of unsharded keyspace and sharded keyspace.
4. They want performance to be fast, so they materialize tables from the unsharded keyspace to reference tables in the sharded keyspace.
5. They need writes to be sent to the unsharded keyspace, and joins in the sharded keyspace to use the reference tables.
6. They have a limited ability to make their code aware of this setup; having separate Hibernate/JPA entities for unsharded source table and the sharded reference table, and re-writing their code to use these two entities, is prohibitively difficult for them.
7. Even if it were an option for them, it would not be an attractive one because of the added complexity and because it could create separate code paths for production vs. other environments.

Historical Support

It used to be possible to route queries to either the source table or reference table.

• Here is a YouTube demo by Sougou showing how to do this.
• It looks like this feature was introduced here.
• It looks like it was reverted here due to concerns that this feature would not play nicely with planned optimizer improvements.

I think (but am not 100% sure) that "table equivalence" was introduced to support the kind of unqualified routing this RFC is proposing. It's not clear whether table equivalence was designed to allow admins to have reference tables with identical names as the source table, but, in any case, this feature would satisfy the end-goal: provide clients a way to interact with a single, keyspace-unqualified table identifier that maps to either source or reference tables.

Table equivalence does not currently work.

Current Support

• VTGate will route requests for reference tables to the shard-local copy when joined to other tables in the same keyspace, as long as the reference table is qualified e.g. with USE [sharded_ks] or [globally_unique_sharded_table] JOIN [sharded_ks].[reference_table].
• Routing rules can be used to always route requests for a table name to a particular name. However this will prevent INSERT into the source table, unless the routing rules are qualified with @rdonly or @replica.

New Support

Give Vitess users a way to:

• Always send writes to a reference table back to the materialization source.
• Keep joins of reference tables within the keyspace of the other expression in the JOIN.
• Add an option to Materialize to automatically enrich VSchema or Routing rules (depending on which option is adopted).

Proposal

Options

Option 1: expand reference table metadata

• Add new VSchema options to inform VTGate where reference tables are materialized from, e.g.:

  {
    "sharded": true,
    "tables": {
      "products": {
        "type": "reference",
        "source": "unsharded_ks.products"
      }
    }
  }

• For simplicity's sake, require that the referenced table be defined in the VSchema of reference.keyspace, and that it is not a reference table or sequence.
• We can expand the internal structs that we use to model tables to include ReferencedBy []*Table and ReferenceTo *Table, and propagate this information to other internal structure as needed https://github.com/vitessio/vitess/blob/4ff02c0f7af35a520bfc90d32e77fc13810dfdd9/go/vt/vtgate/vindexes/vschema.go#L89-L100
• During table lookup, when we resolve a query for an unqualified table, if all matches are either references to or from each other, return the source of all references, otherwise return the usual error: https://github.com/vitessio/vitess/blob/4ff02c0f7af35a520bfc90d32e77fc13810dfdd9/go/vt/vtgate/vindexes/vschema.go#L566
• During routing, when we merge routes, check to see if the reference table we're trying to join with references (or is referenced by) an identically-named table residing in keyspace of the join expression: https://github.com/vitessio/vitess/blob/22067c7a4e334a7e90850a2119135e6b1ae23279/go/vt/vtgate/planbuilder/operators/route_planning.go#L489-L507
• Always route unqualified DML for a reference table to the keyspace of its source table.
• Add an option to Materialize to automatically enrich VSchema with Reference table and Source.
  • Do this in a way so that the new routing behaviors are enabled only when lag between source and reference are low enough.
  • Can do this manually with a command e.g. MaterializeReferenceTable Cutover.
  • Can do this automatically with vtorc monitoring.
• Add a comment directive to give users more fine-grained control of the new behavior.
  • For example, maybe users will want a way to override the optimal join behavior, e.g. if the user needs to sacrifice performance for the sake of correctness (think: materialization lag).

Option 2: make "table equivalence" work again

Table equivalence doesn't work, but if it did then you could define routing rules like this (example taken from docs):

{"rules": [
  {
    "from_table": "product",
    "to_tables": ["lookup.product", "user.uproduct"]
  }
]}

With these routing rules in place, clients can interact with a single logical table, and VTGate will route queries for that table to the appropriate keyspace/shard.

There are probably a couple different ways we could implement this, but a reasonable approach would be to follow the path of https://github.com/vitessio/vitess/pull/4833 in a way that plays nicely with the Gen4 planner.

Add an option to Materialize to automatically enrich VSchema with Reference table and to add routing equivalence rules.

Option 3: read/write routing rules

We could instruct VTGate to route unqualified queries to one keyspace or another based on the type of statement, e.g.:

{"rules": [
  {
    "from_table": "products",
    "to_tables": ["unsharded_ks.products"],
    "commands": ["DELETE", "INSERT", "UPDATE"]
  },
  {
    "from_table": "products",
    "to_tables": ["sharded_ks.products"],
    "commands": ["SELECT"]
  },
]}

Add an option to Materialize to automatically enrich VSchema with Reference table and (maybe?) add routing rules.

Recommendation

I recommend that we:

1. Do option 1 to expand reference table metadata.
2. Remove documentation for "table equivalence".

Reasoning:

• I think option 1 is the least amount of work compared to the others, based on ✨ feelings ✨ and poking around the code.
  • Require the least amount of internal API changes.
  • Fewer edge cases to think about.
  • Fewer interactions between different Vitess layers.
• While less powerful than the other options, I think it is likely to make reference tables more easily usable and help satisfy common use cases out-of-the-box.

Decision

I like the RAPID model for decision making. Not sure who at Vitess would have the final decision on this RFC.

Recommend: @maxenglander Agree: @aquarapid Perform: @maxenglander Input: @harshit-gangal @systay @deepthi @rohit-nayak-ps community Decide: @harshit-gangal "Let us go for Option 1"

Tasks

Propose tackling this RFC in separate tasks (PRs):

• [x] Support global routing & dml redirection for reference tables (#11875).
• [ ] Expand global routing & dml routing to work in subqueries.
• [x] Let reference tables specify unqualified sources.
• [ ] Manage VSchema reference metadata from materialization workflows.
• [ ] Add comment directive to give users more control over reference table routing behavior.

[deepthi]

I like the proposal. We'll let @harshit-gangal and @systay chime in with any concerns and then we can make a decision on the path forward.

[deepthi]

Separately, I don't know if table equivalence was ever intended to work if using the same table name for the reference table as its source. At least the example in the docs uses a different name uproduct in the sharded keyspace. But if this is the case we need to document it as a known limitation.

[maxenglander]

@deepthi fair enough I'll update my comments about table equivalence to reflect. However I think table equivalence in the example in the docs still satisfies the goal of the RFC is the same: the end user wants to query one logical table for both reads and writes, and have the query get routed appropriately.

[harshit-gangal]

Thank you @maxenglander for writing an elaborative RFC. Let us go for Option 1, the reason I could think of:

1. There would not be any conflicting routing rules. Vitess planner can continue to apply the routing rules based on the table selected in the query.
2. Reference table type seems to be the best table type where this feature becomes usable.

Few things I would like to point out.

"products": {
  "type": "reference",
  "reference": {
    "keyspace": "unsharded_ks",
    "table": "products"
  }
}

type reference and then json property as reference might create confusion. Also, we can mode like

"products": {
  "type": "reference",
  "refer": "unsharded_ks.products", 
}

easier to read, refer can also point to the unqualified table, which can follow the global routing logic.

The code in the RFC regarding the join merge is v3 code, regarding the modification in Gen4 planner. The changes need to be carried out here: https://github.com/vitessio/vitess/blob/22067c7a4e334a7e90850a2119135e6b1ae23279/go/vt/vtgate/planbuilder/operators/route_planning.go#L489-L507

[maxenglander]

Thanks for the guidance @deepthi and @harshit-gangal.

I'm going to start working on option 1.

[maxenglander]

@harshit-gangal

refer can also point to the unqualified table, which can follow the global routing logic.

Is it OK with you if I don't support that initially? Maybe that can be an iteration for the future?

[harshit-gangal]

This can be added next after the PR or I can push a commit on the same PR.

[deepthi]

If we are debating names, I'd like to suggest source instead of refer 😄 Properties should be nouns, not verbs.

[harshit-gangal]

One more thing we should also talk about in the RFC is the automation of updating the Vschema when a materialized workflow is created. We already have similar automation for MoveTables, CreateLookupVindex, etc.

[maxenglander]

@harshit-gangal

We already have similar automation for MoveTables, CreateLookupVindex, etc.

Oh that's cool, didn't know that. Will add something to the RFC about that.

[maxenglander]

@harshit-gangal

One more thing we should also talk about in the RFC is the automation of updating the Vschema when a materialized workflow is created.

Add notes in RFC about this. For option 1 I added:

Add an option to Materialize to automatically enrich VSchema with Reference table and Source.

[rohit-nayak-ps]

We need to wait till we reach a low replication lag before we can route the reference table to the materialized keyspace in the VSchema. Otherwise we will be querying inconsistent or partially copied tables. In MoveTables and Reshard cutover is manually done by doing a TrafficSwitch.

Materialize currently doesn't have this concept. You will have to manually check the lag using Workflow Show and update the VSchema once we are in sync with the source table.

One option is to

• Add a new vtctl command, like MaterializeReferenceTable.
• Start the workflow MaterializeReferenceTable -source commerce -table product <target_keyspace>.<workflow_name> Create This will act like a helper: we internally use Materialize and setup the correct materialize spec..
• Then we can cutover (update the vschema as specified above):
  • manually MaterializeReferenceTable <target_keyspace>.<workflow_name> Cutover OR
  • automatically with additional functionality in vtorc to monitor the lag and do the cutover

[maxenglander]

Thanks @rohit-nayak-ps I'll incorporate your notes in the RFC.

[maxenglander]

After feedback from @harshit-gangal and @systay in #11875 am amending the proposal slightly.

Initially RFC intended to route joins to reference tables to the optimal keyspace only when the reference table is unqualified, e.g.:

SELECT ks2.[table] JOIN [reference_table]

This is now changed to also optimally route joins to qualified reference tables:

SELECT ks1.[global_table] JOIN ks2.[reference_table]

The query will route [reference_table] to ks1 if there is an identically named table in k1 that references ks2.[reference_table].

Added a task to add a comment directive so users can override this behavior for specific queries, e.g. for queries that need to prioritize data correctness over performance (think: materialization lag).

[maxenglander]

Some more adjustments based on feedback:

• Send INSERT/DELETE/UPDATE back to source table, even if the reference table was qualified in the query.
• Don't limit the optimization to identically named tables; also optimize references to differently named tables.
• In addition to joins, do this for subqueries.

[maxenglander]

I won't be able to work on this anymore, un-assigning myself.