Немного не хватает данных для вопроса: сколько уровней подкатегорий?

Если рассмотреть вариант для двух уровней:
Не вижу ничего страшного получать данные в двух запросах.
1) выбираем категории

SELECT * FROM `cat` WHERE `pid`=0

В цикле получаем массив категорий, а так же формируем переменную $ids вида "1, 3, 6, 23, 56, .."
2) получаем подкатегории

SELECT * FROM `cat` WHERE `pid` IN (_переменная_выше_)

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

Если такая большая база, то я полагаю есть условия выборки категорий? Не все же 5к выводить.
Если так, то есть смысл выбрать одним запросом сразу все категории, а уже в цикле обработки результата запроса разрулить все категории и подкатегории.

$cats = array();
$sql = "SELECT * FROM `cat` WHERE <условие>";
$res = $db->query($sql);
while ($row = $db->fetch($res)) {
 $cats[$row['pid']][] = $row;
}

Смысл в том, чтобы верхние категории были в массиве $cats[0], а подкатегории в $cats[_ид_категории_родителя_].
Отображать рекурсивно.

PS: если где ошибся - завтра поправлю. сонный уже)

Введи дополнительно поле в таблицу cat, назови его например hist_index, в нем храни такую информацию : hist_index(родительской строки)+pid.
Таблица должна получиться такого типа :
id pid hist_index
1 0
2 1 -1-
3 1 -1-
4 2 -1-2-
5 3 -1-3-
6 4 -1-2-4-
7 6 -1-2-4-6-
8 5 -1-3-5-

Тогда SQL для выбора все подкатегорий с категории 2 :

SELECT * FROM cat WHERE hist_index like '%-2-%'

Есть и другой вариант, делать JOIN столько раз, сколько уровней... но это геморно и несистемно...

dr_Lev, не совсем понял зачем дополнительное поле в таблицу.
В любом случае запросы LIKE очень и очень медленные. Я бы не стал их использовать в данном случае.

Мой пример быстрее всего по скорости обработки запроса. Если будут проблемы с рекурсивным отображением - напишу пример.

Спасибо! всем кто ответил
так и не смог вывести категорию и под категорию одним запросом без рекурсии

остановился на выводе в два запроса без рекурсии

сперва по pid вывожу родителей потом в цикле вывожу потомков

$cats = array();
$sql = "SELECT * FROM `cat` WHERE <условие>";
$res = $db->query($sql);
while ($row = $db->fetch($res)) {
 $cats[$row['pid']][] = $row;
}