Search results matching tags 'T-SQL' and 'Code'

Bit-Twiddling in SQL

Mike C — Sun, 04 Apr 2010 03:40:00 GMT

Someone posted a question to the SQL Server forum the other day asking how to count runs of zero bits in an integer using SQL. Basically the poster wanted to know how to efficiently determine the longest contiguous string of zero-bits (known as a run of bits) in any given 32-bit integer. Here are a couple of examples to demonstrate the idea:

Decimal = Binary = Zero Run
999,999,999 decimal = 00111011 10011010 11001001 11111111 binary = 2 contiguous zero bits
666,666,666 decimal = 00100111 10111100 10000110 10101010 binary = 4 contiguous zero bits

My first reaction was that SQL is not my first choice of a go-to language for bit twiddling hacks. These types of calculations are generally most efficient in C-style compiled procedural languages with plenty of bit manipulation instructions that map almost directly one-for-one to low-level machine language instructions. In all fairness, SQL does have some bit-level operators (&, |, etc. operators), but the performance isn’t as optimized as a language like C#.

At any rate, a few different ideas were tossed around, like the simplistic loop-and-count procedural method. Using this method you just keep a running total of the longest zero-bit run and keep looping over the bits, adjusting your running total, comparing to your largest run of zero bits, and shifting your integer one bit right each time. But this being SQL, I decided to attack the problem from a set-based perspective. To start with I built a 1,000,000 row table to hold random integers:

CREATE TABLE TempNum
(
    Num BIGINT NOT NULL
);
GO

WITH GenerateRandom
AS
(
    SELECT 1 AS n,
        ABS(CONVERT(BIGINT, CONVERT(BINARY, CHECKSUM(NEWID()))) % 4294967296) AS Random

    UNION ALL

    SELECT n + 1,
        ABS(CONVERT(BIGINT, CONVERT(BINARY, CHECKSUM(NEWID()))) % 4294967296)
    FROM GenerateRandom
    WHERE n < 1000000
)
INSERT INTO TempNum
(
    Num
)
SELECT Random
FROM GenerateRandom
OPTION (MAXRECURSION 0);
GO

Note that I used SQL Server’s BIGINT data type (64-bit integer) since I wanted to deal only in unsigned 32-bit integers. For my initial crack at a solution I split the 32-bit integer up into individual bits and treated the whole thing like a classic Gaps and Islands problem. Essentially the 1 bits are islands, the 0's are gaps, and the length of the longest gap is the correct answer.

DBCC FREEPROCCACHE;
DBCC DROPCLEANBUFFERS;
GO

WITH Powers
AS
(
    SELECT 0 AS id,
        CAST(1 AS BIGINT) AS pwr

    UNION ALL

    SELECT p.id + 1,
        POWER(CAST(2 AS BIGINT), p.id + 1)
    FROM Powers p
    WHERE p.id < 33
),
Islands
AS
(
    SELECT ROW_NUMBER() OVER (PARTITION BY tn.Num ORDER BY id) AS RowNum,
        tn.Num,
        p.id,
        p.pwr
    FROM Powers p
    CROSS JOIN TempNum tn
    WHERE p.pwr & ((tn.Num * 2 ) | CAST(8589934593 AS BIGINT)) <> 0
)
SELECT c.Num AS Num,
    MAX(n.id - c.id - 1) AS ZeroBitRun
INTO #Temp
FROM Islands AS c
INNER JOIN Islands AS n
    ON n.RowNum = c.RowNum + 1
        AND n.Num = c.Num
WHERE n.id - c.id > 1
GROUP BY c.Num,
    n.Num;
GO

One interesting aside on this solution - to ensure that leading and trailing zeroes were counted for every 32-bit number I had to shift the number left one bit (multiply by 2) and do a bitwise OR (| operator) with 8589934593, setting both the lowest bit (bit 0) and the highest bit (bit 33) to 1. Basically this means you’re now dealing with a 34-bit integer, with the highest and lowest bits counted as islands. This ensures that for the 32 bits in between leading and trailing gaps are correctly identified. On my PC this query took an average of just over 360 seconds (6 minutes) to identify the largest run of zero bits in 1,000,000 random numbers. Another solution posted to the group used logarithms combined with bit-shifting in a recursive CTE. This one completed 1,000,000 iterations in about 17.5 minutes.

I couldn't help but think that when you get down to it, a solution to this problem should play to SQL’s strengths. I decided that what I really need for an efficient SQL solution to this problem is a lookup table. Granted, a lookup table of 4+ billion rows (one row for each and every 32 bit number) would take a long time to build and probably wouldn't lend itself to IO efficiencies in SQL Server. So I opted for a scaled down version and built a lookup table of 65,536 rows with one row representing every possible 16 bit number. There are a lot of clever ways to grab bit-level pattern information (Google "de Bruijn sequence", for instance), but to be honest this lookup table is a one-time build and static population so I decided to keep it simple.

CREATE TABLE #Nybbles
(
    Num int primary key not null,
    String varchar(4) not null,
    Leading tinyint not null,
    Trailing tinyint not null
);
GO

INSERT INTO #Nybbles
(
    Num,
    String,
    Leading,
    Trailing
)
VALUES (0, '0000', 4, 4), (1, '0001', 3, 0), (2, '0010', 2, 1), (3, '0011', 2, 0),
    (4, '0100', 1, 2), (5, '0101', 1, 0), (6, '0110', 1, 1), (7, '0111', 1, 0),
    (8, '1000', 0, 3), (9, '1001', 0, 0), (10, '1010', 0, 1), (11, '1011', 0, 0),
    (12, '1100', 0, 2), (13, '1101', 0, 0), (14, '1110', 0, 1), (15, '1111', 0, 0);
GO

CREATE TABLE #BitMask
(
    Length tinyint,
    Mask varchar(16)
);
GO

WITH GetMasks
AS
(
    SELECT 0 AS Length,
        CAST('' AS varchar(16)) AS Mask

    UNION ALL

    SELECT Length + 1,
        CAST(REPLICATE('0', Length + 1) AS varchar(16))
    FROM GetMasks
    WHERE Length < 16
)
INSERT INTO #BitMask
(
    Length,
    Mask
)
SELECT Length,
    Mask
FROM GetMasks;
GO

CREATE TABLE BitPattern
(
    Num int not null primary key,
    Trailing tinyint,
    Leading tinyint,
    Seq tinyint
);
GO

WITH GetBin
AS
(
    SELECT n1.Num * 4096 + n2.Num * 256 + n3.Num * 16 + n4.Num AS Num,
        n1.String + n2.String + n3.String + n4.String AS String
    FROM #Nybbles n1
    CROSS JOIN #Nybbles n2
    CROSS JOIN #Nybbles n3
    CROSS JOIN #Nybbles n4
)
INSERT INTO BitPattern
(
    Num,
    Trailing,
    Leading,
    Seq
)
SELECT g.Num,
    (
        SELECT MAX(b1.Length)
        FROM #BitMask b1
        WHERE RIGHT(g.String, b1.Length) = b1.Mask
    ) AS Trailing,
    (
        SELECT MAX(b2.Length)
        FROM #BitMask b2
        WHERE LEFT(g.String, b2.Length) = b2.Mask
    ) AS Leading,
    COALESCE
    (
        (
            SELECT MAX(b3.Length)
            FROM #BitMask b3
            WHERE CHARINDEX(b3.Mask, g.String) > 0
        ),
    0) AS Seq
FROM GetBin g
ORDER BY Num;
GO

DROP TABLE #BitMask;
DROP TABLE #Nybbles;
GO

The first part of this script puts all 16 combinations of 4-bit nybbles (nybble = half a byte) and their equivalent binary formatted strings (0 = '0000', 14 = '1110') into a temp table called #Nybbles.

There’s also a #BitMask temp table with bitmasks representing zero-bit runs. The bitmasks are just strings of consecutive '0' characters of the necessary length (length 1 = '0', length 5 = '00000').

The BitPatterns table is the actual 16-bit number lookup table. This table is populated by combining every 16-bit combination of nybbles from the #Nybbles temp table. This table has 4 columns:

Num is the 16-bit number
Trailing is the number of zero bits trailing (on the right-hand side) in the number
Leading is the number of zero bits leading (on the left-hand side) in the number
Seq is the longest sequence of zero bits within the number

The total run time to build this lookup table was around 30 seconds on my computer. Keep in mind that’s a one-time cost since you never have to build (or modify) the table again.

With the information in this lookup table the query that locates the longest run of zero bits in any given 32-bit number is relatively simple:

DBCC FREEPROCCACHE;

DBCC DROPCLEANBUFFERS;

WITH CTE

(

SELECT tn.Num,

(

SELECT

CASE WHEN l.Seq > h.Seq THEN

(

CASE WHEN l.Seq > h.Trailing + l.Leading THEN l.Seq

ELSE h.Trailing + l.Leading

END

)

ELSE

(

CASE WHEN h.Seq > h.Trailing + l.Leading THEN h.Seq

ELSE h.Trailing + l.Leading

END

)

END

) AS Seq,

CASE WHEN l.Trailing = 16 THEN h.Trailing + l.Trailing

ELSE l.Trailing

END AS Trailing,

CASE WHEN h.Leading = 16 THEN h.Leading + l.Leading

ELSE h.Leading

END AS Leading

FROM TempNum tn WITH (NOLOCK)

INNER JOIN BitPattern l WITH (NOLOCK)

ON l.Num = (tn.Num & 65535)

INNER JOIN BitPattern h WITH (NOLOCK)

ON h.Num = (tn.Num / 65536)

)

SELECT Num,

Seq,

Leading,

Trailing

INTO #Temp

FROM CTE;

Basically you join the BitPattern lookup table on the high 16 bits and again on the low 16 bits. The first CASE expression in the Seq subquery performs a 3-way maximum calculation. It returns the largest of:

the low word zero-bit run (l.Seq),
the high word zero-bit run (h.Seq), or
the count of high word trailing zero-bits + the count of low word leading zero-bits (h.Trailing + l.Leading)

The other two CASE expressions return the total number of trailing and leading zero-bits in the 32-bit number. The CASE expression is needed to handle the case when the high or low word is all zero-bits.

This particular solution took an average of about 6 seconds to calculate the longest zero-bit run for 1,000,000 numbers.

To my earlier point, I created a C# solution (which itself could have been optimized) that performed the exact same calculation for 1,000,000 random 32 bit integers in 2 seconds flat. So I guess there are two main points here: (1) Make sure you choose the right tool/language for the job, and (2) Whatever tool/language you choose try to play to its strengths.

Yet Another Stored Procedure vs. Ad-hoc Query Discussion?

Peter DeBetta — Thu, 03 Apr 2008 04:44:00 GMT

Earlier today, Will Sullivan posted a blog entry, My Statement on Stored Procedures, in which he emphatically states his official opinion of stored procedures as:

"I prefer not to use them."

He then goes about dismissing most of the misinformation about why stored procedures are better than ad-hoc (parameterized) queries.

The first bit of misinformation he dispels is the now defunct argument that "Stored Procedures are faster than ad-hoc queries". He states that "Unless your ad-hoc queries are always significantly different from each other, their execution plans are cached right along side those of the SP's." I completely agree. We'll call that one a tie, so the score so far: SP 0, Ad-hoc 0.

Another myth he tries to debunk is that "Editing SP's is a breeze with Query Analyzer". Query Analyzer - that's so SQL Server 2000. Seriously, though, there are a number of fine code editors that allow you to edit SPs with ease. Query Analyzer is not at the top of that list, however. I will say that when you write T-SQL you should use a code editor that is meant for T-SQL, for the same reasons that when you write C#, you want to use a code editor meant for C#. Again, no winner here, so the score remains: SP 0, Ad-hoc 0.

He addresses another statement that is supposedly made in defense of SPs: "Ad-hoc queries are a nightmare to maintain, as they are spread all over your code". Again, either one is easy to maintain, with the right tools. We are still scoreless: SP 0, Ad-hoc 0.

It just so happens that I agree with many of his points. And there are other objective and subjective points on topics such as organization, maintenance, design, and so on, which one could argue for either SPs or ad-hoc queries equally so. Don't get me wrong, however, as I believe that using ad-hoc queries when you could have used stored procedures is simply wrong.

And so I will address Will's last point (actually, it was his second point) that is repeatedly misrepresented: "Stored Procedures are safe against SQL injection attacks; ad-hoc queries are not".

Ad-hoc queries prevent SQL Injection attacks as well as SPs do. Any claim otherwise would be wrong. But that's not the issue. The problem is that ad-hoc queries require that you expose the underlying objects of the database. In order to use ad-hoc queries, you must allow direct access for select, insert, update, and delete operations to the tables in the database. Although I know most experienced developers would only write ad-hoc/parameterized queries against the underlying data, at a later date, some disgruntled or inexperienced developer may write dynamic SQL instead (I have seen it happen), and expose the database to SQL injection attacks (which I have also seen in production systems), including exposure to such awful actions as...

-- Can you say Identity Theft?
SELECT FirstName, LastName, ZIP, CreditCardNumber, CreditCardType, CreditCardExpoiration, CVV
FROM Customers

...or worse...

-- Do we really need all those customers?
DELETE Customers

...or even worse...

-- NEVER EVER DO THIS, PLEASE
-- This will execute a DELETE against all tables
EXEC sp_MSforeachtable 'DELETE ?'

...or even, even worse (assuming the SQL login has elevated permissions - which many apps do)...

-- NEVER EVER DO THIS, PLEASE
-- This will drop all tables from the database
EXEC sp_MSforeachtable 'DROP TABLE ?'

...and so although your ad-hoc query code won't allow SQL injection, some other programmer's dynamic SQL will. Assuming you've correctly secured your database, this doesn't happen with stored procedures since you do not have to expose any of the underlying tables (because of a little something known as chain of ownership).

Of course, you could completely self-destruct any security benefits by creating a SP such as this one:

-- NEVER EVER DO THIS, PLEASE, I beg of you...
CREATE PROC prExecuteSql (@sql VARCHAR(MAX))
WITH EXECUTE AS dbo
AS
EXEC (@sql)
GO

As you can see, SPs aren't fool proof, but you can mitigate your risk by having an employee or a consultant who knows what they are doing in the database.

Yes, there are some applications will not require the extra security, or other factors may simply prevent you from using stored procedures, and so using ad-hoc SQL is a viable option in those cases. But I believe that security should be at the top of your important-things-for-your-application list, and alas, ad-hoc queries require you to unnecessarily expose your database objects, which will more than likely lead to problems down the road. You can argue any other point and there are no clear winners, but when it comes to security, ad-hoc loses. If you want to a more secure database, you need to be using SPs.

And so, the final score (well, for now anyways): SP 1, Ad-hoc 0.