After redesigning the schema to have a bunch of duplicate information in different tables and rebuilding the whole thing over night the queries are taking much less time.
Like half a second instead of minutes.
So that was worth it.
I still don't really approve of this 'sql' thing.