Правильная ссылка на эту страницу
http://az-design.ru/Support/DataBase/SQL/SQL0003.shtml

Еще один круглый конь в вакууме
или очередное издевательство над Firebird.

Для тестирования применялся следующий вариант:

Firebird-2.0.1.12855-1-Win32 SS

AMD Sempron 2.0 ГГц, 768 Мб

А также IBExpert 2008.04.28

Задача №1: Имеются две таблицы

CREATE TABLE A (
    ID     BIGINT NOT NULL,
    INFO   VARCHAR(100));
ALTER TABLE A ADD CONSTRAINT PK_A PRIMARY KEY (ID);
CREATE TABLE B (
    ID      BIGINT NOT NULL,
    OTHER   BIGINT NOT NULL,
    INFO    VARCHAR(100));
ALTER TABLE B ADD CONSTRAINT PK_B PRIMARY KEY (ID, OTHER);

Необходимо выбрать из таблицы A значения столбца ID, которые отсутствуют в соответствующем столбце таблицы B. Структура таблицы B подразумевает возможность дублирования в столбце ID.

Для тестирования таблицы были заполнены следующим образом:

A — 10000 записей
Столбец ID — числа от 1 до 10000 с шагом 1 в произвольном порядке
Столбец INFO — произвольный текст

Таблица B — 49847 записей (т.к. некоторое кол-во записей пришлось удалить, чтобы задача имела не пустое решение)
ID, OTHER — произвольные числа от 1 до 10000
INFO — произвольный текст

После всех экспериментов с вариантами заполнения таблиц был выполнен backup и restore в новую БД.

Вся информация для сравнения производительности взята из анализа производительности IBExprt'а

Запросы выполнялись в режиме выборки всех записей.

Варианты решения №1.1 — «в лоб»

SELECT A.ID
  FROM A
 WHERE A.ID NOT IN (SELECT B.ID FROM B)
PLAN (B NATURAL)
PLAN (A NATURAL)
	
Prepare Execute Avg fetch time Read Writes Fetches
0ms 2m 17s 197ms 952.76 ms 65 0 202 665 995

Table Name Records Total Indexed reads Non-Indexed reads
A 10 000 0 10 000
B 49 847 0 100 647 402

Испугало слово NATURAL в анализе плана запроса. Заставим сервер использовать индекс принудительно.

Варианты решения №1.1.б — «Обхитрить оптимизатор»

SELECT A.ID
  FROM A
 WHERE A.ID NOT IN (SELECT B.ID FROM B ORDER BY B.ID)
PLAN (B ORDER PK_B)
PLAN (A NATURAL)
Prepare Execute Avg fetch time Read Writes Fetches
10ms 14m 35s 999ms 6 083,33 ms 55 0 760 080 553

Table Name Records Total Indexed reads Non-Indexed reads
A 10 000 0 10 000
B 49 847 253 254 707 0

При попытке использовать индекс ситуация сильно ухудшилась. Может нужно попробовать облегчить перебор и сравнивать только с уникальными?

Варианты решения №1.1.в — «Упростить перебор»

SELECT A.ID
  FROM A
 WHERE A.ID NOT IN (SELECT DISTINCT B.ID FROM B)
PLAN SORT ((B NATURAL))
PLAN (A NATURAL)
Prepare Execute Avg fetch time Read Writes Fetches
40ms 34m 40s 953ms 14 451.06 ms 63 0 1 983 461 606

Table Name Records Total Indexed reads Non-Indexed reads
A 10 000 0 10 000
B 49 847 0 498 470 000

Похоже пора прекращать возиться с IN.

Варианты решения №1.2 — «JOIN»

SELECT A.ID
  FROM A
  LEFT JOIN B ON A.ID = B.ID
  WHERE B.ID IS NULL
PLAN JOIN (A NATURAL, B INDEX (PK_B))
Prepare Execute Avg fetch time Read Writes Fetches
10 ms 470ms 3.26 ms 460 0 149 890

Table Name Records Total Indexed reads Non-Indexed reads
A 10 000 0 10 000
B 49 847 49 847 0

Менее полсекунды — уже приемлемое время. Также ясно видно, что каждая запись читалась по одному разу.

Варианты решения №1.3 — «EXISTS»

SELECT A.ID
  FROM A
 WHERE NOT EXISTS(SELECT B.ID FROM B WHERE B.ID = A.ID)
PLAN (B INDEX (PK_B))
PLAN (A NATURAL)
Prepare Execute Avg fetch time Read Writes Fetches
0ms 130ms 0.90 ms 0 0 69 900

Table Name Records Total Indexed reads Non-Indexed reads
A 10 000 0 10 000
B 49 847 9 856 0

Результат еще лучше. Из подчиненной таблицы читались только уникальные данные, и только по одному разу.

Задача №2: добавлена еще одна таблица C, идентичная таблице B по структуре, способу заполнения и количеству записей. В таблицах B и C нет двух одинаковых записей. Задача аналогична предыдущей — выбрать все значения столбца ID таблицы A, которых нет на в B ни в C.



Варианты решения №2.1 — «в лоб»

SELECT A.ID
  FROM A
 WHERE A.ID NOT IN (SELECT B.ID FROM B)
   AND A.ID NOT IN (SELECT C.ID FROM C)
PLAN (B NATURAL)
PLAN (C NATURAL)
PLAN (A NATURAL)
Prepare Execute Avg fetch time Read Writes Fetches
0ms 2m 17s 558ms 1 375.58 ms 337 0 213 310 476

Table Name Records Total Indexed reads Non-Indexed reads
A 10 000 0 10 000
B 49 847 0 100 647 402
C 49 847 0 5 286 473

Как видно ситуация не сильно изменилась по сравнению с предыдущим случаем (№1.1)

Вариант

SELECT A.ID
  FROM A
 WHERE A.ID NOT IN (SELECT B.ID FROM B
                    UNION ALL
                    SELECT C.ID FROM C)

Дал те же результаты по количеству чтений, но на 20% медленнее.

Варианты решения №2.2 — «JOIN»

SELECT A.ID
  FROM A
  LEFT JOIN B ON A.ID = B.ID
  LEFT JOIN C ON A.ID = C.ID
 WHERE B.ID IS NULL AND C.ID IS NULL
PLAN JOIN (JOIN (A NATURAL, B INDEX(PK_B)), C INDEX (PK_C))
Prepare Execute Avg fetch time Read Writes Fetches
10 ms 1s 81ms 10,81 ms 57 0 799 877

Table Name Records Total Indexed reads Non-Indexed reads
A 10 000 0 10 000
B 49 847 49 847 0
С 49 847 249 857 0

Опять время на прядок меньше чем с IN, но из таблицы C все равно слишком много чтений.

Варианты решения №2.2б — «JOIN и UNION»

SELECT A.ID
  FROM A
  LEFT JOIN(SELECT B.ID FROM B
            UNION ALL
            SELECT C.ID FROM C) AS B ON B.ID = A.ID
 WHERE B.ID IS NULL
PLAN JOIN (A NATURAL(B B INDEX (PK_B))
PLAN (B C INDEX (PK_C)))
Prepare Execute Avg fetch time Read Writes Fetches
0ms 501ms 501ms 0 0 279 632

Table Name Records Total Indexed reads Non-Indexed reads
A 10 000 0 10 000
B 49 847 49 847 0
С 49 847 49 847 0

Еще быстрее.

Варианты решения №2.2в — «Последовательный JOIN»

SELECT A.ID
  FROM (SELECT A.ID
          FROM A
          LEFT JOIN B ON B.ID = A.ID
         WHERE B.ID IS NULL) A
  LEFT JOIN C ON C.ID = A.ID
 WHERE C.ID IS NULL
PLAN JOIN (JOIN (A A NATURAL, A B INDEX (PK_B)), C INDEX (PK_C))
Prepare Execute Avg fetch time Read Writes Fetches
0ms 231ms 2.31ms 0 0 150 831

Table Name Records Total Indexed reads Non-Indexed reads
A 10 000 0 10 000
B 49 847 49 847 0
С 49 847 258 0

А такой вариант еще лучше.

Варианты решения №2.3 — «EXISTS»

SELECT A.ID
  FROM A
 WHERE NOT EXISTS (SELECT B.ID FROM B WHERE B.ID = A.ID)
   AND NOT EXISTS (SELECT C.ID FROM C WHERE C.ID = A.ID)
PLAN (B INDEX (PK_B))
PLAN (C INDEX (PK_C))
PLAN (A NATURAL)
Prepare Execute Avg fetch time Read Writes Fetches
0ms 130ms 1.30 ms 0 0 70 421

Table Name Records Total Indexed reads Non-Indexed reads
A 10 000 0 10 000
B 49 847 9 856 0
С 49 847 44 0

А этот вариант оказался самым эффективным как и в случае задачи №1, и по времени выполнения не отличается от первого варианта.
Как и в случае 2.1 подзапрос с UNION дал то же количество чтений, тот же план, и опять медленнее – 140ms.

SELECT A.ID
  FROM A
 WHERE NOT EXISTS (SELECT B.ID FROM B WHERE B.ID = A.ID
                   UNION ALL
                   SELECT C.ID FROM C WHERE C.ID = A.ID)

Задача №3: Аналогично первой, но вместо таблицы B используется таблица D, совпадающая по структуре с A. Для тестирования таблица D была заполнена данными из таблицы B.

Варианты решения №3.1 — «IN»

SELECT A.ID
  FROM A
 WHERE A.ID NOT IN (SELECT D.ID FROM D)
PLAN (D NATURAL)
PLAN (A NATURAL)
Prepare Execute Avg fetch time Read Writes Fetches
10ms 57s 783ms 401.27 ms 0 0 100 305 575

Table Name Records Total Indexed reads Non-Indexed reads
A 10 000 0 10 000
D 9 856 0 49 994 560

Как обычно этот вариант дает неприемлемое время.

Варианты решения №3.2 — «JOIN»

SELECT A.ID
  FROM A
  LEFT JOIN D ON A.ID = D.ID
 WHERE D.ID IS NULL
PLAN JOIN (A NATURAL, D INDEX (PK_D))
Prepare Execute Avg fetch time Read Writes Fetches
0 ms 90ms 0.63ms 0 0 69 852

Table Name Records Total Indexed reads Non-Indexed reads
A 10 000 0 10 000
D 9 856 9 856 0

При наличии уникального индекса по полю ID результат нмного лучше случая 2.2б

Варианты решения №3.3 — «EXISTS»

SELECT A.ID
  FROM A
 WHERE NOT EXISTS(SELECT D.ID FROM D WHERE D.ID = A.ID)
PLAN (D INDEX (PK_D))
PLAN (A NATURAL)
Prepare Execute Avg fetch time Read Writes Fetches
0 ms 90ms 0.63ms 0 0 69 852

Table Name Records Total Indexed reads Non-Indexed reads
A 10 000 0 10 000
D 9 856 9 856 0

Абсолютно эквивалентно случаю с JOIN

Задача №4: Смесь второй и третьей — добавляем таблицу E, заполняя ее из таблицы C.

Варианты решения №4.1 — «IN»

SELECT A.ID
  FROM A
 WHERE A.ID NOT IN (SELECT D.ID FROM D)
   AND A.ID NOT IN (SELECT E.ID FROM E)
PLAN (D NATURAL)
PLAN (E NATURAL)
PLAN (A NATURAL)
Prepare Execute Avg fetch time Read Writes Fetches
10ms 59s 196ms 591.96ms 0 0 102 705 364

Table Name Records Total Indexed reads Non-Indexed reads
A 10 000 0 10 000
D 9 856 0 49 994 560
E 9 856 0 1 196 120

Как обычно.

Варианты решения №4.2 — «JOIN»

SELECT A.ID
  FROM (SELECT A.ID FROM A
          LEFT JOIN D ON D.ID = A.ID
         WHERE D.ID IS NULL) A
  LEFT JOIN E ON E.ID = A.ID
 WHERE E.ID IS NULL
PLAN JOIN (JOIN (A A NATURAL, A D INDEX(PK_D)), E INDEX (PK_E))
Prepare Execute Avg fetch time Read Writes Fetches
0ms 80ms 2.96ms 0 0 70 373

Table Name Records Total Indexed reads Non-Indexed reads
A 10 000 0 10 000
D 9 856 9 856 0
E 9 856 44 0

Наличие уникальных индексов сильно ускоряет процесс.

Варианты решения №4.3 — «EXISTS»

SELECT A.ID
  FROM A
 WHERE NOT EXISTS (SELECT D.ID FROM D WHERE D.ID = A.ID)
   AND NOT EXISTS (SELECT E.ID FROM E WHERE E.ID = A.ID)
PLAN (D INDEX (PK_D))
PLAN (E INDEX (PK_E))
PLAN (A NATURAL)
Prepare Execute Avg fetch time Read Writes Fetches
0ms 80ms 0.80 ms 0 0 70 373

Table Name Records Total Indexed reads Non-Indexed reads
A 10 000 0 10 000
D 9 856 9 856 0
E 9 856 44 0

Как и в случае задачи №3 EXISTS и JOIN работают эквивалентно.

По непонятным для меня причинам запрос

SELECT A.ID
  FROM A
 WHERE NOT EXISTS (SELECT D.ID FROM D WHERE D.ID = A.ID
                   UNION ALL
                   SELECT E.ID FROM E WHERE E.ID = A.ID)

опять дал то же количество чтений, но опять медленнее — 90ms.

Некоторые выводы:

  1. Оптимизатор упорно отказывается что-либо делать с предикатом IN. Даже наличие уникального индекса не дает никаких улучшений.
  2. NATURAL — не всегда плохо. Если нужно обработать все записи, то индекс не может ускорить процесс, а зачастую только замедляет.
  3. В случае проверки вхождения в несколько таблиц нужно правильно выбирать стратегию — какую таблицу проверять первой, но это тема отдельного исследования.
  4. Во всех тестах EXISTS показал себя не хуже JOIN, а при отсутствии уникальности — намного лучше.
  5. Для решения данных задач UNION не смог оказать содействия.

© 12.05.2008, Борисов Г.В.

Оглавление
Главная страница




Дата последнего изменения:
Thursday, 21-Aug-2014 09:10:44 MSK


Постоянный адрес статьи:
http://az-design.ru/Support/DataBase/SQL/SQL0003.shtml