Workaround: This query was being exported after running, and included several filters for export purposes only. There are filters in the query to look for only constituents who have a primary phone number/email or no phone number/email at all, and to output the primary phone/email only:
(Constituent\Phones\Number is blank
Constituent\Phones\Primary phone number is equal to Yes)
(Constituent\Email address\Email is blank
Constituent\Email address\Primary email address is equal to Yes)
When these fields are removed, the results are returned quickly, and the number of results does not change. Users can then modify the export definition used to output primary email and phone only. However, previously the export was being generated directly from the ad-hoc query, so the additional step of building an export definition is not ideal.