В статье "Working with the MySQL Access Privilege System (http://www.devshed.com/c/a/MySQL/Working-with-the-MySQL-Acce.../)" доступно и подробно рассказывается про организацию системы контроля доступа в MySQL.

В заметке "Why MySQL could be slow with large tables (http://www.mysqlperformanceblog.com/2006/06/09/why-mysql-cou.../)" рассмотрены три фактора (размер буферов, индексы и "join" операции ) влияющие на производительность MySQL при работе с таблицами с большим объемом данных.

URL: http://www.devshed.com/c/a/MySQL/Working-with-the-MySQL-Acce.../
Новость: http://www.opennet.me/opennews/art.shtml?num=7703

• Управление привилегиями в MySQL. Производительности и большие таблицы,igorsia, 09:23 , 11-Июн-06
• Управление привилегиями в MySQL. Производительности и большие таблицы,sabay, 11:33 , 11-Июн-06
  • Управление привилегиями в MySQL. Производительности и больши...,Vadim Tkachenko, 20:44 , 12-Июн-06
    • Управление привилегиями в MySQL. Производительности и больши...,igorsia, 09:09 , 13-Июн-06

По моим наблюдениям у MySQL проблема не с большими таблицами а с оптимизатором запросов. В версии 4.1 запрос по двум индексированным полям, связанным через OR вызывал full scan. В 5.0 уже используются индексы, но более сложные запросы все равно могут уводить в полное сканирование таблицы.
Зачастую сабжу проще сделать сотню простых (в одно условие) поисков чем один сложный запрос. Не рекомендуется использовать подзапросы, там где можно обойтись обычным JOIN а также конструкцией IN - на порядок быстрее сделать запрос по каждому значению.

Полностью поддерживаю. Оптимизатор мерзкий в mysql. Если в таблице составные индексы и подмножества полей в них пересекаются - то mysql jxtym часто берет не лучший из индексов. и  при явном указании индекса запрос часто начинает работать на ПОРЯДОК быстрее.

Если можно то дайте пример таблицы, индексов и запроса.

Если есть желание обсудить вопрос лучше обращайся ко мне на почту.