1
`table4`:

id(int), id_parent(int), name(varchar), level(int)

Выбор элементов без детей

SELECT *
    FROM `table4` AS `p`
LEFT JOIN `table4` AS `c` ON `c`.`id_parent` = `p`.`id`
WHERE `p`.`level` =5
    AND `c`.`id` IS NULL
ORDER BY `p`.`id`

Происходит непозволительно долго(85К записей, максимальный уровень сейчас - 26) - около 30 секунд. Уверен, опять накосячил с индексами (сейчас id - primary, auto increment);

Можно ли как-то оптимизировать операции с иерархией, не прибегая к nested set? Очень уж у нее громоздкие и запутанные insrertы.

P.S. совсем листья, то есть элементы, которые не могут в принципе иметь детей - в отдельной таблице.

4
  • Пора давно перейти на NESTED SETS там удобнее делать выборки и быстрее.
    – Artem
    3 окт 2012 в 11:43
  • не прибегая к nested set// я же написал. =( Выборки-то там сказка. А, вот вставка, редактирование, перемещение, копирование... - happy tree friends.
    – knes
    3 окт 2012 в 11:45
  • >А, вот вставка, редактирование, перемещение, копирование... - happy tree friends. Ну не скажи, если сделать нормальные функции обхода CRUD, то все достаточно просто. Ну да обход большого кол-ва записей при удалении/вставки/копировании есть такое, но это разовые и не постоянные действия с деревьями.
    – Artem
    3 окт 2012 в 11:55
  • Ладно. Ча будет еще вопрос... :)
    – knes
    3 окт 2012 в 12:03

2 ответа 2

3

А так?

select t1.id, t1.id_parent, t1.name
from table4 t1 left join table4 t2 on t1.id = t2.id_parent
where t1.level = 5
group by t1.id, t1.id_parent, t1.name
having count(t2.id)=0
3
  • Так даже медленнее. У меня все-таки подозрение, что надо как-то оптимизировать индексы. Либо и правда переходить к nested set.
    – knes
    3 окт 2012 в 12:12
  • возможные индексы: * id_parent * id_parent+level 3 окт 2012 в 12:29
  • ЙЕС. Оно: доп. индекс по id_parent+level. спасибо огромное. Просто не знал, что индексы могут иметь неуникальное значение. Что только не узнаешь...
    – knes
    3 окт 2012 в 12:30
2

Изредка хочется вспомнить SQL

Так не сработает ?

SELECT * FROM table4 AS p WHERE p.level = 5 AND p.id NOT IN (SELECT id_parent FROM table4)

Собственно идея в том, что лист это запись, на которую никто по id_parent не ссылается (или я ошибаюсь?). Вот и будем выбирать только тех с уровня 5, чей id нигде в id_parent не прописан.

Если так, то могу предположить, что MySQL может эффективно реализовать такой запрос без индексов.

3
  • без индексов... не будет. Хотя, вынужден признать, что скорость работы завидная: почти вчетверо быстрее предложенного мной варианта. 0.02с и 0.07с. Другое дело, у вашего способа, по-идее, расходуется много больше памяти, если я хоть что-нибудь в чем-нибудь понимаю.
    – knes
    3 окт 2012 в 14:41
  • Не знаю, как это реализует MySQL, но по идее достаточно 2-х сортировок временных файлов (одна для всего множества id_parent, другая для записей с level=5 по id) и слияния (точнее операции "обратной" слиянию). Не знаю, как коротко и правильно это описать, но думаю идея ясна. 85К записей и последовательное чтение - это д.б. быстро.
    – avp
    3 окт 2012 в 14:50
  • Еще по поводу памяти-скорости. "Руками на Си" с учетом конкретного размера таблицы я бы делал так: Последовательное чтение всех записей table4. Для каждой записи 1. Отбор во временный файл "возможный" результат, т.е. записи с level=5; 2. Выборка в массив в памяти всех id_parent (85K int займут 340KB, (влезет в кэш CPU!)); После прохода сортировка массива id_parent. Проход по временному файлу. Двоичным поиском ищем id в массиве id_parent (скажем 16 проверок). Если не нашли, то отправляем эту запись в результат. Удаляем временный файл. До физической записи данных на диск дело не дойдет.
    – avp
    3 окт 2012 в 19:37

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.