估计 DISTINCT
此页面描述了可能改进 DISTINCT 值数量估计的方法。最初，这是 实现跨列统计的努力 的副作用，因为其中一种提议的方法需要更精确的 DISTINCT 估计，但由于某种原因它是单独的努力，因此我创建了单独的页面。
基于采样的估计器
统计学中的传统估计器是基于小样本（例如总体的 1%）。这在 DISTINCT 值的情况下效果很好，除非对表的大部分进行采样（参见下一节）。
Charikar 和 Chaudhuri
在他们发表的论文（2000 年）中，他们指出并证明了基于采样的估计器是死胡同。他们证明的定理（定理 1）基本上说，对于每个基于小样本的估计，都存在一个数据集，其中比率误差可以任意变大。定理有点复杂（将样本量、最大误差和获得此类数据集的概率联系起来），但最终它表明，你无法基于小样本获得良好的估计器。如果将一个估计器替换为另一个，则可能会修复一个数据集的行为，但存在另一个数据集。
JOSH BERKUS：抱歉，那篇论文没有说以上内容。请再读一遍。它说完美的基于样本的估计是不可能的……但完美的基于蒸汽的估计也是不可能的。总的来说，这篇论文说，通过了解足够的知识来根据预期误差分布类型选择样本算法，可以减少所需的样本量或误差率，并且在没有此知识的情况下，降低误差率是困难的。另外，我要指出 2000 年绝不是样本估计论文的终点。
他们提供“最佳估计器”，它始终如一地达到比率误差的下限，但总的来说，存在更好的估计器（尽管对于某些数据集，它们的失败更为严重）。
TOMAS VONDRA：但这就是那个定理的关键所在。他们基本上说“对于每个基于样本的估计器，我们将给你一个数据集，其中它的失败误差与样本量成反比（即样本量越小，误差越大）”。当然，对于某些输入，存在比提议的“最佳估计器”性能更好的估计器，但最佳估计器的妙处（和目的）在于它对于所有可能的数据集都是一致的。
基于流的估计器
数据库不是唯一需要 DISTINCT 值数量的领域 - 另一个需要此数据的领域是数据流分析。提议的估计器是基于对数据的单遍遍历以及位图的增量更新 - 第一个这样的估计器是基于概率计数，下一个是基于 Wegman 的自适应采样等。在 2010 年，描述了一种具有任意精度和 O(log(n)) 空间复杂度的算法 - 这非常有希望。
它与 布隆过滤器 非常相似，但布隆过滤器需要更多空间并提供更多信息 - 它旨在识别集合中的元素（在本例中为 DISTINCT 值）。这与概率计数等中使用的位图不同。
Gibbons 在 2001 年描述了一种非常有趣的方法，称为 DISTINCT 采样。不要被“采样”所迷惑 - 它不是随机采样，而是基于对数据的单遍遍历中的自适应样本选择（原理与 Wegman 的自适应采样非常相似）。该算法需要更多空间，但它可以提供对“满足谓词 P 的 DISTINCT 值有多少”等问题的估计，而“简单”算法无法做到这一点。
所以这更有意思，但也有一些缺点。首先，这些估计器需要对数据进行单遍遍历（然后进行增量更新），这与当前的估计器完全不同。其次，这些估计器是为“数据流”设计的，在默认情况下没有删除。一些算法确实描述了一些解决方案。
论文
这是一个与 DISTINCT 估计相关的论文列表，分为三个部分。论文始终按从最新到最旧的顺序排序。如果您知道任何未在此列出的有趣论文，请随时将其添加在此处。
采样论文
- 用于 DISTINCT 值的估计误差保证 PDF
- 发表时间：2000 年
- 作者：Moses Charikar、Surajit Chaudhuri、Rajeev Motwani、Vivek Narasayya
- 提供了一个证明，即使用有限的样本，你实际上无法获得精确的估计（误差有限）。
- 换句话说：对于每个基于有限样本的估计，存在一个概率分布，其中该估计器会严重失败。
- 因此，要获得良好的估计，你实际上需要对大部分表（几乎全部）进行采样。
- 他们提供了一个“最佳估计器”（由几个简单估计器组成的混合估计器），因为它达到了最低可能的误差（在基于采样的估计器中）。
- 估计有限总体中的类别数量 citeseerx PDF
- 发表时间：1996 年
- 作者：Peter J. Haas、Lynne Stokes
- 提供了几个基于采样的估计器，我们目前正在使用其中一个（D_uj1）。
- 基于采样的属性 DISTINCT 值数量估计 PDF
- 发表时间：1995 年
- 作者：Peter J. Haas、Jeffrey F. Naughtont、S. Seshadrit、Lynne Stokes
- 提供了几个基于采样的估计器，并对它们进行了比较等。
- 这比 Haas/Stokes 的文章早一年，所以请阅读那篇。
流论文
- 用于 DISTINCT 元素问题的最佳算法 citeseerx PDF
- 发表时间：2010 年（PODS’10，2010 年 6 月 6 日 - 11 日）
- 作者：Daniel M. Kane、Jelani Nelson、David P. Woodruff
- 基本上是“概率计数”的改进版本（参见 P. Flajolet 和 G. N. Martin 的论文）。
- 他们提出了一个空间复杂度为 O(log(n)) 位，更新复杂度为 O(1) 的算法。
- 可以通过组合几个这样的估计器来提高精度。
- 数据流上的 DISTINCT 值估计 PDF
- 发表时间：2009 年
- 作者：Phillip B. Gibbons
- 这是一个关于可能方法的非常好的总结 - 关于基于采样的算法的简短段落，以及为什么它是一个死胡同，关于基于流的算法的更深入分析（Flajolet-Martin 概率计数算法，然后是来自 Alon、Matias 和 Szegedy 的另一种算法），以及关于“协调采样”的部分。
- 有一个非常好的表格，总结了各种算法的功能（是否具有 DISTINCT 值样本，是否以某种方式处理删除等）。
- 使用自学习位图进行 DISTINCT 计数 PDF
- 发表时间：2009 年
- 作者：Aiyou Chen、Jin Cao
- 他们描述了一种使用位图进行自适应采样的算法。
- 该算法基于马尔可夫链模型，但总的来说，它似乎与 Wegman 的自适应采样类似（参见 1990 年的论文）。
- 用于对 DISTINCT 值查询和事件报告进行高精度回答的 DISTINCT 采样 citeseerx PDF
- 发表时间：2001 年
- 作者：Phillip B. Gibbons
- 虽然标题说是“采样”，但这篇论文不是关于传统采样（从表中收集一个小的随机样本，然后从它计算一个估计），而是关于从数据流（对表的单遍遍历）中收集一个样本，并选择一个“DISTINCT 样本”。
- 这不仅提供了对 DISTINCT 行数量的估计，还提供了对行上任意谓词的 DISTINCT 值的估计。
- 看起来很有趣，虽然它需要的跨度比其他“概率计数”算法多得多。
- 关于自适应采样 citeseerx PDF
- 发表时间：1990 年
- 作者：Philippe Flajolet
- 提出了基于 Wegman 的自适应采样的概率计数的替代算法。
- 该算法的精度低于原始概率计数算法，但对于小文件（无偏）来说更好。
- 数据库应用的概率计数算法 citeseerx PDF
- 发表时间：1985 年
- 作者：Philippe Flajolet、G. Nigel Martin
- 这是关于此主题的第一篇论文，描述了一个基本算法和一个改进的“随机”版本（PCSA）。
- 包括对定理等相当彻底的证明。
相关论文
- 针对一组属性的 DISTINCT 值组合数量的估计 PDF
- 发表时间：2005 年
- 作者：Xiaohui Yu、Calisto Zuzarte、Kenneth C. Sevcik
- 这篇论文不是关于估计各个列的 DISTINCT 值数量，而是关于使用其分布的知识（或直方图形式的近似）估计多个列的组合。
- 他们提出的算法称为 COLSCARD。
- 这篇论文的一个重大缺点是，他们假设列是独立的，但似乎可以通过使用多维直方图来解决这个问题（只需将分布的乘积替换为直方图中的值）。
- 如果我们无法使用某些“流”解决方案，这可能是一种方法（在这种情况下，我们可以很容易地收集有关各个列的信息，以及有关有趣的组合的信息）。
