columnas con dos datos posibles (M,F)

Estimados,

quisiera compartir con ustedes una inquietud.
Cuando se hace un "group by" de algunas columnas considerando una
condición en la que se seleccione algún valor de otra columna con dos
datos posibles (ej: columna sexo:masculino/femenino), el tiempo de
respuesta excede los 15 segundos cuando la tabla contiene más de 6
millones de registros, como es mi caso.

Para la siguiente consulta:
SELECT edad, region, count(*) AS cantidad FROM afiliados WHERE
sexo='M' GROUP BY edad, region ORDER BY edad, region;
se puede crear un índice en la columna sexo que me permita mejorar el
rendimiento, pero la verdad es que seleccionar registros con sexo
masculino, me significa obtener algo así como la mitad de la tabla, o
sea, + de 3 millones de registros y luego un ordenamiento secuencial
para edad y región, por lo que en estos casos el rendimiento no se nota
mucho.

He oído algo parecido a "índices binarios" de postgreSQL que justamente
permite mejorar el tiempo de procesamiento en estos casos donde las
columnas contienen pocos datos separables (ej: M o F) en tablas con
millones de datos.
Si alguno de ustedes me pudiera decir cómo podría manejar esta situación
o si alguien hubiese escuchado de este "indice binario" o algo así, se
lo agradecería. Ah, y por supuesto, cualquier comentario es siempre
bienvenido.

Atentamente,

Luis Salas E.
SAFP
Santiago, Chile.