How to generate all Possible Alphabit pattern in a sequence?
-
Hi,
In one query, starting either at "Select" OR ";With", how can we generate all possible patterns of capital alphabits, order by All alphabits.
For example the desired output is follows.
A
AB
ABC
ABCD
ABCDEFGHIJKLMNOPQRSTUVWXYZ
...
...
...
B
BC
BCD
BCDE
BCDEFGHIJKLMNOPQRSTUVWXYZ
...
...
...
YZ
Z
May be following is useful. I have added this just for reference.
;WITH cte(Alpha,Increment)
as
(
select CHAR(65),1
union all
select CHAR(65+Increment),Increment+1
from
cte
where
Increment < 26
)
SELECT a1.*
from
cte a1
Thanks.
-
Do you just want them to be returned in order or do you want true permutations?
Jason...AKA CirqueDeSQLeil
_______________________________________________
I have given a name to my pain...MCM SQL Server, MVP
SQL RNNR
Posting Performance Based Questions - Gail Shaw[/url]
Learn Extended Events -
Using a tally table
WITH AllAlpha(Letter) AS (SELECT CHAR(ASCII('A')+N)
FROM dbo.Tally
WHERE N BETWEEN 0 AND 25)
SELECT (SELECT c.Letter AS "text()"
FROM AllAlpha c
WHERE c.Letter BETWEEN a.Letter AND b.Letter
ORDER BY c.Letter
FOR XML PATH('')) AS Perms
FROM AllAlpha a
INNER JOIN AllAlpha b ON b.Letter>=a.Letter
ORDER BY Perms;
____________________________________________________
Deja View - The strange feeling that somewhere, sometime you've optimised this query before
How to get the best help on a forum
http://www.sqlservercentral.com/articles/Best+Practices/61537
-
nice Mark! ,because my Tally Table starts at 1 and not Zero, for me it's missing the group that starts with 'A', but it was trivial to change that.
Lowell
--help us help you! If you post a question, make sure you include a CREATE TABLE... statement and INSERT INTO... statement into that table to give the volunteers here representative data. with your description of the problem, we can provide a tested, verifiable solution to your question! asking the question the right way gets you a tested answer the fastest way possible! -
Lowell (10/18/2011)
nice Mark! ,because my Tally Table starts at 1 and not Zero, for me it's missing the group that starts with 'A', but it was trivial to change that.Very slick indeed
Jason...AKA CirqueDeSQLeil
_______________________________________________
I have given a name to my pain...MCM SQL Server, MVP
SQL RNNR
Posting Performance Based Questions - Gail Shaw[/url]
Learn Extended Events -
SQLRNNR (10/18/2011)
Lowell (10/18/2011)
nice Mark! ,because my Tally Table starts at 1 and not Zero, for me it's missing the group that starts with 'A', but it was trivial to change that.Very slick indeed
Thanks for the feedback!
____________________________________________________
Deja View - The strange feeling that somewhere, sometime you've optimised this query before
How to get the best help on a forum
http://www.sqlservercentral.com/articles/Best+Practices/61537 -
is the OP question related to the following article:
http://www.sqlservercentral.com/articles/T-SQL+Challenges/76259/
??
________________________________________________________________
you can lead a user to data....but you cannot make them think
and remember....every day is a school day -
J Livingston SQL (10/18/2011)
is the OP question related to the following article:http://www.sqlservercentral.com/articles/T-SQL+Challenges/76259/
??
I wondered that, but the two seem different enough.
Jason...AKA CirqueDeSQLeil
_______________________________________________
I have given a name to my pain...MCM SQL Server, MVP
SQL RNNR
Posting Performance Based Questions - Gail Shaw[/url]
Learn Extended Events -
MidBar (10/17/2011)
In one query, starting either at "Select" OR ";With"
hmmm...:-)
this is quite a speciic statement ...that is also clearly prescribed on the "Challenge" under
__________________________________________________________
1 . Restrictions
The solution should be a single query that starts with a "SELECT" or “;WITH”
________________________________________________________________
you can lead a user to data....but you cannot make them think
and remember....every day is a school day -
J Livingston SQL (10/18/2011)
MidBar (10/17/2011)
In one query, starting either at "Select" OR ";With"
hmmm...:-)
this is quite a speciic statement ...that is also clearly prescribed on the "Challenge" under
__________________________________________________________
1 . Restrictions
The solution should be a single query that starts with a "SELECT" or “;WITH”
hmmm - very good point. Well, we can certainly verify that the work was Marks in this case so it would be disqualified - if it were for that.:-)
Jason...AKA CirqueDeSQLeil
_______________________________________________
I have given a name to my pain...MCM SQL Server, MVP
SQL RNNR
Posting Performance Based Questions - Gail Shaw[/url]
Learn Extended Events -
Sorry for late reply.
Thanks MARK's for the query. Excellent work!!!! great idea.
Yes I accept that idea came to mind from TSQL challenge 67. Thats why i have added my initial thoughts in the question as well . This also proves that my logic was not that bad, i shall try to change this a bit now. Actually, I was struggling to make this kind of alphabit sequence as i was getting proper control on sequence.
Again thanks mark and others for being much attentive 😉 😀
Cheers Guys.
-
Mark-101232 (10/18/2011)
Using a tally tableWITH AllAlpha(Letter) AS (SELECT CHAR(ASCII('A')+N)
FROM dbo.Tally
WHERE N BETWEEN 0 AND 25)
SELECT (SELECT c.Letter AS "text()"
FROM AllAlpha c
WHERE c.Letter BETWEEN a.Letter AND b.Letter
ORDER BY c.Letter
FOR XML PATH('')) AS Perms
FROM AllAlpha a
INNER JOIN AllAlpha b ON b.Letter>=a.Letter
ORDER BY Perms;
Heh... pretty darned good, Mark. Keep that up and I can retire. 😛 I can remember when no one even knew what a Tally Table was. :w00t:
I would like to make a suggestion, though because it might help for larger problems. Because you call the AllAlpha CTE 3 times, you also call the Tally table 3 times and doing the "Compute Scalar" 3 times(see the execution plan for confirmation of that). All of that leads to 2 nested joins. You're also comparing letter-to-letter in the INNER JOIN criteria and, even though FOR XML PATH is definitely the way to go for concatenation, concatenation is still comparatively wicked expensive. Finally, and this one is the real killer, you're doing a sort on a calculated value in the ORDER BY instead of on the PK of the Tally which wouldn't even produce a sort icon in the execution plan never mind one that takes 97% of the query cost.
With those thoughts in mind, please consider the following...
SET STATISTICS TIME OFF;PRINT '===== Mark''s Code ================================================================================='
SET STATISTICS TIME ON;
WITH AllAlpha(Letter) AS (
SELECT CHAR(ASCII('A')+N)
FROM dbo.Tally
WHERE N BETWEEN 0 AND 25)
SELECT (SELECT c.Letter AS "text()"
FROM AllAlpha c
WHERE c.Letter BETWEEN a.Letter AND b.Letter
ORDER BY c.Letter
FOR XML PATH('')) AS Perms
FROM AllAlpha a
INNER JOIN AllAlpha b ON b.Letter>=a.Letter
ORDER BY Perms;
SET STATISTICS TIME OFF;
PRINT '===== Another way =================================================================================='
SET STATISTICS TIME ON;
SELECT SUBSTRING('ABCDEFGHIJKLMNOPQRSTUVWXYZ',t1.N,t2.N-t1.N+1)
FROM dbo.Tally t1,
dbo.Tally t2
WHERE t1.N BETWEEN 1 AND 26
AND t2.N BETWEEN 1 AND 26
AND t1.N <= t2.N
ORDER BY t1.N, t2.N;
SET STATISTICS TIME OFF;
You probably won't see much of a difference on a fast machine so here's what I see on my 9 year old, single CPU desktop using SQL Server 2005...
===== Mark's Code =================================================================================(351 row(s) affected)
SQL Server Execution Times:
CPU time = 63 ms, elapsed time = 119 ms.
===== Another way ==================================================================================
(351 row(s) affected)
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 36 ms.
If you really want to see something interesting, compare the execution plans. What's really cool about the example code I created is that even though I explicitly said to sort on N from both Tally Table aliases, you won't see a sort in the entire execution plan on my code. That's because the code didn't have to sort on any scalar computations.
Like I said, it really doesn't matter that much because of the guaranteed low number of rows for this problem but getting even such a small problem to run in less than 1/3rd of the time is really good practice for something bigger.
Heh... now, if you want to cut the reads to near zero... but you guys already know how to do that.
--Jeff Moden
RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.Change is inevitable... Change for the better is not.
Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally) -
MidBar (10/17/2011)
Hi,In one query, starting either at "Select" OR ";With", how can we generate all possible patterns of capital alphabits, order by All alphabits.
For example the desired output is follows.
A
AB
ABC
ABCD
ABCDEFGHIJKLMNOPQRSTUVWXYZ
...
...
...
B
BC
BCD
BCDE
BCDEFGHIJKLMNOPQRSTUVWXYZ
...
...
...
YZ
Z
May be following is useful. I have added this just for reference.
;WITH cte(Alpha,Increment)
as
(
select CHAR(65),1
union all
select CHAR(65+Increment),Increment+1
from
cte
where
Increment < 26
)
SELECT a1.*
from
cte a1
Thanks.
I strongly recommend that you [font="Arial Black"]never[/font], ever, use a Recursive CTE for counting (or much of anything else, either). Please see the following article for why I've violated the "It Depends" taboo of never saying "Never". 😉
http://www.sqlservercentral.com/articles/T-SQL/74118/
--Jeff Moden
RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.Change is inevitable... Change for the better is not.
Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally) -
Jeff Moden (10/18/2011)
Mark-101232 (10/18/2011)
Using a tally tableWITH AllAlpha(Letter) AS (SELECT CHAR(ASCII('A')+N)
FROM dbo.Tally
WHERE N BETWEEN 0 AND 25)
SELECT (SELECT c.Letter AS "text()"
FROM AllAlpha c
WHERE c.Letter BETWEEN a.Letter AND b.Letter
ORDER BY c.Letter
FOR XML PATH('')) AS Perms
FROM AllAlpha a
INNER JOIN AllAlpha b ON b.Letter>=a.Letter
ORDER BY Perms;
Heh... pretty darned good, Mark. Keep that up and I can retire. 😛 I can remember when no one even knew what a Tally Table was. :w00t:
I would like to make a suggestion, though because it might help for larger problems. Because you call the AllAlpha CTE 3 times, you also call the Tally table 3 times and doing the "Compute Scalar" 3 times(see the execution plan for confirmation of that). All of that leads to 2 nested joins. You're also comparing letter-to-letter in the INNER JOIN criteria and, even though FOR XML PATH is definitely the way to go for concatenation, concatenation is still comparatively wicked expensive. Finally, and this one is the real killer, you're doing a sort on a calculated value in the ORDER BY instead of on the PK of the Tally which wouldn't even produce a sort icon in the execution plan never mind one that takes 97% of the query cost.
With those thoughts in mind, please consider the following...
SET STATISTICS TIME OFF;PRINT '===== Mark''s Code ================================================================================='
SET STATISTICS TIME ON;
WITH AllAlpha(Letter) AS (
SELECT CHAR(ASCII('A')+N)
FROM dbo.Tally
WHERE N BETWEEN 0 AND 25)
SELECT (SELECT c.Letter AS "text()"
FROM AllAlpha c
WHERE c.Letter BETWEEN a.Letter AND b.Letter
ORDER BY c.Letter
FOR XML PATH('')) AS Perms
FROM AllAlpha a
INNER JOIN AllAlpha b ON b.Letter>=a.Letter
ORDER BY Perms;
SET STATISTICS TIME OFF;
PRINT '===== Another way =================================================================================='
SET STATISTICS TIME ON;
SELECT SUBSTRING('ABCDEFGHIJKLMNOPQRSTUVWXYZ',t1.N,t2.N-t1.N+1)
FROM dbo.Tally t1,
dbo.Tally t2
WHERE t1.N BETWEEN 1 AND 26
AND t2.N BETWEEN 1 AND 26
AND t1.N <= t2.N
ORDER BY t1.N, t2.N;
SET STATISTICS TIME OFF;
You probably won't see much of a difference on a fast machine so here's what I see on my 9 year old, single CPU desktop using SQL Server 2005...
===== Mark's Code =================================================================================(351 row(s) affected)
SQL Server Execution Times:
CPU time = 63 ms, elapsed time = 119 ms.
===== Another way ==================================================================================
(351 row(s) affected)
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 36 ms.
If you really want to see something interesting, compare the execution plans. What's really cool about the example code I created is that even though I explicitly said to sort on N from both Tally Table aliases, you won't see a sort in the entire execution plan on my code. That's because the code didn't have to sort on any scalar computations.
Like I said, it really doesn't matter that much because of the guaranteed low number of rows for this problem but getting even such a small problem to run in less than 1/3rd of the time is really good practice for something bigger.
Heh... now, if you want to cut the reads to near zero... but you guys already know how to do that.
Very very intriguing.
I ran your test script 20 times and Marks query finishes in 10ms every time while your query takes between 70 and 96 ms. Both show 0ms CPU time
Jason...AKA CirqueDeSQLeil
_______________________________________________
I have given a name to my pain...MCM SQL Server, MVP
SQL RNNR
Posting Performance Based Questions - Gail Shaw[/url]
Learn Extended Events -
Jeff Moden (10/18/2011)
Mark-101232 (10/18/2011)
Using a tally tableWITH AllAlpha(Letter) AS (SELECT CHAR(ASCII('A')+N)
FROM dbo.Tally
WHERE N BETWEEN 0 AND 25)
SELECT (SELECT c.Letter AS "text()"
FROM AllAlpha c
WHERE c.Letter BETWEEN a.Letter AND b.Letter
ORDER BY c.Letter
FOR XML PATH('')) AS Perms
FROM AllAlpha a
INNER JOIN AllAlpha b ON b.Letter>=a.Letter
ORDER BY Perms;
Heh... pretty darned good, Mark. Keep that up and I can retire. 😛 I can remember when no one even knew what a Tally Table was. :w00t:
I would like to make a suggestion, though because it might help for larger problems. Because you call the AllAlpha CTE 3 times, you also call the Tally table 3 times and doing the "Compute Scalar" 3 times(see the execution plan for confirmation of that). All of that leads to 2 nested joins. You're also comparing letter-to-letter in the INNER JOIN criteria and, even though FOR XML PATH is definitely the way to go for concatenation, concatenation is still comparatively wicked expensive. Finally, and this one is the real killer, you're doing a sort on a calculated value in the ORDER BY instead of on the PK of the Tally which wouldn't even produce a sort icon in the execution plan never mind one that takes 97% of the query cost.
With those thoughts in mind, please consider the following...
SET STATISTICS TIME OFF;PRINT '===== Mark''s Code ================================================================================='
SET STATISTICS TIME ON;
WITH AllAlpha(Letter) AS (
SELECT CHAR(ASCII('A')+N)
FROM dbo.Tally
WHERE N BETWEEN 0 AND 25)
SELECT (SELECT c.Letter AS "text()"
FROM AllAlpha c
WHERE c.Letter BETWEEN a.Letter AND b.Letter
ORDER BY c.Letter
FOR XML PATH('')) AS Perms
FROM AllAlpha a
INNER JOIN AllAlpha b ON b.Letter>=a.Letter
ORDER BY Perms;
SET STATISTICS TIME OFF;
PRINT '===== Another way =================================================================================='
SET STATISTICS TIME ON;
SELECT SUBSTRING('ABCDEFGHIJKLMNOPQRSTUVWXYZ',t1.N,t2.N-t1.N+1)
FROM dbo.Tally t1,
dbo.Tally t2
WHERE t1.N BETWEEN 1 AND 26
AND t2.N BETWEEN 1 AND 26
AND t1.N <= t2.N
ORDER BY t1.N, t2.N;
SET STATISTICS TIME OFF;
You probably won't see much of a difference on a fast machine so here's what I see on my 9 year old, single CPU desktop using SQL Server 2005...
===== Mark's Code =================================================================================(351 row(s) affected)
SQL Server Execution Times:
CPU time = 63 ms, elapsed time = 119 ms.
===== Another way ==================================================================================
(351 row(s) affected)
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 36 ms.
If you really want to see something interesting, compare the execution plans. What's really cool about the example code I created is that even though I explicitly said to sort on N from both Tally Table aliases, you won't see a sort in the entire execution plan on my code. That's because the code didn't have to sort on any scalar computations.
Like I said, it really doesn't matter that much because of the guaranteed low number of rows for this problem but getting even such a small problem to run in less than 1/3rd of the time is really good practice for something bigger.
Heh... now, if you want to cut the reads to near zero... but you guys already know how to do that.
Jeff, that query is way better than mine, a touch of brilliance I think.
____________________________________________________
Deja View - The strange feeling that somewhere, sometime you've optimised this query before
How to get the best help on a forum
http://www.sqlservercentral.com/articles/Best+Practices/61537
Viewing 15 posts - 1 through 15 (of 21 total)
You must be logged in to reply to this topic. Login to reply