0

非常に大きなテーブルでグループ化されたランキングが必要です。この問題の解決策がいくつか見つかりました。たとえば、この投稿や Web 上の他の場所です。ただし、これらのソリューションの最悪の場合の複雑さを把握することはできません。特定の問題は、各行に多数のポイントと関連付けられた名前が含まれるテーブルで構成されています。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とtilrankを与えます。データベース内のレコードの総数は n です。擬似コードは次のようになります。

中央値を見つけ、この値よりも少ない行を数えます (この数は、同じ量のポイントを持つものを考慮せずに、ランクの大まかな推定値を示します)。返された数値が fromrank 区切り文字よりも大きい場合、前半を細分化し、中央値を見つけます。fromrank を開始するポイントの量が特定されるまで、これを続けます。次に、名前 index を使用してそのポイント数内で同じことを行い、正しい行に到達するまで中央値を見つけます。ティルランクについてもまったく同じことを行います。

結果は 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。つまり、pointsandを使用できるようにnameするには、1 つの順序で並べ替える必要があります( bothまたは both )。で高速に並べ替えたい場合は、データベースに負の点を保持し、句の符号を変更する必要があります。INDEX SORTASCENDINGDESCENDINGASCnameSELECT

インデックスからまったく削除nameして、インデックスを使用せずに最終的なORDER'ing を実行することもできます。

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 に答える