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.

Now the situation due to which this question came to me. Schema is

    Table User_Read_Book
       user_id | book_id 

Now I want to get users who have read certain books. Say give me users who have read book number 1 and 2. Number of books to test can go upto 10.

First query I wrote :

Select user_id from User_Read_Book Where book_id In (1,2) Group by user_id Having count(book_id) = 2

Second query:

Select  user_id from User_Read_Book as U join User_Read_Book as U1 On
 U.user_id = U1.user_id And U1.book_id = 1 where U.book_id = 2

As said in this answer http://stackoverflow.com/a/621891 that prefer joins in case of group by and having I did the second query.

But my question is which is better query when number to match up are large. Say when you have to find users who have read 7 books

   Having Count(book_id) = 7
   or
   6 joins to the same table.

I know this question is best answered when tested on large and real time data. Still what is the opinion of experts on this?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

With 7 books, my guess would be that 7 joins is faster than GROUP BY / HAVING.

But it depends on the DBMS, the version, the optimizer's settings, the database settings, the RAM you have, the hard disks' performance, the indexes fragmentation, the overall pressure on the server and possibly several other parameters. Even more, even all the previous are set still, it depends on your data (and its distribution) and the specific parameters of the query. For example, if the 7 books are the 7 books of Harry Potter and all your users are Harry Potter's fans, then the GROUP BY/HAVING may be faster.

Plus, you shouldn't trust others, however experts they may (look to) be, when you can test. Why don't you test - with your data in your server and your settings - the performance of both ways, using variable number of books (and titles)?

Check also this question (with a similar query) where several other (more than 10) ways are shown (and benchmarked in PostgrSQL): How to filter SQL results in a has-many-through relation


UPDATE

explanation of the "guess" that 7 Joins are usually better than GROUP BY / HAVING:

Imagine you have a million users and about a million books. Now, on average, a user has read 100 books (in your database, totally fictional data and distribution). So, the table has about 100M rows.

Now, the GROUP BY query would have something like WHERE book_id IN (1,2,3,4,5,6,7). Lets assume that book_id=1 is the most popular (the Bible) and has about 100K readers and the other 6 are not so popular, having between 100 to 1000 readers each. This would limit the rows to be grouped to something between 100K and 106K. That translates (roughly) to the SQL engine reading 106K data from the proper index and then doing the GROUP BY user_id. So, (it will probably choose to use the (user_id, book_id) index), and it will do about 100K calculations of the COUNT(book_id) - and reject anyone that is not 7.

In the 7 JOIN query, it has more options. The optimizer may choose to use the other index, the (book_id, user_id) one. Imagine "taking out" 7 smaller parts of this big index, the (1, user_id) part (remember: 100K data (user_ids) in it), the (2, user_id) part (less than 1000 data in here), ..., up to the (7, user_id) part (less than 1000 data in here, too). So now, it has to somehow combine those 7 index-parts (which is just 7 lists of userids) and find which userids are in ALL of the 7 lists. There are some clever algorithms that do just that, without having to do a whole reading (full scan) of the 7 lists. Just notice that even a dumb algorithm that combines first the 6 smaller lists, may end up with only a handful of userids (lets say just 1). To find if this 1 user_id is in the big (first) list, only a binary search is needed (remember it's not really a list, it's an index and that's what is good about indexes, you can search fast in them). So, even if there are only 100 user_ids, 100 searches in the big 100K list/index will only need less than 100*17 operation ( log(100K) ~= 17 ). Which is 1700 operations, much less than the GROUP BY 100K operations. And no COUNT(*) is needed.

Therefore, with the Joins, if most books are not very popular (or just one book and we get lucky), the query will be quite efficient because it will have to look at the index on a very small number of places.
(Another thought is that with the Group By method, the query has calculated - before rejecting them - how many books have read all those users that have read 1 or 2 or ... or 6 books. But we don't care if they read 1 or 6. We just need to know if they have read all 7 !)

The situation is different off course if all the 7 chosen books are very popular. Now, the 7 index parts are all big and combining them may be less efficient than using the GROUP BY method which uses only one pass at one index.
(And the other thought says that the Group By is efficient now because almost all Count calculations will be a 7, so a very small number of calculations is wasted)

share|improve this answer
    
I am using Postgresql. So GROUP BY works better if the data is related and more meaningful. Random data makes it slow. Right? –  codecool Mar 29 '12 at 17:09
    
No, randomness is not the issue here (if I understand what you mean). Updated the answer. –  ypercube Mar 29 '12 at 19:16
    
So it depends upon popularity and size of the individual ids data. That is an awesome explanation. Thanks –  codecool Mar 29 '12 at 19:24
    
@codecool: Yeah, data distribution can affect performance. –  ypercube Mar 29 '12 at 19:31
    
Also note that if you want to find readers that have read at least 4 - out of 7 books, then the GROUP BY method is almost the only way to go. –  ypercube Mar 29 '12 at 19:33

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.