问题标签 [cardinality-estimation]

Flajolet 等人的HyperLogLog 算法描述了一种仅使用少量内存来估计集合基数的巧妙方法。但是，它确实在计算中考虑了原始集合的所有 N 个元素。如果我们只能访问原始 N 的一小部分随机样本（例如 10%）怎么办？有没有研究过 HyperLogLog 或类似算法如何适应这种情况？

我知道这本质上是描述为不同价值估计的问题，对此存在大量研究（例如，请参阅本文以获取概述）。然而，据我所知，对不同价值估计的研究使用了许多与 HyperLogLog 使用的方法非常不同的临时估计器。因此，我想知道是否有人已经考虑过将 HyperLogLog 用于不同的值估计问题。

我试图理解这个草图，但无法理解。如果我错了，请纠正我，但基本上，假设我有一个文本数据..单词..我有一个散列函数..它需要一个单词并创建一个整数散列，然后我将该散列转换为二进制位向量？对.. 然后我跟踪我从左边看到的第一个 1.. 那个 1 的位置（比如说，k）......这个集合的基数是 2^k？

http://ravi-bhide.blogspot.com/2011/04/flajolet-martin-algorithm.html

但是……说我只有一个字。并且它的散列函数使得它生成的散列是2 ^ 5，那么我猜有5个（？？）尾随0？所以它会预测 2^5 (??) 基数？这听起来不对？我错过了什么

我有一个数据仓库数据库，我在使用 SQL Server 2014 的新基数估计器时遇到问题。

将数据库服务器升级到 SQL Server 2014 后，我观察到查询性能存在很大差异。一些查询的执行速度要慢得多（SQL 2012 为 30 秒，而 SQL 2014 为 5 分钟）。在研究了执行计划后，我发现 SQL Server 2014 上的基数估计值相差甚远，我找不到原因。

这是 SQL 2012 与 SQL 2014 中的查询执行计划（左上角运算符）的示例：

一些细节：

• 我的查询是典型的数据仓库事实表加载查询。我查询一个事务表并加入很多（15-20）个维度表（总是有 0 或 1 条记录从维度表中加入）。

• 我已经更新了所有表的统计信息（使用 FULLSCAN）以确保统计信息是最新的。

• 对维度表的业务键进行索引（唯一非聚集索引）。在我看来，由于这个索引的唯一性，旧的基数估计器（SQL 2012）正确地假设有最大值。1 条连接的记录（估计的记录数在执行计划中没有变化）。

我试图将问题缩小到最简单的示例——带有 2 个连接的 SELECT：

这是 SQL 2012 与 SQL 2014 中运算符 1 和 2 的基数估计：

如您所见，SQL Server 2014 与估计的差距超过 30%（10000 与 7653）。因为我有cca。在一个典型的查询中加入 15 到 20 个，最终的估计值相差甚远。

我可以将数据库置于较低的兼容性模式（110），然后它可以正常工作（就像在 SQL Server 2012 上一样），但我真的很想知道这种行为的原因是什么。为什么 SQL Server 2014 的基数估计结果错误？

我已将 Pre-Prod 服务器从 SQL Server 2012 升级到 SQL Server 2014 Sp1。

然而，这在很大程度上是好的，在我们简短的手动测试中，我们发现了一些问题，新的基数估计器在少数查询上显着降低了性能。（即以 110 或 (QUERYTRACEON 9481) 的数据库兼容模式运行相同的查询，并且相同的查询速度快如闪电）。

有没有一种（好的）方法可以从我们的高事务生产服务器中获取查询，并在我们的 Pre-Prod 服务器上对其进行大规模测试，以查看问题有多大以及哪些查询会受到影响，以便我们可以缓解它们？

谢谢，詹姆斯

在我们的生产环境中，我们有几台带有SQL server 2012 SP2+Windows Server 2008R2. 3 个月前，我们将所有服务器迁移到SQL Server 2014 SP1+Windows Server 2012 R1. 我们创建了具有新配置的新服务器（更多 RAM、更多 CPU、更多磁盘空间）并从SQL Server 2012--> 恢复到新SQL Server 2014服务器备份我们的数据库。恢复后，我们将兼容性级别从 110 更改为 120+Rebuild Index+Update 统计信息。

但是现在我们遇到了一些问题，当兼容性级别为 120 时，这些查询运行速度非常慢。如果我们将兼容性级别更改为旧的 110，它运行速度非常快。

我搜索了很多关于这个问题，但没有找到任何东西。

在不久的将来，当前当前的数据库基础架构将从 2008R2 迁移到 SQL Server 2017。

将所有数据库迁移到新服务器后，我想将兼容级别升级到 140。这是为了利用 2017 年的新功能，例如自适应查询引擎。

然而，许多人警告说，这将对基数估计器和其他特征产生影响。

我如何测试更改兼容性级别的影响，以确保更改几乎没有影响？

我在 hazelcast 中获得基数服务时遇到问题。在下面的代码中，我向基数估计器添加了一些访问者。messageID是唯一的。在此代码填充 5K 唯一项的测试环境中。

在另一个类中的viewsList到期时，我编写了侦听器代码。入口事件键是之前代码中的 messageID。但是当调用这个函数时，访问为0。似乎它得到了另一个空对象。

我试图理解为什么 Flajolet-Martin 算法 (FM) 工作时间过长。这里对算法的描述（第 4.4.2 节）很有希望，但并不完美。

为什么任何元素的最大尾部长度（尾随零的数量）可以作为流中不同元素数量的估计值？想象一下只有两个不同的元素 {1,2}，它们分别散列到 {10001, 10000}。这意味着不同元素的数量是 2^4，这显然是不正确的。

有什么诀窍？

我有一个以每分钟几百万的速度通过我的服务集群的传入值流。我想计算在给定时间范围内通过所有实例的唯一值。我正在查看 Hazelcast 的基数估计器来完成这项工作，但我不确定这是否会成为瓶颈，因为更新分布式数据结构中的值需要时间。是否有允许 Hazelcast 创建本地实例作为缓冲区的配置？或者也许是一种处理如此高的吞吐量收入率的方法。

我被困住了，似乎没有找到任何有用的文档。

设想：

-2 列正在连接，每列都有直方图。

- 左列有 1 个 bin，在 [1,5] 范围内有 3 个不同的值，总共出现 30 次。当我们假设 bin 内的一致性时，这 3 个未知值各有 1/10 的机会。

- 右栏有单独的频率（值：频率）：1:10、2:50、3:50、4:500、5:100.. 1 出现 10 次，2 出现 50 次......

估计连接选择性的正确方法是什么？