MySQL: оптимизация запроса JOIN

Question

Скажем, у меня есть две таблицы MyISAM:

tab_big:   id1, id2, id_a, ord         (5 billion records)
tab_small: id1, id2, id_b              (1 billion records)


CREATE TABLE IF NOT EXISTS `tab_big` (
  `id_a` int(10) unsigned NOT NULL,
  `id1` int(10) unsigned NOT NULL,
  `id2` int(10) unsigned NOT NULL,
  `ord` int(10) unsigned NOT NULL DEFAULT '1',
  PRIMARY KEY (`id_a`,`id1`,`id2`),
  KEY `id1` (`id1`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1;


CREATE TABLE IF NOT EXISTS `tab_small` (
  `id_b` int(10) unsigned NOT NULL,
  `id1` int(10) unsigned NOT NULL,
  `id2` int(10) unsigned NOT NULL,
  PRIMARY KEY (`id_b`,`id1`,`id2`),
  KEY `id_b` (`id_b`),
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

Все поля INT. В обеих таблицах комбинация трех значений полей идентификаторов (соответственно id1, id2, id_a и id1, id2, id_b) уникальна, поэтому для обеих я создал первичный ключ для этих трех полей.

Мне нужен эффективный запрос, который получает уникальные значения id_a из первой таблицы, где:

1. id_b во второй таблице - это заданное значение (сужение до примерно 10 тыс. Записей)
2. комбинация id1 / id2 идентична в обеих таблицах
3. id_a в первой таблице не совпадает ни с одним из полей id1, id2 в подмножестве tab_small (сужается по полю id_b); после некоторой путаницы кажется, что создание списка (около 200 идентификаторов) в php и предоставление его в виде текста работает лучше, чем добавление еще одного JOIN).

Я считаю, что это не очень хорошо кэшируется, поскольку обе таблицы постоянно меняются (строки добавляются).

Мой текущий запрос довольно прост:

SELECT tab_big.id_a FROM tab_big, tab_small
    WHERE tab_small.id_b = '$constant'
    AND tab_big.id1 = tab_small.id1 AND tab_big.id2 = tab_small.id2
    AND tab_big.id_a NOT IN ({comma delimited list of 200 ids})
    GROUP BY tab_big.id_a
    ORDER BY SUM(tab_big.ord) DESC
    LIMIT 10

Работает, но недостаточно быстро, чтобы реально его использовать. Что с этим можно сделать?

EXPLAIN говорит, что сначала получает ранжированный запрос от tab_big, а затем применяет его к tab_small (Редактирование: добавлено ниже). Я не знаю почему (EXPLAIN говорит, что запрос использует первичные ключи), но добавление индекса tab_big.id1, ​​кажется, немного помогает. Кроме того, попытка сделать все по-другому с STRAIGHT_JOIN, сначала выбирая подмножество 10k из (меньшего) tab_small, а затем используя его для поиска в (большем) tab_big, дает гораздо худшие результаты, чем по умолчанию (Edit: с небольшим набором данных, который Теперь нужно проверить, по производственным данным это будет наоборот, и EXPLAIN будет выглядеть как второй).

+----+-------------+-----------+--------+-----------------+---------+---------+-------------------------------------------+---------+----------------------------------------------+
| id | select_type | table     | type   | possible_keys   | key     | key_len | ref                                       | rows    | Extra                                        |
+----+-------------+-----------+--------+-----------------+---------+---------+-------------------------------------------+---------+----------------------------------------------+
|  1 | SIMPLE      | tab_big   | range  | PRIMARY,id1     | PRIMARY | 4       | NULL                                      | 1374793 | Using where; Using temporary; Using filesort | 
|  1 | SIMPLE      | tab_small | eq_ref | PRIMARY,id_b    | PRIMARY | 12      | const,db.tab_big.id1,db.tab_big.id2       |       1 | Using index                                  | 
+----+-------------+-----------+--------+-----------------+---------+---------+-------------------------------------------+---------+----------------------------------------------+

Для больших наборов данных EXPLAIN, вероятно, будет выглядеть примерно так (не учитывая значения 'rows' - оно взято из меньшего набора данных):

+----+-------------+-----------+------+---------------------+---------+---------+------------------+-------+----------------------------------------------+
| id | select_type | table     | type | possible_keys       | key     | key_len | ref              | rows  | Extra                                        |
+----+-------------+-----------+------+---------------------+---------+---------+------------------+-------+----------------------------------------------+
|  1 | SIMPLE      | tab_small | ref  | PRIMARY,id_b,id1    | PRIMARY | 4       | const            |   259 | Using index; Using temporary; Using filesort | 
|  1 | SIMPLE      | tab_big   | ref  | PRIMARY,id1         | id1     | 4       | db.tab_small.id1 | 25692 | Using where                                  | 
+----+-------------+-----------+------+---------------------+---------+---------+------------------+-------+----------------------------------------------+

Есть мысли?

Answer 1

Создайте следующие индексы:

CREATE INDEX ix_big_1_2_a ON tab_big (id1, id2, id_a)
CREATE UNIQUE INDEX ux_small_b_2_1 ON tab_small (id_b, id2, id1)

и попробуйте это:

SELECT  DISTINCT
        a.id_a
FROM    tab_small b
JOIN    tab_big a
ON      (a.id1, a.id2) = (b.id1, b.id2)
WHERE   b.id_b = 2
        AND a.id_a NOT IN
        (
        SELECT  id1
        FROM    tab_small b1 /* FORCE INDEX (PRIMARY) */
        WHERE   b1.id_b = 2
        )
        AND a.id_a NOT IN
        (
        SELECT  id2
        FROM    tab_small b2 /* FORCE INDEX (ux_small_b_2_1) */
        WHERE   b2.id_b = 2
        )

, который производит этот план запроса:

1, 'PRIMARY', 'b', 'ref', 'PRIMARY,ux_small_b_2_1', 'PRIMARY', '4', 'const', 1, 100.00, 'Using index; Using temporary'
1, 'PRIMARY', 'a', 'ref', 'ix_big_1_2', 'ix_big_1_2', '8', 'test.b.id1,test.b.id2', 2, 100.00, 'Using where'
3, 'DEPENDENT SUBQUERY', 'b2', 'ref', 'ux_small_b_2_1', 'ux_small_b_2_1', '8', 'const,func', 1, 100.00, 'Using index'
2, 'DEPENDENT SUBQUERY', 'b1', 'ref', 'PRIMARY', 'PRIMARY', '8', 'const,func', 1, 100.00, 'Using index'

Это не так эффективно, как могло бы быть, но я ожидаю, что это будет быстрее, чем ваш запрос.

Я закомментировал операторы FORCE INDEX, но вам может понадобиться раскомментировать их, если оптимизатор не выберет эти индексы.

Все было бы намного проще, если бы MySQL был способен сделать FULL OUTER JOIN, используя MERGE, но это не так.

Обновление:

Судя по вашей статистике, этот запрос будет более эффективным:

SELECT  id_a
FROM    (
        SELECT  DISTINCT id_a
        FROM    tab_big ad
        ) a
WHERE   id_a NOT IN
        (
        SELECT  id1
        FROM    tab_small b1 FORCE INDEX (PRIMARY)
        WHERE   b1.id_b = 2
        )
        AND id_a NOT IN
        (
        SELECT  id2
        FROM    tab_small b2 FORCE INDEX (ux_small_b_2_1)
        WHERE   b2.id_b = 2
        )
        AND EXISTS
        (
        SELECT  NULL
        FROM    tab_small be
        JOIN    tab_big ae
        ON      (ae.id1, ae.id2) = (be.id1, be.id2)
        WHERE   be.id_b = 2
                AND ae.id_a = a.id_a
        )

Работает следующим образом:

• Создает список из DISTINCT id_a (длина которого 100,000 строк)
• Отфильтровывает значения, присутствующие в подмножестве
• Для каждого значения id_a он ищет в подмножестве наличие (id_a, id1, id2). Это делается путем итерации подмножества. Поскольку вероятность найти это значение высока, скорее всего, поиск будет успешным в 10 строк или около того с начала подмножества, и EXISTS вернет этот самый момент.

Скорее всего, потребуется приблизительно 1043 * записи или около того.

Убедитесь, что используется следующий план:

1, 'PRIMARY', '<derived2>', 'ALL', '', '', '', '', 8192, 100.00, 'Using where'
5, 'DEPENDENT SUBQUERY', 'be', 'ref', 'PRIMARY,ux_small_b_2_1', 'PRIMARY', '4', 'const', 1, 100.00, 'Using index'
5, 'DEPENDENT SUBQUERY', 'ae', 'eq_ref', 'PRIMARY,ix_big_1_2', 'PRIMARY', '12', 'a.id_a,test.be.id1,test.be.id2', 1, 100.00, 'Using index'
4, 'DEPENDENT SUBQUERY', 'b2', 'ref', 'ux_small_b_2_1', 'ux_small_b_2_1', '8', 'const,func', 1, 100.00, 'Using index'
3, 'DEPENDENT SUBQUERY', 'b1', 'ref', 'PRIMARY', 'PRIMARY', '8', 'const,func', 1, 100.00, 'Using index'
2, 'DERIVED', 'ad', 'range', '', 'PRIMARY', '4', '', 10, 100.00, 'Using index for group-by'

, самая важная часть - Using index for group-by в последнем ряду.

Answer 2

Я бы предложил поместить индекс во все четыре столбца, которые являются частью объединения (либо четыре отдельных индекса в столбце tb.id1, ​​tb.id2, ts.id1 и ts.id2, либо два в tb.id1 / id2 и ts.id1 / id2). Тогда посмотрите, даст ли это вам лучшую производительность. (Я думаю, что это так, но вы никогда не узнаете, если не попробуете.)

---

ПРИМЕЧАНИЕ. Следующая идея не работает, но я оставил ее, поэтому комментарии по-прежнему имеют смысл.

Кроме того, вместо использования списка, сгенерированного PHP, вы не можете также выразить свое ограничение (3) в условии соединения (или, если хотите, в предложении where)? (Аналогично тому, что предложил rexem)

SELECT tb.id_a
  FROM TAB_BIG tb
  JOIN TAB_SMALL ts ON ts.id1 = tb.id1
                 AND ts.id2 = tb.id2
                 AND tb.id1 <> ts.id_a
                 AND tb.id2 <> ts.id_a
 WHERE ts.id_b = ?

Но это больше для ясности и простоты, чем для производительности. (Также обратите внимание, что для дополнительных условий может потребоваться другой индекс для id_a и, возможно, отдельные индексы для tb.id1 и tb.id2.)

Answer 3

Вы пробовали tab_small LEFT JOIN tab_big? Также вы можете создавать индексы по полям tab_small.id_b и tab_big.id_a