Rolling up two lists to find cheapest price

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)

Rolling up two lists to find cheapest price

Author

Topic

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2011-08-23 : 12:02:04

Hello everyone.

Suppose I have two lists of quotes that model outbound and inbound legs of possible trips. Each list is a collection of 2 tuples, (or key value) of DepartureDateTime and Quote. I want to roll up those lists and produce a header row showing the *cheapest* possible combination (a trip that you could actually make based on the outbound dates and inbound dates)

Example:


Possible Outbounds (
      ('2011-01-01T12:00:00', 100)
    , ('2011-01-01T15:00:00', 75)
    )

Possible Inbounds (
      ('2011-01-01T14:00:00', 50)
    , ('2011-01-01T16:00:00', 150)
    )

The result I want in this case is:


Results [Outbound, Inbound, TotalPrice] (
    ('2011-01-01T12:00:00', '2011-01-01T14:00:00', 150)
    )

Here the cheapest possible combined quote is 150 (100 + 50)

Now as the lists get large this kind of operation gets expensive if you do it the nieve way (cross join everything possible and then take the minimum).

Does anyone have a better way than the second way illustrated in this example?


SET NOCOUNT ON

/*
-- Create Data Set
IF OBJECT_ID('tempDb..#outBoundList') IS NOT NULL DROP TABLE #outBoundList
CREATE TABLE #outBoundList  (
	[OutboundDateStamp] DATETIME PRIMARY KEY
	, [Price] SMALLMONEY
	)

IF OBJECT_ID('tempDb..#inBoundList') IS NOT NULL DROP TABLE #inBoundList
CREATE TABLE #inBoundList (
	[InboundDateStamp] DATETIME PRIMARY KEY
	, [Price] SMALLMONEY
	)

-- Populate Outbound List
INSERT #outBoundList ([OutboundDateStamp], [Price])
SELECT
	DATEADD(SECOND, ABS(CAST(CAST(NEWID() AS VARBINARY(32)) AS INT)), '19700101')
	, CAST(ABS(CAST(CAST(NEWID() AS VARBINARY(16)) AS SMALLINT)) AS SMALLMONEY)
FROM
	           ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS a
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS b
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS c
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS d
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS e
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS f
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS g
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS h
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS i
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS j
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS k
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS l

INSERT #inBoundList ([InboundDateStamp], [Price])
SELECT
	DATEADD(SECOND, ABS(CAST(CAST(NEWID() AS VARBINARY(32)) AS INT)), '19700101')
	, CAST(ABS(CAST(CAST(NEWID() AS VARBINARY(16)) AS SMALLINT)) AS SMALLMONEY)
FROM
	           ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS a
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS b
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS c
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS d
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS e
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS f
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS g
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS h
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS i
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS j
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS k
	CROSS JOIN ( SELECT 1 AS [a] UNION SELECT 2 AS [b] ) AS l

--SELECT * FROM #outBoundList
--SELECT * FROM #inBoundList
*/

-- Find the absolute best price possible by Cross Joining all possible combinations
SELECT TOP 1
	o.[OutboundDateStamp]
	, i.[InboundDateStamp]
	, o.[Price] + i.[Price] AS [Cheapest Possible Price]
FROM
	#outBoundList AS o
	JOIN #inBoundList AS i ON i.[InboundDateStamp] > o.[OutboundDateStamp]
ORDER BY
	o.[Price] + i.[Price] ASC


-- ALternative method b (produce Candidate Lists)
-- Produce Candidate Lists
DECLARE @bestOutbounds TABLE ([OutboundDateStamp] DATETIME PRIMARY KEY, [Price] SMALLMONEY)
DECLARE @bestInbounds TABLE ([InboundDateStamp] DATETIME PRIMARY KEY, [Price] SMALLMONEY)

-- Shorten the lists
INSERT @bestOutbounds ([OutboundDateStamp], [Price])
SELECT o.[OutboundDateStamp], o.[Price]
FROM #outBoundList AS o
WHERE NOT EXISTS (
			SELECT 1
			FROM #outBoundList AS o2
			WHERE o2.[OutboundDateStamp] < o.[OutboundDateStamp] AND o2.[Price] <= o.[Price]
			)

INSERT @bestInbounds ([InboundDateStamp], [Price])
SELECT i.[InboundDateStamp], i.[Price]
FROM #inBoundList AS i
WHERE NOT EXISTS (
			SELECT 1
			FROM #inBoundList AS i2
			WHERE i2.[InboundDateStamp] > i.[InboundDateStamp] AND i2.[Price] <= i.[Price]
			)

-- Then get the best price from the shortened lists
SELECT TOP 1
	o.[OutboundDateStamp]
	, i.[InboundDateStamp]
	, o.[Price] + i.[Price] AS [Cheapest Possible Price]
FROM
	@bestOutbounds AS o
	JOIN @bestInbounds AS i ON i.[InboundDateStamp] > o.[OutboundDateStamp]
ORDER BY
	o.[Price] + i.[Price] ASC

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

yosiasz
Master Smack Fu Yak Hacker

1635 Posts

Posted - 2011-08-23 : 19:03:02

what is the maximum trip days. I am sure you do not want a $1 trip that makes you stay one year? :)
are outbound and inbound user selectable?

If you don't have the passion to help people, you have no passion

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2011-08-24 : 04:11:48

My data sample is a little broad..... (and a little simplified)

In general these lists would model about a week's worth of quotes. Say a mix of train and plane or coach quotes. Each quote has a departure and arrival date and time. Obviously you can't leave on a trip back before you got there in the first place.

My question was more of a general algorithm one. What is the best way to find the *guaranteed* (or any one if there is a tie) lowest possible quote in this scenario.

My idea is to:
1) Scan each list (outbound and inbound). Remove any quote that has a better candidate quote in the list (for outbounds : if there is an earlier quote that is the same price or lower). (Inbound if there is a later quote that is the same price or lower).

Then combine those shortened lists to find the best possible quote.

This still causes 2 scans on the inbound and outbound lists. One scan on the reduced outbound list and a bunch of lookups. I'm sure someone has a better way.

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

Kristen
Test

22859 Posts

Posted - 2011-08-24 : 04:45:55

I wish the comparison sites would do that. I use one for cheapest-book-price, which tells me per book the best price, including carriage, but they have no ability to tell me what the best composite price is for 2+ books ...

yosiasz
Master Smack Fu Yak Hacker

1635 Posts

Posted - 2011-08-24 : 11:10:54

Charlie

It might not be the exact answer you want but I know Peso helped me with best ship date algorithm a sort of Ganttish algorithm

http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=124410&SearchTerms=ship,date

If you don't have the passion to help people, you have no passion

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources