Есть 2 таблицы:

request: (Запросы/заказы)
- id
- product_id
- shop_id
- customer_id

customer_name: (Имя клиента в разрезе пользователя)
- customer_id
- user_id
- name

(Нужно вывести список запросов с фильтром по shop_id, и сортировкой по имени клиента)

SELECT c.name, r.* FROM request r
LEFT OUTER JOIN customer_name c ON c.customer_id = r.customer_id AND c.user_id = 'yyy'
WHERE c.shop_id = 'xxx'
ORDER BY c.name
LIMIT 20
OFFSET 20

Дак вот есть подозрение, что сервер умрет на таком запросе если будет много (миллион) строк.

Даже если будет индекс на customer_name с сортировкой по name и фильтрами (user_id, curstomer_id), серверу все равно придется сначала в памяти сформировать временный результат из request (SELECT FROM request r WHERE c.shop_id = 'xxx'), а это может быть миллион строк, далее пойдет процесс "пристыковки" сортированной таблицы customer_name, и от сюда уже возьмется только 20 строк.

p2. чтобы ткнули в избыточную левость запроса?
левость тут не избыточна - таблица customer_name может быть пустой, но заказы выдать все равно нужно.

p2. а тему то заводил для чего,
Что-б спецы подсказали, есть ли решение лучше (этого решения "в лоб"), либо подтвердили, что sql тут "сосет".

если описать задачу на пальцах - клиенты делают заказы, а сотрудники захотели именовать клиентов по своему - сотрудники именуют одних и тех же клиентов по своему (и именования других сотрудников им показывать нельзя), в результирующей таблице нужна возможность сортировать заказы по клиенту.

Скажите пожалуйста, зачем вам request r LEFT OUTER JOIN customer_name c, если вы тут же пишете WHERE c.shop_id = 'xxx' ? Проблемы будут как раз из-за этого.
Упс, опечатка, нужно фильтровать заказы по магазину (WHERE r.shop_id = 'xxx'):

SELECT c.name, r.* FROM request r
LEFT OUTER JOIN customer_name c ON c.customer_id = r.customer_id AND c.user_id = 'yyy'
WHERE r.shop_id = 'xxx'
ORDER BY c.name
LIMIT 20
OFFSET 20

В крайнем случае можно для этого держать кеш-таблицу с нужными индексами, но это не "интересно" - в этом случае psql со своими джойнами не лучше чем какой-нибудь nosql.