Podría crear una 'vista materializada'.http://en.wikipedia.org/wiki/Materialized_view
básicamente una tabla que son los resultados de JOIN, y crea un índice de texto completo sobre eso.
CREATE TABLE materialized (FULLTEXT idx (user_name,department_name))
SELECT u.id,user_name,department_name
FROM users u INNER JOIN departments d ON (d.id = dept_id)
En su lugar, puede ejecutar consultas en esa tabla.
SELECT * FROM materialized WHERE MATCH(user_name,department_name) AGAINST('test' IN BOOLEAN MODE)
pero...
Deberá actualizar la tabla periódicamente (o cuando se actualicen las tablas subyacentes); lo más fácil es simplemente DROP y recrear - O puede usar TRUNCATE luego INSERT INTO ... SELECT ... FROM ... formato.
(Los esquemas más elaborados involucran activadores para mantener la 'vista' actualizada, o incluso mirar el binlog y reproducir actualizaciones contra la 'vista')
