Advanced Search on relationship to group members runs very long

On an installation with more than 100K contacts, searching for contacts with a relationship to members of a group runs very long on the server (past a five minute front end timeout).

This is the case even with a non-smart group of 37 contacts (and fewer than 1000 total relationships).

The same search, done via reports instead, works fine.

Does not reproduce on 4.7 demo, but then that only has a smaller number of contacts.