Any possibility to speed up WHERE IN or replace it with faster alternative?

Question

I am trying to speed up select in query below where I have over 1000 items in WHERE IN

table:

CREATE TABLE `user_item` (
  `user_id` int(11) unsigned NOT NULL,
  `item_id` int(11) unsigned NOT NULL,
  PRIMARY KEY (`user_id`,`item_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

query:

SELECT
    item_id
FROM
    user_item
WHERE
    user_id = 2
    AND item_id IN(3433456,67584634,587345,...)

With 1000 items in IN list, query takes about 3 seconds to execute. is there any optimization that can be done in this case? There can be billions of rows in this table. Is there an alternative to doing this faster be it with another DB or programming method?

UPDATE:

Here's results of explain:

If I have 999 items in the IN(...) statement:

+------+-------------+----------+-------+---------------+---------+---------+------+------+--------------------------+
| id   | select_type | table    | type  | possible_keys | key     | key_len | ref  | rows | Extra                    |
+------+-------------+----------+-------+---------------+---------+---------+------+------+--------------------------+
|    1 | SIMPLE      | user_item | range | PRIMARY       | PRIMARY | 8       | NULL |  999 | Using where; Using index |
+------+-------------+----------+-------+---------------+---------+---------+------+------+--------------------------+

If I have 1000 items in IN(...) statement:

+------+--------------+-------------+--------+---------------+---------+---------+--------------------+------+--------------------------+
| id   | select_type  | table       | type   | possible_keys | key     | key_len | ref                | rows | Extra                    |
+------+--------------+-------------+--------+---------------+---------+---------+--------------------+------+--------------------------+
|    1 | PRIMARY      | <subquery2> | ALL    | distinct_key  | NULL    | NULL    | NULL               | 1000 |                          |
|    1 | PRIMARY      | user_item    | eq_ref | PRIMARY       | PRIMARY | 8       | const,tvc_0._col_1 |    1 | Using where; Using index |
|    2 | MATERIALIZED | <derived3>  | ALL    | NULL          | NULL    | NULL    | NULL               | 1000 |                          |
|    3 | DERIVED      | NULL        | NULL   | NULL          | NULL    | NULL    | NULL               | NULL | No tables used           |
+------+--------------+-------------+--------+---------------+---------+---------+--------------------+------+--------------------------+

Update 2

I want to explain why I need to do above:

I want to give the user the ability to list items ordered by sort_criteria_1, sort_criteria_2 or sort_criteria_3 and exclude from the list those items that have been marked by given (n) users in the user_item table.

Here's sample schema:

CREATE TABLE `user` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(45) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

CREATE TABLE `item` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `file` varchar(45) NOT NULL,
  `sort_criteria_1` int(11) DEFAULT NULL,
  `sort_criteria_2` int(11) DEFAULT NULL,
  `sort_criteria_3` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_sc1` (`sort_criteria_1`),
  KEY `idx_sc2` (`sort_criteria_2`),
  KEY `idx_sc3` (`sort_criteria_3`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

CREATE TABLE `user_item` (
  `user_id` int(11) NOT NULL,
  `item_id` int(11) NOT NULL,
  PRIMARY KEY (`user_id`,`item_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Here's how I would get items ordered by sort_criteria_2 excluding ones that have record by users (300, 6, 1344, 24) in user_item table:

SELECT
    i.id,
FROM
    item i
    LEFT JOIN user_item ui1 ON (i.id = ui1.item_id AND ui1.user_id = 300)
    LEFT JOIN user_item ui2 ON (i.id = ui2.item_id AND ui2.user_id = 6)
    LEFT JOIN user_item ui3 ON (i.id = ui3.item_id AND ui3.user_id = 1344)
    LEFT JOIN user_item ui4 ON (i.id = ui4.item_id AND ui4.user_id = 24)
WHERE
    ui1.item_id IS NULL
    AND ui2.item_id IS NULL
    AND ui3.item_id IS NULL
    AND ui4.item_id IS NULL
ORDER BY
    v.sort_criteria_2
LIMIT
    800

Main problem with above approach is that more users I'm filtering by, more expensive query gets. I want the toll for filtering to be paid by client browser. So I would send list of items and list of matching user_item records per user to the client to filter by. This would help with sharding as well, since I would not have to have user_item tables or set of records on the same machine.

Answer 1

It's hard to tell exactly, but there could be lag on parsing your huge query because of many constant item_id values.

1. Have you tried getting just all the values by user_id ? As this field is first (main) in the PRIMARY KEY, relevant index would still be used.

2. Have you tried replacing constant list with a subquery ? Maybe you're interested in items of specific type, for example.

3. Make sure that you use Prepared statement concept - at least if your database and language support it. This would protect your code from possible SQL injections and enable database built-in query caching (if your database supports it).

Answer 2

Instead of putting the 1000 item_id's into IN-clause, you could put them into temporary table with index and join it with the user_item-table.

If you also have an index with both user_id and item_id, that would make the query fastest that it gets. The rest depends on the data distribution.