Busque en 300 millones de direcciones con pg_trgm

La partición de tablas no ayudará en absoluto .

Pero sí, hay una buena manera:Actualizar a una versión actual de Postgres. Ha habido muchas mejoras para los índices GiST, para el módulo pg_trgm en particular y para big data en general. Debería ser sustancialmente más rápido con Postgres 10.

Su búsqueda de "vecino más cercano" parece correcta pero para un pequeño LIMIT use esta consulta equivalente en su lugar:

SELECT address, similarity(address, '981 maun st') AS sml 
FROM   addresses 
WHERE  address % '981 maun st' 
ORDER  BY address &lt-> '981 maun st'
LIMIT  10;

Citando el manual: