TSQL Challenge 47

Am I correct in assuming that any given chain can be of completely arbtrary length?
That is, [Changes] can be 100,000.

Rick Bielawski:

Am I correct in assuming that any given chain can be of completely arbtrary length?
That is, [Changes] can be 100,000.

That's correct.

Here is some more data for logic testing:

INSERT TC47(OldCardNo,NewCardNo)
SELECT 2,2 UNION ALL
SELECT 100,10 UNION ALL
SELECT 4,100 UNION ALL
SELECT 2,5 UNION ALL
SELECT 77,77 UNION ALL
SELECT 77,77 UNION ALL
SELECT 88,88 UNION ALL
SELECT 100,100 UNION ALL
SELECT 10,10 UNION ALL
SELECT 99,3 UNION ALL
SELECT 100,100 UNION ALL
SELECT 20,30 UNION ALL
SELECT 50,60 UNION ALL
SELECT 60,70 UNION ALL
SELECT 5,99

-- expected result:

FirstCardNo LastCardNo  Changes
----------- ----------- -----------
2           3           4
4           10          5
20          30          1
50          70          2
77          77          2
88          88          1

And here is a script for performance testing:

 

-- tc47_perftest

-- parameters
declare @m float=0.01 -- card change probability
declare @n int=10000  -- number of real changes
declare @s float=0.2  -- probability for duplicates

if object_id('tempdb..#c') is not null drop table #c
create table #c (card int, sort int, sort2 int, number int)

set nocount on
declare @i int, @j int, @k int
declare @card int, @sort int

set @i=rand(1) -- repeatable seed

begin tran
set @k=0
set @card=1
while @k<@n begin
	if rand()<@m set @card=@card+1
	set @sort = rand()*1000000000
	insert into #c (card, sort, sort2, number)	values (@card, @sort, rand()*1000000000, @k)
	-- add duplicates
	while rand()<@s 
		insert into #c (card, sort, sort2, number)	values (@card, @sort, rand()*1000000000, @k)
	set @k=@k+1
end


commit

--select * from #c order by card, sort

IF OBJECT_ID('TC47','U') IS NOT NULL BEGIN
	DROP TABLE TC47
END
CREATE TABLE dbo.TC47 (
	SrNo INT IDENTITY,
	OldCardNo INT NOT NULL,
	NewCardNo INT NOT NULL
)

;with
cte1 as (
	select card, number, row_number() over(partition by card order by sort) as rn, sort, sort2
	from #c
)
, cte2 as (
	select a.card, a.number as oldcardno, b.number as newcardno, a.sort, a.sort2
	from cte1 a
	join cte1 b
	on a.rn=b.rn-1
	and a.card=b.card
)
insert into tc47 (oldcardno, newcardno)
select oldcardno,newcardno 
from cte2
order by sort2

drop table #c

select * from tc47

My stats:

(98 row(s) affected)
Table 'Worktable'. Scan count 9906, logical reads 139812, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'TC47'. Scan count 8, logical reads 264, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

 SQL Server Execution Times:
   CPU time = 359 ms,  elapsed time = 365 ms.

Is there any posibility that any cardNo is Alloted to some another card.

Like 10>>20 and that previous 10 is assign to 25>>10. Is this possible?

 

Alok Chandra Shahi:

Is there any posibility that any cardNo is Alloted to some another card.
Like 10>>20 and that previous 10 is assign to 25>>10. Is this possible?

So your question is: can the input be
25,10
10,20
The answer is obviously yes.

Secondly, look at rule 3 which says a number can be used only on one card.
But you need to keep separate the concept of a card and the concept of a number written on a card.
Here a card is just a piece of paper on which you can write a number followed by erasing that number and writing another number (or the same number) in its place.
The input table tells you the change from one number to another. But it doesn't tell you 'directly' on which card this happens. But because of the rules, the final result can be determined such that each output row corresponds to a card which had a certain number written on it in the beginning and a certain number written on it at the end (plus the number of links in the chain from the first number to the last number).

>> And here is a script for performance testing:

Stefan_G; Since your performance test code is essentially adding, I am right in thinking that you can summarise the expected results as follows...?

INSERT INTO tc47_expected (firstcardno, lastcardno, changes)
SELECT MIN(oldcardno), MAX(newcardno), COUNT(1) FROM #d
GROUP BY card
ORDER BY MIN(oldcardno)

where #d is:

WITH cte1 AS (...), cte2 AS (...)
SELECT card, oldcardno, newcardno
INTO #d
FROM cte2
ORDER BY sort2

and tc47 is:

insert into tc47 (oldcardno, newcardno)
select oldcardno,newcardno from #d

I got (98 row(s) affected) Table 'Worktable'. Scan count 12438, logical reads 214967, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. Table 'TC47'. Scan count 3, logical reads 162, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. SQL Server Execution Times: CPU time = 422 ms, elapsed time = 480 ms. regards David

Could you please add an index to the table tc47?

I can do it with an index!

Without one I am a donkey with no legs climbing an icy reverse overhang in the dark with no sense of direction and a bad case of tinnitus!

Best I have got without an index is about 8 seconds...bah!

MisterMagoo:

Could you please add an index to the table tc47?

I can do it with an index!

Without one I am a donkey with no legs climbing an icy reverse overhang in the dark with no sense of direction and a bad case of tinnitus!

Best I have got without an index is about 8 seconds...bah!

Ain't that typical - I was just about to give up and this happens :-O

(98 row(s) affected)

Table 'Worktable'. Scan count 9908, logical reads 124473, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table 'TC47'. Scan count 3, logical reads 99, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

 

 SQL Server Execution Times:

   CPU time = 312 ms,  elapsed time = 332 ms.

jimbobmcgee:

>> And here is a script for performance testing:
Stefan_G; Since your performance test code is essentially adding, I am right in thinking that you can summarise the expected results as follows...?

@jimbobmcgee
Can you be a bit clearer in what you are trying to say here?
Your solution must first pass the logic test and only then will it be allowed to run the load test.
Also, no temporary tables allowed and no INSERTs allowed.

@jimbobmcgee
I see what you're asking.
You want to see the output from the performance data to see if your solution, besides going like lightning, also produces correct results. :-)
I can give you an answer later today when I get to my computer.

jimbobmcgee:

Stefan_G; Since your performance test code is essentially adding, I am right in thinking that you can summarise the expected results as follows...?

INSERT INTO tc47_expected (firstcardno, lastcardno, changes)
SELECT MIN(oldcardno), MAX(newcardno), COUNT(1) FROM #d
GROUP BY card
ORDER BY MIN(oldcardno)

 No, that is not correct.

The expected result from the performance test is this: 

FirstCardNo LastCardNo  Changes
----------- ----------- -----------
11          116         204
196         200         165
313         310         62
352         367         73
414         412         14
431         441         80
492         490         2
494         493         1
512         515         23
519         526         83
605         598         29
621         616         34
655         659         57
779         728         155
825         828         30
1017        956         269
1120        1194        191
1218        1214        10
1219        1220        1
1236        1234        52
1300        1269        49
1319        1348        77
1381        1377        55
1462        1443        64
1496        1488        82
1718        1560        223
1753        1746        71
1788        1783        34
1802        1805        19
1827        1828        43
1853        1866        58
1941        1896        73
2033        2059        296
2275        2293        205
2348        2352        15
2380        2360        40
2441        2413        153
2529        2526        45
2547        2548        11
2560        2549        16
2581        2572        44
2695        2669        173
2784        2796        164
3001        3034        222
3237        3202        380
3385        3475        145
3479        3479        1
3579        3588        378
3777        3794        36
3852        3853        84
4014        4081        400
4367        4466        397
4498        4511        53
4605        4557        140
4801        4765        326
4951        4969        253
5146        5132        94
5195        5202        22
5217        5215        35
5319        5456        280
5485        5461        95
5539        5538        4
5542        5668        214
5759        5776        521
6143        6147        135
6268        6277        78
6365        6462        245
6534        6525        123
6620        6612        85
6767        6890        390
6973        6969        9
6981        6976        18
6995        7001        13
7157        7085        229
7202        7203        74
7387        7296        229
7471        7443        62
7476        7489        36
7515        7516        22
7576        7553        149
7768        7717        207
8068        8053        357
8095        8104        12
8115        8119        18
8287        8215        262
8369        8391        293
8671        8672        172
8740        8865        554
9176        9165        38
9181        9189        20
9448        9356        319
9488        9498        76
9569        9581        79
9591        9588        9
9792        9683        327
9863        9868        14
9925        9898        112
9994        9971        41

(98 row(s) affected)

MisterMagoo:

Ain't that typical - I was just about to give up and this happens :-O

 

(98 row(s) affected)

Table 'Worktable'. Scan count 9908, logical reads 124473, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table 'TC47'. Scan count 3, logical reads 99, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

 SQL Server Execution Times:

   CPU time = 312 ms,  elapsed time = 332 ms.

 

Good job!

Impressive that you manage to do this with only three scans of the original table.

Stefan_G:

MisterMagoo:

Table 'Worktable'. Scan count 9908, logical reads 124473, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table 'TC47'. Scan count 3, logical reads 99, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

 

Good job!

Impressive that you manage to do this with only three scans of the original table.

 

Thanks - I must admit it was a shock to me too! I had to run it again and again before I believed it!

The sudden change from 8 seconds to 300ms came about from 1 change in the code that I kind of felt might help, but I had no idea it would help this much.

I have since added a little bit to the reads on the worktable as I noticed that chains that consisted of one row of "no change" data (e.g. 77=>77) were not being picked up , but the change to the stats was so small not to bother posting.

I might have a play with pseudo-recursion to see if that can help at all with this one...