1

I have a SQL Server 2014 database table containing a code and two identifiers:

DECLARE @Foo TABLE (code CHAR, id_a INT, id_b INT)
INSERT INTO @Foo (code, id_a, id_b) VALUES
('A', 1, 2),
('B', 2, 1),
('C', 3, 4),
('D', 4, 0),
('E', 5, 3)

The first two rows of the table form a two-way match, as the first row links IDs 1 and 2, and the second row links them in reverse.

I want to find all rows that don't take part in a two-way match, and to that end I've written the following query:

SELECT code FROM @Foo WHERE CONCAT(id_a, ':', id_b) NOT IN (
    SELECT CONCAT(id_b, ':', id_a) FROM @Foo
)

This is working (it returns codes C, D and E for my sample data), but I'm concerned about the performance of those concatenations once the table has millions of rows in it.

I haven't tested the performance with a large dataset (that's tomorrow's job), but in the meanwhile I was wondering if there's a more elegant and performant way I can structure this query?

P.S. The query plan indicates that I'm doing table scans inside a scalar compute inside a nested loop, which doesn't sound like it'll scale too well:

  |--Nested Loops(Left Anti Semi Join, WHERE:([Expr1007] IS NULL OR [Expr1008] IS NULL OR [Expr1007]=[Expr1008]))
       |--Compute Scalar(DEFINE:([Expr1007]=concat(CONVERT_IMPLICIT(varchar(12),[id_a],0),':',CONVERT_IMPLICIT(varchar(12),[id_b],0))))
       |    |--Table Scan(OBJECT:(@Foo))
       |--Compute Scalar(DEFINE:([Expr1008]=concat(CONVERT_IMPLICIT(varchar(12),[id_b],0),':',CONVERT_IMPLICIT(varchar(12),[id_a],0))))
            |--Table Scan(OBJECT:(@Foo))

  • 1
    Both Akina:s and HandyD:s solutions will be more efficient. In addition to what they wrote you can add indexes (a_id, b_id) and (b_id, a_id) to further improve performance. – Lennart Apr 30 '19 at 8:25
  • Thanks everyone for your suggestions. I tested the queries against a test load of 320000 rows and no indexes. My original was taking so long that I gave up. HandyD's query took ~2 seconds, Akina's took ~3 seconds, and Lennart's took ~15 seconds. With the two indexes suggested by Lennart, handyD and Akina's queries dropped down to around 25ms, with Lennart's query remaining unchanged. I'm going to go with HandyD's query, as it's the most efficient and aligns well with my mental model of SQL. – Chris Parton May 1 '19 at 0:31
3

The compute scalar is occurring because it has to convert the INT values to VARCHAR(12) values before concatenating which it can then compare against the subquery returned values. You are correct that this is not likely to scale well, due to cardinality estimation issues among others.

One solution is to LEFT JOIN the table on itself then use a WHERE clause to exclude the rows that do not have a joined row. This plan is simply two table scans, a nested loop and finally a filter to exclude the NULL valued rows. This should scale reasonably well.

Example:

SELECT a.*
FROM @Foo a
LEFT JOIN @Foo b ON a.id_a = b.id_b AND a.id_b = b.id_a
WHERE b.id_a IS NULL

Returns:

code    id_a    id_b
--------------------
C       3       4
D       4       0
E       5       3
2

Define (id_a, id_b) as unique to forbid direct duplicates.

Then use

SELECT *
FROM @foo t1
WHERE NOT EXISTS ( SELECT 1 
                   FROM @foo t2 
                   WHERE t1.id_a=t2.id_b 
                     AND t1.id_b=t2.id_a)

for to remove cross-duplicates.

0

An alternative solution using window function instead of self-join:

select code, id_a, id_b
from (
    select code
         , id_a
         , id_b
         , count(1) over (partition by case when id_a < id_b then id_a else id_b end
                                      ,case when id_a > id_b then id_a else id_b end) as cnt
    from @foo
) as t
where cnt = 1
;

A cleaner solution would have been:

partition by least(id_a, id_b), greatest(id_a, id_b)

, but SQL server does not seem to support these functions.

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.