MSSQL Select all parent rows for which exists a combination of children rows with desired value

Question

I would like to select all parent rows for which exists a combination of children rows with desired value. The easiest approach is to use multiple exists clauses, but this is not optimal - anyone knows better solution? Here is a SQL fiddle: http://sqlfiddle.com/#!6/8da76/5

Schema:

CREATE TABLE [dbo].[Parents](
    [Id] [bigint] IDENTITY(1,1) NOT NULL,
    [GroupId] [uniqueidentifier] NOT NULL
);

INSERT INTO [Parents] ([GroupId]) VALUES ('00000000-0000-0000-0000-000000000001');
INSERT INTO [Parents] ([GroupId]) VALUES ('00000000-0000-0000-0000-000000000002');
INSERT INTO [Parents] ([GroupId]) VALUES ('00000000-0000-0000-0000-000000000003');
INSERT INTO [Parents] ([GroupId]) VALUES ('00000000-0000-0000-0000-000000000004');
INSERT INTO [Parents] ([GroupId]) VALUES ('00000000-0000-0000-0000-000000000005');

CREATE TABLE [dbo].[Childrens](
    [Id] [bigint] IDENTITY(1,1) NOT NULL,
    [ParentId] [bigint] NOT NULL,
    [TypeId] [int] NOT NULL
);

INSERT INTO [Childrens] ([ParentId], [TypeId]) VALUES (1, 1);
INSERT INTO [Childrens] ([ParentId], [TypeId]) VALUES (1, 2);
INSERT INTO [Childrens] ([ParentId], [TypeId]) VALUES (1, 3);
INSERT INTO [Childrens] ([ParentId], [TypeId]) VALUES (1, 4);
INSERT INTO [Childrens] ([ParentId], [TypeId]) VALUES (1, 5);

INSERT INTO [Childrens] ([ParentId], [TypeId]) VALUES (2, 1);
INSERT INTO [Childrens] ([ParentId], [TypeId]) VALUES (2, 4);
INSERT INTO [Childrens] ([ParentId], [TypeId]) VALUES (2, 5);

INSERT INTO [Childrens] ([ParentId], [TypeId]) VALUES (3, 4);
INSERT INTO [Childrens] ([ParentId], [TypeId]) VALUES (3, 5);
INSERT INTO [Childrens] ([ParentId], [TypeId]) VALUES (3, 6);

INSERT INTO [Childrens] ([ParentId], [TypeId]) VALUES (4, 2);
INSERT INTO [Childrens] ([ParentId], [TypeId]) VALUES (4, 6);

INSERT INTO [Childrens] ([ParentId], [TypeId]) VALUES (5, 1);
INSERT INTO [Childrens] ([ParentId], [TypeId]) VALUES (5, 2);
INSERT INTO [Childrens] ([ParentId], [TypeId]) VALUES (5, 3);

Sample query to select all parent rows for which exists a combination of children rows with TypeId = 1 and 2 (query should return parent with Id = 1 and 5):

SELECT *
  FROM Parents p
  WHERE EXISTS( 
        SELECT *
          FROM Childrens c
          WHERE p.Id = c.ParentId
            AND c.TypeId = 1 )
    AND EXISTS( 
        SELECT *
          FROM Childrens c
          WHERE p.Id = c.ParentId
            AND c.TypeId = 2 );

Sample query to select all parent rows for which exists children row with TypeId = 4, 5 and 6 (should return parent with Id = 3)

SELECT *
  FROM Parents p
  WHERE EXISTS( 
        SELECT *
          FROM Childrens c
          WHERE p.Id = c.ParentId
            AND c.TypeId = 4 )
    AND EXISTS( 
        SELECT *
          FROM Childrens c
          WHERE p.Id = c.ParentId
            AND c.TypeId = 5 )
    AND EXISTS( 
        SELECT *
          FROM Childrens c
          WHERE p.Id = c.ParentId
            AND c.TypeId = 6 );

Number of conditions for children TypeId is variable.

Best Regards!

Answer 1

Below is one method. In the outer WHERE clause, specify the number of types included in the IN clause. An composite index on the Childrens table ParentId and TypeId will help optimize the query.

SELECT  *
FROM    Parents p
WHERE   2 = ( SELECT    COUNT(DISTINCT c.TypeId)
              FROM      Childrens c
              WHERE     p.Id = c.ParentId
                        AND c.TypeId IN ( 1, 2 )
            );

SELECT  *
FROM    Parents p
WHERE   3 = ( SELECT    COUNT(DISTINCT c.TypeId)
              FROM      Childrens c
              WHERE     p.Id = c.ParentId
                        AND c.TypeId IN ( 4, 5, 6 )
            );

EDIT: The original DDL in the question didn't include constraints or indexes. These aren't relevant for query functionality but are important to compare performance of alternative solutions.

Assuming the IDENTITY columns in both tables are also the primary keys and the tables are related, I added the constraints below.

ALTER TABLE Parents
    ADD CONSTRAINT PK_Parents PRIMARY KEY CLUSTERED(Id);

ALTER TABLE Childrens
    ADD CONSTRAINT PK_Childrens PRIMARY KEY CLUSTERED(Id);

ALTER TABLE Childrens
    ADD CONSTRAINT FK_Childrens_Parents FOREIGN KEY (ParentId) REFERENCES Parents(Id);

I added candidate indexes on columns specified on JOIN or WHERE clauses and specified UNIQUE for those indexes that include the primary key column. Indexes not deemed to be used can be dropped afterward.

CREATE UNIQUE INDEX idx1 ON Parents (Id, GroupId);
CREATE INDEX idx1 ON Childrens (ParentId, TypeId);
CREATE INDEX idx2 ON Childrens (TypeId, ParentId);

Finally, I ran the original query in my answer in SSMS along with the query below which Tpsamw1 proposed in a comment (but without ORDER BY to level the playing field). SET STATISTICS IO ON and including the actual execution plan:

SELECT  p.Id
      , p.GroupId
FROM    Parents p
        INNER JOIN Childrens c ON c.ParentId = p.Id
WHERE   c.TypeId IN ( 4, 5, 6 )
GROUP BY p.Id
      , p.GroupId
HAVING  COUNT(DISTINCT c.TypeId) = 3;

SSMS reported comparable performance (50% of batch cost for each query) but that doesn't tell the whole story. The STATISTICS IO showed a higher number of logical reads for my original query, which I believe a better indicator of performance. This suggests Tpsamw1's query performs better. Below are the stats:

My original query:

Table 'Childrens'. Scan count 15, logical reads 30, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Parents'. Scan count 1, logical reads 2, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Tpsamw1 query:

Table 'Parents'. Scan count 4, logical reads 8, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Childrens'. Scan count 1, logical reads 2, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

I then loaded additional data by copying the original test data and update stats:

INSERT INTO Parents SELECT NEWID() FROM Parents WHERE Id = 1;
INSERT INTO Childrens SELECT SCOPE_IDENTITY(), TypeId FROM Childrens WHERE ParentId = 1;
INSERT INTO Parents SELECT NEWID() FROM Parents WHERE Id = 2;
INSERT INTO Childrens SELECT SCOPE_IDENTITY(), TypeId FROM Childrens WHERE ParentId = 2;
INSERT INTO Parents SELECT NEWID() FROM Parents WHERE Id = 3;
INSERT INTO Childrens SELECT SCOPE_IDENTITY(), TypeId FROM Childrens WHERE ParentId = 3;
INSERT INTO Parents SELECT NEWID() FROM Parents WHERE Id = 4;
INSERT INTO Childrens SELECT SCOPE_IDENTITY(), TypeId FROM Childrens WHERE ParentId = 4;
INSERT INTO Parents SELECT NEWID() FROM Parents WHERE Id = 5;
INSERT INTO Childrens SELECT SCOPE_IDENTITY(), TypeId FROM Childrens WHERE ParentId = 5;
GO 1000

UPDATE STATISTICS dbo.Childrens WITH FULLSCAN;
UPDATE STATISTICS dbo.Parents WITH FULLSCAN;
GO

Running the queries again shows execution plan changes to both queries. Both queries yielded the same number of logical IOs, indicating performance is be about the same. The only execution plan difference was an inner merge join versus a right outer merge join.

Table 'Parents'. Scan count 1, logical reads 21, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Childrens'. Scan count 1, logical reads 54, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Answer 2

I can't think of a solution that would be more optimised, but offer this as a solution that does not need re-writing when the list changes.

As a performance comparison, I traced your "double exists" query at 0.2 ms for this sample data and my query at 0.7 ms, so it is somewhat slower.

declare @types table(typeid int);

insert @types(typeid) values(4),(5);

select p.Id, p.GroupID
from @types t
cross join Parents p
left outer join Childrens c
on c.TypeId = t.typeid
and c.Parentid = p.Id
group by p.Id, p.GroupID
having count(c.Id) = count(distinct t.typeid);

Answer 3

Apply the GROUP BY logic before the join. If TypeId is not unique do a COUNT(DISTINCT TypeId) instead:

SELECT *
FROM Parents AS p
JOIN 
 ( 
   SELECT ParentId
   FROM Childrens
   WHERE TypeId IN (1,2) -- list of values
   GROUP BY ParentId
   --HAVING COUNT(*) = 2
    HAVING COUNT(DISTINCT TypeID) = 2 -- matching the number of values
 ) AS c
 on p.Id = c.ParentId;


declare @types table(typeid int);

insert @types(typeid) values(4),(5);

SELECT *
FROM Parents AS p
JOIN 
 ( 
   SELECT ParentId
   FROM Childrens AS c
   JOIN @types AS t
   ON c.TypeId = t.typeid
   GROUP BY ParentId
   HAVING COUNT(*) = (SELECT COUNT(*) FROM @types)
   --HAVING COUNT(DISTINCT TypeID) = (SELECT COUNT(*) FROM @types)
 ) AS c
ON p.Id = c.ParentId;

Answer 4

SInce the number of TypeID values is small, try a query like this:

select ParentID
from @Parent p
left join (
    select
         ParentID
        ,CountTypeId_1 = sum(case when TypeId=1 then 1 else 0 end)
        ,CountTypeId_2 = sum(case when TypeId=2 then 1 else 0 end)
        ,CountTypeId_3 = sum(case when TypeId=3 then 1 else 0 end)
        ,CountTypeId_4 = sum(case when TypeId=4 then 1 else 0 end)
        ,CountTypeId_5 = sum(case when TypeId=5 then 1 else 0 end)
        -- etc.
    from @Child c
    group by ParentID
) c
    on c.ParentID = p.Id
where CountTypeId_1 <> 0
  and CountTypeId_1 <> 0
;

A Non-Clustered Index on the child table by ParentID and TypeID will cover the subquery. An Indexed View on the subquery is possible also.