Recursive ORDER BY

Viewed 65

I have a USERS table which is a membership matrix like below. Table is unique on ID, and each ID belongs to at least one group, but could belong to all 3.

SELECT  1 AS ID, 0 AS IS_A, 0 AS IS_B, 1 AS IS_C FROM DUAL UNION ALL
SELECT  2,0,1,0 FROM DUAL UNION ALL
SELECT  3,0,1,1 FROM DUAL UNION ALL
SELECT  4,1,1,0 FROM DUAL UNION ALL
SELECT  5,1,1,0 FROM DUAL UNION ALL
SELECT  6,1,1,1 FROM DUAL UNION ALL
SELECT  7,0,1,1 FROM DUAL UNION ALL
SELECT  8,0,0,1 FROM DUAL UNION ALL
SELECT  9,1,0,0 FROM DUAL UNION ALL
SELECT 10,1,0,1 FROM DUAL UNION ALL
SELECT 11,0,0,1 FROM DUAL UNION ALL
SELECT 12,0,1,1 FROM DUAL

The final goal is to SELECT randomly a sample of at least 4 users from A, 3 from B and 5 from C (just an example) but with exactly 10 distinct IDs (otherwise the solution is trivial; just SELECT *).

The focus is less to determine if it's possible at all, but more to attempt a best effort to maximize memberships.

The output is expected to be unique on ID.

I can only think of a procedural way to achieve this:

  1. Take the first ID with MAX(IS_A+IS_B+IS_C)
  2. Check if the quotas are reached
  3. If, for example, we already have 4 users from A, then we'll continue with the next ID with MAX(IS_B+IS_C), completely ignoring any further contributions from IS_A column
  4. If we have already achieved all quotas, revert back to taking MAX(IS_A+IS_B+IS_C) to get "bonus" points
  5. Stop upon reaching the overall maximum of 10

In essence, we prioritize and incrementally take the ID that has the most memberships in groups that have not reached the quota

However, I can't figure out how to do this in Oracle SQL since the ORDER BY would depend on not just the current row's values, but also recursively on whether the earlier rows have filled up the respective quotas.

I've tried ROWNUM, ROW_NUMBER(), SUM(IS_A) OVER (ORDER BY ...), RECURSIVE CTE but to no avail. Best I have is

WITH CTE AS (
  SELECT ID, IS_A, IS_B, IS_C
  , ROW_NUMBER() OVER (ORDER BY IS_A+IS_B+IS_C DESC) AS RN
  FROM USERS
)
, CTE2 AS (
  SELECT CTE.*
  , GREATEST(4 - SUM(IS_A) OVER (ORDER BY RN), 0.001) AS QUOTA_A --clip negatives to 0.001
  , GREATEST(3 - SUM(IS_B) OVER (ORDER BY RN), 0.001) AS QUOTA_B --so that when all quotas are exhausted,
  , GREATEST(5 - SUM(IS_C) OVER (ORDER BY RN), 0.001) AS QUOTA_C --we still prioritize those that contribute most number of concurrent memberships
  FROM CTE
)
SELECT ID FROM CTE2
ORDER BY QUOTA_A*IS_A + QUOTA_B*IS_B + QUOTA_C*IS_C DESC
FETCH NEXT 10 ROWS ONLY

but it does not work because QUOTA_A is computed based on ORDER BY RN instead of recursively.

Thanks in advance!

0 Answers
Related