5

Below is a script which can be used to re-produce the issue I am facing. Basically the question is this: why is it that the record with (ID1 = 6, ID2 = 7) is not populated into the final #tt2 table? I can INSERT it just fine manually, so it doesn't violate the UNIQUE constraint, but it doesn't get populated as part of INSERT/SELECT.

USE [tempdb]
GO 

IF OBJECT_ID('tempdb..#t1') IS NOT NULL DROP TABLE #t1
CREATE TABLE [#t1] ([ID] INT , [V] VARCHAR(10))

INSERT INTO #t1 (ID, V) 
VALUES
(1,'A'),
(2,'B'),
(3,'B'),
(4,'C'),
(5,'E'),
(6,'E')

IF OBJECT_ID('tempdb..#t2') IS NOT NULL DROP TABLE #t2
CREATE TABLE [#t2] ([ID] INT , [V] VARCHAR(10))

INSERT INTO #t2 (ID, V) 
VALUES
(1,'A'),
(2,'B'),
(3,'C'),
(4,'C'),
(5,'D'),
(6,'E'),
(7,'E')

IF OBJECT_ID('tempdb..#tt') IS NOT NULL DROP TABLE #tt

SELECT t1.ID AS ID1, t2.ID AS ID2, t1.V AS V
INTO #tt
FROM #t1 t1
JOIN #t2 t2 ON t1.V=t2.V

--SELECT * FROM #tt

IF OBJECT_ID('tempdb..#tt2') IS NOT NULL DROP TABLE #tt2
CREATE TABLE #tt2 (ID1 INT, ID2 INT, V VARCHAR(10))

CREATE UNIQUE INDEX IDX_TT_ID1 ON #tt2 (ID1) WITH (IGNORE_DUP_KEY = ON)
CREATE UNIQUE INDEX IDX_TT_ID2 ON #tt2 (ID2) WITH (IGNORE_DUP_KEY = ON)

-- Query 1 - this SELECT returns 9 records. 
SELECT ID1, ID2, V
FROM #tt 
ORDER BY ID1, ID2

-- Query 2 - this INSERT populates 4 records, but I would expect 5
INSERT INTO #tt2 (ID1, ID2, V)
SELECT ID1, ID2, V
FROM #tt 
ORDER BY ID1, ID2

-- Why are there only 4 records in this table? (I would expect 5, but the record with ID1 = 6, ID2 = 7  is missing)
SELECT * FROM #tt2

-- I can INSERT the missing record manually:
INSERT INTO #tt2 (ID1, ID2, V)
VALUES (6, 7, 'E')
7

I think the confusion arises because the indexes are defined as single-column on ID1 and ID2 separately. This means the "ignore duplicates" check is performed on each individually and only if a row passes both checks will it be inserted into the final #tt2 table. I'll step through and show the working.

One way for the system to check for duplicates is to sort the rows then process them in sequence. This is what happens on my local (2017) instance. So let's look at the contents of #tt, ordered:

Row ID1 ID2 V
i   1   1   A
ii  2   2   B
iii 3   2   B
iv  4   3   C
v   4   4   C
vi  5   6   E
vii 5   7   E
iix 6   6   E
ix  6   7   E

Starting with row i the system asks "have I seen ID1=1 already or have I seen ID2 = 1 already?" Since both are false row i is passed through to the output. Similarly with row ii. For row iii, however, ID2=2 which matches row ii that has been seen already. So row iii is rejected. Row iv is accepted. Row v is rejected since it has the same ID1 value as row iv. Row vi is accepted. Row vii is rejected - ID1=5 which matches row vi. Row iix is rejected since ID2=6 matches row vi. Finally row ix is rejected in both ID1 (matches iix) and ID2 (matches vii).

The output is i, ii, iv, vi and these are inserted into #tt2.

Row ID1 ID2 V
i   1   1   A
ii  2   2   B
iv  4   3   C
vi  5   6   E

It is possible to insert {6,7,E} afterwards because it does not conflict with any row that made it through the filtering and was actually inserted into #tt2. All the rows with ID1=6 were eliminated due to their ID2 values and those with ID2=7 due to their ID1 values.


The above is an explanation of the logical algorithm which produces the observed output. The physical implementation of this algorithm, as observed in the actual execution plan, is different but equivalent. Here's the plan: enter image description here fig 1 - actual execution plan for INSERT

The physical plan sorts on ID1 (A in the image) and takes the first row for each value (B). The output of this is then sorted on ID2 (C) and, again, the first row for each value is retained (D). Whichever rows pass both filters are inserted to #tt2.

The tricky part here is the word "first". Relational DB tables have no inherent order. The query optimizer (QO) is free to process rows in whichever order it chooses, as long as its results are logically equivalent to the SQL submitted. This got me wondering if I could produce a different result from the same data without changing the queries. I can.

Sorts are expensive so the QO often chooses other options if it has them. One such option is to read an index. I found that with an index on #tt.ID1 the QO would use it and skip the sort. SQL Server's sorts are order-preserving so if I can present ID2 in an alternate ordering a different "first" row will be chosen for each ID1 value and the overall output will be different. I created a new target table #tt3 identical to #tt2 and ran this (the ORDER BY does not affect this INSERT)

CREATE CLUSTERED INDEX CIX ON #tt(ID1 ASC, ID2 DESC);

INSERT INTO #tt3 (ID1, ID2, V)
SELECT ID1, ID2, V
FROM #tt;

Produced this

Row ID1 ID2 V
i   1   1   A
ii  2   2   B
v   4   4   C
vii 5   7   E

Which is different to the previous result i, ii, iv, vi.

You'll notice that if you order the contents of #tt by ID1 asc, ID1 desc ..

Row ID1 ID2 V
i   1   1   A
ii  2   2   B
iii 3   2   B
v   4   4   C
iv  4   3   C
vii 5   7   E
vi  5   6   E
ix  6   7   E
iix 6   6   E

.. and apply the logical "have I seen" algorithm this alternate result is obtained.

The question remains, why does the QO process ID1 first then ID2? I believe this is driven by the sequence in which the constraints are defined. I would have expected that defining #tt clustered index as (ID2 asc, ID1 desc) would cause ID2 to be processed first, as that would avoid a sort. It is not. It still processed ID1 first with the sort operator brought back. Indeed, creating another constrint in column V adds it to the plan accordingly. Seems like processing in sys.indexes.index_id order may be hard-coded in the QO?

All up, I think caution is advised. Changes in the physical layer can affect the oucome of this query. If the target table's constrints are dropped and re-created we better hope they come back in the same sequence they were previously. If the source table is optimised, say with indexes, it may affect the access path and which row comes "first". This is without considering allocation-order scans or merry-go-round scans.

If more rows were involved it is likely QO would swap to using hash joins. Heavens only knows how that would affect things.

2
  • That "have I seen ID1 already or have I seen ID2 already?" logic does not explain why {6,7,E} is accepted if indexes created in different order.
    – i-one
    Oct 26 at 9:41
  • @i-one the algorithm is sensitive to the initial sort order. If the initial set of 9 rows is sorted ID2,ID1 instead (which would correspond to changing the order of index creation) that logic will certainly insert {6,7,E}. I would be happy to discuss if you see it otherwise? Oct 27 at 13:32
1

I think what we observe here looks like a bug. Documentation states that with IGNORE_DUP_KEY = ON

Only the rows violating the uniqueness constraint will fail.

Based on this, situation when a row from the source data fails to be inserted but can be inserted afterwards without conflict looks unacceptable (as for me).

I believe that correct logic of the INSERT query in this case should be: "Does insertion of the row violate any constraint in the target table?". If "no" - row should be inserted, otherwise skipped. Optimizer is free to implement this simple logic more efficiently, without breaking its semantics though.

Say we insert rows one by one in the following order:

ID1         ID2         V
----------- ----------- ----------
1           1           A
2           2           B
3           2           B
4           3           C
4           4           C
5           6           E
5           7           E
6           6           E
6           7           E

Rows {1,1,A} and {2,2,B} can be inserted, then row {3,2,B} should be skipped as its ID2 column value conflicts with the previously inserted {2,2,B} row. Similarly, row {4,3,C} can be inserted, {4,4,C} should be skipped, {5,6,E} can be inserted, {5,7,E} should be skipped, {6,6,E} should be skipped, and finally {6,7,E} can be inserted.

Following this algorithm, we should get

ID1         ID2         V
----------- ----------- ----------
1           1           A
2           2           B
4           3           C
5           6           E
6           7           E

in the #tt2 table.

Obviously, there is some indeterminacy related to rows processing order. Such as, processing same rows in the backwards order

ID1         ID2         V
----------- ----------- ----------
6           7           E
6           6           E
5           7           E
5           6           E
4           4           C
4           3           C
3           2           B
2           2           B
1           1           A

would result to

ID1         ID2         V
----------- ----------- ----------
6           7           E
5           6           E
4           4           C
3           2           B
1           1           A

inserted into the #tt2 table, which is not the same set of rows. Important thing, however, is that none of the rest source rows can be inserted afterwards in both these examples.

why is it that the record with (ID1 = 6, ID2 = 7) is not populated into the final #tt2 table?

Unfortunately, execution plan of the INSERT query does not follow this logic. Instead, it takes non-duplicate rows in regard to the one index, and from them takes non-duplicate rows in regard to the other index then. This is where rows being inserted may be lost.

Here is the graphical representation of the execution plan:

query plan

Between the Table Scan (reading data from the #tt table) and the Table Insert (inserting data into the #tt2 table) there are two similar groups of operators added by the optimizer for handling IGNORE_DUP_KEY over two indexes.

Given that target table is empty, following are the rows flowing to the output of the first group of operators:

ID1         ID2         V
----------- ----------- ----------
1           1           A
2           2           B
3           2           B
4           3           C
5           6           E
6           6           E

Rows at the output of the second group are:

ID1         ID2         V
----------- ----------- ----------
1           1           A
2           2           B
4           3           C
5           6           E

These rows are inserted into #tt2 then.

If you create indexes in different order

CREATE UNIQUE INDEX IDX_TT_ID2 ON #tt2 (ID2) WITH (IGNORE_DUP_KEY = ON);
CREATE UNIQUE INDEX IDX_TT_ID1 ON #tt2 (ID1) WITH (IGNORE_DUP_KEY = ON);

execution plan will be changed such that index over ID2 is examined first. In such case, rows at the output of the first group of operators are following:

ID1         ID2         V
----------- ----------- ----------
1           1           A
2           2           B
4           3           C
4           4           C
5           6           E
6           7           E

And rows at the output of the second group of operators (inserted into #tt2 then) are:

ID1         ID2         V
----------- ----------- ----------
1           1           A
2           2           B
4           3           C
5           6           E
6           7           E

In the first case, row {6,7,E} is not inserted (but can be inserted manually afterwards) which I think is incorrect because its insertion along with the selected rows does not violate uniqueness constraints. In the second case, none of the source rows can be inserted afterwards which is correct.

I think that generated plan shape is wrong, because it does not ensure logic stated in the documentation.

The last note is that ORDER BY ID1, ID2 in your INSERT query does not make sense (and is ignored by the optimizer).

2
  • Can you explain, please, which row "that does not violate uniqueness constraint" and which constraint you mean? Oct 27 at 13:38
  • @MichaelGreen, I extended answer to explain my vision better.
    – i-one
    Oct 28 at 9:16

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.