2

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!

  • If the number of possible TypeId values is manageably small, simply pivot the Count(TypeId) calculation into columns and do a straight WHERE condition on Count_TypeId_N > 0 as required. – Pieter Geerkens May 31 '15 at 14:17
  • Number of TypeId is small (?), lets say about 10-30 types. I need to check your suggestion. Another idea is to add a bigint column for Parent table, add index for it and use it as a field with flags for each TypeId. Then in query use a bit operations (select * from Parents p where p.TypeId & somevalue = somevalue). – Tpsamw1 May 31 '15 at 14:41
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.
  • And what about this one: 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 ORDER by p.Id; I think that this one is faster, but I would like to get rid off defining number of types. – Tpsamw1 May 30 '15 at 23:29
  • @Tpsamw1, this query yields the same execution plan as the one I provided, but only after adding additional rows of test data. There is are tipping points. I'll expand on my answer. – Dan Guzman May 31 '15 at 12:48
  • Thanks for explanation, by the way, as for "The sample data suggests that only one row per type may exist for a given ParentId. I added the unique constraint below to enforce this data integrity rule." - there can be more than one row with the same TypeId in Children table. – Tpsamw1 May 31 '15 at 14:34
  • @Tpsamw1, I removed the unique constraint and added non-unique indexes instead. This didn't change the plan and stats. – Dan Guzman May 31 '15 at 15:24
0

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);
  • There is something wrong with this query, it returns too much rows, probably this having count(c.Id) = count(distinct t.typeid); – Tpsamw1 May 30 '15 at 23:29
  • For what input? – Mister Magoo May 30 '15 at 23:39
  • For a real data, instead of returning ~800 records it returns several thousand of records. – Tpsamw1 May 31 '15 at 8:41
  • @Tpsamw1 It would help you get a working answer is if you could post some sample data that the query fails to return the correct results, otherwise it's impossible to help you. – Mister Magoo May 31 '15 at 9:23
0

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;
0

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.

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.