MySQLネストされたサブカテゴリの計算が遅い

Question

ネストされたセットモデルを持つカテゴリのテーブルがあります。各行には、そのサブカテゴリの数とそれらに含まれる記事の数が含まれている必要があります。

私はarroundの検索と2つの解決策を見つけましたが、それらの何も動作しました：
MySQL & nested set: slow JOIN (not using index)
Why isn't MySQL using any of these possible keys?

表カテゴリを作成します。

CREATE TABLE `categories` (
    `GROUP_ID` varchar(255) CHARACTER SET utf8 NOT NULL, 
    `GROUP_NAME` varchar(255) CHARACTER SET utf8 NOT NULL, 
    `PARENT_ID` varchar(255) CHARACTER SET utf8 NOT NULL, 
    `TYPE` enum('root','node','leaf') CHARACTER SET utf8 NOT NULL DEFAULT 'node', 
    `LEVEL` tinyint(2) NOT NULL DEFAULT '0', 
    `GROUP_ORDER` int(11) NOT NULL, 
    `GROUP_DESCRIPTION` text CHARACTER SET utf8 NOT NULL, 
    `total_articles` int(11) unsigned NOT NULL DEFAULT '0', 
    `total_cats` int(11) unsigned NOT NULL DEFAULT '0', 
    `lft` smallint(5) unsigned NOT NULL DEFAULT '0', 
    `rgt` smallint(5) unsigned NOT NULL DEFAULT '0', 
    PRIMARY KEY (`GROUP_ID`), 
    KEY `PARENT_ID` (`PARENT_ID`), 
    KEY `lft` (`lft`), 
    KEY `rgt` (`rgt`) 
) ENGINE=MyISAM DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci 

total_catsは、サブカテゴリーの量であります行ツリー。
次のクエリは、すべて私の望むことを行います：すべてのサブカテゴリと記事数。 しかし、それは非常に遅いです。 〜5000カテゴリと〜40000記事では、実行には80秒以上かかります。total_articlesの計算は別のスクリプトで既に実行されています。それは場合に役立ちます

+-------------------------------------------+-------------------------------------+------------+----------------+ 
| GROUP_ID         | PARENT_ID       | total_cats | total_articles | 
+-------------------------------------------+-------------------------------------+------------+----------------+ 
| 69_69_1         | 69_69_0        |  4252 |    0 | 
| 69_69_Abfall__Wertstoffsammler___zubehoer | 69_69_NWEAB290h001     |   5 |    20 | 
| 69_69_Abisolierzangen      | 69_69_NWAAA458h001     |   4 |    56 | 
| 69_69_Abzieher_2       | 69_69_NWAAB944h001     |   23 |   476 | 
| 69_69_Abziehvorrichtung     | 69_69_Abzieher_2     |   3 |    18 | 
| 69_69_Aexte        | 69_69_NWEAA615h001     |   6 |    45 | 
| 69_69_Alarmgeraete_Melder     | 69_69_Sicherungstechnik__Heimschutz |   3 |    4 | 
| 69_69_Allgemeiner_Industriebedarf   | 69_69_Industrieausruestung   |   8 |    21 | 
| 69_69_Allgemeines_Schweisszubehoer  | 69_69_NWEAB113h001     |   27 |    97 | 
| 69_69_Anker__Befestigungstechnik__1  | 69_69_Befestigungstechnik   |   5 |   163 | 

説明：

SELECT a.GROUP_ID,a.PARENT_ID,COUNT(b.GROUP_ID) as total_cats,(
    SELECT SUM(c.total_articles) 
    FROM categories c 
    WHERE c.PARENT_ID = a.GROUP_ID) as total_articles 
FROM categories as b 
    INNER JOIN categories as a 
    ON a.lft < b.lft AND a.rgt > b.rgt 
GROUP BY a.GROUP_ID 

それはこのようなものになり：

クエリ

（任意の記事をそこアレント場合は、すべての行がtotal_articlesため0を保持する必要があります）

+----+--------------------+-------+------+---------------+-----------+---------+------+------+------------------------------------------------+ 
| id | select_type  | table | type | possible_keys | key  | key_len | ref | rows | Extra           | 
+----+--------------------+-------+------+---------------+-----------+---------+------+------+------------------------------------------------+ 
| 1 | PRIMARY   | b  | ALL | lft,rgt  | NULL  | NULL | NULL | 4253 | Using temporary; Using filesort    | 
| 1 | PRIMARY   | a  | ALL | lft,rgt  | NULL  | NULL | NULL | 4253 | Range checked for each record (index map: 0xC) | 
| 2 | DEPENDENT SUBQUERY | c  | ref | PARENT_ID  | PARENT_ID | 767  | func | 7 | NULL           | 
+----+--------------------+-------+------+---------------+-----------+---------+------+------+------------------------------------------------+ 

ご覧のとおり、インデックスは使用されません。私がJOINの隣にFORCE INDEX (lft,rgt)を置くと、クエリは実行されますが、何も変わりません。また、左と右の両方の列にインデックスを追加しようとしました：

ALTER TABLE `categories` ADD INDEX `nestedset` (`lft`, `rgt`); 

しかし、それはまったく役に立ちません。クエリはまだ遅いです。

興味深いことに、カテゴリテーブルがちょうど少数の行で満たされている場合、クエリはかなり高速です。しかし、それが1000+に達すると、遅くなり、遅くなります。

〜4000カテゴリの例データ：http://pastebin.com/BsViwFM5大きなファイル！
ご協力いただきありがとうございます！

Answer 1

この外観のEXPLAINはどのようなものですか？

SELECT a.GROUP_ID 
    , a.PARENT_ID 
    , COUNT(b.GROUP_ID) total_cats 
    , c.total_articles 
    FROM categories b 
    JOIN categories a 
    ON a.lft < b.lft 
    AND a.rgt > b.rgt 
    JOIN 
    (SELECT parent_id 
      , SUM(total_articles) total_articles 
     FROM categories 
     GROUP 
      BY parent_id 
    ) c 
    ON c.parent_id = a.GROUP_ID 
GROUP 
    BY a.GROUP_ID 

Answer 2

右下のツリーは、かわいい "教科書"テクニックです。しかし、あなたが見つけているように、それは「現実の世界」のために拡大しません。

EXPLAINはbのすべてをスキャンしていることを示していますが、このような行ごとにはaのすべてをスキャンしています。それは秩序（N^2） - 5000 * 5000 = 2,500万回の操作です。

実際、この比較的新しい操作（Range checked for each record (index map: 0xC)）は、それほど悪くないことを意味します。

オプティマイザは、欠けている情報の1つのビット：範囲が重複しているかどうかで、 'betweenness'を見つける際に本当にうまくいくことができません。

あなたのタスクは、階層スキーマに切り替えて、アプリケーションコードまたはストアドルーチンのいずれかでツリーを「ウォーキング」すると、よりうまく達成できます。

MariaDB 10.2またはMySQL 8.0を使用すると、複雑なクエリーでツリーを移動する「再帰的なCTE」を書くことができます。