Introduction
The PostgreSQL HOT Series walks through how HOT (Heap Only Tuple) Update works, with the ultimate goal of establishing approaches to performance optimization and monitoring.
To get there, this article first explains pages and the related concepts below. These concepts are all closely connected and come up often throughout the series, so they need to be understood precisely.
- Page Layout
- HOT
- Single-page Vacuuming
- Fillfactor
1. Page Layout
📢 A page, as represented on disk, is called a block. Blocks are numbered sequentially from 0, and this number is called the block number.
Every table and index in PostgreSQL is an array of fixed-size pages (usually 8KB). Each page is divided broadly into a header area and a data area, and the data area stores data using the Slotted Page Layout structure.
📢 Slotted Page Layout is the page storage structure used by most DBMSs. Each time a tuple is stored, a slot is added and then the tuple is stored, and the slot holds the start address of its tuple. The slot array that holds the slots sits at the start of the data area, while the actual data (tuples) is stored from the end of the data area.
Each PostgreSQL page can be divided into 5 detailed areas, as shown below. Let's go through each.
- Header area
1. PageHeaderData
- Data area
1. ItemId (Line Pointer)
2. Free Space
3. Item (Tuple)
4. Special Space
1-1. PageHeaderData
First is the header area, PageHeaderData. It is allocated at the start of the page (the lowest address) and is fixed at 24 Bytes. It holds general information about the page (such as the checksum and the sizes of the other parts of the page).
Field | Type | Length | Description |
pd_lsn | PageXLogRecPtr | 8 bytes | LSN : the next byte after the last byte of the WAL record for the last change to this page |
pd_checksum | uint16 | 2 bytes | Page checksum (if enabled) |
pd_flags | uint16 | 2 bytes | Flag bits |
pd_lower | LocationIndex | 2 bytes | Offset to the start of free space
(the maximum position allowed in the page) |
pd_upper | LocationIndex | 2 bytes | Offset to the end of free space
(the start position of a newly inserted tuple) |
pd_special | LocationIndex | 2 bytes | Offset to the start of the special space |
pd_pagesize_version | uint16 | 2 bytes | Page size and layout version number |
pd_prune_xid | TransactionId | 4 bytes | Oldest unpruned XMAX on the page, or 0 if none |
📢 The PageHeaderData structure is defined in src/include/storage/bufpage.h .
2-1. ItemId
ItemId, also called a line pointer, sits at the very start of the data area, right after the page header. Each ItemId stores information pointing to an actual item, and these ItemIds are managed as an array ([1]→[2]→…); each time a new item is added, an ItemId pointing to it is added to the array. The array number, together with the page number, also serves as the page's table of contents (index), described below.
📢 ItemId means each element of the array, but it is also used to refer to the whole array.
Each ItemId holds (offset, length), a 4 Bytes value that represents the physical location (address) of the item it points to.
However, with direct addresses, any change to the data (a change in physical location) requires updating the index values that reference it, and they are not suited to solving page fragmentation, so PostgreSQL manages indirect addresses separately in addition to direct addresses.
An indirect address is a value made up of (Page Number, Index of ItemId), and it is generally called CTID, the pointer that identifies an item. From here on, read a CTID written as (n,m) as an indirect address pointing to the m-th ItemId of the n-th page, and the actual item can be located using the (offset, length) held by that ItemId.
📢 When an item moves within a page, only the current offset of the item that the ItemId points to is updated; the ItemId itself does not move, so the CTID stays the same.
This allows access to the item without breaking references from indexes that point to the CTID value, and prevents page fragmentation.
2-2. FreeSpace
A page can have free space (space with nothing allocated) left between the ItemIds and the items.
This empty space between the end of the last ItemId and the start of the newest item is called FreeSpace. New ItemIds (line pointers) are allocated from the start of this area, and new items (tuples) are allocated from its end. When nothing more can be added to this area, PostgreSQL considers the page full and appends an empty page to the end of the file to make room.
2-3. Item
The item area stores the actual data, including meta information. Here, data means tuples for table pages and index entries for index pages.
The item area sits right before the special space and builds up in order from the end of FreeSpace.
📢 PostgreSQL tables use concurrency control through multiversioning, so the same tuple can have multiple versions. For this reason, an item should be understood as "a version of a tuple", not "a tuple".
For table pages, items that represent "each version of a tuple" are stored in the Tuple Layout structure. Like a page, this structure is divided broadly into a header area and a data area, and after the fixed-size header come optional attributes such as the null bitmap, object id and user data.
In the header area of a table page, the following information makes multiversioning of tuples possible.
HeapTupleHeaderData
Field | Type | Length | Description |
t_xmin | TransactionId | 4 bytes | txid of the transaction that inserted this tuple; used to distinguish tuple versions |
t_xmax | TransactionId | 4 bytes | txid of the transaction that deleted or updated this tuple; used to distinguish tuple versions (0 if not deleted or updated) |
t_cid | CommandId | 4 bytes | Command ID (cid), starting from 0: the number of SQL commands executed in the current transaction before this command ran |
t_xvac | TransactionId | 4 bytes | xid of the Vacuum operation that moved this tuple version |
t_ctid | ItemPointerData | 6 bytes | Current tuple ID of this tuple or of the newest tuple version; gives the LP of the next updated version of the same tuple (if the tuple is updated, it points to the new version; otherwise t_ctid points to itself) |
t_infomask2 | uint16 | 2 bytes | Number of attributes + various flag bits |
t_infomask | uint16 | 2 bytes | Various flag bits that provide information defining the attributes of this tuple version |
t_hoff | uint8 | 1 byte | Offset to user data |
📢 The HeapTupleHeaderData structure is defined in src/include/access/htup_details.h .
Null bitmap
Located after the fixed field HeapTupleHeaderData, the null bitmap is an array of bits that marks the columns that can contain NULL values.
However, if t_infomask in the header indicates that the tuple has no nulls, the null bitmap is not stored. (Optional)
2-4. Special Space
The special space sits at the end of the page and uses the highest addresses. Some indexes use it to store extra information, so for tables and index pages that do not use it, its size is 0.
In index pages, the content of the special space depends on the index type. A single index can also have different types of pages; for example, a B-Tree index can have a specially structured metadata page and regular pages. (The metadata stores data such as links to the page's left and right siblings and the index structure.)
📢 Since the rest of the series deals with tables, from here on we refer to the ItemId of the page layout as LP (Line Pointer) and the item as a tuple.
2. HOT(Heap-only Tuple)
HOT (Heap-Only Tuple), introduced in PostgreSQL 8.3, is described in the official documentation as "a tuple that exists only in the table, not in the index".
Beyond that description, HOT and HOT Update can be described as a kind of update optimization technique that works (differently from the regular update method) only on tables with no indexes at all, or when updating columns that are not included in any index.
Constraints
HOT Update works when the following 2 conditions are met, including the point mentioned above.
- The columns referenced by the table's indexes must not be updated. (In other words, the update must not affect index pages.)
- There must be enough space in the same page as the pre-update version to store the new tuple version, so that the tuples before and after the update are in a single table page.
📢 A parameter called Fillfactor is used when checking whether a page has enough space, and depending on its setting, the share of updates performed as HOT Updates can change.
HOT Chain
When a HOT Update happens, the LP information pointing to the new tuple version created by the update is stored in the t_ctid of the old tuple. Tuples created through HOT Update are linked to each other in the form LP → Tuple → LP …, and this is called a HOT Chain. The HOT Chain lets you identify the newest tuple version.
📢 Both ctid and t_ctid are (pageno, lp) pairs. Both are used as indirect addresses (pointers) to identify tuples.
- ctid: a value that identifies the current tuple version. It combines the page number where the tuple is stored and the LP, and you can find the tuple you want with it. (This value is also stored in index entries and used during index scans.)
- t_ctid: a value that identifies the tuple version created by the next update of the same row. With it, you can find the next updated version and check whether the current version is the newest. (It is an important value for building the HOT Chain.)
If a tuple is updated, the ctid of the new tuple version is stored in the t_ctid of the previous version; if the tuple is the newest version, its t_ctid equals its own ctid.
- In the figure above, Tuple v1 pointed to by "LP 1" has ctid (0,1) and t_ctid (0,2), which points to "LP 2", and Tuple v2 pointed to by "LP 2" has t_ctid (0,3), pointing to "LP 3".
- Here, Tuple v3 pointed to by "LP 3" has the same ctid (0,3) and t_ctid (0,3), so we know it is the end of the HOT Chain, that is, the newest tuple version.
- The LP accessed first in a HOT Chain (LP 1 in the figure above) is called the head of the HOT Chain. The head is the only LP referenced directly from the index, and its value does not change. (In other words, unlike other LPs, the head of a HOT Chain cannot be released from the HOT Chain even if the tuple it points to becomes a dead tuple and is removed.)
- Because the head of the HOT Chain does not change, no index modification is needed for a HOT Update. (During an index scan, the tuple can be found by going from the index to the head of the HOT Chain and following the HOT Chain in order.)
- If HOT Update happens many times for one tuple, the HOT Chain can grow long.
- A long HOT Chain can be shortened by removing dead tuples through single-page vacuuming, described below.
Advantages of HOT Update
- No index modification is needed even when a HOT Update happens. This is because the head (LP) of the HOT Chain linked to the index stays the same; the original index entry can be used as is, so it incurs less overhead than a regular update.
- It reduces the need for Vacuum. Tuples created by HOT Update are not referenced from outside the page, so 4.Single-page Vacuuming alone can remove dead tuples, clean up LPs and reorganize the page. (Pages can be cleaned up quickly at low cost.)
3. Fillfactor
Fillfactor is an option that sets how full table pages are filled, as a percentage between 10 and 100 (default 100). When Fillfactor is less than 100, insert operations fill table pages only up to that percentage, and the remaining space is left empty as reserved space.
This reserved space is used for updates, and its existence also means the tuples before and after a change may end up in the same page. If the values before and after an update are in the same page, you can expect to minimize the number of pages that must be accessed.
For this reason, the more updates a table gets, the more it benefits from a lower Fillfactor. Let's look at the difference between a value of 100 (default) and a value below 100.
Fillfactor = 100 (%)
The default Fillfactor is 100(%). This setting aims to store (insert) as much data as possible in a single page, and when a page fills up with inserts, a new page is created to insert and modify data.
This setting is very efficient for inserts, but when an update happens, the changed data always has to be in a different page from the previous data. In other words, Fillfactor=100(%) suits data that is rarely or never changed after it is inserted.
10 (%) ≤ Fillfactor < 100 (%)
If you set Fillfactor below 100(%) (for example, 80), a page is filled only up to that percentage, and further inserts are not allowed. Once the set percentage is reached, a new page is created to store data, and the remaining space is kept free for updates only.
At first glance, this setting may seem wasteful of space, but when updates are frequent, you get both update performance optimization through HOT Update and benefits in space management.
📢 For the situations where HOT Update can be used, see 2. Constraints of HOT (Heap-only Tuple) above.
4. Single-page Vacuuming
When PostgreSQL decides there is not enough space in a page while reading or updating it, it tries to clean up the page to make room for new tuples. This is called single-page vacuuming, and it is an important concept for understanding why HOT Update is efficient.
Single-page vacuuming is not much different from the regular Vacuum process. The difference is that its target is limited to a table page, so updates to the FSM (Free Space Map) and indexes are excluded. It also does not generate additional WAL (Write Ahead Log), so it can be done quickly at a much lower cost than a regular Vacuum.
Like a regular Vacuum, single-page vacuuming can remove dead tuples, but the line pointer information pointing to a removed tuple can still be referenced from the index. (Since only one page is cleaned up, the link to the index is not released right away.)
📢 Single-page vacuuming is also called in-page vacuuming or single-page cleanup.
When It Occurs
- If, on update, there is not enough space to allocate the new tuple version in the page where the previous version is stored, this is recorded in the page header, and single-page vacuuming runs the next time.
- When the page fills up beyond the Fillfactor setting, single-page vacuuming runs immediately.
Because single-page vacuuming runs page-level vacuum continually whenever these Fillfactor-related conditions are met, it prevents tables from growing unnecessarily due to dead tuples and reduces the load of table-level Vacuum.
Wrapping Up
This article explained the essential concepts for understanding the upcoming posts in the HOT Series. Page layout, HOT Update, Fillfactor and single-page vacuuming are important on their own, but keep in mind that you need them to understand the posts that follow.
Related articles
