PostgreSQL外存管理——表和元组的存储方式

在了解表和元组的组织方式之前，我们先简单了解下PostgreSQL里面的文件块的概念。PostgreSQL的存储管理器采用与操作系统类似的分页存储管理方式，即数据在内存中是以页面块的形式存在。每个表文件由多个BLCKSZ（一个可配置的常量，在pg_config.h中定义，默认是8KB）字节大小的文件块组成，每个文件块又可以包含多个元组（tuple），如下图所示。表文件以文件块为单位读入内存中，每一个文件块在内存中形成一个页面块（页面块是文件块在内存中的存在形式，二者大小相同，很多时候不区分这两个概念）。同样，文件的写入也是以页面块为单位。PostgreSQL是传统的行式数据库，是以元组为单位进行数据存储的。一个文件块中可以存放多个元组，但是PostgreSQL不支持元组的跨块存储，每个元组最大为MaxHeapTupleSize。这样就保证了每个文件块中存储的是多个完整的元组。

在PostgreSQL中，同一个表的元组按照创建顺序依次插入到表文件中（随着表的删除更新，也可能无序插入），元组之间不进行关联，这样的表文件称为堆文件。PostgreSQL系统中包含了四种堆文件：普通堆、临时堆、序列和TOAST表。临时堆和普通堆相同，但临时堆仅在会话过程中临时创建，会话结束后会自动删除。序列则是已中国元组值自动增长的特殊值。TOAST表其实也是一种普通堆，但是它专门用于存储变长数据。尽管这几种堆文件功能各异，但在底层的文件结构却是相似额：每个堆文件由多个文件块组成，在物理磁盘中的存储形式如下图：

我觉得PG源码里面的表示也不错：

/*
 * A postgres disk page is an abstraction layered on top of a postgres
 * disk block (which is simply a unit of i/o, see block.h).
 *
 * specifically, while a disk block can be unformatted, a postgres
 * disk page is always a slotted page of the form:
 *
 * +----------------+---------------------------------+
 * | PageHeaderData | linp1 linp2 linp3 ...           |
 * +-----------+----+---------------------------------+
 * | ... linpN |                                      |
 * +-----------+--------------------------------------+
 * |           ^ pd_lower                             |
 * |                                                  |
 * |             v pd_upper                           |
 * +-------------+------------------------------------+
 * |             | tupleN ...                         |
 * +-------------+------------------+-----------------+
 * |       ... tuple3 tuple2 tuple1 | "special space" |
 * +--------------------------------+-----------------+
 *                                  ^ pd_special
 *
 * a page is full when nothing can be added between pd_lower and
 * pd_upper.
 *
 * all blocks written out by an access method must be disk pages.
 *
 * EXCEPTIONS:
 *
 * obviously, a page is not formatted before it is initialized by
 * a call to PageInit.
 *
 * NOTES:
 *
 * linp1..N form an ItemId array.  ItemPointers point into this array
 * rather than pointing directly to a tuple.  Note that OffsetNumbers
 * conventionally start at 1, not 0.
 *
 * tuple1..N are added "backwards" on the page.  because a tuple's
 * ItemPointer points to its ItemId entry rather than its actual
 * byte-offset position, tuples can be physically shuffled on a page
 * whenever the need arises.
 *
 * AM-generic per-page information is kept in PageHeaderData.
 *
 * AM-specific per-page data (if any) is kept in the area marked "special
 * space"; each AM has an "opaque" structure defined somewhere that is
 * stored as the page trailer.  an access method should always
 * initialize its pages with PageInit and then set its own opaque
 * fields.
 */

一个文件块由PageHeaderData、LinpN、Freespace、TupleN、Special space五部分组成。

typedef struct PageHeaderData
{
    /* XXX LSN is member of *any* block, not only page-organized ones */
    XLogRecPtr  pd_lsn;         /* LSN: next byte after last byte of xlog
                                 * record for last change to this page */
    uint16      pd_tli;         /* least significant bits of the TimeLineID
                                 * containing the LSN */
    uint16      pd_flags;       /* flag bits, see below */
    LocationIndex pd_lower;     /* offset to start of free space */
    LocationIndex pd_upper;     /* offset to end of free space */
    LocationIndex pd_special;   /* offset to start of special space */
    uint16      pd_pagesize_version;
    TransactionId pd_prune_xid; /* oldest prunable XID, or zero if none */
    ItemIdData  pd_linp[1];     /* beginning of line pointer array */
} PageHeaderData;

typedef PageHeaderData *PageHeader;

PageHeaderData包含该文件块的一般信息，比如：

• 空闲空间的起始和结束位置(pd_lower和pd_upper)。
• Special space的起始位置(pd_special)。
• 项指针的起始位置(pd_linp)。
• 标志信息，如是否存在空闲项指针、是否所有元组都可见。

typedef struct ItemIdData
{
    unsigned    lp_off:15,      /* offset to tuple (from start of page) */
                lp_flags:2,     /* state of item pointer, see below */
                lp_len:15;      /* byte length of tuple */
} ItemIdData;

typedef ItemIdData *ItemId;

Linp是ItemIdData类型的数组，ItemIdData类型由lp_off、lp_flags和lp_len三个属性组成，每一个ItemIdData结构用来指向文件块中的一个元组，其中lp_off是元组在文件块中的偏移量，而lp_len则说明了该元组的长度，lp_flags表示元组的状态（分为未使用、正常使用、HOT重定向和死亡四种状态）。每个Linp数组元素为固定4个字节长度，LinpN指向TupleN。需要注意的是，因为lp_off和lp_len都是15个bit，所以PostgreSQL能够支持的最大页大小为2¹⁵=32KB.

3. Freespace

Freespace是指文件块中未分配的空间，新插入页面中的元组及其对应的Linp元素都从这部分空间中来分配，其中Linp元素从Freespace的开头分配，而新元组数据则从尾部开始分配。

4. Special space

该部分是特殊空间，用于存放与索引方法相关的特定数据，不同的索引方法在Special space中存放不同的数据。由于索引文件的文件块结构和普通表文件的相同，因为Special space在普通表文件块中并没有使用，并且不会为其分配空间。

5. TupleN

Tuple的结构和文件块有些像，每个元组也都有一个头部HeapTupleHeaderData，主要用于记录操作此元组的事务ID和命令ID等信息：

typedef struct HeapTupleHeaderData
{
    union
    {
        HeapTupleFields t_heap;
        DatumTupleFields t_datum;
    }           t_choice;

    ItemPointerData t_ctid;     /* current TID of this or newer tuple */

    /* Fields below here must match MinimalTupleData! */

    uint16      t_infomask2;    /* number of attributes + various flags */

    uint16      t_infomask;     /* various flag bits, see below */

    uint8       t_hoff;         /* sizeof header incl. bitmap, padding */

    /* ^ - 23 bytes - ^ */

    bits8       t_bits[1];      /* bitmap of NULLs -- VARIABLE LENGTH */

    /* MORE DATA FOLLOWS AT END OF STRUCT */
} HeapTupleHeaderData;

typedef HeapTupleHeaderData *HeapTupleHeader;

（1）t_choice是具有两个成员的联合类型：

• t_heap：用于记录对元组执行插入/删除操作的事务ID和命令ID，这些信息用于并发控制时检查元组对事务的可见性。
• t_datum：当一个新元组在内存中形成的时候，我们并不关心其事务可见性，因此在t_choice中只需用DatumTupleFields结构来记录元组的长度等信息。但在把该元组插入到表文件时，需要在元组头信息中记录插入该元组的事务和命令ID，故此时会把t_choice所占用的内存转换为HeapTupleFields结构并填充相应数据后再进行元组的插入。

typedef struct HeapTupleFields
{
    TransactionId t_xmin;       /* inserting xact ID */
    TransactionId t_xmax;       /* deleting or locking xact ID */

    union
    {
        CommandId   t_cid;      /* inserting or deleting command ID, or both */
        TransactionId t_xvac;   /* old-style VACUUM FULL xact ID */
    }           t_field3;
} HeapTupleFields;

typedef struct DatumTupleFields
{
    int32       datum_len_;     /* varlena header (do not touch directly!) */

    int32       datum_typmod;   /* -1, or identifier of a record type */

    Oid         datum_typeid;   /* composite type OID, or RECORDOID */

    /*
     * Note: field ordering is chosen with thought that Oid might someday
     * widen to 64 bits.
     */
} DatumTupleFields;

（2）t_ctid：ItemPointerData类型，用于记录当前元组或者新元组的物理位置（块内偏移量和元组长度），若元组被更新（PostgreSQL对元组的更新采用的是标记删除旧版本元组并插入新版本元组的方式），则旧版本元组的t_ctid中记录的是新版本元组的物理位置。

typedef struct ItemPointerData
{
    BlockIdData ip_blkid;
    OffsetNumber ip_posid;
}ItemPointerData;

ip_blkid记录是该元组在哪个文件块，ip_posid记录了该元组对应的Linp项在Linp数组的位置。

（3）t_infomask2使用其低11位表示当前元组的属性个数，其他位用于HOT技术及其元组可见性标志。

（4）t_infomask用于标识元组当前的状态，比如元组是否具有OID、是否具有空属性等，t_infomask的每一位对应不同的状态，共16种状态。

（5）t_hoff用于表示该元组头的大小。

（6）t_bits数组用于标识该元组哪些字段为空。

对于表和元组我们再介绍两个宏：

• MaxTupleAttributeNumber——一条元组中用户列的数目不能超过这个值，PG中默认值是1664。
• MaxHeapAttributeNumber——一个表中用于的列不能超过这个值，PG中默认值是1660。

/*
 * MaxTupleAttributeNumber limits the number of (user) columns in a tuple.
 * The key limit on this value is that the size of the fixed overhead for
 * a tuple, plus the size of the null-values bitmap (at 1 bit per column),
 * plus MAXALIGN alignment, must fit into t_hoff which is uint8.  On most
 * machines the upper limit without making t_hoff wider would be a little
 * over 1700.  We use round numbers here and for MaxHeapAttributeNumber
 * so that alterations in HeapTupleHeaderData layout won't change the
 * supported max number of columns.
 */
#define MaxTupleAttributeNumber 1664    /* 8 * 208 */

/*
 * MaxHeapAttributeNumber limits the number of (user) columns in a table.
 * This should be somewhat less than MaxTupleAttributeNumber.  It must be
 * at least one less, else we will fail to do UPDATEs on a maximal-width
 * table (because UPDATE has to form working tuples that include CTID).
 * In practice we want some additional daylight so that we can gracefully
 * support operations that add hidden "resjunk" columns, for example
 * SELECT * FROM wide_table ORDER BY foo, bar, baz.
 * In any case, depending on column data types you will likely be running
 * into the disk-block-based limit on overall tuple size if you have more
 * than a thousand or so columns.  TOAST won't help.
 */
#define MaxHeapAttributeNumber  1600    /* 8 * 200 */

最后，我们介绍以下PostgreSQL中的“HOT技术”。PostgreSQL中对于元组采用多版本技术存储，对元组的每个更新操作都会产生一个新版本，版本之间从老到新形成一条版本链（将旧版本的t_ctid字段指向下一个版本的位置即可）。此外，更新操作不但会在表文件中产生元组的新版本，在表的每个索引中也会产生新版本的索引记录，即对一条元组的每个版本都有对应版本的索引记录。即使更新操作没有修改索引属性，也会在每个索引中都产生一个新版本。这一技术的问题是浪费存储空间，旧版本占用的空间只有在进行VACUUM时才能被收回，增加了数据库的负担。为了解决这个问题，从版本8.3开始，使用了一种HOT机制，当更新的元组同时满足如下条件是（通过HeapSatisfiesHOTUpdate函数判断）称为HOT元组：

1. 所有索引属性都没有被修改（索引键是否修改是在执行时逐行判断的，因此若一条UPDATE语句修改了某属性，但前后值相同则认为没有修改）。
2. 更新的元组新版本与旧版本在同一文件块内（限制在同一文件块的目的是为了通过版本链向后找时不产生额外的I/O操作而影响到性能）。
   HOT元组会被打上HEAP_ONLY_TUPLE标志，而HOT元组的上一个版本则被打上HEAP_HOT_UPDATED标志。更新一条HOT元组将不会在索引中引入新版本，当通过索引获取元组时首先会找到同一块中最老的版本，然后顺着版本链往后找，直到遇到HOT元组为止。因此HOT技术消除了拥有完全相同键值的索引记录，减小了索引大小。

在堆中要删除一个元组，理论上由两种办法：

1. 直接物理删除：找到该元组所在的文件块，并将其读取到缓冲区中。然后在缓冲区中删除这个元组，最后再将缓冲区块写回磁盘。
2. 标记删除：为每个元组使用额外的数据位作为删除标记。当删除元组时，只需设置相应的删除标记，即可实现快速删除。这种方法并不立即回收删除元组占用的空间。
   PostgreSQL采用的是第二种方法，每个元组的头部信息HeapTupleHeader就包含了这个删除标记，其中记录了删除这个元组的事务ID和命令ID。如果上述两个ID有效，则表明该元组被删除；若无效，则表明该元组是有效的或者说没有被删除的。

本文参考《PostgreSQL数据库内核分析》一书。