Alex Kheben

Не совсем понял что вы хотите. Вы хотите получить готовое дерево? Т.е. готовый многомерный массив?

опции через запятую

Поддерживаю @Aliance. Вам определённо нужно уволить проектировщика БД ;)

Теперь выхода 2:
1) Нормализовать структуру и делать более логичные, лёгкие и простые запросы.
2) Делать выборку по регулярке или полнотекстовому поиску. А чтобы выборка происходила быстрее нужно сделать функциональные индексы на популярные опции.

Давно не работал с MySQL, но вот как мне видится решение:

SELECT a.row_id, a.name
FROM a JOIN b ON b.table_a_id=a.id
WHERE a.id IN (
  SELECT a.id FROM a JOIN b ON b.table_a_id=a.id AND b.status_id=1
  INTERSECT
  SELECT a.id FROM a JOIN b ON b.table_a_id=a.id AND b.status_id=2
)

Кажется, в одной из последних версий MySQL шардинг поддерживается на уровне СУБД и для клиента (PHP) это должно быть прозрачно. Может стоит использовать нативные средства шардинга, чем использовать стороннее решение?

Может есть смысл как-то лимитировать его?

Возможно я ошибаюсь и результаты тестов, которые я проводил весьма субъективные, НО.
Данные имели журнальный характер и простая выборка из таблицы MyISAM была быстрее, чем в Innodb.
И по формату времени «datetime», я стараюсь использовать везде timestamp. Может вам тоже стоит попробовать потестировать производительность с ним, вдруг будет быстрее?)
И ещё один момент «archive_date >= '2013-01-01' and archive_date <= '2013-02-01'». Вот так «archive_date between '2013-01-01' and '2013-02-01'», на мой взгляд, выглядит как-то кошернее. Но я не супер спец, конечно и поэтому, возможно, в чём-то ошибаюсь.