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.

Good evening,

I'm currently up to try to improve the performance of some of my queries. As far as I know, statements like "IN" or "NOT IN" are even faster with a large amount of values if a subquery on an indexed field without conditions is used.

SELECT * FROM table1 WHERE field1 NOT IN (SELECT index_field FROM table2)

When it comes to use conditions at table2, the query becomes realy slow on a large amount of data.

SELECT *
FROM table1
WHERE
    field1 NOT IN (
        SELECT
            index_field
        FROM table2
        WHERE
            user_id = '2'
    )

I was thinking about using LEFT Join but when I need to to the filtering for the user_id, it also becomes slow.

How may I solve this problem? Currently, I've no clue about that.

The original query looked sth. like this

SELECT
    i.*
FROM stream_item si
LEFT JOIN user__publisher_item ui
    ON ui.user_id = 2
    && ui.item_id = si.item_id
INNER JOIN item i
    ON i.id = si.item_id
WHERE 
    si.stream_id IN (5,7,8,9,19,24,29,42,43,44)
    && ui.id IS NULL || (
        ui.`read` = 0 || ui.saved = 1
    )
GROUP BY
    si.item_id
ORDER BY
    si.`found` DESC
LIMIT 0,10

id      select_type     table   type        possible_keys                                                                           key                 key_len     ref                 rows        Extra
1       SIMPLE          si      index       PRIMARY,stream_2_item,stream_id_found                                                   stream_2_item       4           \N                  663236      Using temporary; Using filesort
1       SIMPLE          ui      eq_ref      user_id_item_id,user_2_item,user_id_read_saved_hidden,user_id_saved,user_id_hidden      user_id_item_id     8           const,si.item_id    1           Using where
1       SIMPLE          i       eq_ref      PRIMARY                                                                                 PRIMARY             4           si.item_id          1   

I have a table which represents the n:m relationship between stream and items. An unique item can be accessible via multiple streams. Based upon this i have a state-table for user dependent states of an item. Currently, the user-state-entry will only be generated, if the item was read or saved the first tim. Otherwise, there is no entry in the user_item table. In the beginning, this query was fine but now, it takes a lot of time. Even if I leave out the "INNER JOIN" it takes 7 seconds on the current tables with around 500k rows each.

The table-structure in the background is as follows:

  • stream
  • stream_item //n:m relation between stream and items
  • item //unique items
  • stream_group //user-defined groups of multiple streams
  • stream_group_streams //_n:m relation between stream_groups and streams_
  • user
  • user_item //state-table that holds the user-dependent states of an item - if there is no state, no row exists for an item

I already asked this question at Stackoverflow but added my 2 Edits with further information to late so that I haven't got an answer anymore.

share|improve this question
    
Please post the EXPLAIN –  Kermit Jul 19 '13 at 18:58
    
I added the one of the original query ... the first query was a theoretical sample, the second one a try to improve the performance which does not exist anymore. Currently I tried to resolve the performance issue by duplicating the data for every scenario via triggers. –  Dominik Habichtsberg Jul 19 '13 at 19:28
    
Hav you tried a composite index? On (index_field,user_id) and on (user_id,index_field)? –  ypercube Jul 19 '13 at 23:10
    
What's the sense of a composite key? No I haven't used it because as far as I know a key is used be the order the collumns are used in Condition and Order? –  Dominik Habichtsberg Jul 20 '13 at 7:09
    
Example: a (user_id,index_field) index can be used to efficiently get all the index_field values that are related to user_id=2. The optimizer can then compare these values with the values from the table1(field1) index. –  ypercube Jul 20 '13 at 10:47
add comment

1 Answer 1

In general you can replace a NOT IN (...) subquery with a NOT EXISTS (...) and the latter will be faster. Logically they are the same though some database optimizers handle the NOT EXISTS better as they can stop the subquery check after the first match.

In contrast, if the DB optimizer isn't smart enough to figure out what your doing and the subquery has a lot of rows, then it must buffer all the rows for each subquery before performing each NOT IN check.

Try out something like this:

SELECT *
FROM table1 a
WHERE NOT EXISTS(SELECT 1
                   FROM table2 b
                  WHERE b.user_id = 2
                    AND b.index_field = a.field1)

In this example the optimizer need only check if a single row exists for the matching subquery, including the additional filter on b.user_id = 2. It should use an index on the index_field and user_id if they are available.

share|improve this answer
    
Shouldn't I avoid subquerys as far as somewhat possible? –  Dominik Habichtsberg Jul 19 '13 at 20:22
    
Generally not for an exclusion case like this. Each lookup in table1 will end up doing an index lookup on table2 (assuming user_id and index_field are indexed) so the overall plan is O(n*log(n)). You could try it out with a LEFT JOIN table2 ... and then compare the execution plans but at best that would be the same as this. –  sehrope Jul 19 '13 at 21:46
    
Thank you for your reply ... I'm asking this because I see somehow a "facebook wall" problem. On my overview I might have several items that I have not read but which come from various sources. I don't know if I should cache all settings for all items. The problem is, that I have a multiuser system and every user has another overview with other items. Every item may have a state, but this is not necessarily. My last try was massivley replicating some part's of the data with the help of using triggers. –  Dominik Habichtsberg Jul 19 '13 at 22:54
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.