Slow query with large dataset in Drupal views — better to process in SQL or PHP?

I have a large userbase in my Drupal 7 site, which contains a People finder. Because there are hundreds of thousands of users and we want to display the People finder in a random order on page load, I presume it's transferring the whole userbase into memory at some point, in order to paginate (using the Pager built-in to Views2 Views3).

I've noticed that the query has no limit against it (presumably because of pagination) and that it joins against users_roles twice (because I need to include all users of rôle A but not also of rôles B, C and D). I've added comments against the WHERE clause to explain each line's purpose and how it's come out of my View.

SELECT
    users.uid AS uid,
    'user' AS field_data_field_user_image_user_entity_type,
    'user' AS field_data_field_user_field1_user_entity_type,         -- custom field
    'user' AS field_data_field_user_field2_display_user_entity_type, -- custom field
    'user' AS field_data_field_user_field3_user_entity_type,         -- custom field
    'user' AS field_data_field_user_field4_user_entity_type,         -- custom field
    RAND() AS random_field
FROM
    users users
    INNER JOIN users_roles users_roles ON users.uid = users_roles.uid
    LEFT JOIN users_roles users_roles2
        ON users.uid = users_roles2.uid
        AND (users_roles2.rid = :views_join_condition_0
          OR users_roles2.rid = :views_join_condition_1
          OR users_roles2.rid = :views_join_condition_2)
WHERE
    (( (users.status <> :db_condition_placeholder_3)      -- Active users only
    AND (users_roles.rid = :db_condition_placeholder_4)   -- Must be in rôle A
    AND (users_roles2.rid IS NULL)                        -- Must not be in rôles B, C, D
    AND (users.uid != :users_uid OR users.uid IS NULL) )) -- Must not be current user
ORDER BY random_field ASC

So I have two questions:

1. Is there some way in Views2 that I can somehow get this query to be limited (potentially by sorting on something else that pretends to be random)? I assume that transferring fewer result rows per query is likely to help with the memory overhead?
2. If I want to mess with that WHERE clause, am I better off using a PHP Filter Criterion to do the roles messing (which would presumably remove the double-join) or should I move the whole damn query into either a custom module^[a] or a mySQL view^[b]?

^{a: I assume that would attach to the relevant hook with a function modulename_views_pre_execute(&$view).
b: I assume a mySQL view would still need to do both joins, one inner join and one left join, so I can't quite see how this would help.}

For what it's worth, I know that my site will have a relatively short lifetime and, during that, the rôles won't change, so I am happy to hardcode the rôle IDs, if that will give me a performance benefit.