Antes de entrar en AWK, ¿no te serviría grep +
join?
A propósito de grep, suele ser bastante más rápido que AWK, por lo que me sorprende un poco tu primer comentario, ¿será que no estás haciendo las cosas de la forma más eficiente? ¿cómo es tu programa ahora mismo?