SELECT
`users`.`id` AS `user_id` ,
`utime`.`uid` ,
`utime`.`type`
FROM `users`,`utime` WHERE `users`.`id` = `utime`.`uid`
AND `utime`.`type` is NULL
ORDER BY `user_id` ASC
LIMIT 0 , 6
Нагрузка будет при лбом запросе, другое дело что это нормальная нагрузка до ляма записей, да и после ляма тоже, хотя время выборки конечно возрастет. Но, тут можно еще попробовать innoDB с внешними ключами, но я не подскажу как это правильно реализовать.