MySQL и вложенным набор: медленный JOIN (не используя индекс)

Question

У меня есть две таблицы:

населенные пункты:

CREATE TABLE `localities` (
    `id` int(11) NOT NULL AUTO_INCREMENT, 
    `name` varchar(100) NOT NULL, 
    `type` varchar(30) NOT NULL, 
    `parent_id` int(11) DEFAULT NULL, 
    `lft` int(11) DEFAULT NULL, 
    `rgt` int(11) DEFAULT NULL, 
    PRIMARY KEY (`id`), 
    KEY `index_localities_on_parent_id_and_type` (`parent_id`,`type`), 
    KEY `index_localities_on_name` (`name`), 
    KEY `index_localities_on_lft_and_rgt` (`lft`,`rgt`) 
) ENGINE=InnoDB; 

locatings:

CREATE TABLE `locatings` (
    `id` int(11) NOT NULL AUTO_INCREMENT, 
    `localizable_id` int(11) DEFAULT NULL, 
    `localizable_type` varchar(255) DEFAULT NULL, 
    `locality_id` int(11) NOT NULL, 
    `category` varchar(50) DEFAULT NULL, 
    PRIMARY KEY (`id`), 
    KEY `index_locatings_on_locality_id` (`locality_id`), 
    KEY `localizable_and_category_index` (`localizable_type`,`localizable_id`,`category`), 
    KEY `index_locatings_on_category` (`category`) 
) ENGINE=InnoDB; 

населенные пункты таблицы реализованы в виде вложенного набора ,

Теперь, когда пользователь принадлежит к какой-либо местности (через некоторую локализацию), он также принадлежит всем его предкам (более высокие уровни). Мне нужен запрос, который выберет все точки, в которые все пользователи входят в представление.

Вот моя попытка:

select distinct lca.*, lt.localizable_type, lt.localizable_id 
from locatings lt 
join localities lc on lc.id = lt.locality_id 
left join localities lca on (lca.lft <= lc.lft and lca.rgt >= lc.rgt) 

Проблема здесь состоит в том, что она занимает слишком много времени для выполнения.

Я консультировался EXPLAIN:

+----+-------------+-------+--------+---------------------------------+---------+---------+----------------------------------+-------+----------+-----------------+ 
| id | select_type | table | type | possible_keys     | key  | key_len | ref        | rows | filtered | Extra   | 
+----+-------------+-------+--------+---------------------------------+---------+---------+----------------------------------+-------+----------+-----------------+ 
| 1 | SIMPLE  | lt | ALL | index_locatings_on_locality_id | NULL | NULL | NULL        | 4926 | 100.00 | Using temporary | 
| 1 | SIMPLE  | lc | eq_ref | PRIMARY       | PRIMARY | 4  | bzzik_development.lt.locality_id |  1 | 100.00 |     | 
| 1 | SIMPLE  | lca | ALL | index_localities_on_lft_and_rgt | NULL | NULL | NULL        | 11439 | 100.00 |     | 
+----+-------------+-------+--------+---------------------------------+---------+---------+----------------------------------+-------+----------+-----------------+ 
3 rows in set, 1 warning (0.00 sec) 

Последнее присоединиться явно не использует LFT, RGT индекс, как я ожидаю, что это. Я в отчаянии.

UPDATE: После добавления условия как предложено @cairnz, запрос занимает слишком много времени для обработки.

UPDATE 2: Названия столбцов вместо звездочки

Обновленный запрос:

SELECT DISTINCT lca.id, lt.`localizable_id`, lt.`localizable_type` 
FROM locatings lt FORCE INDEX(index_locatings_on_category) 
JOIN localities lc 
    ON lc.id = lt.locality_id 
INNER JOIN localities lca 
    ON lca.lft <= lc.lft AND lca.rgt >= lc.rgt 
WHERE lt.`category` != "Unknown"; 

Обновлено EXAPLAIN:

+----+-------------+-------+--------+-----------------------------------------+-----------------------------+---------+---------------------------------+-------+----------+-------------------------------------------------+ 
| id | select_type | table | type | possible_keys       | key       | key_len | ref        | rows | filtered | Extra           | 
+----+-------------+-------+--------+-----------------------------------------+-----------------------------+---------+---------------------------------+-------+----------+-------------------------------------------------+ 
| 1 | SIMPLE  | lt | range | index_locatings_on_category    | index_locatings_on_category | 153  | NULL       | 2545 | 100.00 | Using where; Using temporary     | 
| 1 | SIMPLE  | lc | eq_ref | PRIMARY,index_localities_on_lft_and_rgt | PRIMARY      | 4  | bzzik_production.lt.locality_id |  1 | 100.00 |             | 
| 1 | SIMPLE  | lca | ALL | index_localities_on_lft_and_rgt   | NULL      | NULL | NULL       | 11570 | 100.00 | Range checked for each record (index map: 0x10) | 
+----+-------------+-------+--------+-----------------------------------------+-----------------------------+---------+---------------------------------+-------+----------+-------------------------------------------------+ 

оценил любую помощь.

Answer 1

А, это только пришло в голову мне.

Поскольку вы просите все в таблице, mysql решает использовать полное сканирование таблицы вместо этого, поскольку оно считает его более эффективным.

Чтобы получить некоторое использование ключа, добавьте некоторые фильтры, чтобы в любом случае ограничить поиск каждой строки во всех таблицах.

Обновление Ответ:

Ваш второй запрос не имеет смысла. Вы остаетесь присоединенным к lca, но у вас есть фильтр в нем, это отрицает левое объединение. Также вы ищете данные на последнем шаге запроса, то есть вам нужно будет просмотреть все lt, lc и lca, чтобы найти ваши данные. Кроме того, у вас нет индекса с левым столбцом «тип» в местах, поэтому вам все равно нужно полное сканирование таблицы, чтобы найти ваши данные.

Если у вас были образцы данных и пример того, чего вы пытаетесь достичь, возможно, было бы легче помочь.

Answer 2

попытайтесь поэкспериментировать с форсирующим индексом - http://dev.mysql.com/doc/refman/5.1/en/index-hints.html, может быть, это просто проблема оптимизации.

Answer 3

Похоже, вы хотите, чтобы родители достигли единственного результата.

По словам человека, которому присвоено определение Вложенные наборы в SQL, Джо Селко в http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html «Эта модель является естественным способом показать взрыв деталей, поскольку окончательная сборка выполнена из физически вложенных сборок, которые разбиваются на отдельные части. "

Другими словами, вложенные наборы используются для эффективного фильтрации детей на произвольное количество независимых уровней внутри одной коллекции. У вас есть две таблицы, но я не вижу, где свойства набора «locatings» не могут быть де-нормированы в «локации»?

Если таблица местностей была столбец геометрии, я не мог найти один местности от «размещая», а затем выбрать на одном стол с помощью одного фильтра: parent.lft < = row.left И родительского. rgt> = row.rgt?

ОБНОВЛЕНО

В этом ответе https://stackoverflow.com/a/1743952/3018894, есть пример из http://explainextended.com/2009/09/29/adjacency-list-vs-nested-sets-mysql/ где следующий пример получает все предки до произвольной глубины 100000:

SELECT hp.id, hp.parent, hp.lft, hp.rgt, hp.data 
FROM (
    SELECT @r AS _id, 
      @level := @level + 1 AS level, 
      (
      SELECT @r := NULLIF(parent, 0) 
      FROM t_hierarchy hn 
      WHERE id = _id 
      ) 
    FROM (
      SELECT @r := 1000000, 
        @level := 0 
      ) vars, 
      t_hierarchy hc 
    WHERE @r IS NOT NULL 
    ) hc 
JOIN t_hierarchy hp 
ON  hp.id = hc._id 
ORDER BY 
    level DESC