При таких объемах часто применяются всякие денормализации чтобы не было фуллскана, с индексами нужно копаться, запросы иногда писать иначе, может у вас там сотня JOIN в которых связь идет не по ключам, а по простым текстовым полям или еще какие то штуки, при 100к записей незаметно было, а при 500м стало.
ну и как люди выше написали - профилируйте..
И еще кстати, если ваш селект возвращает ну к примеру 100 миллионов из ваших 500, то надо лимит применять, там узким местом может быть уже сетевой стек.