Il partizionamento delle tabelle non aiuterà per niente .
Ma sì, c'è un buon modo:Aggiorna a una versione corrente di Postgres. Ci sono stati molti miglioramenti per gli indici GiST, per il modulo pg_trgm in particolare e per i big data in generale. Dovrebbe essere sostanzialmente più veloce con Postgres 10.
La tua ricerca "vicino più vicino" sembra corretta ma per un piccolo LIMIT usa invece questa query equivalente:
SELECT address, similarity(address, '981 maun st') AS sml
FROM addresses
WHERE address % '981 maun st'
ORDER BY address <-> '981 maun st'
LIMIT 10;
