PostgreSQL原理：从元组、页面结构、索引查找到动态修剪

在 PostgreSQL 中没有undo段，数据库通过数据多版本实现mvcc，老版本的数据元组直接存放在数据页面中，这样带来的问题就是旧元组需要不断地进行清理以释放空间，这也是数据库膨胀的根本原因。

本文简单介绍一下postgresql数据库的元组、页面的结构以及索引查找流程。

元组结构

元组，也叫tuple，这个叫法是很学术的叫法，但是现在数据库中一般叫行或者记录。下面是元组的结构：

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;
struct HeapTupleHeaderData
{
union
{
HeapTupleFields t_heap;
DatumTupleFields t_datum;
} t_choice;

ItemPointerData t_ctid; /* current TID of this or newer tuple (or a
* speculative insertion token) */

/* Fields below here must match MinimalTupleData! */
#define FIELDNO_HEAPTUPLEHEADERDATA_INFOMASK2 2
uint16 t_infomask2; /* number of attributes + various flags */
#define FIELDNO_HEAPTUPLEHEADERDATA_INFOMASK 3
uint16 t_infomask; /* various flag bits, see below */
#define FIELDNO_HEAPTUPLEHEADERDATA_HOFF 4
uint8 t_hoff; /* sizeof header incl. bitmap, padding */
/* ^ - 23 bytes - ^ */
#define FIELDNO_HEAPTUPLEHEADERDATA_BITS 5
bits8 t_bits[FLEXIBLE_ARRAY_MEMBER]; /* bitmap of NULLs */
/* MORE DATA FOLLOWS AT END OF STRUCT */
};


• t_xmin：代表插入此元组的事务xid；

  
  



• t_xmax：代表更新或者删除此元组的事务xid，如果该元组插入后未进行更新或者删除，t_xmax=0；

  
  



• t_cid：command id，代表在当前事务中，已经执行过多少条sql，例如执行第一条sql时cid=0，执行第二条sql时cid=1；

  
  



• t_ctid：保存着指向自身或者新元组的元组标识（tid），由两个数字组成，第一个数字代表物理块号，或者叫页面号，第二个数字代表元组号。在元组更新后tid指向新版本的元组，否则指向自己，这样其实就形成了新旧元组之间的“元组链”，这个链在元组查找和定位上起着重要作用。

  
  

了解了元组结构，再简单了解下元组更新和删除过程。

更新过程

上图中左边是一条新插入的元组，可以看到元组是xid=100的事务插入的，没有进行更新，所以t_xmax=0，同时t_ctid指向自己，0号页面的第一号元组。右图是发生xid=101的事务更新该元组后的状态，更新在pg里相当于插入一条新元组，原来的元组的t_xmax变为了更新这条事务的xid=101，同时t_ctid指针指向了新插入的元组（0,2），0号页面第二号元组，第二号元组的t_xmin=101（插入该元组的xid），t_ctid=（0,2），没有发生更新，指向自己。

删除过程

上图代表该元组被xid=102的事务删除，将t_xmax设置为删除事务的xid，t_ctid指向自己。

页面结构

下面再来看看页面的结构

从上图可以看到，页面包括三种类型的数据

1.header data：数据头是page生成的时候随之产生的，由pageHeaderData定义结构，24个字节长，包含了page的相关信息，下面是数据结构：

typedef struct PageHeaderData
{
/* XXX LSN is member of *any* block, not only page-organized ones */
PageXLogRecPtr pd_lsn; /* LSN: next byte after last byte of xlog
* record for last change to this page */
uint16 pd_checksum; /* checksum */
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[FLEXIBLE_ARRAY_MEMBER]; /* line pointer array */
} PageHeaderData;


pd_lsn: 存储最近改变该页面的xlog位置。

pd_checksum：存储页面校验和。

pd_lower，pd_upper：pd_lower指向行指针（line pointer）的尾部，pd_upper指向最后那个元组。

pd_special: 索引页面中使用，它指向特殊空间的开头。

2.line pointer：行指针，四字节，每一条元组会有一个行指针指向真实元组位置。

3.heap tuple：存放真实的元组数据，注意元组是从页面的尾部向前堆积的，元组和行指针之间的是数据页的空闲空间。

索引查找

看了页面和元组结构，再看看索引的结构。

以上图为例，索引的数据包含两部分（key=xxx，TID=(block=xxx,offset=xxx)），key表示真实数据，tid代表指向数据行的指针，具体block代表页面号，offset代表行偏移量，指向数据页面的line pointer，比如执行下面的查询语句

select * from tbl where id=1000;


key=1000，根据key值在索引中找到tid为5号页面的1号元组，再通过一号元组行指针找到元组1，检查元组1的t_ctid字段，发现指向了新的元组2，于是定位到真实元组数据2。

堆内元组和动态剪枝技术，这两个技术其实是相辅相成的。我们知道在数据库元组插入更新时，索引也需要进行相应维护，因为pg的老元组不会实时清理，那么在更新后索引中就会多出一条索引记录指向新元组，这样造成索引膨胀，维护代价变大。pg为了避免这个问题，从8.3版本开始采用HOT（heap only tuple）解决这个问题，下面简单介绍一下技术原理。

普通更新

如下图所示，当tuple发生更新后，需要新增一条tuple记录到页面中，此时索引中也对应新增了一条记录，该记录指向tuple2的line pointer。这样的话每次更新都需要在索引页面插入新记录，维护开销太大，而且会造成索引膨胀。Pg采用hot技术解决这个问题。

HOT更新

在使用hot更新时，元组更新后不会在索引页面新建相应记录，而通过在新老元组上设置标志位使得老元组指向新元组，形成新旧元组“链”解决这个问题。

前一篇文章介绍过，在元组结构的t_informask2字段中有两个标记位，heap_hot_update和heap_only_tuple，在更新tuple1时，postgresql会将tuple1（老元组）的标记位置为heap_hot_update，代表该元组是经过hot更新的行，同时将tuple2（新元组）的标记位置为heap_only_tuple。具体过程如下：

1.首先找到目标数据的索引元组

2.然后通过索引元组中的位置，访问行指针数组，找到行指针1

3.读取tuple1

4.发现tuple1的标记位是heap_hot_update，表明该元组是经过hot更新的元组，并不是真实要读取的数据，于是通过tuple1的t_ctid字段读取tuple2（上一篇文章也介绍过，当元组被更新过后，元组的t_ctid字段指向新的元组）

动态修剪

上面访问数据的过程其实访问了tuple1和tuple2两个数据块，这时我们可能会考虑到一个问题，因为tuple1是旧元组，它会在合适时机被vacuum掉，这时就无法通过tuple1的ctid字段定位到tuple2了，为了解决这个问题，postgresql会在合适的时候进行line pointer的重定向（redirect），将tuple1的line pointer重定向到line pointer2，这个过程称为动态修剪。

此时访问新元组的流程如下：

1.首先找到目标数据的索引元组

2.然后通过索引元组中的位置，访问行指针数组，找到行指针1

3.通过行指针的重定向，找到行指针2

4.通过行指针2直接定位tuple2

HOT技术的适用场景

当然HOT技术也不是万能的，它也有不适用的场景，比如下面两个场景：

1. 当更新的元组和老元组不在同一个page中时，新旧元组链是不能跨越页面的，指向该元组的索引元组也会被添加到索引页面中。

   
   



2. 当索引的key值更新时，原有索引记录中的key无法再定位到正确元组，此时会在索引页面中插入一条新的索引元组。