The use case is, that I have a table *products* and *user\_match\_product*. For a specific user, I want to select X random products, for which that user has no match.

The naive way to do that, would be to make something like

`SELECT * FROM products WHERE id NOT IN (SELECT p_id FROM user_match_product WHERE u_id = 123) ORDER BY random() LIMIT X`

but that will become a performance bottleneck when having millions of rows.

I thought of some possible solutions which I will present here now. I would love to hear about your solutions for that problem or suggestions regarding my solutions.

**Solution 1: Trust the randomness**

Based on the fact that the product ids are monotonically increasing, one could optimistically generate `X*C` random numbers `R_i` where `i` between `1` and `X*C`, which are in the range `[min_id, max_id]`, and hope that a select like the following will return X elements.

`SELECT * FROM products p1 WHERE p1.id IN (R_1, R_2, ..., R_XC) AND NOT EXISTS (SELECT * FROM user_match_product WHERE u_id = 123 AND p_id = p1.id) LIMIT X`

Advantages

* If the random number generator is good, this will probably work very well within *O(1)*
* Old and newly added products have the same probability of being choosen

Disadvantages

* If the number of matches is near to the number of products, the collision probability might be very high.

**Solution 2: Block-wise PRNG**

One could create a permutation function `permutate(seed, start, end, value)` for the domain `[START, END]` that uses a `seed` for randomness. At time `t0` a user `A` has `0` matched products and observes that `E0` products exist. The first block for the user `A` at `t0` is for the domain `[1, E0]`. The user remembers a counter `C` which initially is `0`.

To select X products the user `A` first has to create the permutations `P_i` like

`P_i = permutate(seed, START, END, C + i)`

The following has to hold for the function.

* `permutate(seed, start, end, value)` is element of `[start, end]`
* `value` is element of `[start, end]`

The following query will return X non-repeating elements.

`SELECT * FROM products WHERE id IN (P_1, ..., P_X)`

When `C` reaches END, the next block is allocated by using `END + 1` as the new `START`, the current count of products `E1` as new `END`. The `seed` and `C` stay the same.

Advantages

* No collisions possible
* Guaranteed *O(1)*

Disadvantages

* The current block has to be finished before new products can be selected