11

我正在阅读 Hadoop：Tom White 的权威指南。在第 13.6 章“HBase 与 RDMS”中，他说如果你有大量数据，即使是像获取 10 个最近的项目这样的简单查询也非常昂贵，他们必须使用 python 和 PL/SQL 重写它们。

他以以下查询为例：

SELECT id, stamp, type FROM streams 
WHERE type IN ('type1','type2','type3','type4',...,'typeN')
ORDER BY stamp DESC LIMIT 10 OFFSET 0;

并说：“RDBMS 查询计划器按如下方式处理此查询：

MERGE (
  SELECT id, stamp, type FROM streams
    WHERE type = 'type1' ORDER BY stamp DESC,
  ...,
  SELECT id, stamp, type FROM streams
    WHERE type = 'typeK' ORDER BY stamp DESC
) ORDER BY stamp DESC LIMIT 10 OFFSET 0;

这里的问题是我们只关注前 10 个 ID，但查询计划器实际上实现了整个合并，然后在最后进行限制。.... 实际上，我们甚至编写了一个执行堆排序的自定义 PL/Python 脚本。...在几乎所有情况下，这都优于本机 SQL 实现和查询计划器的策略...

预期性能和实验结果

我无法想象数据集会导致您必须编写 pl/python 才能正确执行如此简单的查询。所以我玩了一段时间关于这个问题并提出了以下意见：

这种查询的性能受到 O(KlogN) 的限制。因为它可以翻译成这样的东西：

SELECT * FROM (
  SELECT id, stamp, type FROM streams
    WHERE type = 'type1' ORDER BY stamp DESC LIMIT 10,
  UNION
  ...,
  SELECT id, stamp, type FROM streams
    WHERE type = 'typeK' ORDER BY stamp DESC LIMIT 10
) t ORDER BY stamp DESC LIMIT 10;

（注意每个查询中的'LIMIT 10'。顺便说一句，我知道我不能限制和订购联合，但为了便于阅读，我已经去掉了包装选择）

每个子查询的运行速度应该与在索引 O(logN) 中找到正确位置并返回 10 个项目一样快。如果我们重复 K 次，我们得到 O(KlogN)。

即使查询计划器非常糟糕以至于它无法优化第一个查询，我们也可以始终将其转换为带有联合的查询并获得所需的性能，而无需在 pl/python 中编写任何内容。

为了仔细检查我的计算，我在一个填充了 9,000,000 条测试记录的 postgresql 上运行了查询。结果证实了我的预期，两个查询都非常快，第一个查询为 100 毫秒，第二个查询为 300 毫秒（带有联合的查询）。

因此，如果查询在 100 毫秒内运行 9,000,000 (logn=23) 条记录，那么对于 9,000,000,000 (logn=33) 条记录，它应该在 140 毫秒内运行。

问题

  • 您在上述推理中发现任何缺陷吗？
  • 你能想象一个需要在 pl/python 中重写上述查询的数据集吗？
  • 您是否看到这种查询在 O(K log n) 中不起作用的任何情况？
4

4 回答 4

6

他们断言 RDMBS 查询规划器采用该查询解决方案是不正确的，至少对于 Postgresql 9.0，我也应该想象其他平台。我用类似的查询做了一个快速测试：

explain select * from client_attribute where client_attribute_type_code in ('UAG', 'RFR', 'IPA', 'FVD') order by client_attribute_id desc limit 10;

                                                      QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..0.93 rows=10 width=85)
   ->  Index Scan Backward using client_attribute_pkey on client_attribute  (cost=0.00..15516.47 rows=167234 width=85)
         Filter: (client_attribute_type_code = ANY ('{UAG,RFR,IPA,FVD}'::bpchar[]))
(3 rows)

这里 client_attribute_id 被索引，所以它完全按照需要做 - 遍历索引，应用过滤器并在输出达到限制时停止。

如果排序列没有索引，则需要进行表扫描和排序，但只需进行一次表扫描：

explain analyze select * from client_attribute where client_attribute_type_code in ('UAG', 'RFR', 'IPA', 'FVD') order by updated desc limit 10;

                                                              QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=13647.00..13647.03 rows=10 width=85) (actual time=180.961..180.964 rows=10 loops=1)
   ->  Sort  (cost=13647.00..14065.09 rows=167234 width=85) (actual time=180.960..180.961 rows=10 loops=1)
         Sort Key: updated
         Sort Method:  top-N heapsort  Memory: 26kB
         ->  Seq Scan on client_attribute  (cost=0.00..10033.14 rows=167234 width=85) (actual time=0.010..106.791 rows=208325 loops=1)
               Filter: (client_attribute_type_code = ANY ('{UAG,RFR,IPA,FVD}'::bpchar[]))

这使用堆排序来在顺序扫描过程中维护前 10 个结果，这听起来与他们自己编写的解决方案完全一样。

于 2010-11-27T16:36:04.183 回答
4

我不认为 Tom White 是在说关系数据库“不好”。它们对于非关系、非基于集合的数据并不是最优的。

长期以来，众所周知，深度对象图不适合关系数据库。它们通常出现在几何数据的 CAD 表示等问题中，其中装配由零件装配的装配组成。参考链确实很长。

自从我在 90 年代初就意识到它们以来，对象和图形数据库一直是此类问题的解决方案。

关系数据库非常适合基于集合的关系数据。但并非所有数据都属于该类别。这就是 NoSQL 越来越受欢迎的原因。

我认为这就是您引用的示例所说的。

于 2010-11-26T23:11:53.820 回答
1

使用 SQL 或 NoSQL，如果您以错误的方式设计查询，性能将会很糟糕。

我将通过在 where 子句中添加对时间戳的检查来修复该示例。如果您有大量数据，您可能会假设最近的 10 个条目来自最后一分钟 - 那么为什么要尝试阅读和排序上个月的所有内容呢？

我可以通过声称因为默认情况下只能通过 ID 查找记录，所以我可以轻松地设计相同的示例来使 NoSQL 看起来很糟糕，因此您需要加载整个数据集才能找到所需的记录，而忽略设置各种辅助的能力/custom 索引可以让您获得比重要查询更好的 SQL 性能。

于 2010-11-27T00:28:09.540 回答
1

RDBMS 适用于您没有想到的查询。一旦你确定了你想要什么，你就可以应用最优化的解决方案。

于 2010-11-26T23:31:51.003 回答