2

I have a table with records and their scores (table 'Offers'):

OfferId     OfferScore
----------- -----------
1           1
2           20
3           3
4           4
5           5
6           6
7           7
8           8

These records might be related. All relations are stored in the table 'OffersRelation':

OfferId1    OfferId2
----------- -----------
1           2
1           3
1           4
1           5
2           3
3           5
7           8

I want to remove all related Ids (within the group) from table Offers and leave only ones with the highest score.

In my case :

Offers with Ids: 1,2,3,4,5 are related ("group") and the offer with id:2 has the highest score:20 so I want to remove ids: 1,3,4,5 and leave only the one with id:2 from this "group".

Offer with Id:6 doesn't have any related items (no relations in the table OffersRelations) so it stays in the table Offers.

Offers with Ids:7,8 are related and Offer with id:8 has higher score than 7 so i want to remove the offer with id:7 and leave the offer with id:8 from this "group".

Expected result in the table Offers:

OfferId     OfferScore
----------- -----------
2           20
6           6
8           8

How to do it in t-sql?

Data from examples:

drop table if exists dbo.Offers
drop table if exists dbo.OffersRelation
CREATE TABLE [dbo].[Offers](
    [OfferId] [int] NOT NULL,
    [OfferScore] [int] NOT NULL
) 
GO

CREATE TABLE [dbo].[OffersRelation](
    [OfferId1] [int] NOT NULL,
    [OfferId2] [int] NOT NULL
) 
GO

INSERT INTO [dbo].[Offers]
           ([OfferId],[OfferScore])
     VALUES (1,1),(2,20),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8)


INSERT INTO [dbo].[OffersRelation]
           ([OfferId1]
           ,[OfferId2])
     VALUES
            (1,2),
            (1,3),
            (1,4),
            (1,5),
            (2,3),
            (3,5),
            (7,8)
  • I don't get why you would remove Id 1 from table1. What's the relation between table1 and table2? – Mattia Nocerino Sep 26 '18 at 15:04
  • @MattiaNocerino in table1 i have all items (ads with cars on sale), in table2 i have a result of a 'duplicate' detection scan. It means that we might have 5 different offers but all of them display the same car on sale so i want to pick the most complete (highest score) and remove the others. – free4ride Sep 26 '18 at 15:18
  • 1
    This smells like bad design to me, but i may be wrong. Why do you have 2 different tables to store the same thing? Wouldn't be better something like a car table and an ads table? That way it would be even easier to get the highest score for the same car – Mattia Nocerino Sep 26 '18 at 16:06
  • @MattiaNocerino the design is not important here. it's just an example to show the problem – free4ride Sep 26 '18 at 16:11
3

I have completely redone my answer (based on the additional information you provided in your question).

You indicated that you tried recursion and it was too slow on a large set of data. I've created a cursor based solution that works on your test data, but I'm wondering if it gives you the correct answer on your production data. With such a small set of test data, it's difficult to spot flaws in my logic.

Can you give it a try and let me know if I'm any closer to a proper solution?

DECLARE @OfferId INT
DECLARE @OffersToDelete TABLE (id INT)

--Declare cursor for all Offers
DECLARE _CURSOR CURSOR LOCAL FORWARD_ONLY STATIC READ_ONLY
FOR
SELECT [o].offerid
FROM Offers [o]
ORDER BY [o].OfferId

OPEN _CURSOR

FETCH NEXT
FROM _CURSOR
INTO @OfferId

DECLARE @Related TABLE (OfferId INT)

WHILE @@FETCH_STATUS = 0
BEGIN
    --For each Offer, initialize @Related table
    DELETE
    FROM @Related

    --Insert into @Related the Offerid that we are currently processing
    INSERT INTO @Related
    SELECT [or].OfferId2
    FROM OffersRelation [or]
    WHERE [or].OfferId1 = @OfferId

    --Now, loop through all offers related to the one we're processing
    --When @@ROWCOUNT = 0, you have processed all related rows and need
    --to break out of the while loop
    WHILE 1 = 1
    BEGIN
        INSERT INTO @Related
        SELECT [or].OfferId2
        FROM OffersRelation [or]
        JOIN @Related [r]
            ON [r].OfferId = [or].OfferId1
        WHERE NOT EXISTS (
                SELECT *
                FROM @Related
                WHERE OfferId = [or].OfferId2
                )
            AND [r].OfferId <> @OfferId

        IF @@ROWCOUNT = 0
            BREAK;
    END;

    --With all related rows, including the offer we're processing,
    --add a row number ordered by OfferScore desc and insert all rows
    --not = 1 into the @OffersToDelete table
    WITH OfferAndRelated
    AS (
        SELECT Offerid
            ,offerscore
        FROM offers
        WHERE offerid = @OfferId

        UNION

        SELECT [o].offerid
            ,[o].offerscore
        FROM @Related [r]
        JOIN Offers [o]
            ON [o].OfferId = [r].OfferId
        )
        ,OfferAndRelatedWithRowNumber
    AS (
        SELECT *
            ,ROW_NUMBER() OVER (
                ORDER BY OfferScore DESC
                ) AS rn
        FROM OfferAndRelated
        )
    INSERT INTO @OffersToDelete
    SELECT OfferId
    FROM OfferAndRelatedWithRowNumber
    WHERE rn <> 1

    --  SELECT *
    --  FROM @Related
    FETCH NEXT
    FROM _CURSOR
    INTO @OfferId
END

CLOSE _CURSOR

DEALLOCATE _CURSOR

--Delete from Offers where the OfferId is on the @OffersToDelete table
DELETE [o]
FROM Offers [o]
JOIN @OffersToDelete otd
    ON otd.id = [o].OfferId

SELECT *
FROM Offers

| OfferId | OfferScore |
|---------|------------|
| 2       | 20         |
| 6       | 6          |
| 8       | 8          |
| improve this answer | |
3

I worked up a solution for SQL 2017 using graph tables but it's a bit unwieldy. Transitive closure still has to done with a loop as at this version (happy to be corrected). SQL Server 2019 promises to bring transitive closure (as per here) but for now try this:

DROP TABLE IF EXISTS #tmpOffers
DROP TABLE IF EXISTS #tmpOffersRelation
DROP TABLE IF EXISTS dbo.Offers
DROP TABLE IF EXISTS dbo.isRelatedTo
GO

CREATE TABLE #tmpOffers (
    OfferId         INT PRIMARY KEY,
    OfferScore      INT NOT NULL
)
GO

CREATE TABLE #tmpOffersRelation (
    OfferId1    INT NOT NULL,
    OfferId2    INT NOT NULL,

    PRIMARY KEY ( OfferId1, OfferId2 )
)
GO

CREATE TABLE dbo.Offers (
    OfferId         INT PRIMARY KEY,
    OfferScore      INT NOT NULL
    ) AS NODE


CREATE TABLE dbo.isRelatedTo AS EDGE;
GO

INSERT INTO #tmpOffers
VALUES
    ( 1, 1  ),
    ( 2, 20 ),
    ( 3, 3  ),
    ( 4, 4  ),
    ( 5, 5  ),
    ( 6, 6  ),
    ( 7, 7  ),
    ( 8, 8  )

INSERT INTO #tmpOffersRelation 
VALUES
    ( 1, 2 ), 
    ( 1, 3 ), 
    ( 1, 4 ), 
    ( 1, 5 ), 
    ( 2, 3 ), 
    ( 3, 5 ), 
    ( 7, 8 )
GO


INSERT INTO dbo.Offers ( OfferId, OfferScore )
SELECT OfferId, OfferScore
FROM #tmpOffers

INSERT INTO dbo.isRelatedTo ( $from_id, $to_id )
SELECT o1.$node_id, o2.$node_id
FROM #tmpOffersRelation o
    INNER JOIN dbo.Offers o1 ON o.OfferId1 = o1.OfferId
    INNER JOIN dbo.Offers o2 ON o.OfferId2 = o2.OfferId
GO

-- Run match queries
SELECT FORMATMESSAGE( 'Offer %i is related to Offer %i with scores of %i and %i.', o1.OfferId, o2.OfferId, o1.OfferScore, o2.OfferScore )
FROM dbo.Offers o1, dbo.isRelatedTo isRelatedTo, dbo.Offers o2
WHERE MATCH ( o1-(isRelatedTo)->o2 );
GO

/*
OfferId     OfferScore
2           20
6           6
8           8
*/

DROP FUNCTION IF EXISTS dbo.utf_tc
GO

CREATE FUNCTION dbo.utf_tc ( @OfferId INT ) 
RETURNS @var TABLE
(
    OfferId     INT NOT NULL PRIMARY KEY NONCLUSTERED,
    OfferScore  INT NOT NULL,
    xlevel      INT NOT NULL, 

    UNIQUE CLUSTERED( xlevel, OfferId )
)
AS
BEGIN

    DECLARE @xlevel INT = 0

    -- Get first node
    INSERT INTO @var( OfferId, OfferScore, xlevel )
    SELECT OfferId, OfferScore, @xlevel 
    FROM dbo.Offers
    WHERE OfferId = @OfferId


    -- Loop thru children
    WHILE @@rowcount > 0
    BEGIN
        SET @xlevel += 1

        -- Get children
        INSERT INTO @var( OfferId, OfferScore, xlevel )
        SELECT DISTINCT Offers2.OfferId, Offers2.OfferScore, @xlevel
        FROM @var AS tc, dbo.Offers Offers1, dbo.isRelatedTo isRelatedTo, dbo.Offers Offers2
        WHERE tc.OfferId = Offers1.OfferId
          AND MATCH ( Offers1-(isRelatedTo)->Offers2 )
          AND tc.xlevel = @xlevel - 1
          AND NOT EXISTS (  -- id does not already exist
            SELECT *
            FROM @var
            WHERE OfferId = Offers2.OfferId
            )

    END

    RETURN
END
GO


;WITH cte AS (
SELECT o.OfferId AS chainId, f.OfferId, f.OfferScore, f.xlevel
FROM dbo.Offers o
    CROSS APPLY dbo.utf_tc( o.OfferId ) f
), cte2 AS (
SELECT c.OfferId, c.OfferScore, RANK() OVER( PARTITION BY c.chainId ORDER BY c.OfferScore DESC ) AS xrank
FROM cte c
    INNER JOIN
    ( -- Get the min chainid per offerId
    SELECT offerId, MIN(chainId) AS chainId
    FROM cte c2
    GROUP BY offerId
    ) x ON c.chainId = x.chainId  
        AND c.offerId = x.OfferId
)
SELECT OfferId, OfferScore
FROM cte2
WHERE xrank = 1
ORDER BY xrank

My results:

My results

Update after comments from OP

Comment: This is great but it fails with 1 case:Try "INSERT INTO #tmpOffers VALUES (1,1),(2,4),(3,3),(4,2) INSERT INTO #tmpOffersRelation VALUES (1,2),(3,4),(2,4)" .It returns two elements: 2 and 3, It should return only one element: 2 with score 4 because 3 is connected with 4 and 4 is connected with 2. But what is strange in your solution, if you swap relation (3,4) with (4,3) the solution works.... – free4ride 13 hours ago

My reply: The way I've implemented the rules, the relationships are one-directional, so with the original data there are three chains: 1 > 2 > 3 > 5 and 6 and 7 > 8, thus 3 records returned. It looks like this:

first dataset

With your second set of sample data (and with the way I have implemented the rules) there are two chains: 1 > 2 > 4 and 3 > 4, ie both chains end in 4. It looks like this:

second dataset

Try thinking about your rules visually and how you want them implemented. It would in theory be possible to make the relationships bi-directional but now you're learning all about graph in SQL I'll leave it as an exercise for the reader!

PS If you've got a simple way to test out that 200k dataset I would like to trial it as it's also possible to index graph tables.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.