📢 To kick off the Vacuum Series, we look at PostgreSQL's MVCC model. This article ① explains how MVCC works with examples, then ② covers the problems this model can cause.
How MVCC Works
What Is MVCC?
MVCC is short for "Multi Version Concurrency Control". It is one of the essential DBMS features, describing whether a database can manage and serve multiple versions of data from the past to the present. In other words, it describes whether a user can get the exact data as of the moment their query started, even while the data keeps changing. Each DBMS implements it differently, but the goal is the same.
MVCC in PostgreSQL
As is well known, Oracle implements MVCC using a space called Undo. PostgreSQL, instead of using a space like Undo, implements its MVCC model in a somewhat crude and simple way, as shown below.
📌 How PostgreSQL implements MVCC
1. Both the previous version(s) and the current version of the data are kept inside the table.
2. Each record (row) carries 4 Byte of version information (XID) so its point in time can be identified.
3. MVCC is implemented by comparing the Transaction ID at execution time with the record's XID (XMIN).
XMIN / XMAX
Before looking at how MVCC works, let's look at XMIN and XMAX.
XMIN and XMAX exist on every record and are used to store XIDs. XMIN stores the XID that performed the Insert/Update, and XMAX stores the XID that performed the Delete/Update. When data is modified, they behave as follows.
- On Insert, the current XID is set in XMIN
- On Delete, the current XID is set in XMAX of the record being deleted
- On Update, the current XID is set in XMAX of the old record (same as Delete), the new record is inserted, and the XID of the Update is set in its XMIN
📌 A record whose XMAX is Null is the latest version. A record with XMAX set became an old version (deleted or updated) at that point in time.
💡 Different DBMSs use different terms, such as record, row and tuple, but they all mean the same thing. In this article and the rest of the Vacuum Series, we use record and row interchangeably.
PostgreSQL MVCC Example
With the example below, let's see how a page changes when DML runs, and how reading data works under PostgreSQL's MVCC model.
Changes Inside the Page
- At XID=999, [A,10] is inserted. The record's [XMIN, XMAX] is set to [999, Null]
- At XID=1000, [B,20] is inserted. The record's [XMIN, XMAX] is set to [1000, Null]
- Later, at XID=2001, [A,10] is updated to [A,20]. Inside the page, XMAX of the old record [A,10] is set to 2001, the XID of the Update, marking that record as an old version. Then the updated record [A,20] is inserted with XMIN set to 2001.
📌 In PostgreSQL, an Update of a record is internally performed as a delete mark (Delete) → insert of the new value (Insert).
How the Returned Data Changes with Query Time
The reason version information is kept per record in XMIN and XMAX is to extract data as of a specific point in time by comparing these values with the Transaction ID (XID) at query time.
For example, suppose a long-running Select SQL starts at XID=2000, and an Update (XID=2001) SQL starts at almost the same time. By the time the Select SQL actually reaches the records, the Update has already completed.
- The [A,10] record was inserted before the query time (XMIN=999) and is to be deleted in the future (XMAX=2001), so it is included in the result.
- The second record, [B,20], has never been changed (XMAX=Null) and was inserted (XMIN=1000) before the query start point of 2000, so it is included in the result.
- The last record, [A,20], was inserted after the query time (2000) (XMIN=2001), so it is not included.
Problems with This Model
PostgreSQL's MVCC model has the advantage of being relatively easy to implement through per-record XID comparison, but it has also caused a few critical problems.
The main problems, described below, are inefficient space usage and a shortage of Transaction IDs. To address them, PostgreSQL introduced concepts such as VM, Data Freezing and Age, and ultimately set out to solve this series of problems with Vacuum.
Both the previous version(s) and the current version of the data are kept inside the table. Each record (row) carries 4 Byte of version information (XID) so its point in time can be identified.
Problem 1. Inefficient Space Usage
- Tables with frequent Update and Delete must store every previous version of each row, which wastes space and can enlarge the scan range.
- Also, storing XIDs per record rather than per Block, as Oracle does, wastes space inside the page.
Problem 2. XID Shortage
- Another problem with a 4 Byte XID per record is that it can represent only about 4.3 billion Transactions.
- Because of this, the 4.3 billion XIDs are split into Newer/Older halves and used in a circular way (modulo arithmetic), and old XIDs must periodically be set to a special value (
Frozen XID) so they always read as the oldest data.
In the following articles, we cover XID, Age, Data Freezing and VM in turn, and then explain how Vacuum works.
Related articles
