Randomly picking entity not yet in a join table

Question

This seems interesting.

Assume three tables, users, items and a join table users_items. The latter links users.ids to items.ids. We say that user U owns item I when there's a row in the users_items table that contains the pair (U.id, I.id).

Now: how would I go about randomly choosing an item that a particular user does not yet own?

The most feasible solution seems to be:

gather all item ids.
gather ids of items owned by user U.
remove all ids from step #2 from the set generated in #1
pick random element from the resulting set (trivial)

Is this the only sane way? Is it optimal? Let's assume this would be a heavily used feature. And the numbers of elements in each table are huge.

Any fun ideas, thoughts?

score 2 · Accepted Answer · answered May 23 '12 at 23:07

2

You can use a left join to generate a list of item ids that the user does not currently own by doing :

SELECT i.id
FROM items i 
LEFT JOIN users_items ui ON ( i.id = ui.item_id AND ui.users_id = 2 )
WHERE ui.item_id IS NULL;

From here, you can randomly select one of the elements from the result set.

answered May 23 '12 at 23:07

keelerm

2,873
20
12

But that would only join with the items that user 2 owns. For one what if user 2 is the one querying this? For another this would not return all the items that the user doesn't have. This would only work if the querying user owns what user 2 does not and vis versa. – Kyra May 23 '12 at 23:09
The [left join](http://en.wikipedia.org/wiki/Join_(SQL)#Left_outer_join) allows you to match each record in the items table ( the left table ) with rows from the users_items ( right table ), even if a matching record does not exist in the right table.By adding the WHERE ui.item_id IS NULL, you are expressly requesting all rows that **didn't** have a matching record. As for the ui.users_id = 2, you would just want to replace this with the appropriate users_id of interest when generating the query. – keelerm May 23 '12 at 23:13

score 0 · Answer 2 · edited May 23 '17 at 12:20

Why don't you randomize the sql so that so this is done in one query. I'm not sure if you are using mysql, tsql or something else but this question mentioned using ORDER BY RAND() LIMIT 1. How about something like this:

select i.itemName
from users as s
left join items as i
    on i.id not in 
        (select ui.itemID from users_items as ui where ui.userID = u.id)
order by rand()
limit 1

Randomly picking entity not yet in a join table

2 Answers2