5.3. Inserting, Deleting and Updating Tuples

This section describes the processes for inserting, deleting, and updating tuples. It also provides a brief overview of the Free Space Map (FSM), which is used during insertion and update operations.

To focus on tuple-level details, page headers and line pointers are omitted from the following descriptions. Figure 5.3 illustrates the basic representation of tuples used in this section.

5.3.1. Insertion

In an insertion operation, a new tuple is placed directly into a page of the target table (Figure 5.4).

Suppose a transaction with txid 99 inserts a tuple. The header fields of the inserted tuple are set as follows:

• Tuple_1:
  • t_xmin: Set to 99 (the txid of the inserter).
  • t_xmax: Set to 0 (Invalid), as the tuple has not been deleted or updated.
  • t_cid: Set to 0, indicating this is the first command executed by txid 99.
  • t_ctid: Set to (0, 1). It points to itself because it is the latest version.

testdb=# CREATE EXTENSION pageinspect;
CREATE EXTENSION
testdb=# CREATE TABLE tbl (data text);
CREATE TABLE
testdb=# INSERT INTO tbl VALUES('A');
INSERT 0 1
testdb=# SELECT lp as tuple, t_xmin, t_xmax, t_field3 as t_cid, t_ctid
                FROM heap_page_items(get_raw_page('tbl', 0));
 tuple | t_xmin | t_xmax | t_cid | t_ctid
-------+--------+--------+-------+--------
     1 |     99 |      0 |     0 | (0,1)
(1 row)

5.3.2. Deletion

In a deletion operation, the target tuple is deleted logically. The txid of the transaction executing the DELETE command is recorded in the t_xmax field of the tuple (Figure 5.5).

Suppose txid 201 deletes Tuple_1. The header fields are updated as follows:

• Tuple_1:
  • t_xmax: Set to 201.

Once txid 201 commits, Tuple_1 becomes unnecessary. In PostgreSQL, such unneeded tuples are called dead tuples.

Dead tuples are eventually removed by VACUUM processing, which is detailed in Chapter 6.

5.3.3. Update

In an update operation, PostgreSQL logically deletes the existing version and inserts a new one (Figure 5.6).

Suppose a row originally inserted by txid 99 is updated twice by txid 100.

The first UPDATE command logically deletes Tuple_1 by setting its t_xmax to 100 and then inserts Tuple_2. Additionally, the t_ctid of Tuple_1 is updated to point to Tuple_2.

• Tuple_1:
  • t_xmax: Set to 100.
  • t_ctid: Updated from (0, 1) to (0, 2).
• Tuple_2:
  • t_xmin: Set to 100.
  • t_xmax: Set to 0.
  • t_cid: Set to 0.
  • t_ctid: Set to (0, 2).

The second UPDATE command follows the same logic: Tuple_2 is logically deleted, and Tuple_3 is inserted.

• Tuple_2:
  • t_xmax: Set to 100.
  • t_ctid: Updated from (0, 2) to (0, 3).
• Tuple_3:
  • t_xmin: Set to 100.
  • t_xmax: Set to 0.
  • t_cid: Set to 1.
  • t_ctid: Set to (0, 3).

If txid 100 commits, Tuple_1 and Tuple_2 become dead tuples. If txid 100 aborts, Tuple_2 and Tuple_3 become dead tuples.

5.3.4. Free Space Map

PostgreSQL uses the Free Space Map (FSM) to select a page with sufficient capacity when inserting a heap or index tuple.

As described in Section 1.2.3, every table and index has an associated FSM. Each FSM tracks the available free space in each page of its corresponding file.

FSM files are stored with the “.fsm” suffix and are loaded into shared memory as needed.

testdb=# CREATE EXTENSION pg_freespacemap;
CREATE EXTENSION

testdb=# SELECT *, round(100 * avail/8192 ,2) as "freespace ratio"
                FROM pg_freespace('accounts');
 blkno | avail | freespace ratio
-------+-------+-----------------
     0 |  7904 |           96.00
     1 |  7520 |           91.00
     2 |  7136 |           87.00
     3 |  7136 |           87.00
     4 |  7136 |           87.00
     5 |  7136 |           87.00
....