Mysql: оптимизация выбора строк из нескольких диапазонов (с использованием индексов?)

Question

Мой стол (проекты):

id, lft, rgt
1, 1, 6
2, 2, 3
3, 4, 5
4, 7, 10
5, 8, 9
6, 11, 12
7, 13, 14

Как вы, возможно, заметили, это иерархические данные с использованием модели вложенного набора . Дерево красиво напечатано:

1
 2
 3
4
 5
6
7

Я хочу выбрать все подпроекты в рамках проектов 1 и 4. Я могу сделать это с помощью:

SELECT p.id
FROM projects AS p, projects AS ps
WHERE (ps.id = 1 OR ps.id = 4)
AND p.lft BETWEEN ps.lft AND ps.rgt

Тем не менее, это очень медленно с большой таблицей, при запуске EXPLAIN (Query) я получаю:

+----+-------------+-------+-------+------------------------+---------+---------+------+------+-------------------------------------------------+
| id | select_type | table | type  | possible_keys          | key     | key_len | ref  | rows | Extra                                           |
+----+-------------+-------+-------+------------------------+---------+---------+------+------+-------------------------------------------------+
|  1 | SIMPLE      | ps    | range | PRIMARY,lft,rgt,lftRgt | PRIMARY | 4       | NULL |    2 | Using where                                     | 
|  1 | SIMPLE      | p     | ALL   | lft,lftRgt             | NULL    | NULL    | NULL | 7040 | Range checked for each record (index map: 0x12) | 
+----+-------------+-------+-------+------------------------+---------+---------+------+------+-------------------------------------------------+

(Таблица проекта имеет индексы для lft, rgt и lft-rgt. Как видите, mysql не использует никаких индексов и просматривает записи 7040)

Я обнаружил, что если я выберу только один из суперпроектов, mysql сможет использовать индексы:

SELECT p.id
FROM projects AS p, projects AS ps
WHERE ps.id = 1
AND p.lft BETWEEN ps.lft AND ps.rgt

ОБЪЯСНЯЕТ:

+----+-------------+-------+-------+------------------------+---------+---------+-------+------+-------------+
| id | select_type | table | type  | possible_keys          | key     | key_len | ref   | rows | Extra       |
+----+-------------+-------+-------+------------------------+---------+---------+-------+------+-------------+
|  1 | SIMPLE      | ps    | const | PRIMARY,lft,rgt,lftRgt | PRIMARY | 4       | const |    1 |             | 
|  1 | SIMPLE      | p     | range | lft,lftRgt             | lft     | 4       | NULL  |    7 | Using where | 
+----+-------------+-------+-------+------------------------+---------+---------+-------+------+-------------+

НАКОНЕЦ , мой вопрос: есть ли способ ВЫБРАТЬ строки, соответствующие нескольким диапазонам, и при этом получать выгоду от индексов?

Answer 1

С 7.2.5.1. Метод доступа к диапазону для отдельных индексов в справочном руководстве MySQL:

В настоящее время MySQL не поддерживает объединение нескольких диапазонов для метода доступа к диапазонам для пространственных индексов. Чтобы обойти это ограничение, вы можете использовать UNION с идентичными инструкциями SELECT, за исключением того, что вы помещаете каждый пространственный предикат в другой SELECT.

Итак, вам нужно объединить два разных выбора.

Answer 2

Ваш запрос объединяет несколько диапазонов.

Используется метод доступа range для объединения нескольких диапазонов на p (который является ведущим в объединении).

Для каждой строки, возвращаемой из p, проверяется лучший способ извлечь все строки из ps для заданных значений p.lft и p.rgt. В зависимости от избирательности запроса это может быть либо полное сканирование по ps, либо поиск по индексу по одному из двух возможных индексов.

Количество строк, показанных в EXPLAIN, ничего не значит: EXPLAIN просто показывает наихудший возможный результат. Это не обязательно означает, что все эти строки будут проверены. Будет ли оптимизатор или нет, он может сказать только во время выполнения.

Фрагмент документации о невозможности объединения нескольких диапазонов действителен только для SPATIAL индексов (R-Tree тех, которые вы создаете для GEOMETRY типов). Эти индексы хороши для запросов, которые ищут вверх (предки данного проекта), но не вниз.

Простой B-Tree индекс может объединять несколько диапазонов. Из документации :

Для всех типов индексов условия множественного диапазона в сочетании с OR или AND образуют условие диапазона.

Настоящая проблема заключается в том, что оптимизатор в MySQL не может принять единственное правильное решение: либо использовать один полный просмотр (с опережением ps), либо выполнить несколько сканирований диапазона.

Скажем, у вас есть 10,000 строк и границы ваших проектов 0-500 и 2000-2500. Оптимизатор увидит, что каждая граница получит выгоду от индекса, range check приведет к двум доступам диапазона, тогда как один полный просмотр будет лучше.

Может быть даже хуже, если границы вашего проекта, скажем, 0-3000 и 5000-6000. В этом случае оптимизатор выполнит два полных сканирования, тогда как одного будет достаточно.

Чтобы помочь оптимизатору принять правильное решение, вы должны указать индекс покрытия на (lft, id) в следующем порядке:

CREATE INDEX ix_lft_id ON projects (lft, id)

Переломный момент для использования fullscan над индексом покрытия, а не условием диапазона, составляет 90%, это означает, что у вас никогда не будет больше одного полного сканирования в вашем фактическом плане.

Answer 3

ты пробовал союз? возьмите второй пример, добавьте «union» внизу и повторяющийся, но соответствующий id 4. Я не знаю, сработает ли это, но кажется очевидной попытка.

редактирование:

SELECT p.id
FROM projects AS p, projects AS ps
WHERE ps.id = 1
AND p.lft BETWEEN ps.lft AND ps.rgt
UNION
SELECT p.id
FROM projects AS p, projects AS ps
WHERE ps.id = 4
AND p.lft BETWEEN ps.lft AND ps.rgt