0

我想在一张非常大的桌子上进行分组排名，我已经找到了一些解决这个问题的方法，例如在这篇文章和网络上的其他地方。但是，我无法弄清楚这些解决方案的最坏情况复杂性。具体问题包括一个表格，其中每一行都有一些点和一个关联的名称。我希望能够请求排名间隔，例如 1-4。以下是一些数据示例：

name | points
Ab     14
Ac     14
B      16
C      16
Da     15
De     13

使用这些值创建以下“排名”：

Query id | Rank | Name
1          1      B
2          1      C
3          3      Da
4          4      Ab
5          4      Ac
6          6      De

并且应该可以在查询 ID 上创建以下间隔：2-5 给出排名：1、3、4 和 4。

该数据库包含大约 300 万条记录，因此如果可能，我希望避免使用复杂度大于 log(n) 的解决方案。数据库上不断更新和插入，因此这些操作最好也以 log(n) 复杂度执行。我不确定这是否可能，我已经尝试过一段时间了。我得出的结论是二进制搜索应该是可能的，但我无法创建执行此操作的查询。我正在使用 MySQL 服务器。

我将详细说明过滤的伪代码如何工作。首先，需要一个关于 (points, name) 的索引。作为输入，您给出一个 fromrank 和一个 tillrank。数据库中的记录总数为 n。伪代码应如下所示：

找到中点值，计算小于该值的行数（计数给出了粗略估计的排名，不考虑具有相同点数的那些）。如果返回的数字大于 fromrank 分隔符，我们细分前半部分并找到它的中位数。我们一直这样做，直到我们确定 fromrank 应该开始的点数。然后我们使用名称索引在该数量的点内执行相同的操作，并找到中位数，直到我们到达正确的行。我们对tillrank 做同样的事情。

结果应该是 log(n) 的细分数。因此，考虑到中位数和计数可以在 log(n) 时间内完成，应该可以在最坏情况复杂度 log(n) 中解决问题。如果我错了，请纠正我。

4

1 回答 1

2

您需要一个存储过程才能使用参数调用它：

CREATE TABLE rank (name VARCHAR(20) NOT NULL, points INTEGER NOT NULL);

CREATE INDEX ix_rank_points ON rank(points, name);

CREATE PROCEDURE prc_ranks(fromrank INT, tillrank INT)
BEGIN
  SET @fromrank = fromrank;
  SET @tillrank = tillrank;
  PREPARE STMT FROM
  '
  SELECT  rn, rank, name, points
  FROM  (
    SELECT  CASE WHEN @cp = points THEN @rank ELSE @rank := @rn + 1 END AS rank,
            @rn := @rn + 1 AS rn,
            @cp := points,
            r.*
    FROM (
         SELECT @cp := -1, @rn := 0, @rank = 1
         ) var,
         (
         SELECT *
         FROM rank
         FORCE INDEX (ix_rank_points)
         ORDER BY
           points DESC, name DESC
         LIMIT ?
         ) r
    ) o
  WHERE rn >= ?
  ';
  EXECUTE STMT USING @tillrank, @fromrank;
END;

CALL prc_ranks (2, 5);

如果您创建索引并强制MySQL使用它（如在我的查询中），那么查询的复杂性将根本不取决于行数，它将仅取决于tillrank.

它实际上会tillrank从索引中获取最后一个值，对它们执行一些简单的计算并过滤掉第一个fromrank值。

如您所见，此操作的时间仅取决于tillrank，而不取决于有多少条记录。

我刚刚检查了行，它在几秒钟内从到400,000选择排名（即立即）51000,004

重要提示：这仅在您按名称排序时有效DESCENDING。MySQL不支持DESC索引中的子句，这意味着pointsandname必须按一个顺序排序INDEX SORT才能使用（两者ASCENDING或两者DESCENDING）。如果你想快速ASC排序name，你需要在数据库中保留负数，并更改SELECT子句中的符号。

您也可以完全从索引中删除，并在不使用索引的情况下name执行最终'ing：ORDER

CREATE INDEX ix_rank_points ON rank(points);

CREATE PROCEDURE prc_ranks(fromrank INT, tillrank INT)
BEGIN
  SET @fromrank = fromrank;
  SET @tillrank = tillrank;
  PREPARE STMT FROM
  '
  SELECT  rn, rank, name, points
  FROM  (
    SELECT  CASE WHEN @cp = points THEN @rank ELSE @rank := @rn + 1 END AS rank,
            @rn := @rn + 1 AS rn,
            @cp := points,
            r.*
    FROM (
         SELECT @cp := -1, @rn := 0, @rank = 1
         ) var,
         (
         SELECT *
         FROM rank
         FORCE INDEX (ix_rank_points)
         ORDER BY
           points DESC
         LIMIT ?
         ) r
    ) o
  WHERE rn >= ?
  ORDER BY rank, name
  ';
  EXECUTE STMT USING @tillrank, @fromrank;
END;

这将影响大范围的性能，但您几乎不会在小范围内注意到它。

于 2009-02-16T20:04:20.910 回答