较长的专题文章

principle pg_repack 1.5.0 – Reorganize tables in PostgreSQL databases with minimal locks https://github.com/reorg/pg_repack create a log table to record changes made to the original table add a trigger onto the original table, logging INSERTs, UPDATEs and DELETEs into our log table create a new table containing all the rows in the old table build indexes on this new table apply all changes which have accrued in the log table to the new table swap the tables, including indexes and toast tables, using the system catalogs drop the original table The basic idea is...

序言 pgvector是一个向量搜索（根据近似度）的插件，用来加速AKNN（approximate nearest neighbor）。 PASE中提到，向量ANN算法包括4类 tree-based algorithms KD-Tree RTree quantization-based algorithms IVFFlat IVFADC IMI graph based algorithms HNSW NSG SSG hash-base algorithms LSH pgvector 包括两个算法，IVFFlat 和 HNSW，后续内容将以这两个算法的内容及其实现展开。 IVFFlat 概览 IVFFlat 算法主要包括以下几个步骤 索引构建阶段 使用 KMeans 将数据集划分成多个簇(cluster) 查询阶段 通过每个簇的中心点（向量是高维的点）获取N个最近的簇 遍历这N个簇的所有点，从中找到最近的K个点 算法介绍 基础算法kmeans reference k-means clustering - Wikipedia 算法目标：选取K个中心点，使得数据集中的所有点到其最近的中心点“距离”之和最近，以平方和距离为例： Given a set of observations $(x_1, x_2, \dots, x_n)$, where each observation is a $d$-dimensional real vector, k-means clustering aims to partition the $n$ observations into $k$ ($\leq n$) sets $S = {S_1, S_2, \dot, S_k}$ so as to minimize the within-cluster sum of squares (WCSS)....

本文主要为SLRU本身的结构解读。 简述 slru用来干什么？ slru是一个简单的buffer管理模块，simple slru 有了buffer pool manager，为什么还要slru？ bpm管理通用的page，比如heap，vm等 slru最大的特点就是lru，非常适合处理xid这样，递增的信息。 下面的代码分析基于pg15 存储结构 与bpm不同，通过slru管理的page，其文件大小固定，一个文件有32个page，一个page有8KB，故一个文件最大为256K。 与WAL不同，WAL文件的大小在创建时就已经确定为16M，与WAL文件重用保持一致，而slru的文件，先在内存中产生相应的page，再会去落盘。 #define SLRU_PAGES_PER_SEGMENT 32 内存slru 全局 buffer 数组 typedef struct SlruSharedData { LWLock *ControlLock; /* Number of buffers managed by this SLRU structure */ int num_slots; /* * Arrays holding info for each buffer slot. Page number is undefined * when status is EMPTY, as is page_lru_count. */ char **page_buffer; SlruPageStatus *page_status; bool *page_dirty; int *page_number; int *page_lru_count; LWLockPadded *buffer_locks; XLogRecPtr *group_lsn; int lsn_groups_per_page; /*---------- * We mark a page "most recently used" by setting * page_lru_count[slotno] = ++cur_lru_count; * The oldest page is therefore the one with the highest value of * cur_lru_count - page_lru_count[slotno] * The counts will eventually wrap around, but this calculation still * works as long as no page's age exceeds INT_MAX counts....

From access/transam/README Write-Ahead Log Coding 基本思想，日志在数据页前落盘 LSN：刷脏前检查LSN对应的日志已经落盘 优势：仅在必要的时候等待XLOG的IO。（异步IO） LSN的检查模块只用在 buffer manager 中实现 在WAL回放时，避免相同的日志被重复回放（可重入）。（TODO：full page write是否在另一个层面上保证了可重入） WAL 包含一个（或一小组）页的增量更新的重做信息。 依赖文件系统和硬件的原子写，不可靠！ checkpoint，checkpointer后的第一次写全页。通过 checkpoint 留下的 LSN 来判断是否为第一次写 写下WAL日志的逻辑为 pin and exclusive-lock the shared buffer START_CRIT_SECTION，发生错误时确保整个数据库能立即重启 在shared buffer上，进行对应的修改 标记为脏页， 必须在WAL日志写入前完成（TODO，为什么？SyncOneBuffer） 只有在要写WAL时，才能标记脏页（TODO，为什么？） 使用XLogBeginInsert 和 XLogRegister* 函数构建WAL，使用返回的LSN来更新page END_CRIT_SECTION，退出 解锁和unpin （注意顺序） 一些复杂的操作，需要原子地写下一串WAL记录，但中间状态必须自洽(self-consistent)。这样在回放wal日志时，如果中断，系统还能够正常运行。注意：此时相当于事务回滚，但是其部分更改已经落盘。举例： 在btree索引中，页的分裂分为两步（1）分配一个新页（2）在上一层的页(parent page)中新插入一条数据。 但是因为锁，这会形成两个独立的WAL日志。在回放WAL日志时 回放第（1）个日志： 分配一个新页，将元组移动进去 设置标记位，表示上一层的页没有更新 回放第（2）个日志： 在上一层的页中新插入一条数据 清除第（1）个日志中的标记位 标志位通常情况下不可见，因为对 child page 的修改时持有的锁，在两个操作完成后才会释放。 仅在写下第（2）个日志前，数据库恰好崩溃，标志位才会被感知。（该标志位应该没有MVCC，否则会在事务层屏蔽） 搜索时，不管这个中间状态 插入时，如果发现这个中间状态，先在上一层的页插入对应key，以修复这个“崩溃”状态，再继续插入

接口函数 一个WAL记录包含 WAL记录类型。（TODO不同的修改有不同的记录方式？） 这个页的修改方式 被修改的页的信息。被修改的页通过一个唯一ID标识，也可以有更多的关联数据（“record-specific data associated with the block”）。如果要写full page，就没有关联数据 构建一个WAL记录包含5个核心函数 void XLogBeginInsert(void) 初始化相关状态 如果当前无法构建WAL日志（例如在recovery模式），则报错 void XLogRegisterBuffer(uint8 block_id, Buffer buf, uint8 flags); 增加了数据块的信息；注册一个buffer的引用，相当于上述WAL日志的第三部分 block_id is an arbitrary number used to identify this page reference in the redo routine 在redo阶段，可以根据这些信息找到需要redo的page regbuf = &registered_buffers[block_id]; /* * Returns the relfilenode, fork number and block number associated with * a buffer */ BufferGetTag(buffer, &regbuf->rnode, &regbuf->forkno, &regbuf->block); regbuf->page = BufferGetPage(buffer); regbuf->flags = flags; regbuf->rdata_tail = (XLogRecData *) &regbuf->rdata_head; regbuf->rdata_len = 0; registered_buffer的结构...