Yaxshi savol.

Querylarning "kayfiyat"iga qarab ba'zi yechimlarni sinab ko'rish mumkin:

1. Indexing. Querylarni analiz qilib ko'ring. Shunga qarab kerakli columnlarga indexlar qo'shing. Agar zarur bo'lsa non-key value attach qiling.

2. Pagination(PostgreSQL)

3. Agar indexing yetarlicha natija bermasa sal murakkabroq usulni sinab ko'ring: Horizontal partitioning.
Bu usul katta tableni bir nechta kichik tablelarga bo'lishdan iborat.

4. Partial indexing. Google qilib ko'ring. Lekin bu usul implement qilishga qiyinroq va ehtiyot bo'lib ishlatmasangiz teskari natija berishi mumkin.
Upd: Partial indexing orqali siz kutgan natijani olish qiyinroq.
Bo'pti, bu variantni chiqarib tashlang.

P.S. Yuqoridagilarning har birida pros&cons bor.