Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I will try and give an example - this is not my table structure - I'm simply trying to outline the issue in order to find a solution...

Person Id, Name

BrothersNames Id, Name

SistersNames Id, Name

PersonBrothers (join table) PersonId, BrotherNameId

PersonSisters (join table) PersonId, SisterNameId

OK - so imagine this database holds every person from a small country. The database holds a record of the names of everyone's brothers and sisters (it does not map a person to their brother or sister - just their names) so that we can find out statistics about names.

Obviously lots of names are shared so the join tables normalise this for us.

What I want to do is take one user and find out the number of matches of brother's names and number of matches of sister's names with every other user in the system, then add those two matches together and order by that descending. So this would give us a list of users who have the most number of brothers and sister's names in common.

I'm really only interested in the top ten matches but I think I have to get the whole result set to work out the top ten matches.

Please note that in my actual data a person can have a million brothers or a milllion sisters. This is where I'm getting performance issues.

This is how I'm calculating the matches for brothers and I do the same for sisters

select p.id, matches
FROM Person p
LEFT JOIN 
        (
            SELECT 
            COUNT(*) AS Matches,
            pbn.PersonId
            FROM PersonBrothersNames pbn
            INNER JOIN Brothersnames bn on pbn.BrothernameId =bn.Id
            inner join PersonBrothersName otherpbn on otherpbn.BrothernameId = bn.Id

            WHERE pbn.PersonId= @PersonId and pbn.PersonId <> otherpbn.personid
            GROUP BY  pbn.PersonId

        ) As BrothersNamesJoin ON BrothersNamesJoin.Person = p.Id

Please let me know if I should specify more info... I am using SQL Server 2008 but is probably platform agnostic..

share|improve this question
1  
I think this belongs to Stack Overflow, it's a programming question, not a DBA one. –  Quassnoi Jan 28 '12 at 17:25
2  
@Quassnoi - Please read our FAQ. This question about advanced querying is perfectly suited here. –  Nick Chammas Jan 28 '12 at 20:16
1  
@Nick Chammas: this question may have a better chance to get good answers on stackoverflow, from developers. I am with Quassnoi. –  AlexKuznetsov Jan 28 '12 at 20:22
1  
@Victoria it would be helpful to know the number of rows in each of the real tables (Person, PersonBrothersNames, BrothersNames in the example above). Also, what is the average number of 'brothers' per person (surely not many 'people' have 1 million 'brothers'). Finally, if I had a million brothers, I would expect their names not to be unique - does this extend to your case, or is there a uniqueness guarantee there you have not mentioned? –  Paul White Jan 29 '12 at 22:39
3  
@AlexKuznetsov. 1. This site isn't for backup/restore monkeys only 2. The high rep SO SQL developer types are mostly here too 3. If you're not, then why not contribute here and stop bitching –  gbn Jan 30 '12 at 16:11
show 4 more comments

2 Answers 2

up vote 5 down vote accepted

If you don't really need zero-second actuality, you could just run your query time to time and cache the results.

If you still need to have real-time data on this (sacrificing insert performance), I would do this:

Since self-joins are not allowed in indexed views, you need to create two copies of each table:

CREATE TABLE personBrother
        (
        personId INT NOT NULL,
        brotherName INT NOT NULL
        )

CREATE TABLE personBrother2
        (
        personId INT NOT NULL,
        brotherName INT NOT NULL
        )

Create an indexed view on their join:

CREATE VIEW
        commonBrothers
WITH SCHEMABINDING
AS
        SELECT  p1.personId AS p1,
                p2.personId AS p2,
                COUNT_BIG(*) AS cnt
        FROM    dbo.personBrother p1
        JOIN    dbo.personBrother2 p2
        ON      p1.brotherName = p2.brotherName
        WHERE   p1.personId < p2.personId
        GROUP BY
                p1.personId, p2.personId

CREATE UNIQUE CLUSTERED INDEX
        ux_commonBrothers_p1_p2
ON      commonBrothers (p1, p2)

CREATE INDEX
        ix_commonBrothers_cnt
ON      commonBrothers (cnt)

Same for sisters.

You should manually maintain these tables to have same data (write a trigger, insert/update/delete both etc).

Now we can easily get pairs with the most brothers and most sisters:

SELECT  TOP 1 WITH TIES
        *
FROM    commonBrothers
ORDER BY
        cnt DESC

All we need now is to fetch a greatest sum. Unfortunately, we cannot index a join of these views (it's a pure implementation flaw, there's no theoretical limitation for this).

So we need to do the following: the top pair cannot have less brothers than the top sis pair. Same holds for the sisters. So we have this query:

SELECT  TOP 1 WITH TIES
        cb.p1, cb.p2, cb.cnt + cs.cnt AS totalCnt
FROM    commonBrothers cb
JOIN    commonSisters cs
ON      cs.p1 = cb.p1
        AND cs.p2 = cb.p2
WHERE   cs.cnt >=
        (
        SELECT  MAX(cst.cnt)
        FROM    (
                SELECT  TOP 1 WITH TIES
                        p1, p2
                FROM    commonBrothers 
                ORDER BY
                        cnt DESC
                ) cbt
        JOIN    commonSisters cst
        ON      cst.p1 = cbt.p1
                AND cst.p2 = cbt.p2
        )
        AND cb.cnt >=
        (
        SELECT  MAX(cbt.cnt)
        FROM    (
                SELECT  TOP 1 WITH TIES
                        p1, p2
                FROM    commonSisters
                ORDER BY
                        cnt DESC
                ) cst
        JOIN    commonBrothers cbt
        ON      cbt.p1 = cst.p1
                AND cbt.p2 = cst.p2
        )
ORDER BY
        totalCnt DESC

If the numbers of common brothers and sisters are correlated, this query will be very fast.

This solution has two drawbacks:

  1. DML performance: if you insert or delete a record for a name shared by million brothers, the indexed view will get 2M inserts or delete. This is the price you pay for real-time query: the kind of data you are asking for cannot be easily indexed.

  2. Persons with 0 brothers or 0 sisters will not be indexed. If there's a chance that top pair will not have brothers or sisters, you should amend the last query a little.

share|improve this answer
    
Thanks for the detailed answer Quassnoi - it will take me time to understand this fully so I will let you know my feedback in a couple of days –  Victoria Jan 29 '12 at 11:09
    
When you talk about caching do you mean inside of SQL Server or with an external solution? –  Victoria Jan 29 '12 at 16:33
    
@Victoria: whatever suits you more. By caching I mean "run the query and save the top results" –  Quassnoi Jan 29 '12 at 16:52
2  
@Quassnoi there is a typo in your view's ON clause, it is missing the required UNIQUE CLUSTERED INDEX definition, and it seems you have not included the pbn.PersonId <> otherpbn.personid predicate from the original query. You might also like to comment on the likely size of the indexed view (to be added to the duplicated base tables, of course). –  Paul White Jan 29 '12 at 22:42
    
@SQLKiwi: I would better add p1.personId < p2.personId so that each pair would have only indexed once. As for the size of the indexed view, it would be SELECT POWER(COUNT(*), 2) / 2 FROM person in the worst case. Either that or run the query every time. –  Quassnoi Jan 30 '12 at 6:33
add comment

Assuming all id fields have indexes, your query looks good to me. The only way to improve performance I can think about is to use indexed view, so your derived table becomes a view with clustered index on PersonId and non-clustered index on Matches (you also need to remove pbn.PersonId =@PersonId from WHERE while creating a view.
If the view meets all the requirements, underlying tables are not updated frequently, and you are ok with solution that depends on RDMS (you can also do similar with Oracle's materialized views, but surely using different syntax), it will improve performance significantly.

share|improve this answer
    
Thanks. The underlying tables do not change that much. I tried doing that kind of join before without the personId specified (that you are suggesting for the index view) and it creates a massive result set as it's joining every user in the table with every other user in the table through up to 1 million brothers/sisters. I will try it - my only concern is if I make an indexed view out of that it will place a big load on inserts querie –  Victoria Jan 28 '12 at 16:40
    
LEFT JOIN cannot be used in indexed views. –  Quassnoi Jan 28 '12 at 17:24
    
Ok - but what if I just took the inner query and removed the where clause - to in effect join every person's brothers with everyone elses? I'm going to give that a quick try as it's a simple one to test –  Victoria Jan 29 '12 at 11:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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