MySQL Query faster alternative to DISTINCT and REGEXP

You might get faster performance using FIND_IN_SET and a couple of joins:

SELECT DISTINCT locations.*
FROM locations
INNER JOIN users users_include ON
  users_include.user_id = 1      
  AND FIND_IN_SET(users_include.user_locations, locations.combined_locations) > 0
  AND users_include.user_selection = 'Yes'
LEFT JOIN users users_exclude ON
  users_exclude.user_id = 1
  AND FIND_IN_SET(users_exclude.user_locations, locations.combined_locations) > 0
  AND users_exclude.user_selection = 'No'
WHERE users_exclude.user_id IS NULL

Note that the logic implemented here is “at least one location with user_selection = ‘Yes’ and no location with user_selection = ‘No'” – I think this is the same as the logic implemented by your query.

If the logic instead should be “all locations with user_selection = ‘Yes’ and no location with user_selection = ‘No'”, that can be accomplished with a GROUP BY clause and a HAVING clause (with a count):

SELECT locations.*
FROM locations
INNER JOIN users users_include ON
  users_include.user_id = 1
  AND FIND_IN_SET(users_include.user_locations, locations.combined_locations) > 0
  AND users_include.user_selection = 'Yes'
LEFT JOIN users users_exclude ON
  users_exclude.user_id = 1
  AND FIND_IN_SET(users_exclude.user_locations, locations.combined_locations) > 0
  AND users_exclude.user_selection = 'No'
WHERE users_exclude.user_id IS NULL
GROUP BY locations.id, locations.column1, locations.column2, locations.combined_locations
HAVING (1 + CHAR_LENGTH(combined_locations) - CHAR_LENGTH(REPLACE(combined_locations, ',', ''))) = COUNT(users_include.user_id)