Complex query help - SQL Server Forums

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)

Complex query help

Author

Topic

amitmca
Starting Member

13 Posts

Posted - 2012-03-20 : 12:50:01

I have got a really complext query to write.
I have got an ITEM table that contains items with different price and I have to find the items from the table that makes up an order of particular amount.

ITEM TABLE
ID PRICE
1 1.00
2 1.00
3 1.15
4 1.20

Now when order amount is 2 it should return item 1 & 2.
when order amount is 1.15, it should return item 3
when order amount is 1.20, it should return item 4
when order amount is 2.15, it should return item 2 & 3
when order amount is 3.35, it should return item 2, 3 & 4.

Order amount can be anything. Any help would be highly appreciated.

X002548
Not Just a Number

15586 Posts

Posted - 2012-03-20 : 12:59:54

This is VERY Subjective. Data in Rows can be absolutely ANYTHING. It seems you are saying taht for every ID that increases, the Price increases with it.

That, is a very UNLIKELY Situation

How can you say/believe this to be true?

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/

amitmca
Starting Member

13 Posts

Posted - 2012-03-20 : 13:06:36

Hi X002548,

Thanks for your response. You are right the data can be anything. The PRICE does not increase with the ID, this is just an example and I was thinking of ORDERING the item table by PRICE.

I was trying to get the running total of the items and selecting the items where the running total is <= order amount. But that does not give the desired results. It seems like I need to do some parmutations and combinations of the running totals but do not know how to do it.

Vinnie881
Master Smack Fu Yak Hacker

1231 Posts

Posted - 2012-03-20 : 14:18:36

Can you please explain more the purpose of this? Here is a sample of how you can use a cross join to show you combinations of numbers to get to your final number.


declare @END_NUMBER decimal(12,2)

set @End_Number = 150.50
Select top 100 percent
		N002,N001,N01,N02,N03
	From
		-- Maximum number of rows from cross join is 4096, 0 to 4095
		( select N001 = .00 union all select .01 union all select .02  union all select  .03 union all
		  select       .04 union all select  .05 union all select  .06 union all
		  select       .07 union all select  .08 union all select  .09 union all
		  select       .10 union all select .11 union all select .12 union all
		  select      .13 union all select .14 union all select .15 union all
		  select      .16 ) n001
		cross join
	 ( select N002 = .00 union all select .32  union all select  .48 union all
		  select       .64 union all select  .80 union all select  .96) N002
		cross join
		( select N01 = 0 union all select  1 union all select  2 union all
		  select       3 union all select  4 union all select  5 union all
		  select       6 union all select  7 union all select  8 union all
		  select       9 union all select 10 union all select 11 union all
		  select      12 union all select 13 union all select 14 union all
		  select      15 ) n01
		cross join
		( select N02 = 0 union all select  16 union all select  32 union all
		  select      48 union all select  64 union all select  80 union all
		  select      96 union all select 112 union all select 128 union all
		  select     144 union all select 160 union all select 176 union all
		  select     192 union all select 208 union all select 224 union all
		  select     240 ) n02
		cross join
		( select N03 = 0 union all select  256 union all select  512 union all
		  select     768 union all select 1024 union all select 1280 union all
		  select    1536 union all select 1792 union all select 2048 union all
		  select    2304 union all select 2560 union all select 2816 union all
		  select    3072 union all select 3328 union all select 3584 union all
		  select    3840 ) n03
	where
		-- Minimize the number of rows crossed by selecting only rows
		-- with a value less the the square root of rows needed.
		N002+N001+N01+N02+N03 =  @End_Number
		-- Square root of total rows rounded up to next whole number
	
	order by
		1
/*
N002	N001	N01	N02	N03
0.48	0.02	6	144	0

= 150.5
*/

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

Lamprey
Master Smack Fu Yak Hacker

4614 Posts

Posted - 2012-03-20 : 15:30:56

you might be able to make use of a recursive CTE, but it sounds like you want to use some sort of bet fit fill algorithm. Here is a CTE example that works for most cases:

DECLARE @T TABLE (ItemID INT, Price MONEY)

INSERT @T (ItemID, Price)
VALUES
(1, $1.00),
(2, $1.00),
(3, $1.15),
(4, $1.20)

;WITH Cte AS
(
    SELECT *, Price AS SumPrice, CAST(ItemID AS VARCHAR(100)) AS Hierarchy
    FROM @T 
    
    UNION ALL
    
    SELECT D.*, SumPrice + D.Price, CAST(Hierarchy + ' - ' + CAST(D.ItemID AS VARCHAR(100)) AS VARCHAR(100))
    FROM 
        @T AS D
    INNER JOIN
        Cte AS C
        ON D.Price >= C.Price
        AND D.ItemID > C.ItemID
    
)

-- Example
SELECT *
FROM Cte
WHERE SuMPrice = $3.35

amitmca
Starting Member

13 Posts

Posted - 2012-03-21 : 05:25:21

Thanks Lamprey.

That is what I really want. I can then have that heirarchy column in a variable and split it to get the items.

Thank you so much. Much appreciated..

amitmca
Starting Member

13 Posts

Posted - 2012-03-21 : 12:21:25

Hi Lamprey,

I tried running this on the real data and it runs forever. The ITEM table had 99 records.

Is there any other way to stop the recursion when the SUM exceeds the order value.

Vinnie881
Master Smack Fu Yak Hacker

1231 Posts

Posted - 2012-03-21 : 12:50:27

If you have a set max depth to the hierarchy you may get better performance with this (IN this sample I made it go up to 5 levels).


drop table #tmp
DECLARE @T TABLE (ItemID INT, Price MONEY)
declare @Amount money
set @Amount = 3.35

INSERT @T (ItemID, Price)
VALUES(1, $1.00)
INSERT @T (ItemID, Price)
VALUES(2, $1.00)
INSERT @T (ItemID, Price)
VALUES(3, $1.15)
INSERT @T (ItemID, Price)
VALUES(4, $1.20)
INSERT @T (ItemID, Price)
VALUES(10000, $0.00)



select row_Number() over (order by a.itemid) as rowid,
a.itemid,a.price as price0,
b.itemid as ItemID1,b.price as price1,
c.itemid as ItemID2,c.price as price2,
d.itemid as ItemID3,d.price as price3,
e.itemid as Itemid4,e.price as price4,
a.Price + b.Price + c.Price + d.Price + e.price as TOTAL
into #TMP
from
@t a
cross join
@t b
cross join
@t c
cross join
@t d
cross join
@t e
where a.price + b.price + c.price + d.price + e.price = @Amount
and  (a.itemid < b.itemid or b.price = 0)
and  (a.itemid < c.itemid or c.price = 0)
and  (a.itemid < d.itemid or d.price = 0)
and  (a.itemid < e.itemid or e.price = 0)
and  (b.itemid < c.itemid or c.price = 0)
and  (b.itemid < d.itemid or d.price = 0)
and  (b.itemid < e.itemid or e.price = 0)
and  (c.itemid < d.itemid or d.price = 0)
and	 (c.itemid < e.itemid or e.price = 0)
and	 (d.itemid < e.itemid or e.price = 0)


select rowid as MYGROUP,itemid,price0,total from #TMP where price0 > 0
union all
select rowid,itemid1,price1,total from #TMP where price1 > 0
union all
select rowid,itemid2,price2,total from #TMP where price2 > 0
union all
select rowid,itemid3,price3,total from #TMP where price3 > 0
union all
select rowid,itemid4,price4,total from #TMP where price4 > 0
order by mygroup,itemid

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

amitmca
Starting Member

13 Posts

Posted - 2012-03-21 : 13:03:45

Thanks Vinnie,

But that does not work in all situations..

Lamprey
Master Smack Fu Yak Hacker

4614 Posts

Posted - 2012-03-21 : 13:11:12

You might be able to get similar results and gain some performance by adding a WHERE clause to the anchor of the CTE:

    WHERE Price = (SELECT MIN(Price) FROM @T)

SO the Cte becomes:

;WITH Cte AS
(
    SELECT *, Price AS SumPrice, CAST(ItemID AS VARCHAR(100)) AS Hierarchy
    FROM @T 
    WHERE Price = (SELECT MIN(Price) FROM @T)
    
    UNION ALL
    
    SELECT D.*, SumPrice + D.Price, CAST(Hierarchy + ' - ' + CAST(D.ItemID AS VARCHAR(100)) AS VARCHAR(100))
    FROM 
        @T AS D
    INNER JOIN
        Cte AS C
        ON D.Price >= C.Price
        AND D.ItemID > C.ItemID
)

But I don't think that will meet certan condiction. So really, you need a better algorithm that provides a best fit based on your business rules. But, you might get lucky. :)

amitmca
Starting Member

13 Posts

Posted - 2012-03-21 : 13:31:35

Thanks Lamprey,

Putting WHERE clause does not help that much. The query still runs forever. Is there any other way? I dont care about the best match as long as it returns at least one result.

The business logic is that the SumPrice does not exactly have to be the same as the order amount. It could be CERTAIN PERCENTAGE say 5% less than the order amount. So basically SumPrice >= @Amt - @Amt*0.05 AND SumPrice <= @Amt.

And that adds some more complexity.

Does anyone think that it can be done in SQL or do I have to do it in any high level language like C#?

amitmca
Starting Member

13 Posts

Posted - 2012-03-21 : 13:40:49

Is there a way to stop the recursion at the first match?

Vinnie881
Master Smack Fu Yak Hacker

1231 Posts

Posted - 2012-03-21 : 13:48:26

What situation does that not work in? It should work in all situations unless depth > 5 levels, is that your issue?

In that case, take a look at this post below, you can use a function for the hierarchy, and that should improve results. Take a look at the response from SWEPESO, and the final modification I posted. it can be easily modified for what you need.

http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=165671

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

Lamprey
Master Smack Fu Yak Hacker

4614 Posts

Posted - 2012-03-21 : 13:59:35

I'm not sure it'll help, but you might try adding another where clause to the recursive portion of the cte:

        AND SumPrice + D.Price <= $2.00 -- Value you are searching for (repalce with variable?)

So the CTE becomes:

;WITH Cte AS
(
    SELECT *, Price AS SumPrice, CAST(ItemID AS VARCHAR(100)) AS Hierarchy
    FROM @T 
    WHERE Price = (SELECT MIN(Price) FROM @T)
    
    UNION ALL
    
    SELECT D.*, SumPrice + D.Price, CAST(Hierarchy + ' - ' + CAST(D.ItemID AS VARCHAR(100)) AS VARCHAR(100))
    FROM 
        @T AS D
    INNER JOIN
        Cte AS C
        ON D.Price >= C.Price
        AND D.ItemID > C.ItemID
        AND SumPrice + D.Price <= $2.00
    
)

amitmca
Starting Member

13 Posts

Posted - 2012-03-21 : 14:51:37

Thanks Lamprey

No, it seems that the recursion does not stop even after putting that condition. It keeps running..

Vinnie -> Ya if the first five items have the same same value. It does not return anything. I have not tried your second solution yet but I will let you know how it goes.

Lamprey
Master Smack Fu Yak Hacker

4614 Posts

Posted - 2012-03-21 : 18:26:27

Humm, how big is your table? I can create a table (with no indexes) with hundreds of values that runs instantaneously on my mediocre laptop.

amitmca
Starting Member

13 Posts

Posted - 2012-03-22 : 04:30:32

Hi Lamprey,

My table is big but I run this query on the subset of the table containing 99 records only. i.e I get only 99 records into a table variable and then runs my query on this table variable.

I have noticed that the length of time, varies on different amount value. For some it is instantaneous but then for other it runs for 8 - 9 mins and returns thousands of records. If I use TOP to restrict the number, it does not help.

amitmca
Starting Member

13 Posts

Posted - 2012-03-23 : 06:41:43

Hi Vinnie,

I find it bit difficult to mend your solution to resolve my issue. I am stuck.

Recursive CTE runs forever and recursion does not stop even if using a WHERE clause or AND condition to end the recursion. It seems that it tries to calculate all the possible combinations before returning and that turns out to be in millions for only 99 records. It would be really good if there is any way to stop the recursion at the first match.

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2012-03-23 : 08:51:45

It's called "BIN PACKING" and I have an example here http://weblogs.sqlteam.com/peterl/archive/2008/08/12/How-to-sum-up-an-unknown-number-of-records.aspx
and here http://weblogs.sqlteam.com/peterl/archive/2008/11/23/Bin-packaging.aspx

N 56°04'39.26"
E 12°55'05.63"

amitmca
Starting Member

13 Posts

Posted - 2012-03-23 : 12:05:57

Thanks SwePeso.

The first solution seems to work but what I need is the ITEM IDs that make up the order (that amount). If you have any solution, that is fine otherwise I will try to do it myself.

Regarding your second solution, it does not seem to work for some reason. The feedback is same as the comment on your webblog.

Thanks again.

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources