如何保证 Postgres 中的递归 CTE 至少返回 N 行
How to guarantee that at least N rows are returned by recursive CTE in Postgres
大多数描述 Postgres 中的 SELECT TOP ... 查询的资源都说您应该使用 LIMIT 代替，如果您需要 select 顶部，则可能使用 ORDER BY 子句一些排序的元素。
如果您需要 select 递归查询中的前 N 个元素，您会怎么做，其中没有排序并且查询可能 return 少于 N 行而不递归（因此 TOP 部分是确保结果集 至少 N 行所必需的，而 LIMIT 可以允许更少的行）？
我的具体用例是 dynamic SQL pattern for selecting a random subsample of a table.
的修改
这是我修改的link to the sql source。最简单的事情是查看那里定义的最终函数，_random_select。它与上面的 link 非常接近，但是在输入 table 和输出结果集中被修改为多态的，并且正确地考虑了只需要 return 列已经存在于输入 table 中（另一个动态 SQL hack 从最终结果集中排除临时 row_number 结果）。
它有点碍眼，但它是我所拥有的最接近可重现示例的东西。如果您使用 _random_select 并尝试从大于 4500 行的 table 中获取大约 4500 行的内容，您开始看到更小的结果集的可能性很高，并且随着您增加的大小，情况只会变得更糟您想要的样本（因为随着您想要的样本变大，重复的情况会变得更糟）。
请注意，在我的修改中，我没有使用此 link 中的 _gaps 技巧，如果某个索引列中存在间隙，则意味着过度采样以抵消采样效率低下。那部分与这个问题无关，在我的例子中，我使用 row_number 来确保存在一个没有可能间隙的整数列。
CTE 是递归的，以确保如果 CTE 的第一个非递归部分没有为您提供足够的行（因为 UNION 删除了重复项），那么它将返回通过 CTE 的另一轮递归调用，并继续处理更多结果，直到获得足够的结果。
在 linked 示例中，使用了 LIMIT，但我发现这不起作用。该方法 return 结果较少，因为 LIMIT 只是 最多 N 行 保证。
如何保证至少 N 行？选择 TOP N 行似乎是执行此操作的自然方式（因此递归 CTE 必须继续前进，直到它获得足够的行来满足 TOP 条件），但这在Postgres。
可以使用 Set Returning Functions (SRF) 生成已知行数。此外，OUTER 加入保证，加入的一侧将全部返回。
在这种情况下，我假设 FULL JOIN 在 generate_series(1, 100) 之间（如果您的目标是 至少 100 行）应该可以解决问题。事实上，LEFT join 也可以解决这个问题，但它可能会过滤掉实际需要的额外行，因此我会选择 FULL.
P.S。如果你能展示你的代码，提供一些例子会更容易。
这对于评论来说太长了，但可以提供有关我现有查询的情况的信息。从 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 之后）大部分是在正确的轨道上。
如文档所述，这实际上只是一种迭代，它重新使用先前的非递归结果部分代替递归名称用于递归部分。
所以它更像是一个不断缩小的过程，其中用于替代递归名称的“工作 table”仅包含最近一轮递归的特定结果子集 不是以前结果的重复。
这是一个例子。假设我们在 table 中有 5000 行并且我们想要对 3000 个唯一行进行采样，一次对 1000 个（可能不是唯一的）样本进行递归采样。
我们做了第一批 1000 个，删除了重复项，所以对于这些大数字（N=5000，m = 1000，k=1，重新排列项以避免溢出）。
这些 818 成为工作 table 并且这个结果集被替换为我们下一次传递的递归项。我们绘制了另一组大约 818 行的唯一行，但在与工作 table 中的原始 818 行进行比较时，必须删除重复项 (UNION)。两次不同的 818 随机抽取将有明显的重叠（平均大约 150），因此所有这些都被丢弃并且任何 new 独特的行仍然成为 new 工作 table.
所以你会在第一次抽取时添加大约 818 个独特的样本，然后工作 table 缩小，你将在第二次抽取大约 650 个，工作 table 缩小，.. . 你一直这样做，直到达到所需的总样本数（在本例中为 3000） 或 工作 table 最终为空。
一旦 working table 足够小，在下一次抽取 1000 时，其中的所有内容很有可能被复制，此时 working table 变为空并且递归终止。
对于绘制 3000 个样本，您可能能够完成此工作 table 更新足够的次数。但是当你从 3000 接近 table 的总规模 5000 时，概率会很快缩小到几乎为零。
因此，这不是优化器问题，它与较小的结果集短路，实际上是 Postgres 中实现“递归”的特定方式的问题——它实际上不是递归，而是简单的迭代操作当前工作 table 和最近的递归查询结果集之间的集合差异。对于像这样的随机抽样，工作 table 将随着每次迭代非常快地变小，直到由于选择重复项的可能性很高而极有可能为空。
您的评价很中肯。 my referenced answer中的递归查询只是比原来的简单查询灵活了一些。它仍然需要 ID space 中相对较少的间隙和比 table 大小小得多的样本量才能可靠。
虽然我们在简单查询中需要一个舒适的table 盈余 ("limit + buffer") 来涵盖遗漏和重复的最坏情况，但我们可以使用通常足够的较小盈余 - 因为我们有一个递归查询的安全网，如果我们在第一遍中没有达到限制，它将被填充。
无论哪种方式，该技术旨在快速从大量 table 中随机选择少量内容。
对于间隙过多或（您的重点）的情况，该技术毫无意义样本大小太接近总 table 大小 - 因此递归项可能 运行 在达到限制之前变干。对于这种情况，一个普通的旧的：
SELECT * -- or DISTINCT * to fold duplicates like UNION does
FROM TABLE
ORDER BY random()
LIMIT n;
.. 效率更高：无论如何你都会阅读大部分 table。
大多数描述 Postgres 中的 SELECT TOP ... 查询的资源都说您应该使用 LIMIT 代替，如果您需要 select 顶部，则可能使用 ORDER BY 子句一些排序的元素。
如果您需要 select 递归查询中的前 N 个元素，您会怎么做，其中没有排序并且查询可能 return 少于 N 行而不递归（因此 TOP 部分是确保结果集 至少 N 行所必需的，而 LIMIT 可以允许更少的行）？
我的具体用例是 dynamic SQL pattern for selecting a random subsample of a table.
的修改这是我修改的link to the sql source。最简单的事情是查看那里定义的最终函数，_random_select。它与上面的 link 非常接近，但是在输入 table 和输出结果集中被修改为多态的，并且正确地考虑了只需要 return 列已经存在于输入 table 中（另一个动态 SQL hack 从最终结果集中排除临时 row_number 结果）。
它有点碍眼，但它是我所拥有的最接近可重现示例的东西。如果您使用 _random_select 并尝试从大于 4500 行的 table 中获取大约 4500 行的内容，您开始看到更小的结果集的可能性很高，并且随着您增加的大小，情况只会变得更糟您想要的样本（因为随着您想要的样本变大，重复的情况会变得更糟）。
请注意，在我的修改中，我没有使用此 link 中的 _gaps 技巧，如果某个索引列中存在间隙，则意味着过度采样以抵消采样效率低下。那部分与这个问题无关，在我的例子中，我使用 row_number 来确保存在一个没有可能间隙的整数列。
CTE 是递归的，以确保如果 CTE 的第一个非递归部分没有为您提供足够的行（因为 UNION 删除了重复项），那么它将返回通过 CTE 的另一轮递归调用，并继续处理更多结果，直到获得足够的结果。
在 linked 示例中，使用了 LIMIT，但我发现这不起作用。该方法 return 结果较少，因为 LIMIT 只是 最多 N 行 保证。
如何保证至少 N 行？选择 TOP N 行似乎是执行此操作的自然方式（因此递归 CTE 必须继续前进，直到它获得足够的行来满足 TOP 条件），但这在Postgres。
可以使用 Set Returning Functions (SRF) 生成已知行数。此外，OUTER 加入保证，加入的一侧将全部返回。
在这种情况下，我假设 FULL JOIN 在 generate_series(1, 100) 之间（如果您的目标是 至少 100 行）应该可以解决问题。事实上，LEFT join 也可以解决这个问题，但它可能会过滤掉实际需要的额外行，因此我会选择 FULL.
P.S。如果你能展示你的代码，提供一些例子会更容易。
这对于评论来说太长了，但可以提供有关我现有查询的情况的信息。从 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 之后）大部分是在正确的轨道上。
如文档所述，这实际上只是一种迭代，它重新使用先前的非递归结果部分代替递归名称用于递归部分。
所以它更像是一个不断缩小的过程，其中用于替代递归名称的“工作 table”仅包含最近一轮递归的特定结果子集 不是以前结果的重复。
这是一个例子。假设我们在 table 中有 5000 行并且我们想要对 3000 个唯一行进行采样，一次对 1000 个（可能不是唯一的）样本进行递归采样。
我们做了第一批 1000 个，删除了重复项，所以对于这些大数字（N=5000，m = 1000，k=1，重新排列项以避免溢出）。
这些 818 成为工作 table 并且这个结果集被替换为我们下一次传递的递归项。我们绘制了另一组大约 818 行的唯一行，但在与工作 table 中的原始 818 行进行比较时，必须删除重复项 (UNION)。两次不同的 818 随机抽取将有明显的重叠（平均大约 150），因此所有这些都被丢弃并且任何 new 独特的行仍然成为 new 工作 table.
所以你会在第一次抽取时添加大约 818 个独特的样本，然后工作 table 缩小，你将在第二次抽取大约 650 个，工作 table 缩小，.. . 你一直这样做，直到达到所需的总样本数（在本例中为 3000） 或 工作 table 最终为空。
一旦 working table 足够小，在下一次抽取 1000 时，其中的所有内容很有可能被复制，此时 working table 变为空并且递归终止。
对于绘制 3000 个样本，您可能能够完成此工作 table 更新足够的次数。但是当你从 3000 接近 table 的总规模 5000 时，概率会很快缩小到几乎为零。
因此，这不是优化器问题，它与较小的结果集短路，实际上是 Postgres 中实现“递归”的特定方式的问题——它实际上不是递归，而是简单的迭代操作当前工作 table 和最近的递归查询结果集之间的集合差异。对于像这样的随机抽样，工作 table 将随着每次迭代非常快地变小，直到由于选择重复项的可能性很高而极有可能为空。
您的评价很中肯。 my referenced answer中的递归查询只是比原来的简单查询灵活了一些。它仍然需要 ID space 中相对较少的间隙和比 table 大小小得多的样本量才能可靠。
虽然我们在简单查询中需要一个舒适的table 盈余 ("limit + buffer") 来涵盖遗漏和重复的最坏情况，但我们可以使用通常足够的较小盈余 - 因为我们有一个递归查询的安全网，如果我们在第一遍中没有达到限制，它将被填充。
无论哪种方式，该技术旨在快速从大量 table 中随机选择少量内容。
对于间隙过多或（您的重点）的情况，该技术毫无意义样本大小太接近总 table 大小 - 因此递归项可能 运行 在达到限制之前变干。对于这种情况，一个普通的旧的：
SELECT * -- or DISTINCT * to fold duplicates like UNION does
FROM TABLE
ORDER BY random()
LIMIT n;
.. 效率更高：无论如何你都会阅读大部分 table。