Spanner Schema Design and Query Performance

From Key-Value Store to Relational Database

To appreciate the significance of schema in Spanner, it's helpful to understand its evolution. As you know from your experience, many early large-scale storage systems (like Google's own Bigtable) were essentially key-value or "NoSQL" stores. While powerful, they often required application developers to manage data relationships and consistency manually, which can be complex and error-prone.

Spanner was intentionally evolved into a full-fledged relational database with a strong schema system and a SQL interface. This evolution was driven by the need to provide application developers with familiar, powerful tools like transactional consistency and a robust query language, while retaining massive horizontal scalability.

This commitment to the relational model means that the schema is not just metadata; it is the blueprint for how Spanner organizes, stores, and accesses data.

The Foundation: Primary Keys and Lexicographical Order

The most fundamental principle of Spanner's data layout is that rows within a table are stored lexicographically sorted by their primary key.

Imagine all the rows of a table laid out in a single, enormous sorted map. The key for each entry is the concatenation of its primary key columns. This ordering is the direct link between your logical schema and the physical data placement. Since, as we learned, a directory is a contiguous range of keys, this means a directory will contain rows whose primary keys are "close" to each other in this sorted order.

This has a critical performance implication: scanning a range of rows with nearby primary keys is extremely efficient, as it translates to a sequential read from storage.

This principle immediately suggests that if you want certain rows to be stored together, you should design their primary keys to have a common prefix. Spanner formalizes this concept with interleaved tables.

Interleaved Tables: Enforcing Co-location

An interleaved table is a child table whose rows are physically stored alongside the corresponding row of a parent table. This creates a parent-child hierarchy in your schema that directly translates to physical data co-location.

To achieve this, the primary key of the child table must start with the full primary key of the parent table.

Consider a classic Singers and Albums schema:

• Singers (SingerId, FirstName, LastName) with PRIMARY KEY (SingerId)
• Albums (SingerId, AlbumId, AlbumTitle) with PRIMARY KEY (SingerId, AlbumId)

By declaring Albums as interleaved in Singers, you instruct Spanner to store all albums for a given singer physically next to that singer's own row. The SingerId part of the key ensures all of a singer's data (their own row plus all their album rows) has a common key prefix and is therefore contiguous. This collection of a parent row and all its descendant rows is called a row tree.

The image below shows how rows for SingerId = 1 (the singer row, one album row, and two concert rows) are physically stored together, separate from the rows for SingerId = 2.

The primary benefit of this co-location is query performance. When you query for a singer and all of their albums, the join can be executed locally within a single data split (and thus on a single set of servers). This avoids the network latency and coordination overhead of a distributed join that would be required if the Singers and Albums data were in different splits.

The Impact on Query Execution

The performance benefits of a well-designed schema go beyond simple joins. Spanner's query processor is built to exploit the key structure defined by your schema.

1. Joins and Data Locality

As we've seen, interleaving is the most powerful tool for optimizing joins between parent-child tables. The "Spanner: Becoming a SQL System" paper notes that these joins are pushed down and executed locally (resource LINK, section 2), which is the key to their efficiency.

2. Query Range Extraction

When you issue a query with predicates on primary key columns, Spanner's query optimizer performs query range extraction. It analyzes the WHERE clause to calculate the minimal set of key ranges that must be scanned to satisfy the query.

For a table like Documents (ProjectId, DocumentPath, Timestamp), a query like:
WHERE ProjectId = 'P001' AND STARTS_WITH(DocumentPath, '/proposals')

...allows the optimizer to immediately route the query only to the shard(s) responsible for ProjectId = 'P001'. Then, within that shard, it can seek directly to keys starting with '/proposals', skipping all other documents for that project. This is vastly more efficient than a full table scan. Your choice of primary key columns and their order directly determines how effectively the optimizer can perform this extraction.

3. Secondary Indexes

Like any relational database, Spanner uses secondary indexes to speed up lookups on non-primary-key columns. Crucially, Spanner offers two types of indexes that mirror the locality principles we've discussed:

• Non-interleaved indexes (default): The index data is stored as a global table. This is analogous to a standard index in a traditional database. It's great for lookups where you don't know the parent key (e.g., finding a user by their email address across the entire user base). However, using the index to find a row and then fetching that row's data often involves a distributed read.
• Interleaved indexes: The index data is stored interleaved with the base table's data. This is perfect for searches scoped within a parent entity (e.g., finding all posts by a specific user with a certain tag). The index lookup and the data fetch happen within the same row tree, ensuring locality and high performance.

Furthermore, you can use the STORING clause to include additional columns' data directly in the index itself, creating a covering index. If a query can be satisfied entirely from the index, Spanner avoids reading the base table at all, yielding another significant performance gain.

Schema Design Anti-Patterns

Given the direct link between primary keys and physical layout, poor key choices can lead to severe performance problems. The most common issue is creating a hotspot, where a large volume of reads or writes is directed to a single split, overwhelming its resources.

Two common anti-patterns to avoid are:

1. Timestamp-ordered Keys: If you use a timestamp as the leading part of your primary key, every new insert will go to the very end of your key space. All write traffic will be concentrated on the single split that owns the "end" of the table.
2. Sequentially Increasing Keys: Using a traditional auto-incrementing integer as a primary key has the exact same effect. New rows get sequential IDs (e.g., 101, 102, 103) and are all written to the same spot.

For a system like Spanner that is designed for massive parallelism, concentrating work on a single server is the worst thing you can do.

Solutions:

• Instead of a simple sequence, use a bit-reversed sequence.
• Use a UUID, but be careful to choose a version (like v4) that generates random bits in the most significant part of the key, not one that encodes a timestamp there.
• For cross-table timestamp ordering, shard writes across a fixed number of logical shards by prepending a ShardId to the key.

Your experience with sharding should make the reasoning here intuitive; these patterns violate the fundamental principle of distributing load across shards.

Conclusion

In this lesson, we have connected the logical world of schema design to the physical reality of data layout in Spanner. We've seen that your schema is the most potent tool you have for influencing performance and scalability.

The key takeaways are:

• Schema dictates locality: Spanner stores rows lexicographically by primary key. This fundamental rule means your choice of key columns and their order determines which rows are physically stored together.
• Interleaved tables enforce co-location: This feature allows you to explicitly define parent-child relationships that translate directly into physical proximity, making joins and transactions within a row tree highly efficient.
• Query performance depends on key structure: The query optimizer leverages the key structure for efficient routing and data access via range extraction. Secondary index design (interleaved vs. non-interleaved) further refines this control.
• Hotspots are a critical threat: Schema designs that create sequential keys (e.g., using timestamps or simple auto-incrementing integers) will lead to performance bottlenecks by concentrating traffic on a single data split.

You can now describe how to design a Spanner schema that not only models data correctly but also ensures it is stored for optimal performance at scale.

In our next lesson, we will broaden our perspective to: Compare Bigtable and Spanner in terms of their data models, consistency guarantees, and primary use cases. This will highlight the trade-offs between Spanner's strongly consistent, relational model and the more flexible, eventually consistent model of a NoSQL database like Bigtable, providing a clearer picture of when to use each system.