3

在我们的在线竞赛系统中，有一个经常变化standings的整数列表格(user_id, score)。两者都使用唯一约束进行索引。需要两种查询：

  1. 给定一个score不在表中的值，返回从 1 开始的位置，如果它被插入，分数将占据的位置。
  2. 给定user_id表中的a，返回对应分数的位置。

在这两种情况下，位置都是相对于分数升序的：比表中当前所有分数小的新分数将具有位置 1。

这是困难的部分：我们可能负担不起表扫描。该表可能有多达 1000 万条记录，我们需要每秒处理至少 40 个查询。

如何在 PostgreSQL 中做到这一点？

我在 Berkeley DB 中有一个非 SQL 解决方案，它使用了支持逻辑记录号的 B 树。它很容易具有足够好的性能。但是我们想通过使用 PostgreSQL 查询重新实现来摆脱 BDB。我已经尝试了明显的

select 1+count(*) from standings where score < ? limit 1;

这会导致表扫描。

我希望答案是“不可能”，因为 BDB 的逻辑记录编号功能需要为每次编辑锁定整个 B 树。为了获得 O(log N) 的性能，它依赖于每个节点中的叶子数。root 路径中的所有这些计数都必须随着每次编辑而改变；因此，锁定。这种锁定违反了 PostgreSQL 的设计原则，并且可能违反了任何多用户数据库。

因此，如果问题不能用 PostgreSQL 解决，那么确认这一点是这个问题的下一个最佳结果。

4

1 回答 1

2

使用常规表，您在 PostgreSQL 9.1count()中无能为力。导致表扫描，因为索引没有可见性信息。为了验证这些行在此期间没有被删除，PostgreSQL 必须访问该表。

如果表是只读的（或很少更新），您可以向表中添加行号。然后是这样的查询：

SELECT rownumber+1
FROM   standings
WHERE  score < ?
ORDER  BY score DESC
LIMIT  1;

有一个索引：

CREATE INDEX standings_score_idx ON standings (score DESC);

几乎可以立即得到结果。但是，出于显而易见的原因，这不是具有写入负载的表的选项。所以不适合你。

好消息：即将推出的PostgreSQL 9.2的主要新特性之一正适合您：“覆盖索引”或“仅索引扫描”。我在这里引用 9.2 发行说明：

允许查询仅从索引中检索数据，避免堆访问（Robert Haas、Ibrar Ahmed、Heikki Linnakangas、Tom Lane）

这通常称为“仅索引扫描”或“覆盖索引”。正如可见性映射所报告的，这对于具有完全可见元组的堆页面是可能的。作为实现此功能的必要部分，可见性地图是防撞的。

Robert Haas 的这篇博客文章详细介绍了这如何影响计数性能。WHERE即使有一个子句，它也有助于提高性能，就像你的情况一样。

于 2012-07-24T04:59:12.187 回答