Thinking outside the box

Fast easter day function

Peter Larsson — Wed, 08 Sep 2010 13:30:22 GMT

CREATE FUNCTION dbo.fnGetEasterDate

(

@Year SMALLINT

)

RETURNS DATE

BEGIN

RETURN (

SELECT DATEADD(DAY, DATEDIFF(DAY, 0, CONVERT(DATETIME, CAST(@Year AS CHAR(4)) + BaseDate, 112)) / 7 * 7, 6)

FROM (

SELECT CASE @Year % 19

WHEN 0 THEN '0415'

WHEN 1 THEN '0404'

WHEN 2 THEN '0324'

WHEN 3 THEN '0412'

WHEN 4 THEN '0401'

WHEN 5 THEN '0419'

WHEN 6 THEN '0409'

WHEN 7 THEN '0329'

WHEN 8 THEN '0417'

WHEN 9 THEN '0406'

WHEN 10 THEN '0326'

WHEN 11 THEN '0414'

WHEN 12 THEN '0403'

WHEN 13 THEN '0323'

WHEN 14 THEN '0411'

WHEN 15 THEN '0331'

WHEN 16 THEN '0418'

WHEN 17 THEN '0408'

WHEN 18 THEN '0328'

ELSE NULL

END

WHERE @Year BETWEEN 1900 AND 9999

) AS d(BaseDate)

)

END

Married with children

Peter Larsson — Tue, 24 Aug 2010 10:37:44 GMT

will happen in just 4 days. The child part is taken care of. Multiple times.
Now it's time for the married part.

Me and my girlfriend Jennie will be married in Bjuv church at 3pm, Saturday the 28th of August 2010.
Pictures of Bjuv church can be found here.

After the ceromony we'll goto Hovs Hallar for dinner and party.
The famous parts (The chess scenes) of the movie The Seventh Seal by Ingmar Bergman was shot here. We'll sleep there since most of Jennie's family comes from Stockholm (300 miles away).

So I'll soon wear a ring on my finger. I tried the "rule them all" trick, but it didn't work. At all, even if my ring is a copy of the ring. Ask Jennie.

Excel XIRR function

Peter Larsson — Thu, 19 Aug 2010 19:46:33 GMT

First create a table type like this

CREATE TYPE	dbo.MyXirrTable AS TABLE
		(
			theValue DECIMAL(19, 9) NOT NULL, 
			theDate DATETIME NOT NULL
		)
GO

And then you create a function like this

CREATE FUNCTION dbo.XIRR
(
	@Sample MyXirrTable READONLY,
	@Rate DECIMAL(19, 9) = 0.1
)
RETURNS DECIMAL(38, 9)
AS
BEGIN
	DECLARE	@LastRate DECIMAL(19, 9),
		@RateStep DECIMAL(19, 9) = 0.1,
		@Residual DECIMAL(19, 9) = 10,
		@LastResidual DECIMAL(19, 9) = 1,
		@i TINYINT = 0

	IF @Rate IS NULL
		SET	@Rate = 0.1

	SET @LastRate = @Rate

	WHILE @i < 100 AND ABS((@LastResidual - @Residual) / @LastResidual) > 0.00000001
		BEGIN
			SELECT	@LastResidual = @Residual,
				@Residual = 0

			SELECT	@Residual = @Residual + theValue / POWER(1 + @Rate, theDelta / 365.0E)
			FROM	(
					SELECT	theValue,
						DATEDIFF(DAY, MIN(theDate) OVER (), theDate) AS theDelta
					FROM	@Sample
			 	) AS d

			SET	@LastRate = @Rate

			If @Residual >= 0
				SET @Rate += @RateStep
			ELSE
				SELECT	@RateStep /= 2,
					@Rate -= @RateStep

			SET	@i += 1
		END

	RETURN	@LastRate
END
GO

Then all you have to do is to test it! Like this...

DECLARE	@Test MyXirrTable

INSERT	@Test
VALUES	(-10, '20080101'),
	(2.75, '20080301'),
	(4.25, '20081030'),
	(3.25, '20090215'),
	(2.75, '20090401')

SELECT	dbo.XIRR(@Test, 0.1)	--0.373362535

CHECKSUM weakness explained

Peter Larsson — Thu, 19 Aug 2010 14:15:51 GMT

The built-in CHECKUM function in SQL Server is built on a series of 4 bit left rotational xor operations. See here in a previous forum post http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=70832 for more explanation.

Today, I wanted to see how often a collision (or false positive) can occur.

Let's take a very simple CHECKSUM value, for example 123. Decimal 123 is "01111011" in binary representation.
Since CHECKSUM function rotates the iterative checksum value 4 bits to the left (same thing as multiplying by 16), how many permutations of two characters returns the same CHECKSUM value of 123? The answer is 16 permutations.

Let's investigate by writing down the solution of this two character replacement.

     abcd 1011      Second character
0000 aBCD           First character
--------------
0000 0111 1011

Before we do anything more, let's refresh our mind on how XOR works. 0 and 0 returns 0, 0 and 1 returns 1, 1 and 0 return 1 and finally 1 and 1 return 0.

_ _|_0_|_1_|
_0_|_0_|_1_|
_1_|_1_|_0_|

Why did I then write the mysterious abcd and aBCD in the formula above?

Because the resulting bit sequence should be 0111, and only the same bits xor'ed gives 0. And the reason to use lower and upper characters for remaining bits are also due to xor. A result of 1 means the two bits has to be the opposite of each other; 0 xor 1 gives 1 and 1 xor 0 also gives 1 as result.

So "a" can have 2 possible values, and so can "b", "c", and "d" have. It gives 16 permutations in total.
See here

Bitseq1 Bitseq2 xor
0000    0111    0111
0001    0110    0111
0010    0101    0111
0011    0100    0111
0100    0011    0111
0101    0010    0111
0110    0001    0111
0111    0000    0111
1000    1111    0111
1001    1110    0111
1010    1101    0111
1011    1100    0111
1100    1011    0111
1101    1010    0111
1110    1001    0111
1111    1000    0111

This table above can be applied for any number of character for the first or last character.

Can this be applied onto a 3 character replacement? Of course, and in the same way. Still using the original decimal value of 123, the used characters are these

          abcd 1011     Third character
     xxxx aBCD           Second character
0000 xxxx                First character
-------------------
0000 0000 0111 1011

As you now can see, there are 16 times 16 possible (256) permutations giving the same CHECKSUM value!

And for four characters, the map looks like this

               abcd 1011      Fourth character
          yyyy aBCD           Third character
     xxxx yyyy                Second character
0000 xxxx                     First character
------------------------
0000 0000 0000 0111 1011

As you now can see, there are 16 times 16 times 16 permutations (4096) giving the same CHECKSUM value

This means I can with any two characters create same original checksum value 16 times. With any three characters (with a total of 65536 permuations), I can create 256 combinations resulting in the same decimal 123 checksum value.

Let's now see how the likelyness of getting a collision (or a false positive) is.

Character      256^(c-1)     16^(c-1)
replacment     Permutations Collisions
2                       256         16
3                     65536        256
4                  16777216       4096
5                4294967296       65536
6             1099511627776     1048576
7           281474976710656    16777216

From the table above, we can deduct that the number of collisions are the square root of the number possible permutations. This can be interpreted as "if you double the number of records, and calculate a checksum value, the likelyness of getting a collision (false positive) is quadrupled."
Triple the number of records and you have 9 times more chance of getting a collision (false positive).

The reason I don't give more than 7 character example is that for the eight character, the leftmost 4 bits are rotated and xored to the lower part of the iterative CHECKSUM value. It doesn't matter really, because then the flushed bits must match the final "1011" in this example, so the other part still has 16 permutations.

Joe Celko's Puzzles and Answers - The Restaurant seat assignment Problem

Peter Larsson — Fri, 30 Jul 2010 23:20:13 GMT

This problem is designed to come up with a solution that uses the smallest amount of storage possible for a 1,000 seat restaurant.
I've come up with a solution that need only 125 bytes of storage. All other solutions covered in Mr Celko's book has at least 1,000 bytes of storage.

Here is my solution, complete with all procedures to assign and release seats, together with views to display current status of each and one seat.

-- Setup sample data
CREATE TABLE    dbo.Restaurant
                (
                    Seats BINARY(125) NOT NULL
                )

-- Initialize an empty restaurant
INSERT dbo.Restaurant
        (
            Seats
        )
SELECT 0x
GO

-- Create procedure for handling seat assignment
CREATE PROCEDURE dbo.spAssignSeat
(
    @Seat SMALLINT
)
AS

DECLARE @Block TINYINT,
        @Bit TINYINT

SELECT @Block = SUBSTRING(Seats, 1 + (@Seat - 1) / 8, 1),
        @Bit = POWER(2, (@Seat - 1) % 8)
FROM    dbo.Restaurant

UPDATE dbo.Restaurant
SET     Seats = SUBSTRING(Seats, 1, (@Seat - 1) / 8) + CAST(@Bit | @Block AS BINARY(1)) + SUBSTRING(Seats, 2 + (@Seat - 1) / 8, 124 - (@Seat - 1) / 8)
GO

-- Create procedure for handling seat clearance
CREATE PROCEDURE dbo.spClearSeat
(
    @Seat SMALLINT
)
AS

DECLARE @Block TINYINT,
        @Bit TINYINT

SELECT @Block = SUBSTRING(Seats, 1 + @Seat / 8, 1),
        @Bit = CAST(255 AS TINYINT) ^ POWER(2, (@Seat - 1) % 8)
FROM    dbo.Restaurant

UPDATE dbo.Restaurant
SET     Seats = SUBSTRING(Seats, 1, (@Seat - 1) / 8) + CAST(@Bit & @Block AS BINARY(1)) + SUBSTRING(Seats, 2 + (@Seat - 1) / 8, 124 - (@Seat - 1) / 8)
GO

-- Create tally view
CREATE VIEW dbo.vwNums
AS

WITH    L0   AS(SELECT 1 AS c UNION ALL SELECT 1),
        L1   AS(SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),
        L2   AS(SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),
        L3   AS(SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),
        Nums AS(SELECT ROW_NUMBER() OVER(ORDER BY c) - 1 AS Number FROM L3)

SELECT      TOP(125)
            Number
FROM        Nums
ORDER BY    Number
GO

-- Create view CurrentSeatings
CREATE VIEW dbo.vwCurrentSeatings
AS

SELECT      8 * v.number + b.number + 1 AS Seat,
            SIGN(SUBSTRING(Seats, 1 + v.number, 1) & POWER(2, b.number)) AS Taken
FROM        dbo.Restaurant AS s
INNER JOIN dbo.vwNums AS v ON v.Number BETWEEN 0 AND 124
INNER JOIN dbo.vwNums AS b ON b.Number BETWEEN 0 AND 7
GO

-- Create the available seats sequence view
CREATE VIEW dbo.vwAvailableSeats
AS

WITH cteSource(Seat, Taken, grp)
AS (
        SELECT Seat,
                Taken,
                Seat - ROW_NUMBER() OVER (PARTITION BY Taken ORDER BY Seat) AS grp
        FROM    dbo.vwCurrentSeatings
)
SELECT      ROW_NUMBER() OVER (ORDER BY grp) AS Sequence,
            MIN(Seat) AS FromSeat,
            MAX(Seat) AS ToSeat
FROM        cteSource
WHERE       Taken = 0
GROUP BY    grp
GO

-- Display the wanted result
SELECT      Sequence,
            FromSeat,
            ToSeat
FROM        dbo.vwAvailableSeats
ORDER BY    Sequence

More on XML and encoding

Peter Larsson — Tue, 06 Jul 2010 07:40:52 GMT

Today, let's examine encoding with SQL Server and XML datatype.

DECLARE @Inf XML

SET    @Inf = '<?xml version="1.0" encoding="utf-16"?>
                 <root>
                    <names>
                         <name>test</name>
                     </names>
                     <names>
                         <name>test1</name>
                     </names>
                 </root>
                '

SELECT x.value('name[1]', 'VARCHAR(10)') AS Name
FROM    @Inf.nodes('/root/names') AS t(x)

If you try to run the code above, you will get an error message like this

Msg 9402, Level 16, State 1, Line 3
XML parsing: line 1, character 39, unable to switch the encoding

Why is that? If you change the encoding to UTF-8, the code works.
The solution is to know that UTF-16 works like UNICODE, and how do we denote UNICODE strings in SQL Server? Yes, by prefixing the string with N.

So this code works with UTF-16 encoding and you can happily continue to work.

DECLARE @Inf XML

SET    @Inf = N'<?xml version="1.0" encoding="utf-16"?>
                 <root>
                    <names>
                         <name>test</name>
                     </names>
                     <names>
                         <name>test1</name>
                     </names>
                 </root>
                '

SELECT x.value('name[1]', 'VARCHAR(10)') AS Name
FROM    @Inf.nodes('/root/names') AS t(x)

String concatenation and entitization

Peter Larsson — Sun, 04 Jul 2010 21:59:57 GMT

This question has been asked over and over again, and instead of having to redirect to any of my previous answers, I will cover the solution here in my blog.

Consider this sample data

DECLARE @Sample TABLE

(

ID INT,

Data VARCHAR(100)

)

INSERT @Sample

VALUES (1, 'Peso & Performance SQL'),

(1, 'MVP'),

(2, 'Need help <? /> -- '),

(2, 'With XML string concatenation ?')

The "trick" is to use the TYPE directive (to deal with entitization), and then use ".value" function to get the correct value out.
So here is the final query.

SELECT i.ID,

STUFF(f.Content.value('.', 'VARCHAR(MAX)'), 1, 1, '')

FROM (

SELECT ID

FROM @Sample

GROUP BY ID

) AS i

CROSS APPLY (

SELECT ', ' + w.Data

FROM @Sample AS w

WHERE w.ID = i.ID

FOR XML PATH(''),

TYPE

) AS f(Content)

And to deal with characters having ascii values less than 32 (space), you can use this

;WITH cteSource(ID, Content)

AS (

SELECT i.ID,

f.Content.value('.', 'NVARCHAR(MAX)')

FROM (

SELECT ID

FROM @Sample

GROUP BY ID

) AS i

CROSS APPLY (

SELECT CAST(', ' + w.Data AS VARBINARY(MAX))

FROM @Sample AS w

WHERE w.ID = i.ID

FOR XML PATH(''),

TYPE

) AS f(Content)

)

SELECT ID,

STUFF(CAST(Content AS NVARCHAR(MAX)), 1, 2, '') AS Content

FROM (

SELECT ID,

CAST(N'' AS XML).value('xs:base64Binary(sql:column("Content"))', 'VARBINARY(MAX)') AS Content

FROM cteSource

) AS d

Proper Relational Division With Sets

Peter Larsson — Thu, 01 Jul 2010 22:48:04 GMT

I got an email from Mr Celko and he correctly stated that my previous solution was not truly working with sets, so he posted me some solutions and proper sample data.
With this information at my hand, I started to investigate what really is needed to get this Relational Division to work properly with two sets; Dividend and Divisor.

Some of you know me well, and know I am not satisfied with just solving the problem. There have to be some tweaks, and I did that too with this solution. Not only is it only touching the Dividend table once and Divisor table once, you can also set if you want a division with no remainder (which means all records in Divisor should match and not a single record more), or allow a division with remainder (which means all the records should match and maybe more records).
Great? Just set 1 for "No remainder" and 0 for "Allow remainder".

Simple as that. So why does it work? Remember your old algebra? "Divide is the same thing as multiply with the inverse number..."

Now for the sample data (courtesy of Mr Celko)

CREATE TABLE    dbo.Dividend
                (
                    group_id INTEGER NOT NULL,
                    item_name VARCHAR(10) NOT NULL,
                    PRIMARY KEY (
                                    group_id,
                                    item_name
                                )
                )

INSERT INTO    dbo.Dividend
                (
                    group_id,
                    item_name
                )
VALUES          (1, 'one'),
                (1, 'two'),
                (1, 'three'),
                (1, 'four'),
                (2, 'one'),
                (2, 'two'),
                (2, 'three'),
                (3, 'one'),
                (3, 'two')

CREATE TABLE    dbo.Divisor
                (
                    item_name VARCHAR(10) NOT NULL PRIMARY KEY
                )

INSERT INTO     dbo.Divisor
                (
                    item_name
                )
VALUES          ('one'),
                ('two'),
                ('three')

Now for the 4 solutions posted by Mr Celko

-- Celko 1
SELECT      D1.group_id
FROM        Dividend AS D1
WHERE       D1.item_name IN (SELECT item_name FROM Divisor)
GROUP BY    D1.group_id
HAVING      COUNT(DISTINCT D1.item_name) = (SELECT COUNT(*) FROM Divisor)
            AND COUNT(DISTINCT D1.item_name) = (SELECT COUNT(*) FROM Dividend AS D2 WHERE D2.group_id = D1.group_id)

-- Celko 2
SELECT      D1.group_id
FROM        Dividend AS D1
WHERE       D1.item_name IN (SELECT item_name FROM Divisor)
            AND NOT EXISTS (
                                SELECT *
                                FROM    Dividend AS D2
                                WHERE   D2.group_id = D1.group_id
                                        AND D2.item_name NOT IN (SELECT item_name FROM Divisor)
                            )
GROUP BY    D1.group_id
HAVING      COUNT(DISTINCT D1.item_name) = (SELECT COUNT(*) FROM Divisor)

-- Celko 3
SELECT      D1.group_id
FROM        (
                SELECT group_id,
                        item_name,
                        COUNT(*) OVER (PARTITION BY group_id) AS cnt
                FROM    Dividend
            ) AS D1
WHERE       D1.item_name IN (SELECT item_name FROM Divisor)
            AND cnt = (SELECT COUNT(*) FROM Divisor)
GROUP BY    D1.group_id
HAVING      COUNT(D1.cnt) = (SELECT COUNT(*) FROM Divisor)

--Celko 4
;WITH Divisor2
AS (
        SELECT group_id,
                MIN(CASE WHEN item_name IN (SELECT item_name FROM Divisor) THEN 1 ELSE 0 END) OVER(PARTITION BY group_id) AS single,
                SUM(CASE WHEN item_name IN (SELECT item_name FROM Divisor) THEN 1 ELSE 0 END) OVER(PARTITION BY group_id) AS full_basket
        FROM    Dividend
)
SELECT      D.group_id
FROM        Dividend AS D,
            Divisor2
WHERE       D.group_id = Divisor2.group_id
            AND Divisor2.single = 1
            AND Divisor2.full_basket = (SELECT COUNT(*) FROM Divisor)
GROUP BY    D.group_id

You can copy and paste the code to a query window and run them. Investigate the execution plan and compare the 4 of them.
And now to my solution.

-- Peso 1
SELECT      group_id
FROM        (
                SELECT     t.group_id,
                            SUM(CASE WHEN t.item_name = n.item_name THEN 1 ELSE 0 END) AS cnt,
                            COUNT(*) AS Items
                FROM        dbo.Dividend AS t
                CROSS JOIN dbo.Divisor AS n
                GROUP BY    t.group_id,
                            t.item_name
            ) AS d
GROUP BY    group_id
HAVING      SUM(cnt) = MIN(Items)
            AND MIN(cnt) >= 1    -- 1 means no remainder, 0 means remainder

After some challenging with MVP Adam Machanic, here is another version

-- Peso v2
SELECT      t.group_id
FROM        (
                SELECT      group_id,
                            COUNT(*) AS cnt
                FROM        dbo.Dividend
                GROUP BY    group_id
            ) AS kc
INNER JOIN (
                SELECT COUNT(*) AS cnt
                FROM    dbo.Divisor
            ) AS nc ON nc.cnt = kc.cnt
INNER JOIN dbo.Dividend AS t ON t.group_id = kc.group_id
INNER JOIN dbo.Divisor AS n ON n.item_name = t.item_name
GROUP BY    t.group_id
HAVING      COUNT(*) = MIN(nc.cnt)

Here is an algorithm (exact division) which is really fast, but not 100% accurate due to the implementation of CHECKSUM (see http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=70832).

-- Peso 3
SELECT      group_id
FROM        (
                SELECT      group_id,
                            CHECKSUM_AGG(CHECKSUM(item_name)) AS ca1,
                            CHECKSUM_AGG(CHECKSUM(REVERSE(item_name))) AS ca2
                FROM        dbo.Dividend
                GROUP BY    group_id
            ) AS t
INNER JOIN (
                SELECT CHECKSUM_AGG(CHECKSUM(item_name)) AS ca1,
                        CHECKSUM_AGG(CHECKSUM(REVERSE(item_name))) AS ca2
                FROM    dbo.Divisor
            ) AS n ON n.ca1 = t.ca1
                AND n.ca2 = t.ca2

Now copy my solutions and compare them to the other 4.

-- Celko 1
Table 'Dividend'. Scan count 3, logical reads 6.
Table 'Divisor'. Scan count 2, logical reads 20.

-- Celko 2
Table 'Divisor'. Scan count 3, logical reads 32.
Table 'Dividend'. Scan count 4, logical reads 8.

-- Celko 3
Table 'Divisor'. Scan count 3, logical reads 10.
Table 'Worktable'. Scan count 3, logical reads 31.
Table 'Dividend'. Scan count 1, logical reads 2.

-- Celko 4
Table 'Dividend'. Scan count 2, logical reads 9.
Table 'Worktable'. Scan count 3, logical reads 31.
Table 'Divisor'. Scan count 1, logical reads 38.

-- Peso 1
Table 'Divisor'. Scan count 1, logical reads 19.
Table 'Dividend'. Scan count 1, logical reads 2.

-- Peso 2
Table 'Divisor'. Scan count 1, logical reads 8.
Table 'Dividend'. Scan count 2, logical reads 4.

-- Peso 3
Table 'Divisor'. Scan count 1, logical reads 2.
Table 'Dividend'. Scan count 1, logical reads 2.

So it seems my solution is cleaner and faster than the previous existing. But the best thing is yet hidden. My solution cares for multi-column division (just expand the CASE and GROUP BY clauses) whereas the previous 4 do not. Well, not easily anyway.
It will involve some replacing for IN with EXISTS, and some string concatenation for the DISTINCT clauses.

//Peso

Relational division

Peter Larsson — Wed, 30 Jun 2010 19:41:51 GMT

I came across an interesting post on Microsft SQL Server forum this afternoon. It was a question about Relational algebra and the poster wanted to have an efficient query to solve hos problem.
The problem could be solved with relational division, but there is no such operator in SQL Server. Maybe there will be same day.
For a fully working solution, see http://weblogs.sqlteam.com/peterl/archive/2010/07/02/Proper-Relational-Division-With-Sets.aspx

But for now there is no such operator, so we as developers have to find our own ways.
First prepare and populate some sample data

-- Prepare sample data
DECLARE @Sample TABLE
        (
            ParentID INT NOT NULL,
            Keyword VARCHAR(25) NOT NULL,
            UNIQUE (ParentID, Keyword)
        )

-- Populate sample data
INSERT @Sample
        (
            ParentID,
            Keyword
        )
VALUES (1, 'one'),
        (1, 'two'),
        (1, 'three'),
        (1, 'four'),
        (2, 'one'),
        (2, 'two'),
        (2, 'three'),
        (3, 'one'),
        (3, 'two')

People had already been active and posted some solutions, of which this common query was present.

SELECT     s.ParentID
FROM        @Sample AS s
WHERE       s.Keyword IN ('one', 'two', 'three')
GROUP BY    s.ParentID
HAVING     COUNT(DISTINCT s.Keyword) = 3
            AND COUNT(DISTINCT s.Keyword) = (SELECT COUNT(*) FROM @Sample AS x WHERE x.ParentID = s.ParentID)

and this type of query

SELECT      s.ParentID
FROM        @Sample AS s
WHERE       s.Keyword IN ('one', 'two', 'three')
            AND NOT EXISTS (
                            SELECT *
                            FROM    @Sample AS x
                            WHERE   x.ParentID = s.ParentID
                                    AND x.Keyword NOT IN ('one', 'two', 'three')
                           )
GROUP BY    s.ParentID
HAVING      COUNT(DISTINCT s.Keyword) = 3

And even a XML query!

;WITH AggStr
AS (
        SELECT ParentId,
                (
                    SELECT      CAST(',' AS VARCHAR(MAX)) + c.Keyword
                    FROM        @Sample AS c
                    WHERE       c.ParentID = p.ParentID
                    ORDER BY    c.Keyword
                    FOR XML     PATH('')
                ) AS c1
        FROM    (
                    SELECT DISTINCT
                            ParentID
                    FROM    @Sample
                ) AS p
)
SELECT ParentID
FROM    AggStr
WHERE   c1 = ',one,three,two'

The good thing is that all three produce the same wanted result but the bad thing is the inefficient execution plans. Then one poster did his homework and read about Mr Celko and translated his algorithm to the current problem, and then the query looked like this

SELECT      ParentID
FROM        (
                SELECT ParentID,
                        Keyword,
                        COUNT(*) OVER (PARTITION BY ParentID) AS cnt
                FROM    @Sample
            ) AS w
WHERE       Keyword IN ('one', 'two', 'three')
            AND cnt = 3
GROUP BY    ParentID
HAVING      COUNT(cnt) = 3

With these queries in mind, I thought about the problem and realized the problem did in fact have a much simpler solution.
The query I came up with is the simplest of them all, and just does one pass of the source table. Yes, only one pass just as the first Celko query for relational division, but without the internal worktable.
This is the query I came up with

-- Peso
SELECT      ParentID
FROM       @Sample
GROUP BY    ParentID
HAVING      MIN(CASE WHEN Keyword IN ('one', 'two', 'three') THEN 1 ELSE 0 END) = 1
            AND SUM(CASE WHEN Keyword IN ('one', 'two', 'three') THEN 1 ELSE 0 END) = 3

How does the query work? The second aggregation filtering just makes sure all three keywords are present.
But the first aggregation filter? What does it do? To simplify, I just write that it takes care of the modulo part of the relational division. There cannot be a "fractional" part of the relational division, because it means that particular ParentID has more keywords than wanted.

Simple as that.

//Peso

PS. These are the textual execution plans for the four types of queries and then mine.

|--Filter(WHERE:([Expr1003]=CASE WHEN [Expr1007] IS NULL THEN (0) ELSE [Expr1007] END))
       |--Nested Loops(Left Outer Join, OUTER REFERENCES:([s].[ParentID]))
            |--Filter(WHERE:([Expr1003]=(3)))
            |    |--Compute Scalar(DEFINE:([Expr1003]=CONVERT_IMPLICIT(int,[Expr1014],0)))
            |         |--Stream Aggregate(GROUP BY:([s].[ParentID]) DEFINE:([Expr1014]=Count(*)))
            |              |--Index Scan(OBJECT:(@Sample AS [s]), WHERE:(@Sample.[Keyword] as [s].[Keyword]='one' OR @Sample.[Keyword] as [s].[Keyword]='three' OR @Sample.[Keyword] as [s].[Keyword]='two') ORDERED FORWARD)
            |--Compute Scalar(DEFINE:([Expr1007]=CONVERT_IMPLICIT(int,[Expr1015],0)))
                 |--Stream Aggregate(DEFINE:([Expr1015]=Count(*)))
                      |--Index Seek(OBJECT:(@Sample AS [x]), SEEK:([x].[ParentID]=@Sample.[ParentID] as [s].[ParentID]) ORDERED FORWARD)

|--Filter(WHERE:([Expr1007]=(3)))
       |--Compute Scalar(DEFINE:([Expr1007]=CONVERT_IMPLICIT(int,[Expr1010],0)))
            |--Stream Aggregate(GROUP BY:([s].[ParentID]) DEFINE:([Expr1010]=Count(*)))
                 |--Nested Loops(Left Anti Semi Join, OUTER REFERENCES:([s].[ParentID]))
                      |--Index Scan(OBJECT:(@Sample AS [s]), WHERE:(@Sample.[Keyword] as [s].[Keyword]='one' OR @Sample.[Keyword] as [s].[Keyword]='three' OR @Sample.[Keyword] as [s].[Keyword]='two') ORDERED FORWARD)
                      |--Index Seek(OBJECT:(@Sample AS [x]), SEEK:([x].[ParentID]=@Sample.[ParentID] as [s].[ParentID]), WHERE:(@Sample.[Keyword] as [x].[Keyword]<>'one' AND @Sample.[Keyword] as [x].[Keyword]<>'three' AND @Sample.[Keyword] as [x].[Keyword]<>'two') ORDERED FORWARD)

|--Filter(WHERE:([Expr1008]=N',one,three,two'))
       |--Nested Loops(Inner Join, OUTER REFERENCES:([ParentID]))
            |--Stream Aggregate(GROUP BY:([ParentID]))
            |    |--Index Scan(OBJECT:(@sample), ORDERED FORWARD)
            |--UDX(([Expr1007], [C].[Keyword]))
                 |--Compute Scalar(DEFINE:([Expr1007]=CONVERT(varchar(max),',',0)+@sample.[Keyword] as [C].[Keyword]))
                      |--Index Seek(OBJECT:(@sample AS [C]), SEEK:([C].[ParentID]=[ParentID]) ORDERED FORWARD)

   |--Filter(WHERE:([Expr1005]=(3)))
       |--Compute Scalar(DEFINE:([Expr1005]=CONVERT_IMPLICIT(int,[Expr1010],0)))
            |--Stream Aggregate(GROUP BY:([ParentID]) DEFINE:([Expr1010]=Count(*)))
                 |--Filter(WHERE:(([Keyword]='one' OR [Keyword]='three' OR [Keyword]='two') AND [Expr1004]=(3)))
                      |--Nested Loops(Inner Join)
                           |--Table Spool
                           |    |--Segment
                           |         |--Index Scan(OBJECT:(@Sample), ORDERED FORWARD)
                           |--Nested Loops(Inner Join, WHERE:((1)))
                                |--Compute Scalar(DEFINE:([Expr1004]=CONVERT_IMPLICIT(int,[Expr1009],0)))
                                |    |--Stream Aggregate(DEFINE:([Expr1009]=Count(*)))
                                |         |--Table Spool
                                |--Table Spool

|--Filter(WHERE:([Expr1004]=(1) AND [Expr1005]=(3)))
       |--Stream Aggregate(GROUP BY:([ParentID]) DEFINE:([Expr1004]=MIN([Expr1006]), [Expr1005]=SUM([Expr1006])))
            |--Compute Scalar(DEFINE:([Expr1006]=CASE WHEN [Keyword]='three' OR [Keyword]='two' OR [Keyword]='one' THEN (1) ELSE (0) END))
                 |--Index Scan(OBJECT:(@Sample), ORDERED FORWARD)

Another bin-packaging algorithm using recursion and XML

Peter Larsson — Wed, 30 Jun 2010 11:44:40 GMT

This time I will show you an algorithm to do the dreaded bin-packaging using recursion and XML.
First, create some sample data like this

-- Prepare sample data

DECLARE @Sample TABLE

(

RowID INT IDENTITY(1, 1) PRIMARY KEY CLUSTERED,

Expense SMALLMONEY NOT NULL

)

-- Populate sample data

INSERT @Sample

(

Expense

)

VALUES (12.51),

(45.63),

(66.35),

(92.66),

(65.46),

(54.01),

(32.23),

(27.16),

(78.92),

(14.58)

Next, we need to create a variable to hold the user's wanted total sum.

-- Prepare user supplied parameter

DECLARE @WantedSUM SMALLMONEY = 111.09

And we also need to create a temporary staging table to hold the valid combinations

-- Prepare temporary staging table

DECLARE @Temp TABLE

(

CombID INT IDENTITY(1, 1) PRIMARY KEY CLUSTERED,

TrackPath XML NOT NULL

)

Now we only have to do the calculations!
Here I am using a special trick to get the unique combination, since the path of records 1>2>3 is the same as 1>3>2, 2>1>3, 2>3>1, 3>1>2 and 3>2>1. See explanation between combination and permutation at Wikipedia here.
To keep track of which records I already have used in the total sum, I simply remove the record id (RowID) from the Hits list.
And, to give the correct answer at the end, I build a XML string with visited RowID's building up the correct sum.

-- Calculate all possible permutations using recursion

;WITH ctePack(Total, Hits, TrackPath)

AS (

SELECT s.Expense AS Total,

(SELECT '#' + CAST(x.RowID AS VARCHAR(MAX)) FROM @Sample AS x WHERE x.RowID <> s.RowID ORDER BY x.RowID FOR XML PATH('')) + '#' AS Hits,

'<ID>' + CAST(s.RowID AS VARCHAR(MAX)) + '</ID>' AS TrackPath

FROM @Sample AS s

WHERE s.Expense <= @WantedSum

UNION ALL

SELECT p.Total + s.Expense,

REPLACE(p.Hits, '#' + CAST(s.RowID AS VARCHAR(MAX)) + '#', '#') AS Hits,

p.TrackPath + '<ID>' + CAST(s.RowID AS VARCHAR(MAX)) + '</ID>' AS TrackPath

FROM @Sample AS s

INNER JOIN ctePack AS p ON p.Hits LIKE '%#' + CAST(s.RowID AS VARCHAR(MAX)) + '#%'

WHERE p.Total + s.Expense <= @WantedSum

)

INSERT @Temp

(

TrackPath

)

SELECT MIN(TrackPath)

FROM ctePack

WHERE Total = @WantedSum

GROUP BY Hits

When the iterations are over, and we have the wanted combniation(s), the task left is to report the records giving us the correct sum.
We also need the records grouped so that we can see which group each expense belong to. In same cases, one and the same record may used in multiple groups.

-- Display the final resultset

SELECT t.CombID,

s.RowID,

s.Expense

FROM @Temp AS t

CROSS APPLY t.TrackPath.nodes('/ID') AS f(n)

INNER JOIN @Sample AS s ON s.RowID = f.n.value('.', 'INT')

ORDER BY t.CombID,

s.RowID

If you don't want to use XML, you can write the recursive cte like this, to get all included records directly.

-- Calculate all possible permutations using recursion
;WITH ctePack(RowID, Expense, Total, Tracker)
AS (
        SELECT s.RowID,
                s.Expense,
                s.Expense AS Total,
                (
                    SELECT      '#' + CAST(x.RowID AS VARCHAR(MAX))
                    FROM        @Sample AS x
                    WHERE       x.RowID <> s.RowID
                    ORDER BY    x.RowID
                    FOR XML     PATH('')
                ) + '#' AS Tracker
        FROM    @Sample AS s
        WHERE   s.Expense <= @WantedSum

        UNION ALL

        SELECT      s.RowID,
                    s.Expense,
                    p.Total + s.Expense,
                    REPLACE(p.Tracker, '#' + CAST(s.RowID AS VARCHAR(MAX)) + '#', '#') AS Tracker
        FROM        @Sample AS s
        INNER JOIN ctePack AS p ON p.Tracker LIKE '%#' + CAST(s.RowID AS VARCHAR(MAX)) + '#%'
        WHERE       p.Total + s.Expense <= @WantedSum
)
SELECT DISTINCT
        DENSE_RANK() OVER (ORDER BY Tracker) AS CombID,
        RowID,
        Expense
FROM    ctePack
WHERE   Total = @WantedSum