SQL Server - поиск элемента с наивысшим приоритетом с помощью побитовых операторов

Question

Проблема:

Я хочу вернуть все строки из таблицы первичных данных вместе с исключением с наивысшим приоритетом на основе назначенного в данный момент приоритета в таблице исключений.

Я создал упрощенный пример моей настройки данных ниже (со сценариями создания), так что, надеюсь, вы сможете помочь с тем, что должно быть довольно быстрой проблемой T-SQL.

Настройка:

У меня есть первичная таблица данных, в которой каждая строка может иметь одно или несколько исключений, сохраненных в виде битовой маски.

 CREATE TABLE [dbo].[PrimaryData](
    Id [INT] IDENTITY(1,1) NOT NULL,
    SomeData [VARCHAR](30) NOT NULL,
    Exceptions [INT] NOT NULL,
 )
 INSERT INTO [dbo].[PrimaryData](SomeData, Exceptions)
    VALUES('Data A', 0)
 INSERT INTO [dbo].[PrimaryData](SomeData, Exceptions)
    VALUES('Data B', 6)
 INSERT INTO [dbo].[PrimaryData](SomeData, Exceptions)
    VALUES('Data C', 6)
 INSERT INTO [dbo].[PrimaryData](SomeData, Exceptions)
    VALUES('Data D', 192)
 INSERT INTO [dbo].[PrimaryData](SomeData, Exceptions)
    VALUES('Data E', 132)

Исключения хранятся в справочной таблице исключительно потому, что каждому из них присвоен приоритет, назначенный пользователем. В этой таблице не может быть строк, добавленных или удаленных конечным пользователем, они просто контролируют приоритет каждого исключения с 1, являющимся самым высоким .

CREATE TABLE [dbo].[Exception](
    Id [INT] IDENTITY(1,1) NOT NULL,
    Priority [INT] NOT NULL, 
    Mask [SMALLINT] NOT NULL,
    Description [VARCHAR](30) NOT NULL
 )
 INSERT INTO [dbo].[Exception] (Priority, Mask, Description)
      VALUES(1, 1, 'Exception A')
 INSERT INTO [dbo].[Exception] (Priority, Mask, Description)
      VALUES(2, 2, 'Exception B')
 INSERT INTO [dbo].[Exception] (Priority, Mask, Description)
      VALUES(3, 4, 'Exception C')
 INSERT INTO [dbo].[Exception] (Priority, Mask, Description)
      VALUES(4, 8, 'Exception D')
 INSERT INTO [dbo].[Exception] (Priority, Mask, Description)
      VALUES(5, 16, 'Exception E')
 INSERT INTO [dbo].[Exception] (Priority, Mask, Description)
      VALUES(6, 32, 'Exception F')
 INSERT INTO [dbo].[Exception] (Priority, Mask, Description)
      VALUES(7, 64, 'Exception G')
 INSERT INTO [dbo].[Exception] (Priority, Mask, Description)
      VALUES(8, 128, 'Exception H')
 INSERT INTO [dbo].[Exception] (Priority, Mask, Description)
      VALUES(9, 256, 'Exception I')

Поэтому на основе предоставленных образцов данных я хочу вернуть SomeData, Mask (с наивысшим приоритетом) и Description (с наивысшим приоритетом).

т.е.

| Data B | 2 | Exception B

Очевидно, что мне нужно сделать это наиболее эффективным способом, поскольку в таблице первичных данных может быть возвращено 25K строк.

Заранее спасибо.

Answer 1

SELECT  *
FROM    PrimaryData pd
CROSS APPLY
        (
        SELECT  TOP 1 *
        FROM    Exception e
        WHERE   e.Mask & pd.Exceptions <> 0
        ORDER BY
                e.Priority
        ) q

Answer 2

Это получит то, что вы хотите для одной строки PrimaryData.

select top 1 SomeData, Mask
  from PrimaryData
    inner join Exceptions
      on (PrimaryData.Exceptions & Exceptions.Mask <> 0)
  where PrimaryData.Id = 27
  order by Priority

Для всех строк должно работать что-то подобное (отредактировано в соответствии с предложением Кассной)

with data as (
  select SomeData, Mask, row_number() over
      (partition by PrimaryData.Id order by Priority) AS row
    from PrimaryData
      inner join Exceptions
        on (PrimaryData.Exceptions & Exceptions.Mask <> 0)
)
select * 
  from data
  where row = 1

Отредактировано, чтобы изменить | до &

Answer 3

Мой ответ навеян трюком "Найти целочисленный лог 10 из целого очевидного пути", найденным здесь .

Обратите внимание, что если вы расположите приоритеты так, чтобы старший бит соответствовал исключению с наивысшим приоритетом, вы могли бы использовать трюк напрямую, адаптированный для базы 2. В качестве альтернативы, вы могли бы присоединиться к простой формуле FLOOR(LOG(Exceptions)/LOG(2). (В обоих этих решениях вам нужно было бы разрешить тому, чтобы наиболее значимый бит маски не использовался, или в особом случае, так как это делает целое число отрицательным.)

SELECT SomeData, Mask, Description
FROM PrimaryData
INNER JOIN Exception ON
    CASE
        WHEN Exceptions & 0x1 <> 0 THEN 1
        WHEN Exceptions & 0x2 <> 0 THEN 2
        WHEN Exceptions & 0x4 <> 0 THEN 4
        WHEN Exceptions & 0x8 <> 0 THEN 8
        WHEN Exceptions & 0x10 <> 0 THEN 16
        WHEN Exceptions & 0x20 <> 0 THEN 32
        WHEN Exceptions & 0x40 <> 0 THEN 64
        WHEN Exceptions & 0x80 <> 0 THEN 128
        WHEN Exceptions & 0x100 <> 0 THEN 256
        WHEN Exceptions & 0x200 <> 0 THEN 512
        WHEN Exceptions & 0x400 <> 0 THEN 1024
        WHEN Exceptions & 0x800 <> 0 THEN 2048
        WHEN Exceptions & 0x1000 <> 0 THEN 4096
        WHEN Exceptions & 0x2000 <> 0 THEN 8192
        WHEN Exceptions & 0x4000 <> 0 THEN 16384
        WHEN Exceptions & 0x8000 <> 0 THEN 32768
        WHEN Exceptions & 0x10000 <> 0 THEN 65536
        WHEN Exceptions & 0x20000 <> 0 THEN 131072
        WHEN Exceptions & 0x40000 <> 0 THEN 262144
        WHEN Exceptions & 0x80000 <> 0 THEN 524288
        WHEN Exceptions & 0x100000 <> 0 THEN 1048576
        WHEN Exceptions & 0x200000 <> 0 THEN 2097152
        WHEN Exceptions & 0x400000 <> 0 THEN 4194304
        WHEN Exceptions & 0x800000 <> 0 THEN 8388608
        WHEN Exceptions & 0x1000000 <> 0 THEN 16777216
        WHEN Exceptions & 0x2000000 <> 0 THEN 33554432
        WHEN Exceptions & 0x4000000 <> 0 THEN 67108864
        WHEN Exceptions & 0x8000000 <> 0 THEN 134217728
        WHEN Exceptions & 0x10000000 <> 0 THEN 268435456
        WHEN Exceptions & 0x20000000 <> 0 THEN 536870912
        WHEN Exceptions & 0x40000000 <> 0 THEN 1073741824
        WHEN Exceptions & 0x80000000 <> 0 THEN -2147483648
        ELSE 0
    END = Mask
WHERE Exceptions <> 0
ORDER BY PrimaryData.Id

Answer 4

Сначала вы создаете (детерминированную) функцию, которая извлекает маску исключения.Этот принимает младший бит:

CREATE FUNCTION GetPriorityMask(@value int)
RETURNS smallint
with schemabinding
AS
BEGIN
    declare @mask smallint

    if @value = 0 return null

    set @mask = 1
    while @mask <= @value
    begin
        if @value | @mask = @value 
            break;

        set @mask = @mask * 2
    end

    RETURN @mask

END

Затем вы добавляете постоянный вычисляемый столбец в вашу таблицу PrimaryDataTable, значение является результатом функции.индекс для столбца

create index IX_PrimaryDate_PriorityMask
on PrimaryData(PriorityMask)

Конечно, неплохо также добавить внешний ключ, но сначала вы должны добавить уникальный ключ в таблицу исключений:

alter table Exception
add constraint UQ_Exception_Mask UNIQUE (Mask)

теперь добавьте внешний ключ

alter table PrimaryData
add constraint FK_PrimaryData_Exception foreign key(PriorityMask) references Exception(Mask)

и теперь получите ваши данные:

select *
from PrimaryData
left join Exception on PrimaryData.PriorityMask = Exception.Mask