Подсчет колич-ва объектов — пересечение 2 деревьев

Раньше поднимал эту тему, но так и нашел подходящее решение.
Решил создать новую тему, так как там не совсем ясно описал проблему на сколько мне кажется.

Имеем
Доска объявлений(ссылка). В ней 2 дерева: разделы и местоположение(регионы, города).

Таблица разделов(cats) - примерно 1000 записей:
id - идентификатор
root - родитель(из этой же таблице)
level - уровень категории.
и другие информационные поля

Таблица местоположений(locations) - примерно 500 записей:
id - идентификатор
root - родитель(из этой же таблице)
level - уровень.
и другие информационные поля

Таблица объектов(objects) - записей будет много, десятки тысяч, со временем возможно сотни. Пока есть порядка 2000 записей, для тестирования:
id - идентификатор
cat - категория
loc - местоположение
другие информационные поля

Так же есть закэшированые дети, для снижения нагрузки на сервер.

Таблица cat_childs:
cat_id - категория
childs(текстовое поле вида 456#234#324), то есть список детей через разделитель.

Таблица loc_childs:
loc_id - местоположение
childs(текстовое поле вида 456#234#324), то есть список детей через разделитель.

Файлы в котором кэшируются результаты. Для каждого города, отдельный файл, в котором записана статистика по всем категориям.
Нужно получить
Нужно сделать подсчет количества объектов для каждой категории(и его детей) с учетом выбранного города. Так же, надо делать подсчет для всех категорий когда город не выбран.

На данный момент есть 2 способа решения задачи:
1. Обход всех городов, и для каждого города делать запросы вида
SELECT COUNT(id) FROM objects WHERE loc IN (город и его дети) AND cat IN(раздел и его дети)
Результаты кэшируются в файлах.
Проблема в том что количество запросов получается 500(количество городов)*1000(количество разделов) = 500 000 запросов.
2. Изменение файлов статистики при добавлении/удалении/редактировании объекта.
При добавлении:
меняются все файлы городов, начиная от файла города в котором находится объект и заканчивая со всеми его родителями.
При удалении аналогично.
Тут есть 2 проблемных ситуациях:
Изменение раздела или города объекта(такое на практике встречается часто)
Перемещение ветки одного из деревьев в другом месте(это уже реализовано).
Вот для этих 2 моментов не нашел подходящее решение.
Может у кого то есть другие идеи как это можно решить.
Заранее спасибо.

PS: то что мне нужно реализовано на slando.com.ua, но не знаю на сколько хорошо и как.

Да, помню такую тему..

А почему не добавить дополнительное поле в таблицу, которое будет содержать абсолютное количество всех детей?

А сам счётчик будет увеличиваться на +1 если объявление было добавлено/перемещено для одной из дочерных категорий на любой "глубине", или -1, если объявление переместили в другую категорию/город.

получится что-то типо такого:

таблица для городов locations
.....|all_childs|

таблица категорий cats
.....|all_childs|

ещё добавить связку страна - категория

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

сколько объявлений в Киеве? - выборка ещё проще, результат - то что в олл_чилдс для киева.

Тоесть на вершине дерева - глобус (Россия, Украина), второй уровень - город страны, третий - категория и подкатегории.

Для подсчёта количества объявлений для одной из категорий не зависимо от города - нужно выбрать олл_чилдс игнорируя флаг для страны.

Всё поля all_childs заполняются по мере заполнения базы данных, проблемы с частным изменением олл_чилдс в современных БД быть не должно, а на основе текущих данных - можно запросом один раз заполнить поля all_childs и далее сделать автоматическое заполнение в зависимости от характера изменения объявления.

ДУмаю ещё лучше - если зделать отдельные таблицы для контроля "детей", если это не принципиально, конечно это будет +1-+2 запроса при изменении объявления.

Инными словами - предлагаю вести мониторинг детей по мере их поступления, контролируя в этот момент все уровни, вижу этот вариант самый оптимальный, кроме того уровней будет врятли больше 5-ти.

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

Не вижу сложности. Считаете + memcached. Если совсем туго, можно считать приблизительно.

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

А почему не добавить дополнительное поле в таблицу, которое будет содержать абсолютное количество всех детей?

мне это не нужно. Это у меня уже есть. Мне нужно количество объектов, но с учетом города.
Цитата ("kirilev"):

А сам счётчик будет увеличиваться на +1 если объявление было добавлено/перемещено для одной из дочерных категорий на любой "глубине", или -1, если объявление переместили в другую категорию/город.

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

Как раз с уровнями у меня проблем никаких нет. Все работает и очень даже шустро. Проблема с подсчетом объектов.
Цитата ("kirilev"):

эту задачу не на форуме решать, а в тендере.

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

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

Считаете

в этом и проблема. Как считать?
Цитата ("Enkvist"):

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

а это еще как? Поделитесь?

В мемкэш/redis вынести всенафиг
mongo удобно под такие штуки еще, правда надо чуть переделать систему

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

В мемкэш/redis вынести всенафиг

и что это даст? Ведь проблема в самой логике а не в используемом механизме.

WebDesignStudio, глубоко не вникал в задачу - не слишком понятно описано. Мне кажется, что запросы с подсчетом количества и группировкой должны помочь.
SELECT loc_id,count(*) FROM `objects` WHERE cat_id = ? GROUP BY loc_id Так запросов надо по числу городов. Можно попробовать еще навернуть, чтобы вообще чисто через sql апдейтить таблицу. Запускать по крону, а текущие изменения делать инкрементом и декрементом.

Или так
SELECT cat_id, loc_id,count(*) FROM `objects` GROUP BY loc_id,cat_id - не оно?

frig, опишу более коротко и на конкретном примере, так как получилось много буков.

Вот пациент ссылка

допустим заходит на главной пользователь А. Он выбрал Киевскую область. Ему надо показать сколько всего объявлений в Киевской области И в городах этой области(тут на практике вложенность городов=2).
Но надо не общее количество, а для каждой категории отдельно.
Допустим Транспорт. Имеет подкатегории (легковые авто итд). Рядом с ним, надо показать количество объявлений которые есть в категории транспорт и все его подкатегории.
Для подкатегорий та же лолгика.
Надеюсь так понятнее.

WebDesignStudio, тот запрос что в моем последнем сообщение выводит не те данные?
По идее в результатах будут данные по конечным категориям, а для категорий более высокого уровня надо будет эти значения суммировать.

По поводу приблизительного подсчета. Я в задачу сильно не вникал (многобукаф). Так что расскажу на другом примере.
Когда-то очень давно я делал сайт знакомств.
Искать по миллионам анкет было достаточно сложно, поэтому поиск производился в какой-то части ( к примеру, по тысяче анкет). а потом делалось $result *= floor($all_anketas / $our_part).
(идея описана очень примитивно. это то, что мне запомнилось. там еще было пару механизмом, которые корректировали кол-во ). так как никто дальше 10 страницы не заходил - было норм )
так и тут.. устройти свою базу данных так, чтобы можно было по какой-то ее части судить о ней в целом ) . (Все равно никто проверять не будет. главное $our_part = floor($all_anketas / 10 ); сделать.. чтобы погрешность была не слишком безумная).

Enkvist, так не красиво. И не получится использовать ваш метод.

Тогда в чем вопрос вообще? Подсчитали - закэшировали.

frig, думал примерно о таком. Но там вернет большой объем данных, которые надо будет на PHP обработать. Не знаю, идея тоже была, но не до конца ее обдумал.

Так же можно заниматься глобальным отловом всех действий с категориями и делать обсчет по факту)

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

Так же можно заниматься глобальным отловом всех действий с категориями и делать обсчет по факту)

это второй предложенный мною метод
Тут слишком сложно запрограммировать ситуации изменения категории или города для объявления или вообще перенос категории.

WebDesignStudio, дело в том, что чуда не произойдет. Есть memcache.
И есть два варианта:
1) Ломать свои мозги. Если тут вы считаете, что оно того не стоит, тогда вариант:
2) Ломать мозги сервера.

Лучше один раз Цитата ("Enkvist"):

Ломать свои мозг

чем постоянно Цитата ("Enkvist"):

Ломать мозги сервера.

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

Но там вернет большой объем данных, которые надо будет на PHP обработать.

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

Структура дерева каталогов насколько я понимаю, меняется не часто? Тогда для хранения дерева каталогов вместо алгоритма adjacency list что у вас можно использовать алгоритм nested set(ссылка). При помощи него все дочерние узлы выбираются одним запросом. И вторым запрос типа SELECT count(*) from objects where loc=? and cat in(список id каталогов).