分段排除

来自 PostgreSQL 维基
跳转到导航跳转到搜索

Simon Riggs, 2ndQuadrant

分段排除在 Oracle 中也被称为存储索引，在 Vectorwise 中被称为 MinMax 索引，尽管这两个实现都晚于 Postgres 黑客的首次提及。

回顾：超大型表格用例

许多大型表格都有规律的访问模式

  • 频繁插入新行
  • 对“最近”数据进行一些更新和删除
  • 较旧的数据有效地变为只读
  • 在某些时候，数据可能从表格中批量删除

大多数表格在“最近”的含义上有所不同；有些是只插入的，很多不是。一个典型的例子可能是一个大型历史表格，其中最近 6 个月的数据会被更新，但在此之后，数据几乎没有变化。

分区依赖于对数据物理位置的了解，以从扫描中排除数据的部分。

目前，分区知识是通过用户声明以表格约束的形式提供的，这些约束通过视图或继承链接在一起。我们目前也以“约束优先”的方式进行，即我们将数据放置在约束指定的位置，而不是从数据中推导出约束。

表内分区

在常见用例中，某些数据列与表格中数据的物理放置之间存在明显的亲和力。对于诸如 LOG_DATE 或 TRANSACTION_DATE 之类的列，情况确实如此，但对于任何 id 列由 Sequence 分配的列也同样如此。HOT 有助于这种亲和力随着时间的推移而保持不变。

鉴于上述用例，当数据值和数据放置之间存在亲和力 *并且* 我们知道较旧的数据往往会变成只读时，我们就可以意识到表格的某些物理部分将有效地变成只读。（我的经验是，表格越大，写入模式越不随机 - 无论 TPC-C 的编写人员怎么说）。

如果我们能够跟踪表格中哪些部分现在是只读的，那么我们就能记录有关该部分数据的相关信息，并使用它来帮助解决查询。这颠覆了当前的思维方式：我们可以从数据中推导出约束，而不是根据约束放置数据。这将更加自然：将数据加载到表格中，让系统处理其余部分。

我们可以想象我们在单个表格中执行此操作。想象一下：将表格分成 100 个部分，然后记录这些部分中所有元组的最小值和最大值。当我们执行 SeqScan 时，我们可以跳过可以证明永远不会满足查询谓词的部分。与分区相同，但位于表格内部。

目前，表格已经分解成 1GB 的文件段，因此将它们作为我们的部分大小似乎相当自然。这与理想分区大小的建议相当吻合。使用这种技术也易于提供可变大小的部分，方法是使用表格级别的存储参数，例如 fillfactor。

分段排除

在我们注意到某个段是只读之后，我们可以扫描该段并记录所有列的最小值和最大值。这些是“隐式约束”，然后可以用来进行分段排除，其方式类似于我们对当前约束排除机制的处理。

隐式约束然后允许 SeqScans 在执行时为每个段评估分段排除，即如果约束不匹配，扫描可以跳过整个段。如果某个段还没有隐式约束，它将始终被完整扫描。这允许分区、同步扫描和缓冲区回收比目前更有效地协同工作。

其他扫描类型也可能使用分段排除，尽管这只有在扫描检索许多行时才有用，否则分段排除的开销可能不值得。

这也将允许 Merge Join 在执行时利用内计划的分段排除。我们不会从一开始就扫描整个内表格计划，而是能够从合适的分段开始扫描。（这将适用于内表格的第一个元组，而不是每个内元组）。这将要求我们将外部计划的当前值传递到内计划中。内计划上的典型执行器节点将是 SortNode，在其之下是 SeqScan。在这种情况下，执行器需要将外部值从 MergeJoinNode 传递到 SortNode，然后传递到 SeqScan 节点。SeqScan 节点可以执行分区排除，从而减少该扫描的时间，也减少最终排序的时间。这听起来在正常情况下也可能值得去做。事实证明，潜在适用的情况可能已经在计划阶段被排除在外，我还没有对此方面进行足够的思考。

如果我们收集所有列的数据，那么我们许多隐式约束将毫无用处。例如，如果某列只有几个值，并且这些值存在于所有段中。将我们的谓词与所有约束匹配将很昂贵，因此我们必须剔除不良约束。我们将通过删除重叠超过 10% 其他段的任何约束来实现。在开发过程中，可能需要发现各种启发式方法来实现这一点，而不必诉诸手动命令。

请注意，所有这些排除都发生在执行器中，而不是规划器中。这使得这种形式的排除可以在没有问题的情况下与稳定函数和参数一起使用。

也可以仅在规划器中排除某些类型的值，但这只有在规划器和执行器同时运行时才有效。

对这种方法的一个潜在反对意见是，不可变函数和常量无法在准备好的查询中被规划器删除，因为分区约束是动态的。

记录哪些分段是只读的

到目前为止，所有这些都依赖于我们能够记录表格中哪些段是只读的能力。我们可以通过两种方式做到这一点

  • 1) 让系统自动跟踪不变数据
  • 2) 让 DBA 发布命令来“标记”某个段现在是只读的

可能两种方法结合起来更好，因此我们有三种状态用于段

  • READ_WRITE_ALLOWED
  • EFFECTIVE_READ_ONLY（仅由 1 设置）
  • MARKED_READ_ONLY（仅由 2 设置）

尽管如此，我还是想专注于 (1)，但也要考虑另一个方法，以防审查人员要求。

可见性映射

那么我们 *如何* 将段标记为只读？事实证明，尝试这样做与 Heikki 的可见性映射想法非常相似，因此我将用这些术语来描述它，尽管存在一些差异。它也让人想起 Andrew Sullivan 的只读元组概念。

我们将在 *段* 级维护一个动态可见性映射，显示哪些段的所有行都 100% 可见。不会在此级别保存任何空闲空间映射数据。

Heikki 的可见性映射想法的大部分内容都成立，只是我们为表格中的每个段都有一个位，而不是每个块。映射非常小，而且表格几乎不会改变，因此我们可以轻松地将其缓存在每个后端上。如果映射发生变化，我们可以执行 relcache 失效以使每个人重新读取映射。

不需要动态共享内存缓存，因为任何对表格的并发更改都会被扫描忽略，因此在扫描时发生插入、更新或删除并不重要。任何开始的新扫描都将尝试锁定表格，然后执行 rel 缓存检查，然后再继续。因此，可见性将至少针对 *该* 扫描正确设置。

在大多数情况下，可见性映射可以概括为一个布尔值，以显示是否存在任何 100% 可见的段。这使得在常见的未设置情况下访问映射变得非常便宜。

检查 rel 缓存是否已更改本质上是免费的，因为我们已经在获取锁时执行了此操作。唯一不正确的情况是，当我们尝试锁定在本事务中已经锁定的表格时，因为目前已经对此进行了优化。在这种情况下，我们只针对在 *首次* 访问事务期间映射时具有只读段的表格检查 rel 缓存。我们始终会有一个映射来让我们能够在此时进行检查，我们只需要在设置了值时重新检查。如果段在我们的访问期间从读写变为有效只读，我们无需担心。因此，非分区情况下的开销是一个布尔测试，而对于分区表格，我们需要为针对表格的每个语句重新访问缓存。这似乎是可以接受的，因为在许多情况下，我们可能会使用可见性信息来大幅提高性能。

设置可见性映射

我们需要在 VM 中添加另一个中间状态来应对在设置映射时发生的并发更改，称为 READ_ONLY_PENDING。

VACUUM 将扫描所有 READ_WRITE_ALLOWED 段，如果它看到的剩余行的 100% 对所有当前后端可见，则将其中一些段标记为 READ_ONLY_PENDING。标记映射将导致 rel 缓存失效。

然后，我们将重新扫描新标记的段以推导出隐式约束的最小值和最大值，此操作由自动真空工作进程执行。如果我们看到事务在 VACUUM 的 xmin 之后进行的更改，那么我们将中止此扫描并将映射重置为 READ_WRITE_ALLOWED。这允许我们捕获第一个 VACUUM 扫描后面的并发更改。

第一个 VACUUM 之后的但位于第二个扫描的扫描点后面的表格更改将看到 READ_ONLY_PENDING 状态，并将其清除回 READ_WRITE_ALLOWED。

如果第二个 READ_ONLY_PENDING 段扫描没有发现任何新的更改，那么它就可以成功地将映射更新为 EFFECTIVE_READ_ONLY。

我们永远不会将最高编号的段标记为 EFFECTIVE_READ_ONLY，因为它可能会在发生 INSERT 时扩展。这对于从这种功能涉及的开销中排除较小的表格也是一种有用的方法。

在只插入的表格中，这意味着只有最后 1 或 2 个段是读写的，因此 VACUUM 始终会在有限的时间内运行，无论表格有多大。

我们什么时候尝试设置可见性映射？如果我们积极地执行此操作，那么它将很快被取消设置。如果我们等待太久，我们可能会失去这种方法的一些优势。

首先，我们认识到只读段会改变自动清理计算 - 我们直接完全排除它们。这将意味着 VACUUM 将比现在更频繁地运行，但运行时速度会更快。（注意，目前，在不断增长的表上，假设写入速率恒定，VACUUM 运行的频率会随着表的大小而越来越低）。

我的感觉是 VACUUM 足够不频繁，因此我们应该在每次 VACUUM 后积极地设置可见性映射。如果映射很快被取消设置，那么我们等待一段时间后再次尝试。取消设置似乎争用较低（见下文），因此似乎可以接受。

因此，设置和取消设置可见性映射使得这种分区方法“易变”，并且如果更新模式不一致，则无法依赖它来提供性能。

然后，我们将重新扫描新标记的段以推导出隐式约束的最小/最大值，由自动清理工作进程执行。最好的方法似乎是 ANALYZE 命令会自动检测到一个段最近被设置为 EFFECTIVE_READ_ONLY，并执行全行扫描而不是仅仅抽样。（我们只保存具有有效 B 树排序操作符的数据类型的最小/最大值，就像 ANALYZE 已经做的那样）。

以后仍然需要 VACUUM 来冻结行，但这可以在我们达到冻结限制后发生，或者如果我们运行显式 VACUUM FREEZE，则可以更早发生。我们需要为每个段存储最旧的 xid，以便知道何时对表的那部分启动 FREEZE。

这完全偏离了可见性映射和空闲空间映射以某种方式相关的想法。但是，FSM 中需要进行更改以确保建议的技术稳定且有用：如果我们扫描一个段，并且它 100% 可见，如果段中只有一个块存在空闲空间，那么我们很快就会发现我们的可见性位将很快被设置为关闭。

如果段中总的空闲空间超过 5%，那么我们将不会设置 EFFECTIVE_READ_ONLY，也不会将段中的块报告给 FSM。这样，少量空闲空间不会破坏段排除带来的好处。VACUUM 目前会覆盖 FSM 信息，但如果情况并非如此，那么我们必须为新设置为只读的段积极地将其删除。也许该限制应该是 (100 - fillfactor)%，这通常根据用户对表上可能更新次数的预期而设置。

存储可见性映射

可见性映射足够小，可以在每个后端缓存，但如果我们有超过 20 个段，那么在 pg_class 上存储它仍然具有挑战性。

有三个项目需要存储

  • 可见性映射 - 段状态标志
  • 每个段的 relfrozenxids
  • 段边界值
  • 段聚合（例如，该段中的元组数量）

所有这些项目都不会存储在 pg_class 中，以避免膨胀。

可见性映射需要为每个段存储以下状态

  • 0x01 READ_WRITE_ALLOWED 或 EFFECTIVE_READ_ONLY
  • 0x02 PENDING_READ_ONLY
  • 0x04 MARKED_READ_ONLY
  • 0x08 备用状态标志

因此，我们需要为每个段存储 4 位

relfrozenxids 需要每个段 4 个字节。我们还将在 pg_class 上为每个表存储 relfrozenxid，这是任何段的最小值。这主要由自动清理检查，以查看何时启动 vac 冻结。

段边界值将存储在统计表中，作为直方图值的一部分。这将允许它们用作规划的直方图。（XXX 需要更多考虑存储方式 - 我们希望规划器使用这些值作为统计信息，但我们也希望使其易于访问，此外，我们不希望 ANALYZE 覆盖它们）

段聚合也可以存储。reltuples 将需要一个整数数组。

取消设置可见性映射

对于 EFFECTIVE_READ_ONLY，INSERT、UPDATE 和 DELETE 仍然可以执行。对于 MARKED_READ_ONLY，它将被明确拒绝。

将段设置为 EFFECTIVE_READ_ONLY 引起的 relcache 失效可能会刷新每个后端中关系的 rd_targBlock。其他 INSERT 不可执行，因为所有当前代码路径都在表非空时使用扩展或 FSM，并且它们都不会造成问题。扩展只触及最后一个段，它永远不会是 EFFECTIVE_READ_ONLY。FSM 不包含 EFFECTIVE_READ_ONLY 段的任何条目。

可以在 EFFECTIVE_READ_ONLY 段上执行 UPDATE 或 DELETE，但我们预计这种情况很少发生。如果发生这种情况，我们将简单地重置表的可见性映射。这可以使用非事务性覆盖来处理 - 位已经存在，因此覆盖的数据始终具有相同的大小。这比较悲观，因为它即使在 UPDATE/DELETE 终止时也会重置状态，但它比将行锁定到事务完成，这可能会阻止其他事情发生，要好得多。我们可能还想让 VACUUM 清理所有已中止的事务。

用户可能还希望清除非常旧的数据，因此允许 DELETE 可以确保用户仍然可以从表中删除旧数据。通过仔细选择要删除的值，可以删除整个段，然后将其返回到 FSM。

运行巨大的 DELETE 很可能会执行一个 SeqScan，它只避免了要删除的数据。随后的 VACUUM 也会忽略其他段，因此与现在相比，删除较旧的数据似乎已经得到了很好的优化。可以优化它以执行段级截断，但由于分区已经改进了 DELETE 和 VACUUM，所以我还没有提议这样做，如果有的话。

SHARE 锁当前写入数据块，但由于它们表示瞬态状态，因此我们不需要取消设置分区或可见性映射。

实用程序

有可能是也可能是理想的，要有一个段感知的 CLUSTER。这将要求我们在可见性映射中使用另一个标志来指示聚类和非聚类。它还要求我们重建引用聚类的索引部分，这将需要全表锁。需要一个在线版本的 CLUSTER 来使此工作正常进行。

与可见性映射提案的重叠

此提案提供了早期可见性映射提案的许多优点，但无需对堆结构进行重大更改。由于段级可见性映射更细粒度，因此其有效性仅为更详细的块级映射的 80%。话虽如此，簿记开销也会大大减少，因此它似乎是一个很好的联合方法。它还允许完全处理冻结，这是原始可见性映射提案的一个问题。现在，WAL 日志记录可见性映射更改也变得容易得多。

我的想法是直接针对分区，但我必须承认，这个想法是重叠的，在我的世界观中，它取代了可见性映射提案。我非常喜欢可见性映射这个名字。我已经重新阅读了之前的线程，并同意 Jeff Davis 的观点，即我们*可以*有多种可见性映射，但也同意 Heikki 的观点，即这似乎工作量太大。我从未打算在一个提案中解决这两个挑战，这纯粹是巧合，或者可能只是运气，具体取决于你如何看待这个提案。

如果我们确实需要区分这两个提案，我们可以将这个称为段可见性映射（SVM）。

索引扫描

仅索引扫描将查看可见性映射，就像它们在早期提案中所做的那样。

对于索引扫描而言，反复检查可见性映射成本很高，但这样做可能值得。

其他更改

我们可以通过扫描表的非 100% 可见段来处理 select count(*)，然后将每个段的存储计数加起来得到最终总数。不确定它是否真的值得做，但它确实听起来像一个额外的奖励。

选择性估计和计划成本将存在额外的复杂性。上述提案允许动态段排除，无论如何都无法在计划时进行评估，因此欢迎提出建议...

我认为，在 VACUUM 上有一个覆盖选项会很谨慎，允许我们完整地扫描表，进行检查而不是使用可见性映射。此模式将被称为 VACUUM CHECK。

上述内容都不会阻止对只读表的早期提案，这两个功能可以非常直接地协同工作。

与其他分区方法的比较

一旦我意识到这可以用相当自动的方式实现，我就努力避免手动覆盖、命令和新的 DDL。

声明式分区开销很大，尽管对于大型数据库来说值得。没有开销*要*好得多。

这种分区方法解决了以下挑战

  • 允许自动表扩展，因此可以与 Slony 自动配合使用
  • 动态响应数据变化
  • 允许稳定函数、嵌套循环连接和参数化查询
  • 允许通过 SHARE 锁进行 RI
  • 避免需要通过 Append 节点进行操作符下推
  • 允许唯一索引
  • 允许全局索引（因为我们只有一个表）
  • 允许使用只读/可见数据进行高级规划/执行
  • 自然地与同步扫描和缓冲区回收配合使用

到目前为止，我提出的所有其他方法都需要花费相当长的时间来完成所有这些操作...

是的，这与早期讨论的结论不同，尤其是 2005 年的那些讨论，当时我仍在考虑声明式分区。

测试此方法是否适合您的应用程序

可能值得检查现有的应用程序，看看它们迁移到分段表方法的效果如何。以下查询将分析表的某一列，以生成边界值的列表，假设段大小为 131072 个块（1 GB）。

select substr(ctid::text,2,strpos(ctid::text,',')-2)::integer/131072 as seg, min(PrimaryKey), max(PrimaryKey) from bigtable group by seg;

我们应该能够很容易地看到这是否适用于现有的用例。

您可以更改段大小，但我预计分区数量的实际限制为 10-20,000，最大现实大小为 2-5,000 个分区。因此请更改段大小，但不要在大型表上更改得太小。

请注意，段大小可以更改，但需要对表进行完整的 VACUUM 才能重置隐式约束。（我们也可以优化这一点，但不要抱太大希望）。

结论

总体目标是允许我们更轻松地管理超过 10TB 的数据

此技术对于任何以日期或时间戳为键的历史数据表都很有用。它也适用于数据插入时间组件是隐式的，例如许多主要实体表，其中对象 ID 由序列分配。例如，订单表，其中 OrderId 作为主键。一旦在某个时间段内下的所有订单都已发货/解决/关闭，那么这些段将被标记为只读。

它不会真正改变小型表的代码路径，但似乎有可能在各种形状和大小的大型表上都能运行得很好。如果正在更新一个段，我们将保留它，并且可能永远不会实际设置可见性映射。因此，总的来说，这个想法似乎很好地涵盖了主要用例，但对我们支持的现有用例的影响很小。

取自 "https://wiki.postgresql.ac.cn/index.php?title=Segment_Exclusion&oldid=35385"