ファストグループランク（）関数

Question

MySQLでMSSQL RANK（）またはROW_NUMBER（）関数をエミュレートしようとする人はいろいろありますが、これまで試みてきたことはすべて遅いです。それは22万レコードを持っている場合を除き

CREATE TABLE ratings 
    (`id` int, `category` varchar(1), `rating` int) 
; 

INSERT INTO ratings 
    (`id`, `category`, `rating`) 
VALUES 
    (3, '*', 54), 
    (4, '*', 45), 
    (1, '*', 43), 
    (2, '*', 24), 
    (2, 'A', 68), 
    (3, 'A', 43), 
    (1, 'A', 12), 
    (3, 'B', 22), 
    (4, 'B', 22), 
    (4, 'C', 44) 
; 

：

私はこのようになりますテーブルを持っています。約90,000の一意のIDがあります。

*ではないカテゴリを調べることで、最初にIDのランク付けをしたかったのですが、高い評価は低いランクです。

SELECT g1.id, 
     g1.category, 
     g1.rating, 
     Count(*) AS rank 
FROM ratings AS g1 
JOIN ratings AS g2 ON (g2.rating, g2.id) >= (g1.rating, g1.id) 
AND g1.category = g2.category 
WHERE g1.category != '*' 
GROUP BY g1.id, 
     g1.category, 
     g1.rating 
ORDER BY g1.category, 
     rank 

出力：

id category rating rank 
2 A 68 1 
3 A 43 2 
1 A 12 3 
4 B 22 1 
3 B 22 2 
4 C 44 1 

それから私はランクで、彼らは*カテゴリに持っていることを、最小のIDが持っていたランク、平均を取ると思いました。合計クエリ与える：私

id OverallRank 
3 1.5000 
4 1.5000 
2 2.5000 
1 3.0000 

を与える

SELECT X1.id, 
     (X1.rank + X2.minrank)/2 AS OverallRank 
FROM 
    (SELECT g1.id, 
      g1.category, 
      g1.rating, 
      Count(*) AS rank 
    FROM ratings AS g1 
    JOIN ratings AS g2 ON (g2.rating, g2.id) >= (g1.rating, g1.id) 
    AND g1.category = g2.category 
    WHERE g1.category = '*' 
    GROUP BY g1.id, 
      g1.category, 
      g1.rating 
    ORDER BY g1.category, 
      rank) X1 
JOIN 
    (SELECT id, 
      Min(rank) AS MinRank 
    FROM 
    (SELECT g1.id, 
      g1.category, 
      g1.rating, 
      Count(*) AS rank 
     FROM ratings AS g1 
     JOIN ratings AS g2 ON (g2.rating, g2.id) >= (g1.rating, g1.id) 
     AND g1.category = g2.category 
     WHERE g1.category != '*' 
     GROUP BY g1.id, 
       g1.category, 
       g1.rating 
     ORDER BY g1.category, 
       rank) X 
    GROUP BY id) X2 ON X1.id = X2.id 
ORDER BY overallrank 

はこのクエリは正しいと、私が欲しいの出力ですが、それだけで22万レコードの私の本当のテーブルの上にハングアップします。どのように私はそれを最適化できますか？私の本当のテーブルには、id,ratingとcategoryのインデックスとid,category

編集しました：SHOW CREATE TABLE ratingsの

結果：

CREATE TABLE `rating` (
    `id` int(11) NOT NULL, 
    `category` varchar(255) NOT NULL, 
    `rating` int(11) NOT NULL DEFAULT '1500', 
    `rd` int(11) NOT NULL DEFAULT '350', 
    `vol` float NOT NULL DEFAULT '0.06', 
    `wins` int(11) NOT NULL, 
    `losses` int(11) NOT NULL, 
    `streak` int(11) NOT NULL DEFAULT '0', 
    PRIMARY KEY (`streak`,`rd`,`id`,`category`), 
    UNIQUE KEY `id_category` (`id`,`category`), 
    KEY `rating` (`rating`,`rd`), 
    KEY `streak_idx` (`streak`), 
    KEY `category_idx` (`category`), 
    KEY `id_rating_idx` (`id`,`rating`) 
) ENGINE=InnoDB DEFAULT CHARSET=latin1 

PRIMARY KEYは理由があり、このテーブルにクエリの最も一般的な使用例でありますそれはクラスタ化されたキーです。サーバが9GB /秒のFIOランダム読み出しを備えたRAID 10のSSDであることは注目に値する。だから、私はクラスター化されていない指標が多くの影響を与えるとは思わない。 (select count(distinct category) from ratings)の

出力は、これはデータが私の監督であるか、どのように可能性があり、私はテーブル全体の輸出が含まれています関心で50

です。 200キロバイトはzip形式のみです：https://www.dropbox.com/s/p3iv23zi0uzbekv/ratings.zip?dl=0

最初のクエリは、あなたが（行番号）ランクを生成するために、AUTO_INCREMENTカラムを持つ一時テーブルを使用することができます

Answer 1

を実行するために27秒かかります。例えば

- '*' カテゴリのランクを生成する：

drop temporary table if exists tmp_main_cat_rank; 
create temporary table tmp_main_cat_rank (
    rank int unsigned auto_increment primary key, 
    id int NOT NULL 
) engine=memory 
    select null as rank, id 
    from ratings r 
    where r.category = '*' 
    order by r.category, r.rating desc, r.id desc; 

これは30ミリ秒のようなもので動作します。セルフジョインであなたのアプローチは私のマシンで45秒かかる。 (category, rating, id)の新しいインデックスがあっても、実行には14秒かかります。

グループごと（カテゴリごと）にランクを生成するのはもう少し複雑です。我々はまだAUTO_INCREMENTカラムを使用することができますが、カテゴリごとにオフセットを計算し、減算する必要があります。

drop temporary table if exists tmp_pos; 
create temporary table tmp_pos (
    pos int unsigned auto_increment primary key, 
    category varchar(50) not null, 
    id int NOT NULL 
) engine=memory 
    select null as pos, category, id 
    from ratings r 
    where r.category <> '*' 
    order by r.category, r.rating desc, r.id desc; 

drop temporary table if exists tmp_cat_offset; 
create temporary table tmp_cat_offset engine=memory 
    select category, min(pos) - 1 as `offset` 
    from tmp_pos 
    group by category; 

select t.id, min(t.pos - o.offset) as min_rank 
from tmp_pos t 
join tmp_cat_offset o using(category) 
group by t.id 

これは約220ミリ秒で実行されます。セルフジョイン解は新しいインデックスで42秒か13秒かかります。

今、あなたはちょうどあなたの最終的な結果を得るために、最初の一時テーブルで最後のクエリを結合する必要があります。

select t1.id, (t1.min_rank + t2.rank)/2 as OverallRank 
from (
    select t.id, min(t.pos - o.offset) as min_rank 
    from tmp_pos t 
    join tmp_cat_offset o using(category) 
    group by t.id 
) t1 
join tmp_main_cat_rank t2 using(id); 

全体のランタイムは、追加のインデックスとインデックス上で〜240ミリ秒なし〜280ミリ秒であります(category, rating, id)。

セルフジョインアプローチへの注意：これは洗練されたソリューションであり、小規模なグループサイズでも問題なく動作します。それは速いです平均グループサイズ< = 2.それは10のグループサイズのために受け入れられるかもしれません。しかしあなたは平均グループサイズ447（count(*)/count(distinct category)）を持っています。これは、すべての行が平均447行に結合されていることを意味します。グループ句を削除すると、その影響を確認できます。

SELECT Count(*) 
FROM ratings AS g1 
JOIN ratings AS g2 ON (g2.rating, g2.id) >= (g1.rating, g1.id) 
AND g1.category = g2.category 
WHERE g1.category != '*' 

結果は10Mを超える行です。

ただし、インデックスは(category, rating, id)です。私のマシンでは33秒でクエリが実行されます。