sql - 如何保证 Postgres 中的递归 CTE 至少返回 N 行

Question

大多数描述 Postgres 中的 SELECT TOP ... 查询的资源都说您应该使用 LIMIT 代替，可能使用 ORDER BY子句，如果您需要按某种顺序选择顶部元素。

如果您需要从递归查询中选择前 N 个元素，您会怎么做，其中没有排序，并且查询有可能在没有递归的情况下返回少于 N 行(以便 TOP 部分是确保结果集至少 N 行所必需的，而 LIMIT 可以允许更少的行)？

我的具体用例是对 dynamic SQL pattern for selecting a random subsample of a table 的修改.

这是一个link to the sql source我的修改。最简单的事情是查看那里定义的最终函数，_random_select。它非常接近上述链接，但已被修改为在输入表和输出结果集中是多态的，并且正确地考虑了只返回输入表中已经存在的列的需要(另一个动态 SQL hack 以从最终结果集中排除临时 row_number 结果)。

虽然有点碍眼，但它是我所拥有的最接近可重现示例的东西。如果您使用 _random_select 并尝试从大于 4500 行的表中获取大约 4500 行的内容，您开始看到更小的结果集的可能性很高，并且随着您增加您的大小，情况只会变得更糟所需的样本(因为随着所需样本的增加，重复项的出现会变得更糟)。

请注意，在我的修改中，我没有使用此链接中的 _gaps 技巧，如果某个索引列中存在间隙，则意味着过度采样以抵消采样效率低下。那部分与这个问题无关，在我的例子中，我使用 row_number 来确保有一个没有可能间隙的整数列。

CTE 是递归的，以确保如果 CTE 的第一个非递归部分没有为您提供足够的行(因为 UNION 删除了重复项)，那么它将继续通过 CTE 的另一轮递归调用返回，并继续处理更多结果，直到您获得足够的结果。

在链接示例中，使用了 LIMIT，但我发现这不起作用。该方法返回的结果较少，因为 LIMIT 只是一个最多 N 行 保证。

如何保证至少 N 行？选择 TOP N 行似乎是执行此操作的自然方式(因此递归 CTE 必须继续前进，直到它获得足够的行来满足 TOP 条件)，但这在 Postgres 中不可用。

Answer 1

这对于评论来说太长了，但可以提供有关我现有查询的情况的信息。来自documentation on recursive query evaluation ，递归查询将采取的步骤是:

Evaluate the non-recursive term. For UNION (but not UNION ALL), discard duplicate rows. Include all remaining rows in the result of the recursive query, and also place them in a temporary working table.

So long as the working table is not empty, repeat these steps:

a. Evaluate the recursive term, substituting the current contents of the working table for the recursive self-reference. For UNION (but not UNION ALL), discard duplicate rows and rows that duplicate any previous result row. Include all remaining rows in the result of the recursive query, and also place them in a temporary intermediate table.

b. Replace the contents of the working table with the contents of the intermediate table, then empty the intermediate table.

所以我在评论中的直觉(在尝试使用 UNION ALL 之后)大部分是在正确的轨道上。

正如文档所述，这实际上只是一种迭代，它重新使用先前的非递归结果部分来代替递归名称递归部分。

所以它更像是一个不断缩小的过程，其中用于替代递归名称的“工作表”仅包含最近一轮递归结果的特定子集，不是先前结果的重复.

这是一个例子。假设我们在表中有 5000 行，我们想要对 3000 个唯一行进行采样，一次对 1000 个(可能不是唯一的)样本进行递归采样。

我们做了第一批 1000 个，删除重复项，所以我们最终得到大约 818 个非欺骗 based on the binomial distribution对于这些大数(N=5000，m = 1000，k=1，重新排列项以避免溢出)。

这 818 个成为工作表，这个结果集被代入作为我们下一次传递的递归项。我们绘制了另一组大约 818 个唯一行，但在与工作表中的原始 818 行进行比较时，必须删除重复项 (UNION)。两次不同的 818 随机抽取将有明显的重叠(平均大约 150)，因此所有这些都将被丢弃，而保留的任何新唯一行将成为新工作表。

因此，您将在第一次抽取时添加大约 818 个唯一样本，然后工作表缩小，第二次抽取时将增加约 650 个，工作表缩小，...您一直这样做，直到达到所需的总样本总数(在本例中为 3000)或工作表最终为空。

一旦工作表足够小，在下一次抽取 1000 时很有可能复制其中的所有内容，此时工作表变空，递归终止。

对于抽取 3000 个样本，您可能能够将此工作表更新足够多次。但是当您从 3000 接近表的总大小 5000 时，概率会非常快地缩小到几乎为零。

因此，这不是一个优化器问题，它与较小的结果集短路，这实际上是 Postgres 中实现“递归”的特定方式的问题——它实际上不是递归，而是在集合上运行的简单迭代当前工作表与最近的递归查询结果集之间的差异。对于像这样的随机抽样，工作表将随着每次迭代非常快地变小，直到由于选择重复项的可能性很高而极有可能为空。