Hello! Welcome to the final lesson in our module on columnar storage.
So far, we've explored the strengths of column-oriented databases for analytical (OLAP) workloads and delved into powerful compression techniques like RLE, dictionary encoding, and bit packing that thrive in this layout. We've established a clear dichotomy: row stores are great for transaction-heavy (OLTP) workloads, and column stores are great for analytical scans.
But what happens when an analytical query isn't just a simple aggregation on one column? What if it needs to access several columns to produce its result? This is where pure column stores can show a weakness.
Today's lesson bridges the gap between these two worlds. Your learning outcome is to describe the PAX hybrid storage model as a compromise between row and column stores. We'll see how PAX cleverly organizes data on disk to get many of the benefits of columnar storage while mitigating its primary drawback.
1. The Challenge: The Cost of Tuple Reconstruction
Pure column stores, also known as the Decomposition Storage Model (DSM), store each column in a separate file or set of blocks on disk. This is fantastic for queries that only need one or two columns. But when you need to reconstruct a full tuple (or even a partial one with several attributes), the database has to pull data from multiple, disparate locations.
To understand the performance implications of this, let's turn to an excellent technical blog post that breaks down the problem.
Columnar Storage - Paper Trail
The following article from 'The Paper Trail' blog clearly explains the drawbacks of pure columnar formats, particularly the cost of reassembling rows and the impact on CPU cache efficiency.
Please read the section titled 'The Cost of Columnar'. Focus on understanding why reassembling a row can be expensive and what 'in-memory spatial locality' means in this context.
As the article explains, the two main issues with tuple reconstruction in a pure column store are:
- Disk I/O: Reconstructing a row with five attributes could require seeks to five different files on disk, which is much slower than a single sequential read.
- CPU Cache Inefficiency: Even after the data is loaded into memory, the values for a single logical row (
(attr1, attr2, attr3, ...)) are scattered across different memory regions. Processing these tuples requires "pointer chasing" that is unfriendly to modern CPU caches, which are optimized for sequential data access.
This begs the question: can we get the scan and compression benefits of a column store while keeping the data for a single tuple physically closer together?
2. The Solution: Partition Attributes Across (PAX)
The answer is yes, and the most influential design to achieve this is PAX (Partition Attributes Across).
The core idea of PAX is simple but powerful: instead of organizing an entire table as a set of columns (pure DSM) or a set of rows (pure NSM), PAX organizes data columnarly within each data page.
Let's watch a detailed explanation from the CMU Advanced Databases course.
03 - Database Storage Models & Data Layout (CMU Advanced Databases / Spring 2023)
Professor Andy Pavlo explains the PAX model, contrasting it with pure row and column stores. He details its motivation and physical organization.
Watch the segment from 28:32 to 33:51. Pay close attention to the concept of a 'row group' and how attributes are partitioned vertically within it.
To summarize the video's key points:
- First, the table is horizontally partitioned into groups of rows. These are often called row groups or blocks.
- Then, within each row group, the data is vertically partitioned by column.
This creates a hybrid layout on the physical page. Instead of a mix of different attributes, the page contains contiguous "minipages," where each minipage holds all the values for a single attribute for the rows in that group.
This diagram provides a great visual comparison.
Diving deeper, the internal structure of a PAX page is highly organized.
By organizing data this way, PAX achieves an elegant compromise:
- Columnar Benefits Retained: When a query scans a single column (e.g.,
SUM(price)), the processor can rip through the corresponding minipage sequentially, enjoying excellent cache locality and benefiting from column-specific compression. - Tuple Reconstruction is Cheaper: When a query needs to reconstruct a tuple (e.g.,
SELECT name, price WHERE ...), all the necessary attributes (nameandprice) are located in different minipages on the same physical page. This vastly improves spatial locality compared to fetching them from separate files spread across a disk.
Test your understanding!
Consider a query SELECT col_B, col_C FROM table WHERE col_A > 100. Assume the table has 10 columns (A-J) and many rows, spanning many pages/files. Briefly describe the data access pattern (what is read from disk) for this query in:
- A pure row-store (NSM).
- A pure column-store (DSM).
- A PAX-based store.
Show answer
- NSM: The system must perform a full table scan. It reads every page of the table from disk. For each row, it checks
col_A, and if the predicate matches, it extractscol_Bandcol_C. A huge amount of unnecessary data (columns D-J) is read from disk and loaded into memory. - DSM: The system reads only the files/blocks for
col_A,col_B, andcol_C. It first scanscol_Ato find the row IDs that match the predicate. Then, using these row IDs, it fetches the corresponding values fromcol_Bandcol_C. This avoids reading columns D-J entirely, saving significant I/O. However, fetching data from three separate column files can involve multiple disk seeks and potentially random access patterns. - PAX: The system reads each row group (page/block) one by one. Within a row group, it first reads the
col_Aminipage to evaluate the predicate. For matching rows, it then reads the corresponding values from thecol_Bandcol_Cminipages within the same row group. This is more efficient than pure DSM because all necessary data for a set of rows is in the same physical block, improving cache locality. It is far more efficient than NSM because it avoids reading the minipages for columns D-J at all.
3. PAX in the Real World: Parquet and ORC
The PAX model isn't just an academic concept. It is the architectural foundation for the most widely used open-source columnar file formats in the data engineering world: Apache Parquet and Apache ORC.
When you hear about data lakes and systems like Spark, Presto, or DuckDB analyzing data on S3, they are almost always reading Parquet or ORC files. The concepts of row groups, column chunks (minipages), and page headers are all present in these formats, directly inheriting the design principles of PAX. This is a testament to the model's effectiveness in balancing scan performance with the practical need for tuple reconstruction.
4. A Broader View: Other Hybrid Models
While PAX represents a hybrid model within a storage page, other systems implement a hybrid approach at a higher level, combining entirely separate row-store and column-store components.
The following video segment introduces two such models: Fractured Mirrors and Delta Stores.
03 - Database Storage Models & Data Layout (CMU Advanced Databases / Spring 2023)
To provide a more complete picture of hybrid storage, this clip explains system-level hybrid models. Understanding these helps contrast them with the page-level hybrid approach of PAX.
Watch the segment from 55:08 to 1:04:42. Focus on the core difference between the two approaches: Fractured Mirrors maintains two full copies of the data, while Delta Store uses a small row-store for recent updates ('hot' data) and migrates older data to a large column-store ('cold' data).
These models are typically used to adapt a legacy row-store database for analytics or to handle mixed workloads where new data is updated frequently before becoming read-only. This contrasts with PAX, which is designed from the ground up as a single, unified format for analytical workloads.
Conclusion
In this lesson, we've seen how the PAX storage model provides an effective compromise between pure row and column stores, making it the dominant architecture for modern analytical database systems and file formats.
Key Takeaways:
- Pure column stores (DSM) excel at single-column scans but suffer from high tuple reconstruction costs due to poor spatial locality.
- PAX solves this by partitioning attributes vertically within a horizontal row group, creating columnar "minipages" inside a larger data page.
- This design provides the cache-friendly scan performance of a column store while keeping all attributes for a group of rows physically close, making tuple reconstruction much more efficient.
- The PAX model is the foundation for widely used real-world columnar formats like Apache Parquet and Apache ORC.
This lesson concludes our module on columnar storage. You now have a deep understanding of why column stores are so fast for analytics, how they use compression, and how the PAX layout provides a practical and performant physical storage model.
Preview of the Next Lesson
We've spent this module focusing on storage layouts that are highly optimized for fast reads (OLAP). In our next module, we will pivot to an entirely different class of storage structures designed for extremely fast writes: Log-Structured Merge-Trees (LSM-Trees). You will learn about their architecture and why they are the engine behind many modern NoSQL and "NewSQL" databases.