Steps to reproduce, if you have a Moodle site with serveral million users:

1. As admin (or other role with access) go to the Check permisions page for a course of an activity. (That is, a page like https://qa.moodledemo.net/admin/roles/check.php?contextid=25, but the demo site does not have enough users to trigger the bug.)
2. Type something in the search box.

Expected result: search results returned in reasonable time.

Acutal result: painfully slow, possibly even leading to the Ajax request timing out and locking up your session.

The problem is with the quries in admin/roles/classes/check_users_selector.php. For example, there is one doing ... FROM {user} u JOIN (SELECT DISTINCT subu.id FROM {user} subu JOIN ...) which looks very dangerous. Another does ... FROM {user} u LEFT JOIN ({user_enrolments} ue ... which also looks dangerous.

Someone needs to get in there and EXPLAIN those, work out which one(s) are the problem, and optimise them, but they are showing up in our slow query log, taking times like 50+ seconds sometimes.

Following analysis, I think there are several fixes that will help

1. Do an intial query to find the required fieldids, and then put those directly in the main query, instead of requiring a separate join.
2. Change the main query, so that instead of doing SLECT FROM users LEFT JOIN user_info_data it does SELECT FROM users ... UNION SELECT FROM users JOIN user_info_data.
3. Implement an 'exact matches only' option.

I will do 1. and 2. here, and I will do 3. in a separate issue: MDL-78312.