How about trying the following:If you had an index on col and userid it should resolve completely in the index and not need to touch the table at all.
Select count(userid) n, colfrom (select col, userid from users group by col, userid)group by col;