MySQL вложенных подкатегорий подсчет медленных

Question

У меня есть таблица для категорий с вложенной моделью набора. Каждая строка должна содержать количество подкатегорий и количество статей в них или «0», если их нет.

Я искал Arround и нашел два возможных решения, но ничего из них не работает:
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 уже выполнен другим скриптом. (Если Арент любые статьи, все строки должны держать 0 для total_articles)

Запросов:

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 

Это приводит к чему-то вроде этого:

+-------------------------------------------+-------------------------------------+------------+----------------+ 
| 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 | 

Explain, если это помогает:

+----+--------------------+-------+------+---------------+-----------+---------+------+------+------------------------------------------------+ 
| 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           | 
+----+--------------------+-------+------+---------------+-----------+---------+------+------+------------------------------------------------+ 

Как вы можете видеть, он не использует индексы. Если я положил FORCE INDEX (lft,rgt) рядом с JOIN, запрос выполнится, но ничего не изменится. Также попытался добавить индекс на обе колонки на лоф и справа:

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

Но это совсем не помогает. Запрос все еще медленный.

Интересно: запрос довольно быстрый, если таблица категорий просто заполнена небольшим количеством строк, например. 260. Но если он достигнет 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 = 25 миллионов операций.

Фактически, эта относительно новая операция (Range checked for each record (index map: 0xC)) подразумевает, что это не так уж плохо.

Оптимизатор действительно не может сделать намного лучше, чтобы найти «междоусобие», потому что один бит недостающей информации: перекрываются ли диапазоны.

Ваша задача может достигать, достигнув перехода к иерархической схеме и «ходя по дереву» в коде приложения или в хранимой процедуре.

С помощью MariaDB 10.2 или MySQL 8.0 вы можете написать «Рекурсивный CTE», чтобы пройти дерево в одном, хотя и сложном запросе.