Complicated sort algorithm (color coded example)

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2008 Forums

Transact-SQL (2008)

Complicated sort algorithm (color coded example)

Author

Topic

LaurieCox

158 Posts

Posted - 2012-03-30 : 12:08:06

I have a table that stores drug prescription history. I thought I could see the history of given patient/drug by sorting the table by member_id, drug_name, orderhistory and ordercontent. But that turned out not to be the case for reasons that don't need exploring at this juncture.

Anyway within each member_id/Drug_name pairing I have to sort via a couple of "linking fields" (instead of orderhistory/ordercontent).

So here is the table:


CREATE TABLE #RxHistory (
       NumDosages int,
       member_id int,
       Drug_Name varchar(50),
       orderhistory_id int,
       ordercontent_id int,
       srcrx_id int,
       rx_id int,
       event varchar(10),
       rx_dosage_id int)

The fields to create the linking are the srcrx_id and rx_id fields. The srcrx_id points to the rx_id of the record it should follow in the sort. There are two possibilities if srcrx_id = rx_id:

Event = Active - first record in chain

Event = Discontinu – last record in chain*

*A Chain might not end on Discontinu but if it ends on Reorder or Change the srcrx_id will not equal the rx_id.

There is a twist: One member/drug/event can have multiple records (for different dosages). These records should always be grouped together and their order doesn't matter. These records will have the same srcrx_id and rx_id. With the srcrx_id pointing to the rx_id of the record(s) each should follow. The NumDosages field tells how many records are in these groups.

So they say a picture is worth a thousand words, so maybe a color coded table might help.

Here is the data sorted by member_id, drug_name, orderhistory and ordercontent. But I want the data sorted so that each color group is sorted together (data dml at end of post):


NumDosages  member_id   Drug_Name       orderhistory_id ordercontent_id srcrx_id    rx_id       event      rx_dosage_id
----------- ----------- --------------- --------------- --------------- ----------- ----------- ---------- ------------
2           2202716     Adderall        5701362         11190879        10211987    10211987    Active     11344974
2           2202716     Adderall        5701362         11190879        10211987    10211987    Active     11344975
2           2202716     Adderall        5940275         11647794        10211987    10628922    Change     11796332
2           2202716     Adderall        5940275         11647794        10211987    10628922    Change     11796331
1           2202716     Adderall        6033829         11824592        10628922    10791589    Change     11972481
2           2202716     Adderall        6137645         12021262        10972692    10972692    Active     12168474
2           2202716     Adderall        6137645         12021262        10972692    10972692    Active     12168475
1           2202716     Adderall        6137653         12021273        10791589    10791589    Discontinu 11972481
1           2202716     Adderall        6137754         12021459        10972692    10972868    Change     12168664
1           2202716     Adderall        6137763         12021474        10972882    10972882    Active     12168680
1           2202716     Adderall        6388818         12494000        10972868    11405646    Change     12637591
1           2202716     Adderall        6388861         12494082        10972882    11405719    Reorder    12637676
1           2202716     Adderall        6742841         13160076        11405646    11405646    Discontinu 12637591

Explanation of why the red are grouped as shown:

The first two rows are one of the multiple groupings (i.e. two dosages for one member/drug/event). They are also the first record(s) in a set as srcrx_id = rx_id and event = 'Active'. The next two records are also a group and they follow the first two records as their srcrx_id (10211987) = the rx_id in the first two records. The next time the drug was prescribed they dropped one of the dosages which is why there is only one record that points to the previous multi record group.

The last record in the "red" chain is the 8th record above as its srcrx_id (10791589) points to to the rx_id of the 5th record.

So given the table above my expected results should be:


NumDosages  member_id   Drug_Name       orderhistory_id ordercontent_id srcrx_id    rx_id       event      rx_dosage_id
----------- ----------- --------------- --------------- --------------- ----------- ----------- ---------- ------------
2           2202716     Adderall        5701362         11190879        10211987    10211987    Active     11344974
2           2202716     Adderall        5701362         11190879        10211987    10211987    Active     11344975
2           2202716     Adderall        5940275         11647794        10211987    10628922    Change     11796332
2           2202716     Adderall        5940275         11647794        10211987    10628922    Change     11796331
1           2202716     Adderall        6033829         11824592        10628922    10791589    Change     11972481
1           2202716     Adderall        6137653         12021273        10791589    10791589    Discontinu 11972481
2           2202716     Adderall        6137645         12021262        10972692    10972692    Active     12168474
2           2202716     Adderall        6137645         12021262        10972692    10972692    Active     12168475
1           2202716     Adderall        6137754         12021459        10972692    10972868    Change     12168664
1           2202716     Adderall        6388818         12494000        10972868    11405646    Change     12637591
1           2202716     Adderall        6742841         13160076        11405646    11405646    Discontinu 12637591
1           2202716     Adderall        6137763         12021474        10972882    10972882    Active     12168680
1           2202716     Adderall        6388861         12494082        10972882    11405719    Reorder    12637676

Note that the "blue" group does not end on a Discontinue event.

I don't think I really care what order the "color groups" are in for given member_id/drug_name set of records. I.e. the records above could be ordered green/blue/red and I wouldn't care. Though I suppose it would be nice if the color grouping with the smallest first rx_id came first in the sort.

I have been reading about recursive common table expressions where I think my solution lies, but I am having trouble understanding how they work and how to apply them to this problem.

I think the multiple records for a given member/drug/event and the way the beginning (srcrx_id = rx_id and event = Active) and (possible) ending (srcrx_id = rx_id and event = Discontinu) of the "chains" are setup make the solution more complicated than the usual hierarchical solution examples I have seen so far in my reading.

Thanks,

Laurie

Test data for example given:


INSERT INTO #RxHistory
SELECT 2,2202716,'Adderall',5701362,11190879,10211987,10211987,'Active',11344974 UNION ALL
SELECT 2,2202716,'Adderall',5701362,11190879,10211987,10211987,'Active',11344975 UNION ALL
SELECT 2,2202716,'Adderall',5940275,11647794,10211987,10628922,'Change',11796332 UNION ALL
SELECT 2,2202716,'Adderall',5940275,11647794,10211987,10628922,'Change',11796331 UNION ALL
SELECT 1,2202716,'Adderall',6033829,11824592,10628922,10791589,'Change',11972481 UNION ALL
SELECT 2,2202716,'Adderall',6137645,12021262,10972692,10972692,'Active',12168474 UNION ALL
SELECT 2,2202716,'Adderall',6137645,12021262,10972692,10972692,'Active',12168475 UNION ALL
SELECT 1,2202716,'Adderall',6137653,12021273,10791589,10791589,'Discontinu',11972481 UNION ALL
SELECT 1,2202716,'Adderall',6137754,12021459,10972692,10972868,'Change',12168664 UNION ALL
SELECT 1,2202716,'Adderall',6137763,12021474,10972882,10972882,'Active',12168680 UNION ALL
SELECT 1,2202716,'Adderall',6388818,12494000,10972868,11405646,'Change',12637591 UNION ALL
SELECT 1,2202716,'Adderall',6388861,12494082,10972882,11405719,'Reorder',12637676 UNION ALL
SELECT 1,2202716,'Adderall',6742841,13160076,11405646,11405646,'Discontinu',12637591 


--additional test data

INSERT INTO #RxHistory
SELECT 2,1161600,'Geodon',7544749,14665602,13392220,13392220,'Active',14789322 UNION ALL
SELECT 2,1161600,'Geodon',7544749,14665602,13392220,13392220,'Active',14789321 UNION ALL
SELECT 1,1161600,'Geodon',7732911,15019409,13715110,13715110,'Active',15138164 UNION ALL
SELECT 2,1161600,'Geodon',7732911,15019411,13392220,13392220,'Discontinu',14789322 UNION ALL
SELECT 2,1161600,'Geodon',7732911,15019411,13392220,13392220,'Discontinu',14789321 UNION ALL
SELECT 1,1161600,'Geodon',7929106,15390853,13715110,14054760,'Reorder',15505132 UNION ALL
SELECT 1,1161600,'Geodon',8094520,15704031,14054760,14340808,'Reorder',15814169 UNION ALL
SELECT 1,1161600,'Geodon',8979570,17398166,14340808,15889402,'Reorder',17482104 UNION ALL
SELECT 1,1161600,'Geodon',9425431,18242925,15889402,16661267,'Reorder',18310160 UNION ALL
SELECT 1,1161600,'Geodon',9752837,18868647,16661267,17235140,'Reorder',18925047 UNION ALL
SELECT 1,1161600,'Ativan',6901411,13458977,12288560,12288560,'Active',13594431 UNION ALL
SELECT 1,1161600,'Ativan',6997730,13639554,12288560,12454409,'Reorder',13774209 UNION ALL
SELECT 1,1161600,'Ativan',7084079,13801775,12454409,12603558,'Change',13935715 UNION ALL
SELECT 1,1161600,'Ativan',7544749,14665599,12603558,13392217,'Reorder',14789318 UNION ALL
SELECT 1,1161600,'Ativan',9425469,18242997,13392217,16661332,'Reorder',18310231 UNION ALL
SELECT 2,1245979,'Depakote',5246797,10328838,9427751,9427751,'Active',10494363 UNION ALL
SELECT 2,1245979,'Depakote',5246797,10328838,9427751,9427751,'Active',10494362 UNION ALL
SELECT 2,1245979,'Depakote',5367492,10558633,9427751,9636747,'Reorder',10721193 UNION ALL
SELECT 2,1245979,'Depakote',5367492,10558633,9427751,9636747,'Reorder',10721192 UNION ALL
SELECT 1,1245979,'Depakote',5423878,10665776,9733943,9733943,'Active',10826606 UNION ALL
SELECT 1,1245979,'Depakote',5448264,10711872,9733943,9733943,'Discontinu',10826606 UNION ALL
SELECT 2,1245979,'Depakote',5538441,10881088,9636747,9929767,'Reorder',11038935 UNION ALL
SELECT 2,1245979,'Depakote',5538441,10881088,9636747,9929767,'Reorder',11038934 UNION ALL
SELECT 2,1245979,'Depakote',5674794,11140347,9929767,10165950,'Reorder',11295158 UNION ALL
SELECT 2,1245979,'Depakote',5674794,11140347,9929767,10165950,'Reorder',11295159 UNION ALL
SELECT 2,1245979,'Depakote',5915166,11599312,10165950,10584817,'Reorder',11748614 UNION ALL
SELECT 2,1245979,'Depakote',5915166,11599312,10165950,10584817,'Reorder',11748615 UNION ALL
SELECT 3,1245979,'Depakote',6449491,12607778,10584817,11509401,'Change',12749909 UNION ALL
SELECT 3,1245979,'Depakote',6449491,12607778,10584817,11509401,'Change',12749907 UNION ALL
SELECT 3,1245979,'Depakote',6449491,12607778,10584817,11509401,'Change',12749908 UNION ALL
SELECT 3,1245979,'Depakote',6963168,13574815,11509401,11509401,'Discontinu',12749908 UNION ALL
SELECT 3,1245979,'Depakote',6963168,13574815,11509401,11509401,'Discontinu',12749909 UNION ALL
SELECT 3,1245979,'Depakote',6963168,13574815,11509401,11509401,'Discontinu',12749907

X002548
Not Just a Number

15586 Posts

Posted - 2012-03-30 : 12:24:39

Could you be a little simpler in what you want?

Are you just trying to group thins together?

Brett

8-)

Hint: Want your questions answered fast? Follow the direction in this link
http://weblogs.sqlteam.com/brettk/archive/2005/05/25/5276.aspx

Want to help yourself?

http://msdn.microsoft.com/en-us/library/ms130214.aspx

http://weblogs.sqlteam.com/brettk/

http://brettkaiser.blogspot.com/

LaurieCox

158 Posts

Posted - 2012-03-30 : 14:33:59

Yeah I was afraid of that.

Not sure as I can be simpler but I can try to describe it better.

I want to sort a table so that the data is sorted by member_id, drug_name and the records within each given member_id/drug_name are arranged (sorted) according to how they link via the srcrx_id and rx_id.

First I will remove ordercontent_id and orderhistory_id from my example table as they do not have anything to do with the solution and number the rows to use for reference. So here is the table


Row NumDosages  member_id   Drug_Name    srcrx_id    rx_id       event      rx_dosage_id
--- ----------- ----------- ------------ ----------- ----------- ---------- ------------
1   2           2202716     Adderall     10211987    10211987    Active     11344974
2   2           2202716     Adderall     10211987    10211987    Active     11344975
3   2           2202716     Adderall     10211987    10628922    Change     11796332
4   2           2202716     Adderall     10211987    10628922    Change     11796331
5   1           2202716     Adderall     10628922    10791589    Change     11972481
6   2           2202716     Adderall     10972692    10972692    Active     12168474
7   2           2202716     Adderall     10972692    10972692    Active     12168475
8   1           2202716     Adderall     10791589    10791589    Discontinu 11972481
9   1           2202716     Adderall     10972692    10972868    Change     12168664
10  1           2202716     Adderall     10972882    10972882    Active     12168680
11  1           2202716     Adderall     10972868    11405646    Change     12637591
12  1           2202716     Adderall     10972882    11405719    Reorder    12637676
13  1           2202716     Adderall     11405646    11405646    Discontinu 12637591

I will start with the "blue" chain as it is the easiest. The first record in the blue chain is row 10. We know this is a first record in a chain because srcrx_id = rx_id and event = Active. The second record in the blue chain is row 12. We know this row should follow row 10 because its srcrx_id = the rx_id of row 10.

There is nothing about this record that tells us it’s at the end of a chain but we know it is because there is no other record whose srcrx_id = row 12's rx_id. So the blue chain is only two records long and should sort together.

Now I will do the green chain:

The green chain has two records as the beginning of the chain (rows 6 and 7). This is the part I tried to explain in the "There is a twist:" section in my op. These records represent a single script that was written for two different dosages. You can tell that these are a single script as the only difference between the two records is the rx_dosage_id (all other fields are equal).

You can tell these are the beginning of a chain because srcrx_id = rx_id and event = Active for each record.

The next record in the green chain is row 9. Note that there is only one dosage record that follows rows 6 and 7. This is because one of the two dosages was dropped. You can tell that this record follows rows 6 and 7 because the row 9's srcrx_id = the rx_id of rows 6 and 7.

Row 11 is next in the green chain because row 11's srcrx_id = row 9's rx_id.
Row 13 is next because row 13's srcrx_id = row 11's rx_id.

Row 13 is the last in the green chain because srcrx_id = rx_id and event = 'Discontinu', also there will be no other record whose srcrx_id = 13's rx_id.

So I hope that is as clear as mud. I will post more examples on Monday if I don't get any solutions.

I am also trying to solve this myself by reading about recursive common table expressions where I think the solution lies.

Thanks,

Laurie

Vinnie881
Master Smack Fu Yak Hacker

1231 Posts

Posted - 2012-03-30 : 14:38:59

this was a pain:) Next time, just have a column that groups it so you don't need to be as creative on the sort query!

Here you go:


drop table #tmp1,#RxHistory,#FInaltmp
CREATE TABLE #RxHistory (
       NumDosages int,
       member_id int,
       Drug_Name varchar(50),
       orderhistory_id int,
       ordercontent_id int,
       srcrx_id int,
       rx_id int,
       event varchar(10),
       rx_dosage_id int)

insert into #RxHistory
SELECT 2,1161600,'Geodon',7544749,14665602,13392220,13392220,'Active',14789322 UNION ALL
SELECT 2,1161600,'Geodon',7544749,14665602,13392220,13392220,'Active',14789321 UNION ALL
SELECT 1,1161600,'Geodon',7732911,15019409,13715110,13715110,'Active',15138164 UNION ALL
SELECT 2,1161600,'Geodon',7732911,15019411,13392220,13392220,'Discontinu',14789322 UNION ALL
SELECT 2,1161600,'Geodon',7732911,15019411,13392220,13392220,'Discontinu',14789321 UNION ALL
SELECT 1,1161600,'Geodon',7929106,15390853,13715110,14054760,'Reorder',15505132 UNION ALL
SELECT 1,1161600,'Geodon',8094520,15704031,14054760,14340808,'Reorder',15814169 UNION ALL
SELECT 1,1161600,'Geodon',8979570,17398166,14340808,15889402,'Reorder',17482104 UNION ALL
SELECT 1,1161600,'Geodon',9425431,18242925,15889402,16661267,'Reorder',18310160 UNION ALL
SELECT 1,1161600,'Geodon',9752837,18868647,16661267,17235140,'Reorder',18925047 UNION ALL
SELECT 1,1161600,'Ativan',6901411,13458977,12288560,12288560,'Active',13594431 UNION ALL
SELECT 1,1161600,'Ativan',6997730,13639554,12288560,12454409,'Reorder',13774209 UNION ALL
SELECT 1,1161600,'Ativan',7084079,13801775,12454409,12603558,'Change',13935715 UNION ALL
SELECT 1,1161600,'Ativan',7544749,14665599,12603558,13392217,'Reorder',14789318 UNION ALL
SELECT 1,1161600,'Ativan',9425469,18242997,13392217,16661332,'Reorder',18310231 UNION ALL
SELECT 2,1245979,'Depakote',5246797,10328838,9427751,9427751,'Active',10494363 UNION ALL
SELECT 2,1245979,'Depakote',5246797,10328838,9427751,9427751,'Active',10494362 UNION ALL
SELECT 2,1245979,'Depakote',5367492,10558633,9427751,9636747,'Reorder',10721193 UNION ALL
SELECT 2,1245979,'Depakote',5367492,10558633,9427751,9636747,'Reorder',10721192 UNION ALL
SELECT 1,1245979,'Depakote',5423878,10665776,9733943,9733943,'Active',10826606 UNION ALL
SELECT 1,1245979,'Depakote',5448264,10711872,9733943,9733943,'Discontinu',10826606 UNION ALL
SELECT 2,1245979,'Depakote',5538441,10881088,9636747,9929767,'Reorder',11038935 UNION ALL
SELECT 2,1245979,'Depakote',5538441,10881088,9636747,9929767,'Reorder',11038934 UNION ALL
SELECT 2,1245979,'Depakote',5674794,11140347,9929767,10165950,'Reorder',11295158 UNION ALL
SELECT 2,1245979,'Depakote',5674794,11140347,9929767,10165950,'Reorder',11295159 UNION ALL
SELECT 2,1245979,'Depakote',5915166,11599312,10165950,10584817,'Reorder',11748614 UNION ALL
SELECT 2,1245979,'Depakote',5915166,11599312,10165950,10584817,'Reorder',11748615 UNION ALL
SELECT 3,1245979,'Depakote',6449491,12607778,10584817,11509401,'Change',12749909 UNION ALL
SELECT 3,1245979,'Depakote',6449491,12607778,10584817,11509401,'Change',12749907 UNION ALL
SELECT 3,1245979,'Depakote',6449491,12607778,10584817,11509401,'Change',12749908 UNION ALL
SELECT 3,1245979,'Depakote',6963168,13574815,11509401,11509401,'Discontinu',12749908 UNION ALL
SELECT 3,1245979,'Depakote',6963168,13574815,11509401,11509401,'Discontinu',12749909 UNION ALL
SELECT 3,1245979,'Depakote',6963168,13574815,11509401,11509401,'Discontinu',12749907

select row_number() over (order by (select 1)) as rowid,*
into #TMP1
from
#RxHistory
order by srcrx_ID


;with cte(   rowid, NumDosages,
       member_id ,
       Drug_Name ,
       orderhistory_id ,
       ordercontent_id ,
       srcrx_id ,
       rx_id ,
       event,
       rx_dosage_id,sort)
as
(
select * ,'-' + cast(rowid as varchar(max)) + '-'
from
#TMP1
where rx_id = srcrx_id
and event = 'Active'
union all
select b.* ,a.sort + '-' + cast(b.rowid as varchar(max)) + '-'
from
#TMP1 b
inner join
cte a
on  
a.member_id = b.member_id
and
(	b.srcrx_id = a.srcrx_id 
or    b.srcrx_id = a.rx_id 
or	  b.rx_id = a.srcrx_id 
or    b.rx_id = a.rx_id
)
where  
b.rowid > a.rowid
)
select * 
into #FInaltmp
from cte
OPTION (MAXRECURSION 0)



select *
from 
#TMP1 a
cross apply
(select top 1 aa.sort 
	from #Finaltmp aa where aa.sort like '%-' + cast(a.rowid as varchar(10)) + '-%'
	 order by len(aa.sort) desc) b
order by member_id,b.sort,event,rx_id

Success is 10% Intelligence, 70% Determination, and 22% Stupidity.
\_/ _/ _/\_/ _/\_/ _/ _/- 881

LaurieCox

158 Posts

Posted - 2012-03-30 : 15:22:28

Hi Vinnie,

First of all thank you for all your work. I chuckled at your "next time … comment". Oh that I could have nice easy data to work with. The data is not mine I am just trying to work with it. This is actually step x in a process to take this data and convert it to another system (whose table structure I also have no control over).

Anyway I am sorry to report that your solution breaks down when I add the other sample data (in my op) to the RxHistory table. I haven't started analyzing it yet so I don't know why.

Anyway you have given me something to work with (so thank you for that). Probably won't have finished analyzing your solution before the end of the work day so I won't get back with a better response then "it don't work" until Monday. One thing I notice at first glance is that the Adderall records are scattered willy-nilly throughout the result set. The other records (except for the intrusion of Adderall) look like they are at least grouped correctly by member_id/drug_name. I haven't looked at if they order by linked data correctly.

One thing missing from my test data is records for the same drug but different members (if these were there they should sort as completely different groups). The test data does include a member_id (1161600) with more than one drug though.

But again, thank you for your work. I really do appreciate it.

Laurie

Vinnie881
Master Smack Fu Yak Hacker

1231 Posts

Posted - 2012-03-30 : 15:36:24

Did you try it since the last edit, I think I corrected that?

Success is 10% Intelligence, 70% Determination, and 22% Stupidity.
\_/ _/ _/\_/ _/\_/ _/ _/- 881

LaurieCox

158 Posts

Posted - 2012-03-30 : 15:47:03

Hi Vinnie,

Yep, at a glance the results look much better.

By the way I looked it up and Adderall is a drug used to help treat ADHD. I thought maybe that was why the Adderall records were scattered willy-nilly throughout the result set.

Again thank you very much,

Laurie

Vinnie881
Master Smack Fu Yak Hacker

1231 Posts

Posted - 2012-03-30 : 16:01:03

Welcome, since it is not your data you are working with, tell the people that created it that their data structure sucks to work with;)

With some index's and a few minor changes, you should be able to improve the query quite a bit.

I'd also change it into a table-valued function and pass the member_id/drug for better results by filtering the table and issolate the members data into a smaller set so the join that uses all the OR's do not cripple performance.



Select * from
MemberDrugtable a --A table that has the unique members and drug type information.
cross apply
fn_getorderedresults(a.member_id, a.Drug_Name)

this should hopefully allow for more flexibility and better performance.

Success is 10% Intelligence, 70% Determination, and 22% Stupidity.
\_/ _/ _/\_/ _/\_/ _/ _/- 881

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources