SQL查询索引/主键顺序 [英] SQL query for index/primary key ordinal

问题描述

在我们的在线比赛系统中，经常更改的表排名和整数列（user_id，得分）。两者都具有唯一约束。需要两种查询：

In our on-line contest system, there is a frequently changing table standings with integer columns (user_id, score). Both are indexed with a unique constraint. Two kinds of queries are required:

1. 给出一个不在表中的分数，返回分数插入时从1开始的位置。


2. 给出表中的 user_id ，返回相应分数的位置。

1. Given a score not in the table, return the 1-based position that the score would occupy if it were inserted.
2. Given a user_id in the table, return the position of the corresponding score.

在这两种情况下，排名都是相对于分数递增：小于表中当前所有分数的新分数将具有排名1。

In both cases, position is with respect to score ascending: a new score smaller than all currently in the table will have position 1.

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

Here's the tough part: we probably can't afford a table scan. The table may have up to 10 million records, and we need to handle at least 40 queries per second.

如何在PostgreSQL中做到这一点？

How to do this in PostgreSQL?

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

I have a non-SQL solution in Berkeley DB that uses its logical record number-enabled B-trees. It easily has good enough performance. But we would like to get rid of the BDB by re-implementing with a PostgreSQL query. I have tried the obvious

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

这会导致表格扫描。

我希望答案是没有办法，因为BDB的逻辑记录号功能要求每次编辑都锁定整个B-Tree。为了获得O（log N）性能，它依赖于每个节点中的叶子计数。根目录路径中的所有这些计数都必须随着每次编辑而改变。因此，锁定。这种锁定违反了PostgreSQL的设计原则，也违反了任何多用户数据库的设计原则。

I expect the answer to be "no way" because the logical record number facility of BDB requires locking the entire B-Tree for each edit. To get O(log N) performance, it relies on leaf counts in each node. All these counts in the path to root must change with every edit; hence, the locking. Such locking is against the design principles of PostgreSQL and probably any multi-user database.

因此，如果用PostgreSQL无法解决问题，则确认此问题的次佳结果。

So if the problem can't be solved with PostgreSQL, confirmation of this is the next best result of this question.

推荐答案

对于常规表，在PostgreSQL 9.1中您不能做很多操作。 count（）导致表扫描，因为索引没有可见性信息。为了验证同时没有删除行，PostgreSQL必须访问该表。

With a regular table, there is not much you can do in PostgreSQL 9.1. count() results in a table scan, because indexes do not have visibility information. To verify the rows are not deleted in the meantime, PostgreSQL has to visit the table.

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

If the table is read-only (or rarely updated), you could add a row number to the table. Then a query like:

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

具有索引：

CREATE INDEX standings_score_idx ON standings (score DESC);

几乎可以立即获得结果。
但是，出于明显的原因，这不是具有写入负载的表的选项。

Would get the result almost instantly. However, that's not an option for a table with write load for obvious reasons. So not for you.

好消息：即将发布的 PostgreSQL 9.2的主要新功能之一最适合您： 覆盖索引或 仅索引扫描。我在此处：<

The good news: one of the major new features of the upcoming PostgreSQL 9.2 is just right for you: "Covering index" or "index-only scan". I quote the 9.2 release notes here:

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

Allow queries to retrieve data only from indexes, avoiding heap access (Robert Haas, Ibrar Ahmed, Heikki Linnakangas, Tom Lane)

通常称为仅索引扫描或覆盖索引。对于具有完全可见元组的堆页面，这是
的可能，如可见性地图报告的
。可见性地图已制成实现碰撞安全的
作为实现此功能的必要部分。

This is often called "index-only scans" or "covering indexes". This is possible for heap pages with exclusively all-visible tuples, as reported by the visibility map. The visibility map was made crash-safe as a necessary part of implementing this feature.

罗伯特·哈斯（Robert Haas）的博客文章详细介绍了它如何影响计数效果。即使您使用 WHERE 子句，它也可以提高性能，就像您的情况一样。

This blog post by Robert Haas has more details how this affects count performance. It helps performance even with a WHERE clause, like in your case.

这篇关于SQL查询索引/主键顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！