Catalog My learning Blog
Scalability Patterns: Load Balancing, Caching, Sharding · Phase 3 · Lesson 15 · 12 min read

Cross-Shard Queries, Joins and Transactions

On this page
  1. Learning Objective
  2. Concept Explanation
  3. Worked Example: Paginating Across Shards, and Two Ways to Move Money
  4. Real-World Examples
  5. Review Questions & Answers

Learning Objective

Explain why a query that does not include the shard key becomes a scatter-gather whose cost and latency scale with fleet size, describe the standard techniques for avoiding cross-shard joins, and evaluate two-phase commit against the saga pattern for operations that genuinely span shards.

Concept Explanation

Sharding buys write and storage scalability by giving up the thing a single database does best: combining arbitrary rows cheaply. Inside one database, a join is an optimized operation over data the engine can reach directly. Across shards, the engine cannot see the other side, so any operation touching multiple shards has to be assembled by a coordinator sending requests to each shard and merging what comes back. That is a scatter-gather, and its economics are uncomfortable: the work performed grows with the number of shards rather than the number of rows returned, so it gets more expensive every time you add capacity, and its latency is the maximum of all the shard latencies rather than the average, so it is governed by the slowest responder every single time.

The tail latency point deserves emphasis because it is unintuitive. If each shard responds within 10 milliseconds 99 percent of the time, a query touching one shard is fast almost always. A query touching 100 shards is fast only if all 100 are fast, and the probability of that is 0.99 raised to the 100th power, which is about 37 percent. So a p99 that looks excellent per shard produces a scatter-gather that exceeds its target nearly two thirds of the time. This is the mathematics behind the observation that tail latency dominates distributed systems, and it means the only reliable way to make scatter-gather fast is to not do it, or to bound it to a small known set of shards.

The techniques for avoiding cross-shard work are mostly about data modelling rather than query optimization. Co-location is the first and best: choose the shard key so that rows accessed together live together, which is what a compound key with a grouping prefix accomplishes. Denormalization is the second: copy the small amount of data needed from the other side into the row being read, accepting duplicated data and an update obligation in exchange for turning a join into a single read. Reference tables are the third: small, slowly-changing lookup data such as country codes, product categories, or currency rates can be replicated in full to every shard, so joining against them is always local. The fourth is to build a separate read model, fed by a change stream, that is organized by a different key and serves exactly the queries the primary shard key cannot, which is command query responsibility segregation applied for a very concrete reason. And the fifth is to accept that some queries do not belong in the transactional store at all, and route analytics and search to systems designed for them.

Transactions spanning shards are a harder problem than queries because atomicity cannot be faked. Two-phase commit provides genuine atomicity: a coordinator asks every participant to prepare, each participant durably promises it can commit and holds locks, and when all have agreed the coordinator tells everyone to commit. It is correct and it is the right answer when atomicity is genuinely required, but it is a blocking protocol. Participants hold locks from prepare until commit, so a slow or failed coordinator can leave rows locked indefinitely, and if the coordinator crashes after some participants have prepared, those participants cannot unilaterally decide what to do and are stuck. Throughput also suffers badly, since every participant is held for the duration of the slowest one.

The saga pattern trades atomicity for availability. A business operation is decomposed into a sequence of local transactions, each committed independently on its own shard, with a compensating action defined for each step that semantically undoes it if a later step fails. There is no global lock and no blocking, so throughput and availability are far better, but intermediate states are visible to other readers and compensation is a semantic reversal rather than a rollback: a refund is not the same as a payment never having happened. Sagas are the dominant pattern in practice for cross-service and cross-shard business operations, and the discipline they require is that every step must have a genuine compensating action, which is a design constraint on the business process itself, not just on the code. The best strategy of all remains the one from the previous lessons: choose a shard key that keeps the entities that must change together on the same shard, so that most operations need only a local transaction.

OperationCost on One ShardCost Across N ShardsStandard Avoidance
Point lookup by shard keyOne readUnchanged; routed directlyNothing needed
Query without the shard keyOne indexed scanN scans, latency of the slowestSecondary index or a read model keyed differently
Join between two tablesEngine-optimizedCoordinator fetches both sides and joins in memoryCo-locate by key, denormalize, or replicate reference data
Aggregate or countOne scanN partial aggregates plus a mergeMaintain a running counter, or precompute in a read model
Ordered paginationIndex scan with an offsetOver-fetch from every shard, merge, then truncateCursor pagination on a key that includes the shard
Atomic multi-row writeOne local transactionTwo-phase commit or a sagaCo-locate the entities that must change together

Worked Example: Paginating Across Shards, and Two Ways to Move Money

Cross-shard pagination is the operation that most often surprises people, because the naive implementation is not merely slow but wrong. The transfer example that follows contrasts the two ways to make a multi-shard write correct.

Code
# --- CROSS-SHARD PAGINATION: why OFFSET is broken, not just slow ---
# Goal: page 5 of tickets ordered by created_at, 20 per page, 64 shards.
#
# NAIVE (incorrect):
#   each shard: SELECT ... ORDER BY created_at LIMIT 20 OFFSET 80
#   The global rows 81-100 are NOT the union of each shard's rows 81-100.
#   A shard holding 500 of the 100 most recent rows contributes none of
#   its own rows 81-100 to the global top 100 at all. The result is a
#   plausible-looking page of the wrong rows.
#
# CORRECT but expensive:
#   each shard: SELECT ... ORDER BY created_at LIMIT 100   (offset+limit)
#   coordinator: merge 64 * 100 = 6,400 rows, sort, take rows 81-100.
#   Deep pages get quadratically worse: page 500 fetches 64 * 10,020 rows
#   to return 20. This is why "jump to page 500" does not exist in any
#   large sharded product.
#
# CORRECT and cheap: cursor pagination
#   cursor = (last_created_at, last_id)
#   each shard: SELECT ... WHERE (created_at, id) > cursor
#               ORDER BY created_at, id LIMIT 20
#   coordinator: merge 64 * 20 = 1,280 rows, take 20, emit a new cursor.
#   Constant cost per page regardless of depth. No page numbers, which
#   is the interface change the data model is forcing on the product.

# --- MOVING MONEY BETWEEN TWO ACCOUNTS ON DIFFERENT SHARDS ---

# Option A: two-phase commit. Truly atomic, and blocking.
coordinator.begin(txid)
  shard_A.prepare(txid, debit(acct_1, 100))    # locks acct_1, durably promises
  shard_B.prepare(txid, credit(acct_2, 100))   # locks acct_2, durably promises
  if both prepared:  coordinator.commit(txid)  # both apply
  else:              coordinator.abort(txid)   # both release
# Failure mode: coordinator dies after both prepare. Neither participant
# may decide alone. Both hold locks until an operator or a recovery
# process resolves the transaction. Throughput is capped by the slowest
# participant on every single transfer.

# Option B: saga. Never blocks, intermediate states are visible.
step 1  shard_A: debit(acct_1, 100), status=PENDING   # local txn, commits
        compensate: credit(acct_1, 100)
step 2  shard_B: credit(acct_2, 100)                  # local txn, commits
        compensate: debit(acct_2, 100)
step 3  shard_A: mark transfer COMPLETE               # local txn, commits
#
# If step 2 fails, run step 1's compensation. Between steps 1 and 2 the
# money is genuinely in neither account, and a balance query will see
# that. The business must define what it shows there: most real systems
# model it explicitly as "pending" rather than pretending it is atomic.
#
# Requirements sagas impose, all mandatory:
#   - every step idempotent (it WILL be retried)
#   - every step has a real compensating action (a refund, not a rollback)
#   - the saga state itself is durable, so a crashed orchestrator resumes

# Option C, and the reason the other two are rare: shard by customer, so
# both accounts of an intra-customer transfer are on the SAME shard and
# the whole thing is one ordinary local transaction.
A scatter-gather query fanning out to every shard with the coordinator waiting on the slowest responder, annotated with the tail latency arithmetic, alongside a two-phase commit holding locks across two shards and a saga committing local transactions in sequence with compensating actions.
A scatter-gather query fanning out to every shard with the coordinator waiting on the slowest responder, annotated with the tail latency arithmetic, alongside a two-phase commit holding locks across two shards and a saga committing local transactions in sequence with compensating actions.

Real-World Examples

  • Google published "The Tail at Scale" in Communications of the ACM in 2013, quantifying exactly the problem in this lesson: when a request fans out to many servers, the overall latency is governed by the slowest response, so a service whose individual servers have a good 99th percentile can still have a majority of fan-out requests exceed that percentile. The paper presented hedged requests and tied requests as mitigations, which are now standard techniques in systems that cannot avoid fan-out.
  • Vitess, the sharding layer originally built at YouTube to scale MySQL and now used by companies including Slack and GitHub, implements cross-shard queries by parsing the SQL, routing single-shard queries directly, and planning scatter-gather execution with an in-memory merge for the rest, while its documentation explicitly warns that cross-shard joins and deep ordered pagination are expensive and should be designed out through key choice. It is a production system whose public documentation is effectively a catalogue of the constraints described here.
Key TakeawaysIf a request fans out to every shard, its latency is the slowest shard, not the average one. With 100 shards each meeting a 10 millisecond target 99 percent of the time, only about 37 percent of fan-out requests meet that target, because 0.99 to the hundredth power is roughly 0.37. Adding shards makes this strictly worse, so a scatter-gather on a high-volume path is a scaling ceiling disguised as a working query.

Review Questions & Answers

Because offset is defined relative to a single ordered result set, and each shard applies it to its own local ordering rather than to the global one. Asking every shard for rows 81 through 100 of its own data and concatenating the results does not produce rows 81 through 100 of the combined ordering. A shard that happens to hold most of the globally newest rows contributes rows from deep in its own list, which are not in the global top 100 at all, while a shard with few recent rows contributes rows that should not appear either. The output is a set of real rows in a plausible order that is simply not the requested page, and nothing errors. The correct implementation requires each shard to return offset plus limit rows so the coordinator can merge and then apply the offset globally, which is correct but grows linearly with page depth, or cursor pagination, which is both correct and constant cost.

A fan-out request completes only when its slowest component completes, so the probability that the whole request is fast is the product of the probabilities that each component is fast. With per-shard 99th percentile latency of 10 milliseconds, one shard meets that bound 99 percent of the time, 10 shards all meet it about 90 percent of the time, and 100 shards all meet it only about 37 percent of the time. The implication is uncomfortable: adding shards to increase capacity makes every fan-out query slower in the tail, so the scaling action degrades the very queries most exposed to it. This is why fan-out must be bounded to a small known set of shards where possible, why hedged requests exist, sending a duplicate request to another replica after a short delay and taking whichever returns first, and ultimately why data modelling that avoids fan-out matters more than any optimization applied to it.

The deciding dimension is whether the business can tolerate an observable intermediate state. Two-phase commit is genuinely atomic, so no other reader ever sees a half-completed operation, and it pays for that with blocking: participants hold locks from prepare until commit, throughput is bounded by the slowest participant, and a coordinator failure between phases leaves participants unable to resolve on their own. A saga never blocks and never holds distributed locks, so it scales and stays available, but its steps commit independently, which means other readers can observe the state between them and failure is handled by semantic compensation rather than rollback. In practice most business processes already have an intermediate state, a payment is pending, an order is being fulfilled, a transfer is in flight, so making it explicit costs little and buys a great deal. Two-phase commit is reserved for the narrow set of operations where exposing that state is genuinely unacceptable, and even then the better answer is usually to co-locate the data so no distributed transaction is needed.

The first is denormalization: copy the handful of customer fields the report needs onto each order row, so the join disappears and each shard answers locally. The cost is duplicated data and the obligation to update every copy when a customer changes, which is acceptable for fields that rarely change and unacceptable for ones that do. The second is a replicated reference table: if the customer data is small and slowly changing, keep a full copy on every shard so the join is always local. The cost is the replication mechanism and the storage multiplied by shard count, which is fine for thousands of rows and not for millions. The third is to move the query out of the transactional store entirely, feeding a change stream into an analytical database or a read model organized for reporting. The cost is a pipeline to operate and eventual consistency, but it is usually the right answer for reporting specifically, because reporting queries have access patterns fundamentally different from the transactional ones the shard key was chosen to serve.