Búsqueda indexada de substrings

Hola a todos.
Estoy buscando alguna forma para la búsqueda indexada de substrings en
un campo. Es decir, en un campo que contiene nombres quiero buscar todos
aquellos que contengan, en cualquier lugar de la cadena, un determinado
subtexto y, fundamentalmente, esta búsqueda DEBE ser indexada dado el
tamaño de la tabla y la frecuencia de esta consulta.

Hasta el momento encontré tres cosas pero ninguna es suficiente:
1) búsqueda con indexes creados con operadores "pattern" (CREATE INDEX
test_index ON test_table (col varchar_pattern_ops);) : permite la
búsqueda con like pero hay restricciones como por ejemplo que el pattern
no puede empezar con %. Lo probé y efectivamente es así. Es decir, no
serviría porque buscaría el subtexto sólo en el principio de la cadena.
2) tsearch2: busca por palabras completas y no por cualquier subtexto.
3) openFTS: mismo problema que tsearch2.

Alguien conoce alguna otra solución alternativa en lo posible dentro de
la base de datos?

Digo esto último porque una alternativa que barajamos es exportar un
archivo de texto con todos los valores y usar un grep para la búsqueda
(funciona bastante bien y con buenos tiempos), pero no nos convence por
varios motivos:
- es más desprolijo: deja de ser una cuestión transparente de un simple
query.
- es más inseguro: correr un script con el grep tiene sus
vulnerabilidades (supongamos que algún usuario malintencionado logra
meter código que ejecute el script, por ejemplo cerrando el texto de
búsqueda del grep y agregando comandos indeseados).
- hay que lidiar con problemas de sincronización con los valores que van
cambiando y regenerar el archivo cada vez que se producen y esas cosas.

Muchas gracias.