Priority Queue in SQL

Question

I am introducing a queuing system with several priorities.
I need a query that can return X rows with at least Y rows of each priority.

For instance:

Suppose a queue has 3 priorities (high, medium, and low), and I would like 3, 2, and 1 lines for each priority, respectively.

If the table looked like this:

----------------- | Id | Priority | ----------------- | 1 | High | | 2 | High | | 3 | High | | 4 | High | | 5 | Medium | | 6 | Medium | | 7 | Low | ----------------- 

Three simple queries to be combined will return (1, 2, 3, 5, 6, 7).

 SELECT TOP 3 Id FROM tbl WHERE Priority = 'High' UNION SELECT TOP 2 Id FROM tbl WHERE Priority = 'Medium' UNION SELECT TOP 1 Id FROM tbl WHERE Priority = 'Low' 

However, the problem occurs when the table does not contain a sufficiently defined priority:

 ----------------- | Id | Priority | ----------------- | 1 | High | | 2 | High | | 3 | High | | 4 | High | | 5 | Medium | | 6 | Low | | 7 | Low | ----------------- 

I would like to return it (1, 2, 3, 4, 5, 6).
Using the highest priority to fill in the blanks (in this case, using the fourth line of High, as there are not enough Mediums).

Is there a query that matches this, or would I rather filter inside my application, rather than at the SQL level?

Answer 1

You can always write a stored procedure that does this in a for loop (3 times, one for each priority, starting with the lowest) and dynamically adjust the number of values ​​that will be returned in the next iteration (higher priority) at each iteration if This is not enough.

With dynamically, I mean:

 SELECT TOP (@count) * FROM SomeTable 

where count was adjusted, if necessary, in the previous iteration.

The problem with the presence in the application logic is that you will need to get more data (3 times the maximum counter used in TOP ), so that you have enough data to fill your slots, or you need to contact your database again.

For small numbers, preventative overfetch is not important. My preference would be to have it in a stored procedure.

But there are several variables that play a role: the size of the individual selected rows, the size of the lookup table and its indexes, software architecture, network configuration, counter values, number of priorities, etc., etc.

Answer 2

Assuming you are on SQL Server 2005 or higher, a combination of nested CTE and ranking functions should be able to do the trick:

 ;with A as ( select top 3 * from tbl where priority = 'High' ), A1 as ( select id, priority from ( select * from A union all select top 2 id, priority from (select *, ROW_NUMBER() over (order by case when priority = 'Medium' then 1 else 2 end) as ranker from tbl where priority in ('High', 'Medium') and id not in (select id from A))Z order by ranker asc ) X ), A2 as ( select id, priority from ( select * from A1 union all select top 1 id, priority from (select *, ROW_NUMBER() over (order by case when priority = 'Low' then 1 else 2 end) as ranker from tbl where priority in ('High', 'Low') and id not in (select id from A1))Z order by ranker asc ) X ) select * from A2 order by id 

Answer 3

As a result of this request, you will receive up to 3 lowest priorities, up to 6 medium priorities and up to 9 priorities. If there are not enough items with a lower priority to fill the queue, the next highest priority is used.

 ;WITH PriorityRanks AS ( SELECT ID, Priority, ROW_NUMBER() OVER (PARTITION BY Priority ORDER BY ID ASC) as [Rank] FROM PriorityQueue ) , LowPriority AS ( SELECT ID, Priority, ROW_NUMBER() OVER (ORDER BY ID ASC) as [Rank] FROM PriorityRanks WHERE Priority = 'Low' AND [Rank] <= 3 ) , MediumPriority AS ( SELECT ID, Priority, ROW_NUMBER() OVER (ORDER BY ID ASC) as [Rank] FROM PriorityRanks pq WHERE pq.Priority = 'Medium' AND [Rank] <= 6 - (SELECT ISNULL(MAX([Rank]), 0) FROM LowPriority) ) , HighPriority AS ( SELECT ID, Priority FROM PriorityRanks pq WHERE pq.Priority = 'High' AND [Rank] <= 9 - (SELECT ISNULL(MAX([Rank]), 0) FROM LowPriority) - (SELECT ISNULL(MAX([Rank]), 0) FROM MediumPriority) ) SELECT ID, Priority FROM LowPriority UNION ALL SELECT ID, Priority FROM MediumPriority UNION ALL SELECT ID, Priority FROM HighPriority 

Edit: Sorry, I just noticed that you want the highest priority to fill in the blanks. It should not be too difficult to modify, but if you have questions, leave a comment and I will help you.

Answer 4

I went with a CTE-based approach where, hopefully, each step shows the thinking process that I followed:

 declare @t table (Id int not null, Priority varchar(6) not null) insert into @t (Id,Priority) values (1,'High'), (2,'High'), (3,'High'), (4,'High'), (5,'Medium'), (6,'Low'), (7,'Low') --We want 6 rows. We'd like to get 1 low, if available, and 2 mediums, if available ; with NumberedRows as ( select Id,Priority, ROW_NUMBER() OVER (PARTITION BY Priority ORDER BY Id) as rn, CASE Priority WHEN 'High' then 1 WHEN 'Medium' THEN 2 ELSE 3 END as NumPri from @t ), Selection as ( select Id, Priority, NumPri, CASE WHEN NumPri = 3 and rn <= 1 THEN 1 WHEN NumPri = 2 and rn <= 2 THEN 2 WHEN NumPri = 1 THEN 3 WHEN NumPri = 2 THEN 4 ELSE 5 --Low, rn>1 END as Preference from NumberedRows ), Chosen as ( select top 6 * from Selection order by Preference ) select * from Chosen order by NumPri,Id 

(Note that the sample data at the top of my code takes as much formatting as the table in your question, but it can really be used in a script)

If the number of items to select changes, you will need to change:

 WHEN NumPri = 3 and rn <= 1 THEN 1 WHEN NumPri = 2 and rn <= 2 THEN 2 

(Change rn values) and:

 select top 6 * from Selection order by Preference 

(Change it if you want, how much is required)

Please also note that it doesn’t matter that you say you want 3 items with high priority - it doesn’t matter, since items with high priority are used as fillers if not enough low priority values ​​can be located.