Подсчет количества объектов в дочерных категориях

Есть таблица категорий с практически бесконечной вложенностью.
Нужно сделать подсчет объектов в каждой категории, с учетом объектов из дочерных категорий. Как лучше всего это реализовать, что бы тратить как можно меньше ресурсов. Запуск обновления статистики будет по крону.


Таблицы

1. cats - таблица категорий
поля
id - уникальный идентификатор
root - ID родителя
level - уровень вложенности категории
object_count - тут надо записать количество объектов
другие информационные поля

2. objects - таблица объектов
информационные поля, не важно какие.

Написал вот такой запрос

update cats set cats.obj_count=(select count(objects.id) as count_obj from objects where objects.cat=cats.id)

который считает количество объектов для каждой категории, записывает в нужное поле, но без учета дочерных подкатегорий.

Думаю сделать вот как: получить одним запросом количество объектов в каждой категории, потом рекурсивным обходом сделать подсчет для дочерных категорий и суммировать. Может есть какой то другой подход, более правильным?

Цитата ("WebDesignStudio"):

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

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

Цитата ("superkoder"):

и пересчитывать это количество каждый раз при добавлении / удалении дочерних категорий.

не вариант.
Надо будет при каждом добавлении/удалении сделать изменение для всех родительский категорий. Затратно.

Цитата ("WebDesignStudio"):

Надо будет при каждом добавлении/удалении сделать изменение для всех родительский категорий. Затратно.

Всё зависит от того, какая операция проводится чаще.
Если добавление/удаление производится редко, то стоит потратиться сразу.
Зато потом количество будет выдаваться вообще без затрат.

Добавление, удаление, изменение категории в общем взятые будут происходить чаще. Плюс, тут буду операции обновления нескольких категорий. А по крону думаю запустить раз в 5 минут например. Принимаются все идеи, но если можно объяснить почему. будет полезно и другим, которые будут читать данную тему.

Два варианта. В зависимости от актуальности.
1) актуальный. пересчет происходит при каждом добавлении/удалении категории.
а) Создаем отдельную таблицу, тип memory. там храним id, id_parent, level, count
б) Создаем внутреннюю функцию пересчета. Действует она по принципу. Добавили 1 категорию - везде сделать +1. Убрали одну категорию - везде делаем минус столько, сколько в поле count
в) На всякий случай делаем скрипт со второго пункта. На случае, если таблица пропадет.

2)
а) Создаем отдельную таблицу, тип my_isam. там храним id, count
б) Создаем внутреннюю функцию пересчета. Просто с помощью count пересчитываем да и все.

P.S. level нужен, чтобы сортировать по уровню вложенности и начинать пересчет с самых вложеных)
И на самом деле использовать внутреннюю функцию или кучу запросов из php зависит от того, на каком из серверов больше загрузка? (сервер с php или сервер с db)

Наверное можно попробовать написать триггер, который будет обновлять таблицу родителя, плюсуя значение текущей категории. Обнуляем все, проходим от категорий у которых нет предков до верха и получаем полную картину. Я это дело не обдумывал крепко, так что в голову пришло написал - строго не судите. Но по идее должно отрабатывать.

frig, не надо триггер. Триггер - это удобство, а за удобства надо платить

Enkvist, не совсем понял что вы писали.
frig, ну я примерно то же самое делаю. Но тут получается много операций. А я хочу как проще. Кстати в моем варианте, один SELECT для получения количества объектов по всем категориям без учета дочерних. Получаем массив, которого обрабатываем рекурсивно, и получаем количество объектов с учетом дочерних. Потом этот массив записываем обратно в базу. Проблема в том что будет столько UPDATE сколько категорий, что мне не очень нравится. Остальное все хорошо.

Тут без рекурсии не обойтись.

Посмотрите в сторону Nested Sets

ссылка

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

WebDesignStudio, что конкретно не понятно?
Miller_time, отличное решение.

Цитата ("Enkvist"):

WebDesignStudio, что конкретно не понятно?

можно сказать ничего почти не понятно.
Miller_time, сейчас база уже создана, не хотелось бы ее менять. Решение нашел, но хочу понять что будет лучше.

Сейчас в базе примерно 200 категорий. Думаю что будет не больше 300. Получается что надо будет выполнять столько операций UPDATE при каждом запуске скрипта обновления статистики. Эта операция будет запущена примерно раз в 5-10 минут(может и больше, надо будет на практику уже смотреть).
Операции добавления/редактирования/удаления объектов(плюс еще тут есть возможность взять целую ветку и переместить в другом месте. Думаю будет не так часто использоваться, так что с точки зрения затраты ресурсов можно не считать. Зато обработка будет усложнятся на много), скорее всего будут выполнятся не меньше чем 5 в минуту. И если это категории 3-4 уровня, которых больше всех, получается что на каждую операцию с объектом надо сделать 3-4 запроса UPDATE. А это 20 в минуту=150-200 запросов за 10 минут. Вроде получается меньше. Но не знаю, стоит ли усложнять это все? Первый метод легче получается.

Цитата ("Miller_time"):

Тут без рекурсии не обойтись.

Посмотрите в сторону Nested Sets

ссылка

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

Операции выборки очень удобны, а вот операции добавления/удаления элемента, тем более переноса элемента - занимают минимум пару не очевидных запросов.

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

А если это замутить на Transact-SQL?

Должна быть возможность запускать sql-скрипты.. а в Transact-SQL вам и функции, и переменные, и циклы - можно замутить рекурсию и т.п. - всю задачу положить на sql...

Было бы больше инфы о том откуда эти категории - возможно другую модель кто придумал для решения задачи с всеми дочерними.

kirilev, СУБД MySQL.

Цитата:

Операции выборки очень удобны, а вот операции добавления/удаления элемента, тем более переноса элемента - занимают минимум пару не очевидных запросов.

Согласен, это зависит от уровня вложенности. Может задача изначально усложнена?

kirilev, mysql сервер сложнее масштабировать чем php. Несколько простых запросов как правило будут работать быстрее чем один сложный.

Цитата ("superkoder"):

а вот операции добавления/удаления элемента

Это еще цветочки. Если вдруг использовать рекурсию с базами, то можно получить еще больше неочевидных запросов.
Вот перемещение действительно очень сложная операция.

как вариант можно запихнуть все эти данные в массив, сериализовать и в файл. Если объем данных относительно не большой, и запросы не сложные, можно пихать в память + писать на диск. И периодически синхронизировать с БД.

Цитата ("WebDesignStudio"):

Сейчас в базе примерно 200 категорий. Думаю что будет не больше 300.

Если категорий мало, то можно загружать скриптом их все в память, и в скрипте же просчитывать количество.
Результат — кешировать.
При следующей выборке значения брать из кеша.
При обновлении данных — полностью или частично сбрасывать кеш, или сразу пересчитывать, смотря какую стратегию кеширования решите использовать.

Цитата ("superkoder"):

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

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

Цитата ("superkoder"):

Операции выборки очень удобны, а вот операции добавления/удаления элемента, тем более переноса элемента - занимают минимум пару не очевидных запросов.

так и выборка делается 100500 тыс раз, а вставка и перенос разы. взять какой нить форум с ветками комментариев.

Цитата ("Miller_time"):

kirilev, mysql сервер сложнее масштабировать чем php. Несколько простых запросов как правило будут работать быстрее чем один сложный.

ой не факт. sql сам не дурак, да еще если ключи нормально сделаны...