从 table 中选择下一个小于 table 元素的值

Question

我正在使用 SQL Server 2012。我正在编写一个加权优先级队列，我正在尝试根据 table 给出的最大权重从队列中提取项目.

所以我会得到一个如下所示的 table，指定要取出的项目数和最大重量值。我想先取出较大的物品，然后再减少到较小的物品。

选择table

╔════════╦═══════════╗
║ weight ║ numValues ║
╠════════╬═══════════╣
║      1 ║         1 ║
║      2 ║         0 ║
║      3 ║         3 ║
╚════════╩═══════════╝

还有一个 table 看起来像这样

项目table

╔══════╦══════╦════════╗
║ item ║ val  ║ weight ║
╠══════╬══════╬════════╣
║    1 ║ fish ║      1 ║
║    2 ║ goat ║      1 ║
║    3 ║ cat  ║      1 ║
║    4 ║ duck ║      3 ║
║    5 ║ pig  ║      2 ║
╚══════╩══════╩════════╝

我需要的是从 selection table 中 select 适合每个类别的具有最大权重的值。

我希望我的结果看起来像这样

结果

╔══════╦══════╦════════╗
║ item ║ val  ║ weight ║
╠══════╬══════╬════════╣
║    1 ║ fish ║      1 ║
║    2 ║ goat ║      1 ║
║    4 ║ duck ║      3 ║
║    5 ║ pig  ║      2 ║
╚══════╩══════╩════════╝

其中鸭子、猪、鱼满足得到3个重量3的值，山羊满足1个重量的要求。

希望这是有道理的。

我知道我可以用游标做这样的事情，但是这似乎很慢而且有点矫枉过正。我认为可以使用 CTE 来完成，但我不确定如何处理它。

感谢您的帮助。

编辑 一个解决方案

以 Jonathan 的解决方案为起点，这就是我打造的野兽。我认为应该是 "ok" 但可能不会那么快。

declare @selection TABLE 
    ([item] int, [val] varchar(4), [weight] int)
;

INSERT INTO @selection
    ([item], [val], [weight])
VALUES
    (1, 'fish', 1),
    (2, 'goat', 1),
    (3, 'cat', 1),
    (4, 'duck', 3),
    (5, 'pig', 2)
;
 declare @item TABLE 
    ([weight] int, [numValues] int)

INSERT INTO @item
    ([weight], [numValues])
VALUES
    (1, 1),
    (2, 0),
    (3, 3)

declare @potentialValues TABLE([item] int, [val] varchar(4), [weight] int, queueWeight int, [rn] int)
declare @maxRows INT = (SELECT SUM(numValues) FROM @item)
declare @largestQueueItem INT = (SELECT MAX(weight) from @item where numValues > 0)

;with CTE AS (
    Select 
        s.[weight] as itemWeight, 
        i.[weight] as queueWeight, 
        item, 
        val, 
        ROW_NUMBER() OVER (PARTITION BY i.weight ORDER BY s.weight desc) AS RN
    from @selection s
    FULL OUTER JOIN @item i ON s.weight <= i.weight
    where i.numValues > 0)
insert into @potentialValues ([item], [val], [weight], queueWeight, [rn])
select item, val, itemweight, queueWeight, rn from CTE
Where rn <= @maxRows


Declare @currentQueueItemSize INT = @largestQueueItem
while (@currentQueueItemSize > 0)
BEGIN
  DECLARE @count INT = (SELECT numValues from @item where weight = @currentQueueItemSize)
  ; WITH T
     AS (SELECT p.*
         FROM @potentialValues p
         WHERE p.queueWeight = @currentQueueItemSize
         ORDER BY p.rn
         OFFSET @count ROWS)
    DELETE FROM T

    DELETE p FROM @potentialValues p
    INNER JOIN @potentialValues pp 
    ON pp.item = p.item AND p.queueWeight < @currentQueueItemSize AND pp.queueWeight = @currentQueueItemSize

  SET @currentQueueItemSize = @currentQueueItemSize - 1
END

select item, val, weight from @potentialValues order by item

好消息是我没有使用游标。坏消息是我使用了带有 cte 和 delete 语句的 while 循环来正确配对 table。

有什么方法可以在 1 次或 2 次通过中得到这个东西？

Answer 1

declare @selection TABLE 
    ([item] int, [val] varchar(4), [weight] int)
;

INSERT INTO @selection
    ([item], [val], [weight])
VALUES
    (1, 'fish', 1),
    (2, 'goat', 1),
    (3, 'cat', 1),
    (4, 'duck', 3),
    (5, 'pig', 2)
;
 declare @item TABLE 
    ([weight] int, [numValues] int)

INSERT INTO @item
    ([weight], [numValues])
VALUES
    (1, 1),
    (2, 0),
    (3, 3)


;with CTE AS (
select T.item,t.val,tt.weight,ROW_NUMBER()OVER(PARTITION BY TT.weight ORDER BY TT.weight)RN from @selection T 
FULL OUTER  JOIN @item TT
ON T.weight = TT.weight)
SELECT ITEM,
VAL,
COALESCE(weight,ROW_NUMBER()over(PARTITION BY weight ORDER BY item)+1,0)
 FROM CTE where ITEM IS NOT NULL AND RN <= 2

Answer 2

一个解决方案

以 Jonathan 的解决方案为起点，这就是我打造的野兽。我认为应该是 "ok" 但可能不会那么快。

declare @selection TABLE 
    ([item] int, [val] varchar(4), [weight] int)
;

INSERT INTO @selection
    ([item], [val], [weight])
VALUES
    (1, 'fish', 1),
    (2, 'goat', 1),
    (3, 'cat', 1),
    (4, 'duck', 3),
    (5, 'pig', 2)
;
 declare @item TABLE 
    ([weight] int, [numValues] int)

INSERT INTO @item
    ([weight], [numValues])
VALUES
    (1, 1),
    (2, 0),
    (3, 3)

declare @potentialValues TABLE([item] int, [val] varchar(4), [weight] int, queueWeight int, [rn] int)
declare @maxRows INT = (SELECT SUM(numValues) FROM @item)
declare @largestQueueItem INT = (SELECT MAX(weight) from @item where numValues > 0)

;with CTE AS (
    Select 
        s.[weight] as itemWeight, 
        i.[weight] as queueWeight, 
        item, 
        val, 
        ROW_NUMBER() OVER (PARTITION BY i.weight ORDER BY s.weight desc) AS RN
    from @selection s
    FULL OUTER JOIN @item i ON s.weight <= i.weight
    where i.numValues > 0)
insert into @potentialValues ([item], [val], [weight], queueWeight, [rn])
select item, val, itemweight, queueWeight, rn from CTE
Where rn <= @maxRows


Declare @currentQueueItemSize INT = @largestQueueItem
while (@currentQueueItemSize > 0)
BEGIN
  DECLARE @count INT = (SELECT numValues from @item where weight = @currentQueueItemSize)
  ; WITH T
     AS (SELECT p.*
         FROM @potentialValues p
         WHERE p.queueWeight = @currentQueueItemSize
         ORDER BY p.rn
         OFFSET @count ROWS)
    DELETE FROM T

    DELETE p FROM @potentialValues p
    INNER JOIN @potentialValues pp 
    ON pp.item = p.item AND p.queueWeight < @currentQueueItemSize AND pp.queueWeight = @currentQueueItemSize

  SET @currentQueueItemSize = @currentQueueItemSize - 1
END

select item, val, weight from @potentialValues order by item

好消息是我没有使用游标。坏消息是我使用了带有 cte 和 delete 语句的 while 循环来正确配对 table。

有什么方法可以在 1 次或 2 次通过中得到这个东西？

从 table 中选择下一个小于 table 元素的值

Selecting from a table the next values less than a table element

sql-server

priority-queue

cursor

common-table-expression

sql-server-2012