【PostgreSQL】【存储管理】表和元组的组织方式

• 外存管理负责处理数据库与外存介质(PostgreSQL8.4.1版本中只支持磁盘的管理操作)的交互过程。
• 在PostgreSQL中，外存管理由SMGR(主要代码在smgr.c中)提供了对外存的统一接口。
• SMGR负责统管各种介质管理器，会根据上层的请求选择一个具体的介质管理器进行操作。
• 每个表在磁盘中都以一定的结构进行存储，针对磁盘，外存管理模块提供了磁盘管理器和VFD机制。
• 在PostgreSQL8.4.1版本中，还为每个表文件创建了两个附属文件，即空闲空间映射表（FSM）和可见性文件映射表（VM）。
• 另外，对于大数据存储，PostgreSQL也提供了两种处理机制。

表和元组的组织方式

• PostgreSQL中一个表中的元组按照创建顺序依次插入到表文件中。
• 在进行VACUUM操作清除被删除的元组后，元组也可以以无序的方式插入到具有空间空间的文件块中
• 元组之间不进行关联，这样的表文件称为堆文件。
• PostgreSQL系统中包含了四种堆文件：
  • 普通堆：堆文件就是普通堆
  • 临时堆：临时堆和普通堆结构相同，但是临时堆仅在会话过程中临时创建，会话结束会自动结束。
  • 序列：一种特殊的单行表，它是一种元组值自动递增的特殊堆。
  • TOAST表：它其实也是一种普通堆，但是它被专门用于存储变长数据。
• 尽管这几种堆的功能各异，但在底层的文件结构却是相似：每个堆文件由多个文件块组成。

文件块在物理磁盘中的存储形式：

PageHeaderData: 24字节长。包含关于页面的一般信息，包括空闲空间指针。

• 结构体：

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	PageXLogRecPtr	8 bytes	LSN: 最后修改这个页面的WAL记录最后一个字节后面的第一个字节
pd_checksum	uint16	2 bytes	页面校验码
pd_flags	uint16	2 bytes	标志位
pd_lower	LocationIndex	2 bytes	到空闲空间开头的偏移量
pd_upper	LocationIndex	2 bytes	到空闲空间结尾的偏移量
pd_special	LocationIndex	2 bytes	到特殊空间开头的偏移量
pd_pagesize_version	uint16	2 bytes	页面大小和布局版本号信息
pd_prune_xid	TransactionId	4 bytes	页面上最老未删除XID，如果没有则为0

ItemIdData:

• 结构体：src/include/storage/bufpage.h

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

• 每个ItemIdData结构用来指向文件块中的元组，其中lp_off是元组在文件块中的偏移量，而lp_len则说明了该元组的长度，lp_flags表示元组的状态（分为未使用，正常使用，HOT重定向和死亡四种状态）

/** lp_flags has these possible states.  An UNUSED line pointer is available* for immediate re-use, the other states are not.*/
#define LP_UNUSED    0    /* unused (should always have lp_len=0) */
#define LP_NORMAL    1    /* used (should always have lp_len>0) */
#define LP_REDIRECT    2    /* HOT redirect (should have lp_len=0) */
#define LP_DEAD      3    /* dead, may or may not have storage */

• 在页头后面是项标识符（ItemIdData），每个占用四个字节。
• 一个项标识符包含一个到项开头的字节偏移量（它的长度以字节计）， 以及一些属性位，这些属性位影响对它的解释。
• 新的项标识符根据需要从未分配空间的开头分配。
• 项标识符的数目可以通过查看pd_lower来判断，在分配新标识符的时候pd_lower会增长。
• 因为一个项标识符在被释放前绝对不会移动，所以它的索引可以用于长期地引用一个项， 即使该项本身因为压缩空闲空间在页面内部进行了移动。
• 实际上，PostgreSQL创建的每个指向项的指针（ItemPointer，也叫做CTID）都由一个页号和一个项标识符的索引组成。
• 项本身存储在从未分配空间末尾开始从后向前分配的空间里。它们的实际结构取决于表包含的内容。表和序列都使用一种叫做 HeapTupleHeaderData的结构，

Freespace: 是指未分配的空间(空闲空间)

• 新插入页面中的元组即对应的项标识符都将从这部分空间中来分配，其中Linp元素从Freespace的开头开始分配，而新元组数据则从尾部开始分配。

Special space:是特殊空间

• 用于存放与索引方法相关的特定数据，不同的索引方法在Special space中存放不同的数据，比如，b-tree 索引用它存储指向页面的左右兄妹的链接，以及其他一些和索引结构相关的数据。
• 由于索引文件的文件块和普通表文件的相同，因此Special space在普通表文件块中并没有使用，其内容被置为空。

Tuple:每个元组分两个部分元组头部和数据：元组头部存放该元组头部信息，数据部分存放用户存储的实际数据

• 结构体：位于src/include/access/htup_details.h

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 2uint16    t_infomask2;  /* number of attributes + various flags */
#define FIELDNO_HEAPTUPLEHEADERDATA_INFOMASK 3uint16    t_infomask;    /* various flag bits, see below */
#define FIELDNO_HEAPTUPLEHEADERDATA_HOFF 4uint8    t_hoff;      /* sizeof header incl. bitmap, padding *//* ^ - 23 bytes - ^ */
#define FIELDNO_HEAPTUPLEHEADERDATA_BITS 5bits8    t_bits[FLEXIBLE_ARRAY_MEMBER];  /* bitmap of NULLs *//* MORE DATA FOLLOWS AT END OF STRUCT */
};

• 出于编程的考虑，PostgreSQL的源代码中常用指向HeapTupleHeaderData的结构指针HeapTupleHeader来访问元组的头部信息。
• t_choice是具有两个成员的联合类型：
  • t_heap:

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;

    用于记录对元组执行插入/删除操作的事务ID和命令ID,这些信息主要用于并发控制时检查元组对事务的可见性。
- t_datum:

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 *//** datum_typeid cannot be a domain over composite, only plain composite,* even if the datum is meant as a value of a domain-over-composite type.* This is in line with the general principle that CoerceToDomain does not* change the physical representation of the base type value.** Note: field ordering is chosen with thought that Oid might someday* widen to 64 bits.*/
} DatumTupleFields;

    当一个新元组在内存中形成时时候，我们并不关心其事务可见性，因此在t_choice中只需要用DatumTupleFields结构来记录元组的长度等信息。但是该元组插入到表文件时，需要在元组头信息中记录插该元组的事务和命令ID。故此时会把t_choice所占用的内存转化为HeapTupleFields结构，并填充相应数据后再进行元组的插入。

• t_ctid:用于记录当前元组或者新元组的物理位置(块内偏移量和元组长度)

  如果元组更新，PostgreSQL对元组的更新采用的是标记删除旧版本并插入新版本的元组的方式，则记录的是新版本元组的物理位置。

• t_infomask2：

  • 使用其低11位表示当前元组的属性个数，其他位则用于包括用于HOT技术及元组可见性的标记为。

• t_infomask：

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

/** information stored in t_infomask:*/
#define HEAP_HASNULL      0x0001  /* has null attribute(s) */
#define HEAP_HASVARWIDTH    0x0002  /* has variable-width attribute(s) */
#define HEAP_HASEXTERNAL    0x0004  /* has external stored attribute(s) */
#define HEAP_HASOID_OLD      0x0008  /* has an object-id field */
#define HEAP_XMAX_KEYSHR_LOCK  0x0010  /* xmax is a key-shared locker */
#define HEAP_COMBOCID      0x0020  /* t_cid is a combo CID */
#define HEAP_XMAX_EXCL_LOCK    0x0040  /* xmax is exclusive locker */
#define HEAP_XMAX_LOCK_ONLY    0x0080  /* xmax, if valid, is only a locker */
#define HEAP_XMIN_COMMITTED    0x0100  /* t_xmin committed */
#define HEAP_XMIN_INVALID    0x0200  /* t_xmin invalid/aborted */
#define HEAP_XMAX_COMMITTED    0x0400  /* t_xmax committed */
#define HEAP_XMAX_INVALID    0x0800  /* t_xmax invalid/aborted */
#define HEAP_XMAX_IS_MULTI    0x1000  /* t_xmax is a MultiXactId */
#define HEAP_UPDATED      0x2000  /* this is UPDATEd version of row */
#define HEAP_MOVED_OFF      0x4000  /* moved to another place by pre-9.0* VACUUM FULL; kept for binary* upgrade support */
#define HEAP_MOVED_IN      0x8000  /* moved from another place by pre-9.0* VACUUM FULL; kept for binary* upgrade support */

• t_hoff:
  • 表示该元组头的大小，到用户数据的偏移量
• _bits[] : 数组表示该元组中那些字段为空

HOT技术：

• PostgreSQL中对于元组采用多版本控制技术存储。
• 对于元组的更新操作都会产生一个新版本，版本之间从老到新形成一条版本链，将旧版本的t_ctid字段指向下一个版本的位置即可。
• 此外，更新操作不但会在表文件中产生元组的新版本，在表的每个索引中也会产生新版本的索引记录，即对一条元组的每个版本都有对应的索引记录。
• 即使，更新操作没有修改索引属性，也会在每个索引中产生一个新版本。
• 这技术的问题是浪费存储空间，旧版本占用的空间中有在进行VACUUM时才能被回收，增加了数据库的负担。
• 为了解决这个问题，从版本8.3开始，使用一种HOT机制，当更新的元组同时满足如下条件时(通过HeapSatisfiesHOTUpdate函数判断)称为HOT元组
  • 所有索引技术都没有被修改过，索引键是否修改过是在执行时逐行判断的，因此若一条update语句修改了某属性，但是前后值相同则认为没有修改过。
  • 更新的元组新版本与旧版本在同一个文件块内，限制在同一个文件块的目的是为了通过版本链向后查找时不产生额外的I/O操作从而影响到性能。
• HOT元组会被打上HEAP_ONLY_TUPLE标志，而HOT元组上的上一个版本则被打上HEAP_HOT_UODATE标志。
• 更新一条HOT元组将不会在索引中引入新版本，当通过索引获取元组时首先会找到同一块中最老的版本，然后顺着版本链向后找，直到遇到HOT元组为止。
• 因此HOT技术消除了拥有完全相同的键值索引记录，减少了索引大小。

在堆中删除一个元组的方法：理论上有两种方法

• 直接物理删除：找到该元组所在的块，并将其读取到缓冲区，然后再缓冲区中删除这个元组，最后再将缓冲区的数据写回磁盘。
• 标记删除：为每个元组使用额外的数据位作为删除标记。当删除元组时，只设置相应的删除标记，即可实现快速删除。这种方法并不会立即回收删除元组占用的空间。

PostgreSQL采用的是第二种方法，每个元组的头部信息就包含了这个删除标记，其中记录了删除这个元组的事务ID和命令ID。如果上述两个ID有效，则表明该元组被删除，若无效，说明该元组是有效的或者说没有被删除。这种方法对于多版本并发控制也是有好处的。