February 8, 2010 at 1:24 pm
Hi all,
I am in the middle of a project for a bank and I face a challenge trying to resolve performance issues for a simple allocation problem. The aim is to optimally distribute the values of a number of collaterals to the corresponding credit facilities (loans). The connections between collaterals and facilities are many-to-many and the optimization algorithm has already prioritize both collaterals and facilities. Thus the problem can be expressed as follows: Given a list of collateral-facility pairs along with their properties (values and priorities), distribute the value of each collateral to its connected facilities so that (a) the collaterals of the higher priority cover primarily the related facilities of the higher priority and (b) each facility is covered by collaterals value up to its limit (no over-coverage allowed). A facility can receive collateral value from one or more collaterals, no matter from which, as long as they are connected and the (a) term stands.
My first thought was to treat the problem through the “quirky update” technique, but I couldn’t keep track of both collateral and facility remaining values simultaneously. I tried a cursor based solution, but the allocation process in my development environment (300k records instead of 1.5mio in the production) took 3.5h which is absolutely unacceptable. I tried to resolve the issue using recursive CTE but I discovered that I couldn’t use two recursive inner joins from within the CTE. Then I followed a hybrid path: I used a loop but, instead of treating one single row in it, I update as many rows as possible by using set approaches. I got correct results and a 16’ execution time in the development environment. Unfortunately, even much better than 3.5h, it’s still unacceptable (taking into account the 1.5 mio rows in the production environment).
The code of the above solution follows:
*********************************************************
PART 3
Initial allocation of the collaterals to the facilities.
This first run allocates collaterals up to the amount of
each facility (results in no overcollateralized facilities).
**********************************************************/
-- CollateralID + CollateralTypeID is the primary key for collaterals
-- ObligorID + AccountID + FacilityTypeID is the primary key for facilities
-- Create #Covers table
SELECT
CollateralID,
CollateralTypeID,
CollateralPriority,
CAST(0 AS FLOAT) AS CollateralCoverage,
CollateralValue,
-- The following field counts the appearances of a facility
-- in the #Covers table according to the rows prioritizarion
-- (see clustered index below)
ROW_NUMBER() OVER(
PARTITION BY AccountID, FacilityTypeID
ORDER BY CollateralPriority ) AS FacilityOrder,
ObligorID,
AccountID,
FacilityTypeID,
FacilityPriority,
CAST(0 AS DECIMAL (18,3)) AS CollateralUsed,
CAST(0 AS DECIMAL (18,3)) AS PreviousCovers,
FacilityValue,
CAST(0 AS DECIMAL (18,3)) AS CoveredAmount,
CAST(0 AS DECIMAL (18,3)) AS OverCoverage,
-- ScanOrder is used for testing purposes. Must be deleted in the final version
CAST(0 AS BIGINT) AS ScanOrder
INTO
#Covers
FROM
dbo.zzzCovers
-- The following line reduces performance
--CREATE INDEX IX_#Covers1 ON #Covers (CollateralID, CollateralTypeID)
-- CollateralCoverage is used as an index parameter
UPDATE
#Covers
SET
#Covers.CollateralCoverage = #Covers.CollateralValue /
CASE WHEN ColCoverage.TotalExposuresCovered > 0.1 THEN
ColCoverage.TotalExposuresCovered
ELSE
0.1
END
FROM
#Covers
INNER JOIN (
SELECT
CollateralID,
CollateralTypeID,
SUM (FacilityValue) AS TotalExposuresCovered
FROM
#Covers
GROUP BY
CollateralID,
CollateralTypeID ) ColCoverage
ON #Covers.CollateralID = ColCoverage.CollateralID
AND #Covers.CollateralTypeID = ColCoverage.CollateralTypeID
-- Create a clustered index to prioritize #Covers' rows
CREATE CLUSTERED INDEX IX_#Covers ON #Covers (
FacilityPriority,
FacilityOrder,
CollateralPriority,
CollateralCoverage,
CollateralID,
ObligorID,
AccountID)
-- The following inxexes impoved duration of execution by 55%
-- (unfortuna
CREATE INDEX IX_#Covers2 ON #Covers (
ObligorID,
AccountID,
FacilityTypeID)
CREATE INDEX IX_#Covers3 ON #Covers (
CollateralID,
CollateralTypeID)
DECLARE@MaxFacilityOrder DECIMAL(18,3),
@CurFacilityOrder DECIMAL(18,3),
@MaxFacilityPriority DECIMAL(18,3),
@CurFacilityPriority DECIMAL(18,3),
@AmountToCover DECIMAL(18,3),
@LastCollateralID NVARCHAR (50),
@CollateralUsed DECIMAL (18,3),
@CoveredAmount DECIMAL (18,3)
SELECT@MaxFacilityOrder = CASE WHEN MAX(FacilityOrder) < 1000 THEN MAX(FacilityOrder) ELSE 1000 END,
@MaxFacilityPriority = MAX(FacilityPriority),
@CurFacilityPriority = 0
FROM
#Covers
-- Since I can't update both running totals (CollateralUsed and CoveredAmount)
-- in the same pass, I resort to nested while loops
WHILE @CurFacilityPriority < @MaxFacilityPriority
BEGIN
SELECT@CurFacilityOrder = 0,
@CurFacilityPriority = @CurFacilityPriority + 1
WHILE @CurFacilityOrder < @MaxFacilityOrder
BEGIN
SELECT @CurFacilityOrder = @CurFacilityOrder + 1
-- Allocate collaterals to the facilities of the current order
SELECT@LastCollateralID = '',
@CollateralUsed = 0
-- The following "quirky updates" consume just 4% of the time
UPDATE
#Covers
SET
@AmountToCover =
CASE WHEN FacilityValue > PreviousCovers THEN
FacilityValue - PreviousCovers
ELSE
0
END,
@CoveredAmount =
CASE WHEN @LastCollateralID = CollateralID THEN
CASE WHEN CollateralValue - @CollateralUsed < @AmountToCover THEN
CollateralValue - @CollateralUsed
ELSE
@AmountToCover
END
ELSE
CASE WHEN CollateralValue - CollateralUsed < @AmountToCover THEN
CollateralValue - CollateralUsed
ELSE
@AmountToCover
END
END,
@CollateralUsed =
CASE WHEN @LastCollateralID = CollateralID THEN
@CollateralUsed + @CoveredAmount
ELSE
CollateralUsed + @CoveredAmount
END,
@LastCollateralID = CollateralID,
CoveredAmount = @CoveredAmount,
CollateralUsed = @CollateralUsed
FROM
#Covers
WHERE
FacilityOrder = @CurFacilityOrder
AND FacilityPriority = @CurFacilityPriority
OPTION (MAXDOP 1)
-- Check the order of update (always passed)
-- Removed in final version
/*
SELECT
@ScanOrder = MIN(s.ScanOrder)
FROM (
SELECT
CASE WHEN
(t1.CollateralID = t2.CollateralID
AND t1.CollateralUsed <> t2.CollateralUsed + t1.CoveredAmount) OR
(t1.CollateralID <> t2.CollateralID
AND t1.CollateralCoverage < t2.CollateralCoverage) OR
(t1.CollateralCoverage = t2.CollateralCoverage
AND t1.CollateralID < t2.CollateralID) OR
(t1.CollateralCoverage = t2.CollateralCoverage
AND t1.CollateralID = t2.CollateralID
AND t1.ObligorID < t2.ObligorID) OR
(t1.CollateralCoverage = t2.CollateralCoverage
AND t1.CollateralID = t2.CollateralID
AND t1.ObligorID = t2.ObligorID
AND t1.AccountID < t2.AccountID) THEN
t1.ScanOrder
ELSE
CAST(100000000 AS BIGINT)
END AS ScanOrder
FROM
#Covers t1
INNER JOIN #Covers t2
ON t1.FacilityOrder = t2.FacilityOrder
AND t1.FacilityPriority = t2.FacilityPriority
AND t1.ScanOrder = t2.ScanOrder + 1
) s
IF @ScanOrder = 100000000
PRINT 'Check failed. Scan Order =' +
RTRIM(CAST(@ScanOrder AS NVARCHAR(50))) +
'Facility Order = ' + RTRIM(CAST(@CurFacilityOrder AS NVARCHAR(50))) +
', Facility Priority =' + RTRIM(CAST(@CurFacilityPriority AS NVARCHAR(50)))
*/
-- The following two updates consume 95% of the time
IF @CurFacilityOrder < @MaxFacilityOrder
BEGIN
-- Update PreviousCovers of the unprocessed rows
UPDATE
#Covers
SET
PreviousCovers = PreviousCovers + s.TotalCoveredAmount
FROM
#Covers
INNER JOIN (
SELECT
t.ObligorID,
t.AccountID,
t.FacilityTypeID,
SUM(t.CoveredAmount) AS TotalCoveredAmount
FROM
#Covers t
WHERE
t.FacilityPriority = @CurFacilityPriority
AND t.FacilityOrder = @CurFacilityOrder
GROUP BY
t.ObligorID,
t.AccountID,
t.FacilityTypeID) s
ON s.ObligorID = #Covers.ObligorID
AND s.AccountID = #Covers.AccountID
AND s.FacilityTypeID = #Covers.FacilityTypeID
WHERE
#Covers.FacilityPriority > @CurFacilityPriority
OR (#Covers.FacilityPriority = @CurFacilityPriority
AND #Covers.FacilityOrder > @CurFacilityOrder)
-- Update CollateralUsed of the unprocessed rows
UPDATE
#Covers
SET
CollateralUsed = s.TotalCollateralUsed
FROM
#Covers
INNER JOIN (
SELECT
t.CollateralID,
t.CollateralTypeID,
MAX(t.CollateralUsed) AS TotalCollateralUsed
FROM
#Covers t
WHERE
t.FacilityPriority = @CurFacilityPriority
AND t.FacilityOrder = @CurFacilityOrder
GROUP BY
t.CollateralID,
t.CollateralTypeID) s
ON s.CollateralID = #Covers.CollateralID
AND s.CollateralTypeID = #Covers.CollateralTypeID
WHERE
#Covers.FacilityPriority > @CurFacilityPriority
OR (#Covers.FacilityPriority = @CurFacilityPriority
AND #Covers.FacilityOrder > @CurFacilityOrder)
END -- IF @CurFacilityOrder < @MaxFacilityOrder
END -- WHILE @CurFacilityOrder < @MaxFacilityOrder
END -- WHILE @CurFacilityPriority < @MaxFacilityPriority
I would greatly appreciate any help, suggestion or idea on reducing the execution time.
Thanks in advance
February 8, 2010 at 2:14 pm
Please post more detailed information (including execution plan) as described in the second link in my signature.
February 8, 2010 at 3:39 pm
Can you show what you are trying to do with the aid of a couple of sample tables and a result set?
All the better if the sample data is reasonably authentic in terms of rows on each side, and figures - while of course avoiding any reference to true names or companies. It would be awesome if you could set this up as a series of statements including a CREATE TABLE or two, and INSERT INTO; easily-consumable so folks can get cracking on your problem straight away.
Cheers
ChrisM@home
For better assistance in answering your questions, please read this[/url].
Hidden RBAR: Triangular Joins[/url] / The "Numbers" or "Tally" Table: What it is and how it replaces a loop[/url] Jeff Moden[/url]
February 9, 2010 at 8:27 am
Thank you both for your reply.
Lutz, I followed your advice and tried to get the execution plan, however, because of the two while loops which produce queries, the size of the plan soon became enormous and eventually the SQL Management Studio crashed. I repeted the process, but this time I interrupted the query after a few seconds, so I have a part of the plan (which I send attached).
Here is the code to create a sample table on which the script could run:
CREATE TABLE [dbo].[zzzCovers](
[CollateralID] [nvarchar](50) NOT NULL,
[CollateralTypeID] [varchar](4) NOT NULL,
[CollateralPriority] [smallint] NULL,
[CollateralValue] [decimal](18, 3) NULL,
[ObligorID] [nvarchar](50) NOT NULL,
[AccountID] [nvarchar](50) NOT NULL,
[FacilityTypeID] [smallint] NOT NULL,
[FacilityPriority] [smallint] NULL,
[FacilityValue] [decimal](18, 3) NULL
) ON [PRIMARY]
GO
SET ANSI_PADDING OFF
GO
INSERT [dbo].[zzzCovers] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue]) VALUES (N'1', N'1', 1, CAST(100000.000 AS Decimal(18, 3)), N'1', N'101', 1, 1, CAST(190000.000 AS Decimal(18, 3)))
INSERT [dbo].[zzzCovers] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue]) VALUES (N'1', N'1', 1, CAST(100000.000 AS Decimal(18, 3)), N'1', N'102', 1, 1, CAST(130000.000 AS Decimal(18, 3)))
INSERT [dbo].[zzzCovers] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue]) VALUES (N'2', N'1', 1, CAST(10000.000 AS Decimal(18, 3)), N'2', N'201', 1, 1, CAST(150000.000 AS Decimal(18, 3)))
INSERT [dbo].[zzzCovers] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue]) VALUES (N'2', N'1', 1, CAST(10000.000 AS Decimal(18, 3)), N'3', N'301', 1, 1, CAST(30000.000 AS Decimal(18, 3)))
INSERT [dbo].[zzzCovers] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue]) VALUES (N'3', N'1', 1, CAST(20000.000 AS Decimal(18, 3)), N'1', N'101', 1, 1, CAST(190000.000 AS Decimal(18, 3)))
INSERT [dbo].[zzzCovers] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue]) VALUES (N'3', N'1', 1, CAST(20000.000 AS Decimal(18, 3)), N'1', N'102', 1, 1, CAST(130000.000 AS Decimal(18, 3)))
INSERT [dbo].[zzzCovers] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue]) VALUES (N'4', N'1', 1, CAST(80000.000 AS Decimal(18, 3)), N'3', N'301', 1, 1, CAST(30000.000 AS Decimal(18, 3)))
INSERT [dbo].[zzzCovers] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue]) VALUES (N'5', N'1', 1, CAST(110000.000 AS Decimal(18, 3)), N'1', N'102', 2, 2, CAST(50000.000 AS Decimal(18, 3)))
INSERT [dbo].[zzzCovers] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue]) VALUES (N'6', N'1', 2, CAST(30000.000 AS Decimal(18, 3)), N'1', N'101', 1, 1, CAST(190000.000 AS Decimal(18, 3)))
And here are the results:
--1234567891011121314
-------------------------------------------------------------------------------------------------------------------------------------------------------
--2110,055510000.000122011110000.0000.000150000.00010000.000
--2110,055510000.000133011110000.0000.00030000.0000.000
--3110,062520000.000111021120000.0000.000130000.00020000.000
--1110,3125100000.0001110111100000.0000.000190000.000100000.000
--3110,062520000.000211011120000.000100000.000190000.0000.000
--1110,3125100000.0002110211100000.00020000.000130000.0000.000
--4112,666680000.000233011130000.0000.00030000.00030000.000
--6120,157830000.000311011130000.000100000.000190000.00030000.000
--5112,2000110000.000111022250000.0000.00050000.00050000.000
-- Columns:
-----------
--1CollateralID
--2CollateralTypeID
--3CollateralPriority
--4CollateralCoverage
--5CollateralValue
--6FacilityOrder
--7ObligorID
--8AccountID
--9FacilityTypeID
--10FacilityPriority
--11CollateralUsed
--12PreviousCovers
--13FacilityValue
--14CoveredAmount
Thank you again,
Elias
February 9, 2010 at 2:29 pm
Hi Elias
This job will be quite a bit easier if you could split table [dbo].[zzzCovers] into three, as follows:
Collaterial information, which should have unique CollateralId.
Facility information, which should have unique FacilityID.
You also need a many-to-many link table - if [dbo].[zzzCovers] models this accurately then great, as it also has the prioritisation data.
You could model all three tables by extracting from [dbo].[zzzCovers] into #temp tables.
Try and create these tables / queries with the minimum information necessary i.e. remove columns which are not directly related to the issue.
You may well resolve the problem yourself by doing this, if not, then post back.
Cheers
ChrisM
For better assistance in answering your questions, please read this[/url].
Hidden RBAR: Triangular Joins[/url] / The "Numbers" or "Tally" Table: What it is and how it replaces a loop[/url] Jeff Moden[/url]
February 9, 2010 at 11:12 pm
Hi Chris,
Actually zzzCovers table is not a real table in the database, I used it just to describe the issue isolated from the rest of the process. Let me explain the initial challenge:
Consider the three following tables:
1. Table Collaterals:
CollateralID (Primary key - PK),
CollateralTypeID (PK),
CollateralPriority (Gets numbers from 1 to 10, where 1 = higher priority)
CollateralValue
2. Table Facilities:
ObligorID (PK),
Account (PK),
FacilityTypeID (PK),
FacilityPriority (Gets numbers from 1 to 4, where 1 = higher priority),
FacilityValue
3. Table Collaterals_Facilities_Connections:
CollateralID (PK),
CollateralTypeID (PK),
ObligorID (PK),
Account (PK),
FacilityTypeID (PK),
MaxCoverageAmount (It is the maximum collateral value that can be allocated to the facility)
Each callateral can be connected to multiple facilities and each facility can be connected to multiple collaterals.
Given the above, the objective is to assign values from the collaterals to each connected facility so that:
1. The sum of collateral values assigned to a facility does not exceed the facility value,
2. The sum of values of a collateral assigned to facilities does not exceed the collateral value,
2. Each assigned collateral value must not exceed the MaxCoverageAmount of the relevant connection,
3. The higher priority facilities should be covered selectively by the higher possible priority collaterals.
My solution just builds a temporary table (#Covers) based on the table Collaterals_Facilities_Connections so that the "quirky update" can be used, since the initial table has many more fields and rows; besides it is partitioned.
Thank you anyway for your time,
Elias
February 9, 2010 at 11:33 pm
pink_panther (2/9/2010)
Hi Chris,Actually zzzCovers table is not a real table in the database, I used it just to describe the issue isolated from the rest of the process. Let me explain the initial challenge:
Consider the three following tables:
1. Table Collaterals:
CollateralID (Primary key - PK),
CollateralTypeID (PK),
CollateralPriority (Gets numbers from 1 to 10, where 1 = higher priority)
CollateralValue
2. Table Facilities:
ObligorID (PK),
Account (PK),
FacilityTypeID (PK),
FacilityPriority (Gets numbers from 1 to 4, where 1 = higher priority),
FacilityValue
3. Table Collaterals_Facilities_Connections:
CollateralID (PK),
CollateralTypeID (PK),
ObligorID (PK),
Account (PK),
FacilityTypeID (PK),
MaxCoverageAmount (It is the maximum collateral value that can be allocated to the facility)
Each callateral can be connected to multiple facilities and each facility can be connected to multiple collaterals.
Given the above, the objective is to assign values from the collaterals to each connected facility so that:
1. The sum of collateral values assigned to a facility does not exceed the facility value,
2. The sum of values of a collateral assigned to facilities does not exceed the collateral value,
2. Each assigned collateral value must not exceed the MaxCoverageAmount of the relevant connection,
3. The higher priority facilities should be covered selectively by the higher possible priority collaterals.
My solution just builds a temporary table (#Covers) based on the table Collaterals_Facilities_Connections so that the "quirky update" can be used, since the initial table has many more fields and rows; besides it is partitioned.
Thank you anyway for your time,
Elias
Here is what would help. Based on the above, create the minimally needed DDL for the three tables. Create a small set of sample data for the three tables (insert into statements), and then develop the expected results (you could create and load a table with the expected results) based on the sample data. You don't need a lot of data, just enough to demonstrate the problem domain and any special cases (which you should clearly identify).
February 10, 2010 at 1:52 am
Lynn I apologize for not being specific in my previous posts. Below is a script for creating the above three tables along with some data. I also include one more table (ExpectedResults) with the results taken from my approach. I remind that I am happy with those results but not with the performance of the query. It must be noted also that the solution (the results) is not unique and any other one is acceptable as far as it meets the requirements.
/****** Object: Table [dbo].[Facilities] Script Date: 02/10/2010 10:26:50 ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE TABLE [dbo].[Facilities](
[ObligorID] [nvarchar](50) NOT NULL,
[AccountID] [nvarchar](50) NOT NULL,
[FacilityTypeID] [smallint] NOT NULL,
[FacilityPriority] [smallint] NULL,
[FacilityValue] [decimal](18, 3) NULL,
CONSTRAINT [PK_Facilities] PRIMARY KEY CLUSTERED
(
[ObligorID] ASC,
[AccountID] ASC,
[FacilityTypeID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]
GO
INSERT [dbo].[Facilities] ([ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue]) VALUES (N'1', N'102', 1, 1, CAST(130000.000 AS Decimal(18, 3)))
INSERT [dbo].[Facilities] ([ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue]) VALUES (N'2', N'201', 1, 1, CAST(150000.000 AS Decimal(18, 3)))
INSERT [dbo].[Facilities] ([ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue]) VALUES (N'3', N'301', 1, 1, CAST(30000.000 AS Decimal(18, 3)))
INSERT [dbo].[Facilities] ([ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue]) VALUES (N'4', N'401', 1, 2, CAST(150000.000 AS Decimal(18, 3)))
INSERT [dbo].[Facilities] ([ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue]) VALUES (N'4', N'401', 2, 3, CAST(50000.000 AS Decimal(18, 3)))
/****** Object: Table [dbo].[ExpectedResults] Script Date: 02/10/2010 10:26:50 ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE TABLE [dbo].[ExpectedResults](
[CollateralID] [nvarchar](50) NOT NULL,
[CollateralTypeID] [nvarchar](4) NOT NULL,
[CollateralPriority] [smallint] NULL,
[CollateralValue] [decimal](18, 3) NULL,
[ObligorID] [nvarchar](50) NOT NULL,
[AccountID] [nvarchar](50) NOT NULL,
[FacilityTypeID] [smallint] NOT NULL,
[FacilityPriority] [smallint] NULL,
[FacilityValue] [decimal](18, 3) NULL,
[CoveredAmount] [decimal](18, 3) NULL,
[FacilityOrder] [bigint] NULL,
[CollateralCoverage] [float] NULL,
[CollateralUsed] [decimal](18, 3) NULL,
[PreviousCovers] [decimal](18, 3) NULL
) ON [PRIMARY]
GO
INSERT [dbo].[ExpectedResults] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue], [CoveredAmount], [FacilityOrder], [CollateralCoverage], [CollateralUsed], [PreviousCovers]) VALUES (N'2', N'1', 1, CAST(10000.000 AS Decimal(18, 3)), N'2', N'201', 1, 1, CAST(150000.000 AS Decimal(18, 3)), CAST(10000.000 AS Decimal(18, 3)), 1, 0.055555555555555552, CAST(10000.000 AS Decimal(18, 3)), CAST(0.000 AS Decimal(18, 3)))
INSERT [dbo].[ExpectedResults] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue], [CoveredAmount], [FacilityOrder], [CollateralCoverage], [CollateralUsed], [PreviousCovers]) VALUES (N'2', N'1', 1, CAST(10000.000 AS Decimal(18, 3)), N'3', N'301', 1, 1, CAST(30000.000 AS Decimal(18, 3)), CAST(0.000 AS Decimal(18, 3)), 1, 0.055555555555555552, CAST(10000.000 AS Decimal(18, 3)), CAST(0.000 AS Decimal(18, 3)))
INSERT [dbo].[ExpectedResults] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue], [CoveredAmount], [FacilityOrder], [CollateralCoverage], [CollateralUsed], [PreviousCovers]) VALUES (N'3', N'1', 1, CAST(20000.000 AS Decimal(18, 3)), N'1', N'102', 1, 1, CAST(130000.000 AS Decimal(18, 3)), CAST(20000.000 AS Decimal(18, 3)), 1, 0.15384615384615386, CAST(20000.000 AS Decimal(18, 3)), CAST(0.000 AS Decimal(18, 3)))
INSERT [dbo].[ExpectedResults] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue], [CoveredAmount], [FacilityOrder], [CollateralCoverage], [CollateralUsed], [PreviousCovers]) VALUES (N'4', N'1', 1, CAST(80000.000 AS Decimal(18, 3)), N'3', N'301', 1, 1, CAST(30000.000 AS Decimal(18, 3)), CAST(30000.000 AS Decimal(18, 3)), 2, 0.34782608695652178, CAST(30000.000 AS Decimal(18, 3)), CAST(0.000 AS Decimal(18, 3)))
INSERT [dbo].[ExpectedResults] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue], [CoveredAmount], [FacilityOrder], [CollateralCoverage], [CollateralUsed], [PreviousCovers]) VALUES (N'1', N'1', 1, CAST(100000.000 AS Decimal(18, 3)), N'1', N'102', 1, 1, CAST(130000.000 AS Decimal(18, 3)), CAST(100000.000 AS Decimal(18, 3)), 2, 0.76923076923076916, CAST(100000.000 AS Decimal(18, 3)), CAST(20000.000 AS Decimal(18, 3)))
INSERT [dbo].[ExpectedResults] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue], [CoveredAmount], [FacilityOrder], [CollateralCoverage], [CollateralUsed], [PreviousCovers]) VALUES (N'7', N'2', 3, CAST(60000.000 AS Decimal(18, 3)), N'2', N'201', 1, 1, CAST(150000.000 AS Decimal(18, 3)), CAST(60000.000 AS Decimal(18, 3)), 2, 0.4, CAST(60000.000 AS Decimal(18, 3)), CAST(10000.000 AS Decimal(18, 3)))
INSERT [dbo].[ExpectedResults] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue], [CoveredAmount], [FacilityOrder], [CollateralCoverage], [CollateralUsed], [PreviousCovers]) VALUES (N'4', N'1', 1, CAST(80000.000 AS Decimal(18, 3)), N'4', N'401', 1, 2, CAST(150000.000 AS Decimal(18, 3)), CAST(80000.000 AS Decimal(18, 3)), 1, 0.34782608695652178, CAST(80000.000 AS Decimal(18, 3)), CAST(0.000 AS Decimal(18, 3)))
INSERT [dbo].[ExpectedResults] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue], [CoveredAmount], [FacilityOrder], [CollateralCoverage], [CollateralUsed], [PreviousCovers]) VALUES (N'5', N'1', 1, CAST(110000.000 AS Decimal(18, 3)), N'4', N'401', 1, 2, CAST(150000.000 AS Decimal(18, 3)), CAST(70000.000 AS Decimal(18, 3)), 2, 0.73333333333333339, CAST(70000.000 AS Decimal(18, 3)), CAST(80000.000 AS Decimal(18, 3)))
INSERT [dbo].[ExpectedResults] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue], [ObligorID], [AccountID], [FacilityTypeID], [FacilityPriority], [FacilityValue], [CoveredAmount], [FacilityOrder], [CollateralCoverage], [CollateralUsed], [PreviousCovers]) VALUES (N'4', N'1', 1, CAST(80000.000 AS Decimal(18, 3)), N'4', N'401', 2, 3, CAST(50000.000 AS Decimal(18, 3)), CAST(0.000 AS Decimal(18, 3)), 1, 0.34782608695652178, CAST(80000.000 AS Decimal(18, 3)), CAST(0.000 AS Decimal(18, 3)))
/****** Object: Table [dbo].[Connections] Script Date: 02/10/2010 10:26:50 ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE TABLE [dbo].[Connections](
[CollateralID] [nvarchar](50) NOT NULL,
[CollateralTypeID] [nvarchar](4) NOT NULL,
[ObligorID] [nvarchar](50) NOT NULL,
[AccountID] [nvarchar](50) NOT NULL,
[FacilityTypeID] [smallint] NOT NULL,
CONSTRAINT [PK_MaxCoverageAmount] PRIMARY KEY CLUSTERED
(
[CollateralID] ASC,
[CollateralTypeID] ASC,
[ObligorID] ASC,
[AccountID] ASC,
[FacilityTypeID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]
GO
INSERT [dbo].[Connections] ([CollateralID], [CollateralTypeID], [ObligorID], [AccountID], [FacilityTypeID]) VALUES (N'1', N'1', N'1', N'101', 1)
INSERT [dbo].[Connections] ([CollateralID], [CollateralTypeID], [ObligorID], [AccountID], [FacilityTypeID]) VALUES (N'1', N'1', N'1', N'102', 1)
INSERT [dbo].[Connections] ([CollateralID], [CollateralTypeID], [ObligorID], [AccountID], [FacilityTypeID]) VALUES (N'2', N'1', N'2', N'201', 1)
INSERT [dbo].[Connections] ([CollateralID], [CollateralTypeID], [ObligorID], [AccountID], [FacilityTypeID]) VALUES (N'2', N'1', N'3', N'301', 1)
INSERT [dbo].[Connections] ([CollateralID], [CollateralTypeID], [ObligorID], [AccountID], [FacilityTypeID]) VALUES (N'3', N'1', N'1', N'101', 1)
INSERT [dbo].[Connections] ([CollateralID], [CollateralTypeID], [ObligorID], [AccountID], [FacilityTypeID]) VALUES (N'3', N'1', N'1', N'102', 1)
INSERT [dbo].[Connections] ([CollateralID], [CollateralTypeID], [ObligorID], [AccountID], [FacilityTypeID]) VALUES (N'4', N'1', N'3', N'301', 1)
INSERT [dbo].[Connections] ([CollateralID], [CollateralTypeID], [ObligorID], [AccountID], [FacilityTypeID]) VALUES (N'4', N'1', N'4', N'401', 1)
INSERT [dbo].[Connections] ([CollateralID], [CollateralTypeID], [ObligorID], [AccountID], [FacilityTypeID]) VALUES (N'4', N'1', N'4', N'401', 2)
INSERT [dbo].[Connections] ([CollateralID], [CollateralTypeID], [ObligorID], [AccountID], [FacilityTypeID]) VALUES (N'5', N'1', N'1', N'102', 2)
INSERT [dbo].[Connections] ([CollateralID], [CollateralTypeID], [ObligorID], [AccountID], [FacilityTypeID]) VALUES (N'5', N'1', N'4', N'401', 1)
INSERT [dbo].[Connections] ([CollateralID], [CollateralTypeID], [ObligorID], [AccountID], [FacilityTypeID]) VALUES (N'6', N'1', N'1', N'101', 1)
INSERT [dbo].[Connections] ([CollateralID], [CollateralTypeID], [ObligorID], [AccountID], [FacilityTypeID]) VALUES (N'7', N'2', N'2', N'201', 1)
/****** Object: Table [dbo].[Collaterals] Script Date: 02/10/2010 10:26:50 ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE TABLE [dbo].[Collaterals](
[CollateralID] [nvarchar](50) NOT NULL,
[CollateralTypeID] [nvarchar](4) NOT NULL,
[CollateralPriority] [smallint] NULL,
[CollateralValue] [decimal](18, 3) NULL,
CONSTRAINT [PK_Collaterals] PRIMARY KEY CLUSTERED
(
[CollateralID] ASC,
[CollateralTypeID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]
GO
INSERT [dbo].[Collaterals] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue]) VALUES (N'1', N'1', 1, CAST(100000.000 AS Decimal(18, 3)))
INSERT [dbo].[Collaterals] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue]) VALUES (N'2', N'1', 1, CAST(10000.000 AS Decimal(18, 3)))
INSERT [dbo].[Collaterals] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue]) VALUES (N'3', N'1', 1, CAST(20000.000 AS Decimal(18, 3)))
INSERT [dbo].[Collaterals] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue]) VALUES (N'4', N'1', 1, CAST(80000.000 AS Decimal(18, 3)))
INSERT [dbo].[Collaterals] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue]) VALUES (N'5', N'1', 1, CAST(110000.000 AS Decimal(18, 3)))
INSERT [dbo].[Collaterals] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue]) VALUES (N'6', N'1', 2, CAST(30000.000 AS Decimal(18, 3)))
INSERT [dbo].[Collaterals] ([CollateralID], [CollateralTypeID], [CollateralPriority], [CollateralValue]) VALUES (N'7', N'2', 3, CAST(60000.000 AS Decimal(18, 3)))
Finally, I enclose the uptated script that was used to return the above results:
IF OBJECT_ID('tempdb..#Covers') IS NOT NULL DROP TABLE #Covers
-- Create #Covers table
SELECT
dbo.Collaterals.CollateralID,
dbo.Collaterals.CollateralTypeID,
dbo.Collaterals.CollateralPriority,
dbo.Collaterals.CollateralValue,
dbo.Facilities.ObligorID,
dbo.Facilities.AccountID,
dbo.Facilities.FacilityTypeID,
dbo.Facilities.FacilityPriority,
dbo.Facilities.FacilityValue,
CAST(0 AS DECIMAL (18,3)) AS CoveredAmount, -- The field stores the results
-- The following fields are used for CoveredAmount calculation
ROW_NUMBER() OVER(
PARTITION BY
dbo.Facilities.ObligorID,
dbo.Facilities.AccountID,
dbo.Facilities.FacilityTypeID
ORDER BY dbo.Collaterals.CollateralPriority ) AS FacilityOrder,
CAST(0 AS FLOAT) AS CollateralCoverage,
CAST(0 AS DECIMAL (18,3)) AS CollateralUsed,
CAST(0 AS DECIMAL (18,3)) AS PreviousCovers
INTO
#Covers
FROM
dbo.Connections
INNER JOIN dbo.Collaterals
ON dbo.Connections.CollateralID = dbo.Collaterals.CollateralID
AND dbo.Connections.CollateralTypeID = dbo.Collaterals.CollateralTypeID
INNER JOIN dbo.Facilities
ON dbo.Connections.ObligorID = dbo.Facilities.ObligorID
AND dbo.Connections.AccountID = dbo.Facilities.AccountID
AND dbo.Connections.FacilityTypeID = dbo.Facilities.FacilityTypeID
-- CollateralCoverage is used for ensuring that the collaterals which
-- do not cover the associated facilities are fully exploited (take
-- higher percentage. Not a crucial assumption but sometimes leads to
-- better results.
UPDATE
#Covers
SET
#Covers.CollateralCoverage = #Covers.CollateralValue /
CASE WHEN ColCoverage.TotalExposuresCovered > 0.1 THEN
ColCoverage.TotalExposuresCovered
ELSE
0.1
END
FROM
#Covers
INNER JOIN (
SELECT
CollateralID,
CollateralTypeID,
SUM (FacilityValue) AS TotalExposuresCovered
FROM
#Covers
GROUP BY
CollateralID,
CollateralTypeID ) ColCoverage
ON #Covers.CollateralID = ColCoverage.CollateralID
AND #Covers.CollateralTypeID = ColCoverage.CollateralTypeID
-- Create a clustered index to prioritize #Covers' rows
CREATE CLUSTERED INDEX IX_#Covers ON #Covers (
FacilityPriority,
FacilityOrder,-- The field just helps the applied technique.
CollateralPriority,
CollateralCoverage,
CollateralID,
ObligorID,
AccountID)
-- The following inxexes impoved duration of execution by 55%
CREATE INDEX IX_#Covers2 ON #Covers (
ObligorID,
AccountID,
FacilityTypeID)
CREATE INDEX IX_#Covers3 ON #Covers (
CollateralID,
CollateralTypeID)
DECLARE @MaxFacilityOrder DECIMAL(18,3),
@CurFacilityOrder DECIMAL(18,3),
@MaxFacilityPriority DECIMAL(18,3),
@CurFacilityPriority DECIMAL(18,3),
@AmountToCover DECIMAL(18,3),
@LastCollateralID NVARCHAR (50),
@CollateralUsed DECIMAL (18,3),
@CoveredAmount DECIMAL (18,3)
SELECT @MaxFacilityOrder = CASE WHEN MAX(FacilityOrder) < 1000 THEN MAX(FacilityOrder) ELSE 1000 END,
@MaxFacilityPriority = MAX(FacilityPriority),
@CurFacilityPriority = 0
FROM
#Covers
-- Since I can't update both running totals (CollateralUsed and CoveredAmount)
-- in the same pass, I resort to nested while loops
WHILE @CurFacilityPriority < @MaxFacilityPriority
BEGIN
SELECT @CurFacilityOrder = 0,
@CurFacilityPriority = @CurFacilityPriority + 1
WHILE @CurFacilityOrder < @MaxFacilityOrder
BEGIN
SELECT @CurFacilityOrder = @CurFacilityOrder + 1
-- Allocate collaterals to the facilities of the current order
SELECT @LastCollateralID = '',
@CollateralUsed = 0
-- The following "quirky updates" consume just 4% of the time
-- It has passed all the tests for right ordering the updates
UPDATE
#Covers
SET
@AmountToCover =
CASE WHEN FacilityValue > PreviousCovers THEN
FacilityValue - PreviousCovers
ELSE
0
END,
@CoveredAmount =
CASE WHEN @LastCollateralID = CollateralID THEN
CASE WHEN CollateralValue - @CollateralUsed < @AmountToCover THEN
CollateralValue - @CollateralUsed
ELSE
@AmountToCover
END
ELSE
CASE WHEN CollateralValue - CollateralUsed < @AmountToCover THEN
CollateralValue - CollateralUsed
ELSE
@AmountToCover
END
END,
@CollateralUsed =
CASE WHEN @LastCollateralID = CollateralID THEN
@CollateralUsed + @CoveredAmount
ELSE
CollateralUsed + @CoveredAmount
END,
@LastCollateralID = CollateralID,
CoveredAmount = @CoveredAmount,
CollateralUsed = @CollateralUsed
FROM
#Covers
WHERE
FacilityOrder = @CurFacilityOrder
AND FacilityPriority = @CurFacilityPriority
OPTION (MAXDOP 1)
-- The following two updates consume 95% of the time
IF @CurFacilityOrder < @MaxFacilityOrder
BEGIN
-- Update PreviousCovers of the unprocessed rows
UPDATE
#Covers
SET
PreviousCovers = PreviousCovers + s.TotalCoveredAmount
FROM
#Covers
INNER JOIN (
SELECT
t.ObligorID,
t.AccountID,
t.FacilityTypeID,
SUM(t.CoveredAmount) AS TotalCoveredAmount
FROM
#Covers t
WHERE
t.FacilityPriority = @CurFacilityPriority
AND t.FacilityOrder = @CurFacilityOrder
GROUP BY
t.ObligorID,
t.AccountID,
t.FacilityTypeID) s
ON s.ObligorID = #Covers.ObligorID
AND s.AccountID = #Covers.AccountID
AND s.FacilityTypeID = #Covers.FacilityTypeID
WHERE
#Covers.FacilityPriority > @CurFacilityPriority
OR (#Covers.FacilityPriority = @CurFacilityPriority
AND #Covers.FacilityOrder > @CurFacilityOrder)
-- Update CollateralUsed of the unprocessed rows
UPDATE
#Covers
SET
CollateralUsed = s.TotalCollateralUsed
FROM
#Covers
INNER JOIN (
SELECT
t.CollateralID,
t.CollateralTypeID,
MAX(t.CollateralUsed) AS TotalCollateralUsed
FROM
#Covers t
WHERE
t.FacilityPriority = @CurFacilityPriority
AND t.FacilityOrder = @CurFacilityOrder
GROUP BY
t.CollateralID,
t.CollateralTypeID) s
ON s.CollateralID = #Covers.CollateralID
AND s.CollateralTypeID = #Covers.CollateralTypeID
WHERE
#Covers.FacilityPriority > @CurFacilityPriority
OR (#Covers.FacilityPriority = @CurFacilityPriority
AND #Covers.FacilityOrder > @CurFacilityOrder)
END -- IF @CurFacilityOrder < @MaxFacilityOrder
END -- WHILE @CurFacilityOrder < @MaxFacilityOrder
END -- WHILE @CurFacilityPriority < @MaxFacilityPriority
SELECT * FROM #Covers
ORDER BY
FacilityPriority,
FacilityOrder,
CollateralPriority,
CollateralCoverage,
CollateralID,
ObligorID,
AccountID
DROP TABLE #Covers
Thanks,
Elias
February 11, 2010 at 1:35 pm
Hi Elias
The code I sent you yesterday is primarily an attempt to identify facilities by means of a single surrogate key, and introduce a parent for common facility/collateral pairs, with one set of data across three 'owners'.
For the first part, you could answer this yourself by posting a query which would return distinct facilities, using ROW_NUMBER over (PARTITION BY... ORDER BY ...).
The second question is the one which really has me stumped, because you've introduced the column 'Obligor', which would seem like a good candidate as the owner of a set of collaterals and of facilities, and yet there's no structure to the sample collaterals and facilities to support this - indeed, the table of collaterals and facilities could all belong to a single entity. Whatever algorithm you choose to use will require awareness of the owner of facilities and collaterals, preferably by means of a single surrogate key. The boundary changes are very significant and will require specific coding.
I note that when you run some of my code against your table, it takes a considerable amount of time to run - this in itself tells me that you have much more data to provide as cues to resolving the problem. The code I sent to you exposes 3 sets of data i.e. sets of collateral / facility with three different owners. May I suggest that you post a set of sample data which is similarly organised?
I believe the problem as you have described it in words is trivial and that the difficulties faced by myself and others is in the choice of sample data values, and to some extent the noise of superfluous data. Please don't feel in any way awkward about this, it's an impossibly easy thing to do when you are surrounded by a tricky problem.
So, here's what I'd suggest:
expand your sample data so you have say three sets of collateral / facility pairs with owners. If you've already done this, then it requires clarification.
identify your facilities to us using a surrogate key using code if possible. We need to know which columns identify a facility.
Your first choice of using the running totals update would almost certainly work with a minor change, saving off the ID's of consumed collateral. The advantages of using a hierarchical CTE over the quirky update to do a running totals query are that you don't have to write out a table, then index it, then update it, or worry about parallelism. On the other hand, there's a finite recursion limit with hierarchical CTE's. See MAXRECURSION in BOL.
Let's try both, see which works best for you 🙂
Cheers
ChrisM@home
For better assistance in answering your questions, please read this[/url].
Hidden RBAR: Triangular Joins[/url] / The "Numbers" or "Tally" Table: What it is and how it replaces a loop[/url] Jeff Moden[/url]
February 11, 2010 at 2:11 pm
Hi Chris,
Thank you very much once more. Indeed the problem seems trivial but I am stuck with it more than a month now. I don’t believe that a broader sample has anything more to offer in the issue understanding. There are not hidden clues; we have just some collateral values to distribute to connected facilities, taking into account the relevant priorities for optimization reasons.
Unfortunately there is not always a common owner for facilities and collaterals; of course the connections are known (see my last reply). The ObligorID is not a key for collaterals (a guarantor with a different ObligorID may be the collateral's owner as well). Moreover, a facility may be covered by several collaterals of different owners each. Therefore, I cannot send any data based on common owners; it would be a misleading sample.
Concerning using hierarchical CTE or quirky update, there is no problem with me as far as it performs well.
Best regards,
Elias
February 11, 2010 at 2:30 pm
It's more difficult without fixed boundaries but I don't think it's unsurmountable. Thanks for the extra info Elias.
For better assistance in answering your questions, please read this[/url].
Hidden RBAR: Triangular Joins[/url] / The "Numbers" or "Tally" Table: What it is and how it replaces a loop[/url] Jeff Moden[/url]
February 11, 2010 at 2:41 pm
I may be confused on how things are applied. Could you take one set of records and show how the business rules work to generate one of the sample records?
I may have been looking at things backwards when i first reviewed the data.
February 11, 2010 at 3:07 pm
Lynn Pettis (2/11/2010)
I may be confused on how things are applied. Could you take one set of records and show how the business rules work to generate one of the sample records?I may have been looking at things backwards when i first reviewed the data.
Hi Lynn
Generation of the sample source records is something I was intending to ask Elias after a first-pass solution had been provided. No mention has been made of the time/effort involved, or whether or not the algorith could be applied with the solution as a single step rather than two.
I'm guessing you'll have this step cracked before tomorrow, it's 10pm here and I'm done. Reckon a quirky update may be the way to go though, given the rowcount and the value of MAXRECURSION.
@Elias - you've yet to answer a fundamental question - which columns uniquely identify a facility.
Cheers & best wishes
ChrisM@home
For better assistance in answering your questions, please read this[/url].
Hidden RBAR: Triangular Joins[/url] / The "Numbers" or "Tally" Table: What it is and how it replaces a loop[/url] Jeff Moden[/url]
February 11, 2010 at 3:48 pm
lobbymuncher (2/11/2010)
Lynn Pettis (2/11/2010)
I may be confused on how things are applied. Could you take one set of records and show how the business rules work to generate one of the sample records?I may have been looking at things backwards when i first reviewed the data.
Hi Lynn
Generation of the sample source records is something I was intending to ask Elias after a first-pass solution had been provided. No mention has been made of the time/effort involved, or whether or not the algorith could be applied with the solution as a single step rather than two.
I'm guessing you'll have this step cracked before tomorrow, it's 10pm here and I'm done. Reckon a quirky update may be the way to go though, given the rowcount and the value of MAXRECURSION.
@Elias - you've yet to answer a fundamental question - which columns uniquely identify a facility.
Cheers & best wishes
ChrisM@home
Don't bet on it. Too many things going on at home this evening. I may not get a chance to work on it. But I do need to be sure i understand the process, and I seem to be a bit confused as to what covers what here.
February 12, 2010 at 2:32 am
Hi,
Columns uniquely identifying collaterals are: CollateralID + CollateralType
Columns uniquely identifying facilities are: ObligorID, AccountID, FacilityTypeID
@chris-2: I have included the above in my posts #862954 (see PK columns) and #863007 (in the tables definitions).
Here is the definition of the whole problem and my thoughts about its solution:
I start with the description of the sent sample which can be used as a reference dataset:
The collaterals available in the database are the followings (columns uniquely identifying collaterals are CollateralID + CollateralType):
CollateralIDCollateralTypeIDCollateralPriorityCollateralValue
111100000
21110000
31120000
41180000
511110000
61230000
72360000
The facilities, on the other hand, and their connections with the above collaterals are:
ObligorIDAccountIDFacilityTypeIDFacilityPriorityFacilityAmountCovered by(CollateralID, CollateralTypeID)
110211130000(1,1), (3,1), (5,1)
220111150000(2,1), (7,2)
33011130000(2,1), (4,1)
440112150000(4,1), (5,1)
44012350000(4,1)
Given the above, the request is to distribute the value of each one of the collaterals to the facilities covered by it so that:
(a)The covers assigned to each facility does not exceeds its facility amount (each facility can be totally or partially covered by one or more of the associated collaterals),
(b)The value of the collaterals of higher priority (1 is the higher) covers first the associated facilities of higher priorities (optimization for the collateral allocation) and
(c)The maximum possible use of collateral values is achieved.
The following description concerns my approach for solving the problem. However, maybe this particular approach is per se the reason for the performance issues. Anyway my way of thinking, from the start of treating the challenge till now, can be summarized as follows:
(a)In attempt to use the “quirky update” technique, which I think is the faster one for treating running totals, I built a temporary table which connects collaterals and connected facilities and I sorted it by: Collateral Priority, Collateral coverage, Collateral unique ID (CollateralID + CollateralTypeID), Facility priority and facility unique ID. CollateralCoverage is the maximum percentage of the collateral value that can be used by facilities (ie. if a collateral has a value of 100 and the total Facility amount of all connected facilities is 200 then the CollateralCoverage is 50%). Using this figure has been empirically proved that leads to some better collateral exploitation in portfolio basis, but it is not crucial for the solution.
(b)I added some columns to the temporary table to store the intermediate and the total results. More specifically those columns are:
CollateralUsed to store the running total of the used value of the current collateral (I remind that the sort order retains all the rows with a collateral together). Using this field is not necessary in case of using “quirk update” as it is treated through a @CollateralUsed variable, but I decided to keep it for checking the process.
PreviousCovers to store the running total of the covered amount of the current facility. Unfortunately this cannot be tracked by the “quirky update” (or by a recursive CTE, since you need two joins to itself to keep track for both CollateralUsed and PreviousCovers).
CoveredAmount is the final result, i.e. the part of the value of the current collateral that is allocated by the process to the current facility.
Based on the above sample the temporary table looks like that:
CollateralIDCollateralTypeIDCollateralPriorityCollateralValueObligorIDAccountIDFacilityTypeIDFacilityPriorityFacilityValueCoveredAmountCollateralCoverageCollateralUsedPreviousCovers
21110000220111150000NULL0,055556NULLNULL
2111000033011130000NULL0,055556NULLNULL
31120000110211130000NULL0,153846NULLNULL
4118000033011130000NULL0,347826NULLNULL
41180000440112150000NULL0,347826NULLNULL
4118000044012350000NULL0,347826NULLNULL
511110000440112150000NULL0,733333NULLNULL
111100000110211130000NULL0,769231NULLNULL
72360000220111150000NULL0,4NULLNULL
(c)After that, the obvious process to solve the problem consists of the following steps:
1.Get the first row. Set @ CollateralUsed = 0
2.Set PreviousCovers equal to the sum of all the CoveredAmount fields of all previous rows (under the ordering of this table) with the same Facility unique ID (ObligorID, AccountID, FacilityTypeID).
3.Calculate the uncovered part of the facility: @UncoveredPart = FacilityValue - PreviousCovers
4.Calculate the covered amount: If CollateralValue > UncoveredPart then CoveredAmount = UncoveredPart else CoveredAmount = CollateralValue
5.@CollateralUsed = CollateralUsed = @CollateralUsed + CoveredAmount
6.Get the next row. If in different collateral then @ CollateralUsed = 0
7.Go to step 2
The main pitfall in the above methodology is that I cannot find a way for satisfying the step 2 from inside a set operation. I tried a SELECT to the same table, but, of course, the values returned were NULLs as the updates were more recent than the dataset generation time. I tried to run the process using a recursive CTE but I need simultaneous access to at least three rows (the current one, the row of the previous row according to collateral ordering and the previous row according to facility ordering).
Therefore, instead of using an RBAR solution (I couldn’t anyway because it needs a century to run in the production environment) I applied a hybrid methodology. This methodology is based on the observation that (in the above table) the first time a facility is met we know that the PreviousCovers is always zero. So we can use a set operation (quirk update or CTE) to treat all these rows as a set. After finishing with these rows, we have to update all the other ones with the right values for PreviousCovers and CollateralUsed taking into account the CoveredAmount’s of the first run. Now we are ready to continue with the second appearances. We run again the above-mentioned set operation for these rows and so on. The result set for the above example according to this procedure, can be found in table “ExpectedResults” I sent in my post #863007. In the same post there is the script applying it.
Even if the above methodology significantly shortens process time (compared to RBAR approach) the performance remains unacceptable. Maybe another technique, based on a different basis could be full set oriented and effective. Anyway, in case there are no other ideas, I’ll try to optimize as much as I can the current methodology, maybe checking for zero updates from the quirky update before calling the other two (time-consuming) ones and things like that.
I hope the above gives the full picture about my perspective.
Thanks and regards,
Elias
PS. Sorry for the appearance of the tables, I couldn't find a way for better displaying them.
Viewing 15 posts - 1 through 15 (of 20 total)
You must be logged in to reply to this topic. Login to reply