Выборка, сортировка, подсчет данных по нескольким ключам, как решить?
Не буду претендовать на абсолютную верность моей точки зрения, но все же, разные мысли вслух.
Писал в том порядке в каком приходило в голову :)
1. Мне кажется что решение с хранением заранее рассчитанных счетчиков изначально не верное, т.к имеет сложность N2. По базе ФИАС только в РФ территориальных единиц начиная с поселка ~55 000, а если Вы захотите расширяться за пределы?
2. Если говорить про SQL можно делать выборки видаselect count(*) from items where category_id IN ( 1,2,3 ) and region_id IN (1,2,3)
Соответственно что бы получить id элементов для подстановки - можно кешировать id детей в таблицах категорий и регионов. Вам подгадят запросы уровня Россия - т.к там по сути будут все id какие есть)
C учетом того, что запрос IN начинает себя не очень хорошо вести на ~тысячах значений внутри условия, - я бы шардировал таблицу items по полям category_id и region_id 
3. Так ли Вам нужна возможность бесконечной вложенности категории и региона? Неужели десятка уровней не хватит? Да, это раздует таблицу items, но её можно будет просто шардировать по item_id
4. Не очень понятно сколько у Вас items, но если тоже сотни миллионов - я бы посмотрел куда то в сторону Hadoop MapReduce
5. Для хранения счетчиков можно тупо взять redis.
instagram-engineering.tumblr.com/post/12202313862/...
Вот тут ребята пишут что на хранение 1kk ключей у них ушло ~70MB в лоб, и это можно оптимизировать.
Пост двухлетней давности, память с тех пор подешевела. Вам нужно будет всего то 12Gb по верхней оценке, опять же шардирование никто не отменял.
Правда см п1, с учетом сложности N2 это может быть быстрым временным решением, но надолго его не хватит, если вы будете увеличивать регионы и категории.
Фуф. Давайте дискутировать :)
Для поиска лучше использовать сервисы, ориентированные на поиск. Например Solr. Копать в сторону /dataimport, либо реализовать демон, например, на nodejs - для индексации по требованию (через http-запрос либо очередь, например, rabbitmq). Поиск будет работать быстро. вопрос только за быстрой индексацией.