Search results matching tags 'SQL' and 'SQL Server'

SQLSaturday #69 - Philly Love

Mike C — Mon, 07 Mar 2011 01:38:00 GMT

Thanks to the Philly SQL Server User Group (PSSUG) and to everyone who attended SQLSaturday #69 in the City of Brotherly Love yesterday. It was a great event with a lot of great people. My presentations are available for download at the links below:

http://www.sqlsaturday.com/viewsession.aspx?sat=69&sessionid=3333

http://www.sqlsaturday.com/viewsession.aspx?sat=69&sessionid=3334

I just went through my speaker evaluations, and I'm happy to report the response was pretty positive across the board. Having lived in Philly, I know Philadelphians aren't shy about telling how they really feel, so I really appreciate the positive feedback.

For those of you who wrote comments with areas for improvement, rest assured I appreciate the feedback and I'll work your suggestions into future presentations!

Next stop is SQLSaturday #71 in Boston (http://www.sqlsaturday.com/71/eventhome.aspx). Lots of top-notch speakers presenting at this one, and I'm looking forward to learning a little Power Shell from the master, and maybe learn a little bit o' that DBA stuff this time around :)

See you in Boston!

Sell Yourself! Presentation

Mike C — Sun, 05 Dec 2010 23:01:00 GMT

Thanks to everyone who attended my "Sell Yourself!" presentation at SQLSaturday #61 in Washington, D.C., and thanks to NOVA SQL for setting up the event!

I'm uploading the presentation deck here in PDF, original length, with new materials (I had to cut some slides out due to time limits). This deck includes a new section on recruiters and a little more information on the resume.

BTW, if you're rewriting your resume I highly recommend the book Elements of Resume Style by S. Bennett. I've used it as a reference when rewriting my resume and when helping others, and it's a very valuable tool. There are one or two things I disagree with the author about (he recommends against the use of bulleted lists in the resume, I think they're great for emphasis and readability in certain areas so long as they're not overused, for instance); but overall the book has plenty of solid advice on how to get the most out of your resume.

Also, if you haven't done so yet, check out Steve Jones' presentation "The Modern Resume: Building Your Brand" and his new blog: http://modernresume.blogspot.com/. Steve is a SQL MVP, entrepreneur (a founder and editor-in-chief at SQL Server Central: http://www.sqlservercentral.com), SQL Server guru, and all-around great guy. His new career-oriented professional-development blog and presentations are full of great career advice and tips for SQL Professionals.

Try-N-Save SSIS Packages

Mike C — Mon, 29 Nov 2010 05:17:00 GMT

The Try-N-Save SSIS Packages from my SSIS Dimensional Data Optimization presentation are available at http://cid-8f7e6c950afc6b3e.office.live.com/self.aspx/.Public/Presentation/TryNSave.zip.

I'm still working on getting the sample database uploaded - even compressed a backup is larger than SkyDrive's upload filesize limit. I'll script it out when I have time (in addition to DDL, there are some tables that need to be prepopulated).

High Performance Dimensional Data Loads With SSIS Presentation

Mike C — Sat, 20 Nov 2010 18:25:00 GMT

Just finished giving the SSIS High-Performance Dimensional Data Load presentation at SQLSaturday #59 NYC. Here are the slides in PDF format. I'll upload the Try-N-Save code and sample data later for attendees to play with.

Thanks to everyone who attended my session and thanks to Melissa D. and NJSQL for putting this together. For those who are interested in Alejandro Mesa's composable DML solution to the problem of Type 2 dimension updates, here's the complete statement from the demo:

INSERT INTO Dim.Geography_Hash
(
CityName, CountyFIPS, CountyName, StateFIPS,
StateUSPS, StateName, ZIP, TimeOffset,
DaylightSavingTime, StartDateID, CurrentFlag, BatchID,
LineageID, CubeInd, SortOrder, Hash
)
SELECT CityName, CountyFIPS, CountyName, StateFIPS,
StateUSPS, StateName, ZIP, TimeOffset,
DaylightSavingTime, StartDateID, CurrentFlag, BatchID,
LineageID, CubeInd, SortOrder, Hash
FROM
(
MERGE INTO Dim.Geography_Hash AS Target
USING Staging.Geography_Hash AS Source
ON Target.ZIP = Source.ZIP
  AND Target.CurrentFlag = Source.CurrentFlag
WHEN MATCHED AND Target.Hash <> Source.Hash
  THEN UPDATE SET CurrentFlag = 'N'
WHEN NOT MATCHED
  THEN INSERT
  (
   CityName, CountyFIPS, CountyName, StateFIPS,
   StateUSPS, StateName, ZIP, TimeOffset,
   DaylightSavingTime, StartDateID, CurrentFlag, BatchID,
   LineageID, CubeInd, SortOrder, Hash
  )
  VALUES
  (
   Source.CityName, Source.CountyFIPS, Source.CountyName, Source.StateFIPS,
   Source.StateUSPS, Source.StateName, Source.ZIP, Source.TimeOffset,
   Source.DaylightSavingTime, Source.StartDateID, Source.CurrentFlag, Source.BatchID,
   Source.LineageID, Source.CubeInd, Source.SortOrder, Source.Hash
  )
OUTPUT $action, inserted.CityName, inserted.CountyFIPS, inserted.CountyName, inserted.StateFIPS,
   inserted.StateUSPS, inserted.StateName, inserted.ZIP, inserted.TimeOffset,
   inserted.DaylightSavingTime, inserted.StartDateID, inserted.CurrentFlag, inserted.BatchID,
   inserted.LineageID, inserted.CubeInd, inserted.SortOrder, inserted.Hash
)
AS T
(
action, CityName, CountyFIPS, CountyName, StateFIPS,
StateUSPS, StateName, ZIP, TimeOffset,
DaylightSavingTime, StartDateID, CurrentFlag, BatchID,
LineageID, CubeInd, SortOrder, Hash
)
WHERE action = 'UPDATE';

As mentioned, the OUTPUT clause on the inner MERGE statement feeds the outer INSERT clause. Next stop is SQLSaturday #61 in DC at the beginning of December.

Find a Hash Collision, Win $100

Mike C — Sat, 17 Apr 2010 21:38:00 GMT

Margarity Kerns recently published a very nice article at SQL Server Central on using hash functions to detect changes in rows during the data warehouse load ETL process. On the discussion page for the article I noticed a lot of the same old arguments against using hash functions to detect change. After having this same discussion several times over the past several months in public and private forums, I've decided to see if we can't put this argument to rest for a while. To that end I'm going to hold a little contest: Generate an SHA-1 hash collision and win $100 and a book (see bottom section for details). Before I get into the details of the contest I'm going to give a little background of how this came about.

Background Info

NOTE: If you aren't familiar with hash functions I highly recommend first reading the Wikipedia article at http://en.wikipedia.org/wiki/Cryptographic_hash_function.

The idea of using a hash function for change detection is not new. Essentially a hash function generates a "fingerprint" of your data that you can use to compare an inbound row and an existing row.

Some people are wary of hash functions because they map a theoretically infinite number of large inputs to a much smaller finite set of hash values. Most of the arguments people make against using hash functions for change detection boil down to variations of Murphy's Law:

"There's a chance of a hash collision [generating the same hash value for two different inputs], so a collision will happen!"

People have different ways of dealing with this issue, including taking one of the following positions:

The chance of collision is negligible so no additional precautions are required.
A collision will absolutely happen so I won't use hash functions for change detection at all!
A collision may happen so I want to use hash values only to initially narrow down the number of rows I need to compare fully.

Positions #1 and #2 above are at different ends of the spectrum. Position #3 sits in the middle as a compromise solution. While compromises may make for good politics, they often make for terrible technical solutions, as I'll discuss below.

Position #1: Odds of Collision are Low Enough to be Ignored

As far as position #1 is concerned, it depends on which hash function you're using. You need to choose a true one-way collision-free* cryptographic hash function with a wide bit length. I normally recommend an SHA-2 hash function (256, 384 or 512 bit hash value), or when that's not available the SHA-1 160 bit hash function. The odds of generating a collision with a 160 bit hash function are 2^80. That is to say you can expect a collision after you generate hashes for 1,208,925,819,614,629,174,706,176 rows of data.

Of course if you're identifying rows by their natural or business keys this alternatively means you need to generate 1,208,925,819,614,629,174,706,176 variations of that single row before you'll hit a collision with SHA-1.

To put that number in perspective, consider that Google processes 20,000,000,000,000,000 bytes (20 petabytes) of data per day. If you were to store a single row in a database table for every single byte Google processes each day, it would take you 60,446,290 days (approximately 156,600 years) to store 1,208,925,819,614,629,174,706,176 rows in that table.

I personally assume position #1 on this subject, with the assumption that you have chosen a good solid hash function for the job. More on this later.

*A collision-free cryptographic hash function is a one-way hash function with negligible probability of generating the same hash value for two different inputs. SHA-1 and SHA-256 are examples of collision-free cryptographic hash functions.

Position #2: I Don't Trust Hash Functions

This position can't really be argued with. As shown above the odds of a collision with SHA-1 or another collision-free hash function are extremely low. But if you don't trust it, you just don't trust it. So the alternative is to compare every inbound column with every existing column. It will cost you in efficiency on wide tables, but if you're not concerned about processing power, server resources and execution time this classic method of change detection is well-proven to be 100% effective.

Position #3: The Compromise - Use Hash Values to Initially Narrow Down Results

This position is the compromise position that combines the implementation of #1 and #2 above. It sounds wonderful in theory - use a hash function to narrow down your results, eliminating rows that don't need to be compared column by column; then compare all of the columns in the remaining rows that haven't been eliminated. So let's look at a scenario:

You are processing Row A through your ETL process into a target table. Row B is the equivalent row in the target table (it has the same natural key/business key as Row A). This assumes we are first locating the equivalent row in the target table by natural key/business key of the incoming row.

There are three possible scenarios:

Row B exists in the target table, and is equal to Row A (no change).
Row B exists in the target table, but it is not equal to Row A (update).
Row B does not exist in the target table (insert Row A).

Let's say you've generated two hash values, h(A) is the hash for Row A and h(B) is the hash for Row B. Now we need to use h(A) and h(B) to eliminate rows to get rid of the extra column by column comparisons. Here are the rules you need to implement to use h(A) and h(B) to eliminate extra comparisons in this compromise solution:

A. h(A) is equal to h(B): according to the compromise, if h(A) = h(B) we need to compare all columns of the inbound row against the existing row since the belief is that the hash function can/will generate collisions. The idea is that h(A) may have generated the same value as h(B) even if A <> B. So we need to:

(1) Compare all columns in A and B. If A = B then perform no action.

(2) Compare all columns in A and B. If A <> B then update.

B. h(A) is not equal to h(B): cryptographic hash functions guarantee that they will generate the same hash value for the exact same inputs. So we can eliminate full row comparisons if h(A) <> h(B). We know automatically that if h(A) <> h(B) then A <> B. Just perform the update.

C. h(B) is NULL: that is, if Row B does not exist in the target table than h(B) is NULL. This is a case where no further full-row comparisons are necessary. Just insert the row.

Now consider a slowly changing dimension (SCD) in a datamart application. Many SCDs change slowly over time (hence the name slowly changing dimension). This means that new rows (updates and inserts) are far less common than receiving duplicate rows during ETL. So the vast majority of your inbound data will fall under rule A(1) above. So you're still performing comparisons of all columns for the vast majority of rows in a given table just to figure out that you don't need to update them after all!

If you eliminate even 90% of the inbound rows under rule A(1) above you haven't saved much processing (you're still comparing all columns for changes for 90% of your inbound rows). You probably actually cost yourself a lot of time and efficiency since you haven't accounted for the overhead of generating hash values for 100% of the inbound rows.

The only way this compromise is more efficient is if a very large percentage of your inbound rows (much greater than 50+%) are inserts under Rule C or updates under Rule B above. If the majority of your inbound rows are duplicates of existing rows under Rule A, you gain nothing.

The Contest

One-way collision-free cryptographic hash functions are supposed to have negligible probability of a hash collision, or two different inputs generating the same output. Hash collisions are what cause change detection with hashes to fail.

For instance, consider the following example of an MD5 hash collision:

DECLARE @A varbinary(8000),
      @B varbinary(8000),
      @hA binary(16),
      @hB binary(16);

SELECT @A = 0xd131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f8955ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5bd8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70,
      @B = 0xd131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f8955ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5bd8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70;

SELECT @hA = HASHBYTES('MD5', @A),
      @hB = HASHBYTES('MD5', @B);

SELECT CASE WHEN @A = @B
                  THEN '@A Equals @B'
                  ELSE '@A Is Not Equal To @B'
                  END AS AB_Equal,
            CASE WHEN @hA = @hB
                  THEN '@hA Equals @hB'
                  ELSE '@hA Is Not Equal To @hB'
                  END AS Hash_Equal;

The results are shown below:

When you run this you'll notice that the query reports the two source varbinary strings @A and @B are not equal, yet the two MD5 hashes they generate are equal. This is an example of a simple hash collision with MD5.

Now the challenge is to populate the following script with two different binary values that generate the same hash value. The output should be the same as shown above in the MD5 example.

-- Begin script
DECLARE @A varbinary(8000),
      @B varbinary(8000),
      @hA binary(20),
      @hB binary(20);

-- Replace the ? below with binary strings

SELECT @A = ?,
      @B = ?;

SELECT @hA = HASHBYTES('SHA1', @A),
      @hB = HASHBYTES('SHA1', @B);

SELECT CASE WHEN @A = @B
                  THEN '@A Equals @B'
                  ELSE '@A Is Not Equal To @B'
                  END AS AB_Equal,
            CASE WHEN @hA = @hB
                  THEN '@hA Equals @hB'
                  ELSE '@hA Is Not Equal To @hB'
                  END AS Hash_Equal;
-- End script

The first person who sends me an example of two varbinary strings that generate the same SHA1 hash value will win $100 (US$) and a copy of my book Pro T-SQL 2008 Programmer's Guide.

And here are the inevitable conditions:

No NULLs. @A and @B in the script above cannot be set to NULL for purposes of this contest.
8,000 bytes or less. The T-SQL HASHBYTES function accepts varbinary(8000) values, so the values passed into it in this contest must be 8,000 bytes in length or less. The values assigned to @A and @B above must be 8,000 bytes or less in length.
No unnecessary changes to the script. The only change allowed to the script above are the replacement of the question marks (?) with binary strings. No other changes to the script are authorized.
Only one person will win. The first person who sends me a copy of the above script with two different binary values that generate an SHA-1 hash collision will win.
Void where prohibited. Obviously if contests like this aren't legal in your country, state, county, city, etc. then you can't take part. Petition your government to make it legal :)
Time limits. Entries must be received prior to midnight U.S. Eastern Standard Time on October 31, 2010.
Decisions of the judge are final. For purposes of this contest that would be me.
SQL Server 2005 or 2008. Entries must be runnable on SQL Server 2005 and SQL Server 2008 Developer Edition, and the results must be reproducible.

If a winning entry is received prior to the deadline, I'll post an update entry to the blog with the winning script and the name of the winner.

T-SQL Tuesday #005: Creating SSMS Custom Reports

Mike C — Tue, 13 Apr 2010 00:14:00 GMT

This is my contribution to the T-SQL Tuesday blog party, started by Adam Machanic and hosted this month by Aaron Nelson. Aaron announced this month's topic is "reporting" so I figured I'd throw a blog up on a reporting topic I've been interested in for a while -- namely creating custom reports in SSMS.

Creating SSMS custom reports isn't difficult, but like most technical work it's very detailed with a lot of little steps involved. So this post is a little longer than usual and includes a lot of screenshots. There's also a downloadable ZIP file with the projects from this article included.

SSMS Custom Reports

SQL Server 2008 and 2005 both offer custom report functionality in Management Studio. With a little bit of work you can create custom SSMS reports just like the standard reports that Microsoft ships with Management Studio. The Disk Usage Report shown below is just one of the many standard reports that comes with SSMS.

Creating a Report Project

SSMS uses the SQL Server Reporting Services (SSRS) 2005 client/viewer control to render both standard and custom reports. This is true for both SSMS 2005 and SSMS 2008. So the first step to building a custom SSMS report is to fire up Visual Studio 2005 and create a new Report Server Project as shown below. For this example we'll create a custom report that lists missing indexes, so give the project the name Missing Index.

Once you create the Report Server Project right-click on Reports in the Solution Explorer and choose Add > New Item...

When the Add New Item box appears, choose the Report template and give the report a name. For this example I named the report Missing Index.rdl - the .rdl extension stands for "Report Definition Language", and is the standard extension for SSRS report definition files.

Defining the Report Dataset

Once the report is added to your project you have to add a new dataset to the report. The dataset defines the structure and content of the source data that will populate your report. Choose <New Dataset...> from the Dataset: dropdown.

Visual Studio will respond with a Data Source box. Just make sure the Type: dropdown is set to the default Microsoft SQL Server and put Data Source=. in the Connection string: box. This is all that's required since the SSMS custom report you're creating will use connections created and managed by SSMS's Object Explorer.

After you define the data source, you can define the SQL query that will populate your report. Just put the query in the dataset window as shown below.

I borrowed (and slightly modified) the following query from Brent Ozar. He originally published it at SQLServerPedia. This particular query uses SQL Server's missing index Dynamic Management Views (DMVs) to identify missing indexes.

-- Begin missing index query

WITH cte
AS
(
    SELECT mid.object_id AS object_id,
        QUOTENAME(OBJECT_SCHEMA_NAME(mid.object_id)) AS table_schema,
        QUOTENAME(OBJECT_NAME(mid.object_id)) AS table_name,
        QUOTENAME('IX_' + OBJECT_SCHEMA_NAME(mid.object_id) + '_' +
            LEFT(CAST(NEWID() AS CHAR(36)), 8)) AS index_name,
        mid.index_handle
    FROM sys.dm_db_missing_index_details mid
)
SELECT
    DENSE_RANK() OVER
    (
        ORDER BY cte.table_schema, cte.table_name
    ) AS table_color,
    ROW_NUMBER() OVER
    (
        PARTITION BY cte.table_schema, cte.table_name
        ORDER BY (avg_total_user_cost * avg_user_impact) * (user_seeks + user_scans) DESC
    ) AS index_color,
    cte.table_schema,
    cte.table_name,
    cte.index_name AS index_name,
    (avg_total_user_cost * avg_user_impact) * (user_seeks + user_scans) AS calc_impact,
    'CREATE NONCLUSTERED INDEX ' + cte.index_name + ' ON ' +
    cte.table_schema + '.' + cte.table_name +
    ' (' + COALESCE(mid.equality_columns, '') +
        CASE WHEN mid.inequality_columns IS NULL
            THEN ''
            ELSE CASE WHEN mid.equality_columns IS NULL
                THEN ''
                ELSE ','
                END + mid.inequality_columns
            END +
    ') ' + CASE WHEN mid.included_columns IS NULL
            THEN ''
            ELSE 'INCLUDE (' + mid.included_columns + ')'
            END +
    ';' AS create_stmt,
    mid.equality_columns,
    mid.inequality_columns,
    mid.included_columns
FROM sys.dm_db_missing_index_group_stats AS migs
INNER JOIN sys.dm_db_missing_index_groups AS mig
    ON migs.group_handle = mig.index_group_handle
INNER JOIN sys.dm_db_missing_index_details AS mid
    ON mig.index_handle = mid.index_handle
        AND mid.database_id = DB_ID()
INNER JOIN cte
    ON cte.index_handle = mid.index_handle
WHERE migs.group_handle IN
(
    SELECT group_handle
    FROM sys.dm_db_missing_index_group_stats WITH (NOLOCK)
)
ORDER BY calc_impact DESC;

-- End missing index query

There are a couple of caveats to keep in mind about the missing index DMVs that this query relies on:

They're not designed to be exhaustive. If you want to get a serious analysis of useful indexes in your databases, you definitely want to use a tool that will perform a more extensive analysis.
The DMVs only persist their information since the last time the SQL Server service was restarted. If you've recently restarted the service you'll get very little information back. These DMVs are best to use when your server has been running under normal load for a while.
The suggestions returned by the DMVs aren't always the best way to go. These DMVs often recommend suggested indexes with lots of overlap (lots of columns in common, often in similar order).

To put it another way, don't take the raw information returned by these DMVs at face value. The information they return is definitely useful for determining where indexes might provide benefit if your system has been running under normal load for a while, and the redundant index suggestions tend to indicate which indexes might be most useful. But these DMVs just amount to a starting point for analyzing your indexing needs. I'd recommend against creating dozens of redundant indexes based on the raw output of these DMVs.

Visual Studio will normally populate the dataset fields. If for some reason it doesn't, you can manually edit the fields by hitting the Edit Selected Dataset button to pull up the Dataset window. You can then enter the field names on the Fields tab if they aren't already populated.

Building the Report

So far most of what we've done is just setup. With this done, it's time to design and build the actual report. For this, click on the Visual Studio Layout tab to get to the report designer surface. You can drag and drop text boxes, charts, tables, images and any other controls from the Toolbox onto the designer surface. To keep it simple we'll just drag a text box and a table onto the designer.

Put the title of the report in the text box (in this case "Missing Index Report") and format it to your liking. The table we dragged onto the designer surface has three columns by default. For this example we want six columns total. To add more columns right-click on the top border of the table and choose Insert Column to the Left to add a new column. Repeat two more times.

In the Header row of the table we'll type in the headers for each column like the following:

In the Detail row we'll put in the formulas to populate the database fields like this:

SSRS formulas begin with the equal sign (=). Fields from the dataset are referenced directly using the format Fields!field_name.Value.

Deploying and Running the Report

At this point use Visual Studio to build the project. Once it builds without error, navigate to the project directory in Windows Explorer and copy the Missing Index.rdl file to the SSMS Custom Reports directory (on my computer this directory is located at C:\Users\Michael\Documents\SQL Server Management Studio\Custom Reports, it'll be different on yours).

You can now bring up this report in SSMS by right-clicking on a database in the Object Explorer and selecting Reports > Custom Reports... to select the custom report.

Choose your custom report from the file selection box and click Open.

When you run a custom report in SSMS you'll get a warning like the following:

Just choose Run. You might also want to check the box that says "Please don't show this warning again" to keep the box from popping up every time you run a custom report. The simple custom report you've created looks like the one shown below.

You can use images, color and other formatting techniques to make the report easier to read and use, and more flexible for your users. Consider the image below, which is a screenshot of a reformatted version of the Missing Index report. This one includes more information, color and collapsible sections. Both reports are included in the attached ZIP file under the Missing Index and Missing Index Color directories.

You can play around with the source files included in the attached ZIP file.

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.

Calculating Holidays in SQL

Mike C — Thu, 25 Feb 2010 21:51:00 GMT

Ask about nearly any kind of SQL-based date calculation in the newsgroups, and you'll likely get responses that include use of an auxiliary calendar table. It's a really good idea, and something I highly recommend to anyone who has to do date-based calculations on the server. For those who do dimensional modeling, you'll probably notice the auxiliary calendar table closely resembles a Time dimension with one-day intervals. I won't get into too much detail on it, since ASPFAQ and the newsgroups cover it well.

What I do want to talk about is calculating holidays, which can be important when populating your auxiliary calendar table. When you create an auxiliary calendar table you may need to perform calculations based on business days, for instance; or you may need to schedule activities before, after, or even during certain holidays. There are two types of holidays that I'll address:

Fixed holidays that fall on the same day every year
Floating holidays for which the date can change from year to year

Fixed holidays include holidays that always fall on the same day each year. Some examples of fixed holidays include Christmas (always December 25 in the West), Canada Day (always July 1), U.S. Independence Day (always July 4). These are fairly easy to detect and set in your auxiliary calendar table. Just look for the static month + day combinations in your table and update it accordingly.

Floating holidays are far more interesting and difficult to calculate. Take Easter. Easter actually has two definitions. The popular definition is:

"Easter Day is the first Sunday after the full moon that occurs next after the vernal equinox"

This is not the exact ecclesiastical definition though. The full moon here is not the astronomical full moon but an "ecclesiastical moon" that's determined through precalculated lookup tables. The ecclesiastical rules are:

Easter falls on the first Sunday following the first ecclesiastical full moon that occurs on or after the day of the vernal equinox
This particular ecclesiastical full moon is the 14th day of a tabular lunation (new moon)
The vernal equinox is fixed as March 21

I'm not going to recount the long and painful history leading to the modern definition of Easter--but the details can be found on Wikipedia if you're interested. The main point is that Easter calculation is fairly complex. The udf_CalculateEaster function below accepts the year (integer) as a parameter and returns the date of Easter for that year (datetime). Notice the large number of calculations required to make this function work:

CREATE FUNCTION dbo.udf_CalculateEaster
(
@Year INT
)
RETURNS DATETIME
AS
BEGIN
    DECLARE @Date DATETIME,
    @c INT,
    @n INT,
    @i INT,
    @k INT,
    @j INT,
    @l INT,
    @m INT,
    @d INT;

    SELECT @n = @Year - 19 * (@Year / 19),
    @c = @Year / 100,
    @k = (@c - 17) / 25,
    @i = @c - @c / 4 - (@c - @k) / 3 + 19 * @n + 15,
    @i = @i - 30 * (@i / 30),
    @i = @i - (@i / 28) * (1 - (@i / 28) * (29 / (@i + 1)) * ((21 - @n) / 11)),
    @j = @Year + @Year / 4 + @i + 2 - @c + @c / 4,
    @j = @j - 7 * (@j / 7),
    @l = @i - @j,
    @m = 3 + (@l + 40) / 44,
    @d = @l + 28 - 31 * (@m / 4),
    @Date = CAST
    (
      CAST(@Year AS CHAR(4)) +
      RIGHT
      (
        '0' + CAST
        (
          @m AS VARCHAR(2)
        ), 2
      ) +
      RIGHT
      (
        '0' +CAST
        (
          @d AS VARCHAR(2)
        ), 2
      ) AS DATETIME
    );
    RETURN @Date;
END;
GO

If you want the date for Easter 2010, just run a query like the following:

SELECT dbo.udf_CalculateEaster (2010);
GO

The result is 2010-04-04.

Another somewhat daunting type of floating holiday is the type that is based on the Nth weekday of the month. These holidays are defined using terms like "the 4th Thursday of November" (U.S. Thanksgiving), "the 3rd Monday in January" (U.S. Martin Luther King Day), or even "the *last* Monday in May" (U.S. Memorial Day). These floating holidays are not as hard to calculate as Easter, but still a little tricky (particularly Memorial Day).

To calculate these dates we need a function like udf_nthWeekDay below. This function accepts 4 parameters:

@n = integer that represents which instance of the weekday you're looking for. This would be the 4 in "4th Thursday in November".
@weekDay = 3-character day of week ("SUN" = Sunday, "MON" = Monday, etc.) I used character abbreviations instead of numbers just to make it a little easier.
@year = integer year for which to calculate
@month = integer month for which to calculate (1 = January, 2 = February, etc.)

As you can see below, the Nth weekday calculation is pretty simple.

CREATE FUNCTION dbo.udf_nthWeekDay
(
@n       INT,
@weekDay CHAR(3),
@year    INT,
@month   INT
)
RETURNS DATETIME
AS
BEGIN
DECLARE @date    DATETIME,
    @dow         INT,
    @offset      INT,
    @wd          INT;

SELECT @wd = CASE @weekDay
      WHEN 'SUN' THEN 1
      WHEN 'MON' THEN 2
      WHEN 'TUE' THEN 3
      WHEN 'WED' THEN 4
      WHEN 'THU' THEN 5
      WHEN 'FRI' THEN 6
      WHEN 'SAT' THEN 7
    END,
    @date = CAST
    (
      CAST(@year AS VARCHAR(4)) +
      RIGHT
      (
        '0' + CAST
        (
          @month AS VARCHAR(2)
        ), 2
      ) +
      '01' AS DATETIME
    ),
    @dow = DATEPART(dw, @date),
    @offset = @wd - @dow,
    @date = DATEADD(day, @offset + (@n - CASE WHEN @offset >= 0 THEN 1 ELSE 0 END) * 7, @date);
RETURN @date;
END;
GO

To get the date for Thanksgiving 2024 you could call the function like this:

SELECT dbo.udf_nthWeekDay
(
    4,
    'THU',
    2024,
    11
);

The result is 2024-11-28. Now for a holiday like U.S. Memorial Day ("the last Monday in May") the calculation is a little trickier. You have no idea up front how many Mondays there are in any given May. As an example, in 2010 and 2011 there are 5 Mondays in May; in 2012 and 2013 there are only 4. You could try to figure out the number of Mondays in May of the given year, but that's way too much work.

There's one thing we know about the last Monday in May with absolute certainty: after the last Monday in May, the next Monday we encounter will *always* be the first Monday in June. So the easier way to figure out the last Monday in May is to calculate the first Monday in June and then back into it (subtract 7 days), like this:

SELECT DATEADD
(
day,
-7,
dbo.udf_nthWeekDay
(
    1,
    'MON',
    2012,
    6
)
);

By calculating the date of the first Monday in June 2012, we can then subtract 7 days to get the date of the last Monday of May: 2012-05-28.

You can use the functions to calculate holidays for your auxiliary calendar table. I covered U.S. federal (and some other national) holidays in this one, but it can be extended to cover other national, state, and local holidays.

Service Packs... Coming to a Download Near You!

Mike C — Sun, 14 Feb 2010 23:07:00 GMT

Based on feedback from the community (https://connect.microsoft.com/SQLServer/feedback/details/522123/sql-server-2008-service-pack-2 and https://connect.microsoft.com/SQLServer/feedback/details/522122/service-pack-4-for-sql-server-2005), Microsoft has announced plans to release Service Pack 2 for SQL Server 2008 and Service Pack 4 for SQL Server 2005. The official announcement from the SQL Server Group Project Manager Matthias Berndt is here.

Here's the abbreviated version:

Service Pack 2 for SQL Server 2008 is targeted for a Q3 release.
Service Pack 4 for SQL Server 2005 is targeted for a Q4 release.

SP 4 is currently scheduled to be the final SP for 2005. The announcement also contains some info. about SQL 2005 going into extended support from April 2011 to April 2016.

Almost T-SQL Tuesday #003: Calculating Products - An Oldie But Goodie

Mike C — Wed, 10 Feb 2010 05:11:00 GMT

Looks like I just missed the deadline for T-SQL Tuesday #003 [oh well, whatcha gonna do]. The other day someone asked me about an oldie but goodie that hits on a math-based relationship. SQL Server has several aggregate functions like SUM for summation. Summation is the addition of a set of numbers, and it's represented with sigma notation, like this:

The question was how do you calculate a product in SQL? Keep in mind that SQL has no built-in PRODUCT aggregate. A product is the multiplication of a series of numbers, and is represented with capital PI notation:

The question was how do you perform a product aggregation in SQL? The most obvious way to solve the problem is with a simple cursor or loop. You could also create a SQL CLR UDF. But we can solve it even simpler than that, in pure SQL. So how do we solve it with a SQL set-based solution?

Well, mathematics provides us a relationship between logarithms and exponents that allows us to turn a product into a simple summation. The code below demonstrates.

CREATE TABLE Tab
(
val float
);
GO

INSERT INTO Tab (val)
VALUES (9.3),
(4.5),
(2.6),
(11.4),
(3);
GO

SELECT EXP(SUM(LOG(val))) AS product
FROM Tab;
GO

The sample sums the natural logarithms of val, and then returns the exponential of that sum. The end result is the product of the values in the val column. One thing to watch out for is that this method will error out if any of the values are <= 0. You can accomodate for this issue with a CASE expression, but that's for another day.

WHO DAT?