SQL Server - Finding the Highest Priority item using Bitwise operators

The Problem:

I want to return all of the rows from the Primary Data table together with the Highest Priority Exception based on the currently assigned Priority in an Exception table.

I have created a simplified example of my data set-up below (with creation scripts) so hopefully you can help with what should be a fairly quick T-SQL problem.

The setup:

I have a primary data table where each row can have one or more exceptions stored as a bit mask.

 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].[Pri开发者_如何学JAVAmaryData](SomeData, Exceptions)
    VALUES('Data D', 192)
 INSERT INTO [dbo].[PrimaryData](SomeData, Exceptions)
    VALUES('Data E', 132)

The Exceptions are stored in a lookup table purely because each of them is given a user assigned priority. This table cannot have rows added or deleted by the end user they just have control of the priority of each exception with 1 being the highest.

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')

So based on the sample data supplied I want to return SomeData, Mask (of highest priority) and Description (of highest priority).

i.e.

| Data B | 2 | Exception B

Obviously I need to do this in the most efficient way possible as there could be 25K rows being returned in the Primary Data Table.

Thanks in advance.

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

This will get what you want for a single PrimaryData row.

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

For all the rows, something like this should work (edited as suggested by Quassnoi)

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

Edited to change | to &

My answer is inspired by the "Find integer log base 10 of an integer the obvious way" trick found here.

Note that if you were to arrange the priorities so that the highest bit corresponds to the highest priority exception, you could use the trick directly, adapted for base 2. Alternatively, you could join on the simple formula FLOOR(LOG(Exceptions)/LOG(2). (In both of these solutions, you would need to allow the most significant bit of the mask to go unused or special case it since it makes the integer negative.)

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

First you create a (deterministic) function that retrieves the exception mask. This one takes the lowest bit:

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

Then you add a persisted computed column to your PrimaryDataTable the value is the result of the function.

alter table PrimaryData
add PriorityMask as (dbo.GetPriorityMask(Exceptions)) persisted

And now you van just add an index to the column

create index IX_PrimaryDate_PriorityMask
on PrimaryData(PriorityMask)

Of course it is not a bad idea to also add a foreign key, but first you should add a unique key to the exceptions table:

alter table Exception
add constraint UQ_Exception_Mask UNIQUE (Mask)

now add the foreign key

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

and now retrieve your data:

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