Sql: Оптимизация МЕЖДУ пунктом
Я записал оператор, который занимает почти час для выполнения так, я прошу помогать так, я могу добраться, чтобы сделать это быстрее. Таким образом, здесь мы идем:
Я делаю внутреннее объединение двух таблиц:
У меня есть много временных интервалов, представленных интервалами, и я хочу получить данные меры из мер только в тех интервалах.
intervals: имеет два столбца, каждый - время начала, другой время окончания интервала (количество строк = 1295)
measures: имеет два столбца, один с мерой, другим со временем, которым мера была сделана (количество строк = один миллион)
Результатом, который я хочу получить, является таблица с в первом столбце мера, затем время, мера была сделана, начинание/время окончания продуманного интервала (это будет повторено для строки со временем в продуманном диапазоне),
Вот мой код:
select measures.measure as measure, measures.time as time, intervals.entry_time as entry_time, intervals.exit_time as exit_time
from
intervals
inner join
measures
on intervals.entry_time<=measures.time and measures.time <=intervals.exit_time
order by time asc
Спасибо
9 ответов
Ваш SQL эквивалентен:
select m.measure. m.time,
i.entry_time, i.exit_time
from intervals i
join measures m
on m.time Between i.entry_time And i.exit_time
order by time asc
Единственное, что я могу предложить, это убедиться, что в m.Time есть индекс. Затем, если это недостаточно улучшит производительность, попробуйте добавить индексы и на i.Start_Time, и на i.End_Time
.Это довольно распространенная проблема.
Простые B-Tree индексы не подходят для таких запросов:
SELECT measures.measure as measure,
measures.time as time,
intervals.entry_time as entry_time,
intervals.exit_time as exit_time
FROM intervals
JOIN measures
ON measures.time BETWEEN intervals.entry_time AND intervals.exit_time
ORDER BY
time ASC
Индекс хорош для поиска значений в заданных границах, как этот:
, но не для поиска границ, содержащих заданное значение, как этот:
Эта статья в моем блоге объясняет проблему более подробно:
(модель вложенных множеств имеет дело с аналогичным типом предиката).
Индекс можно сделать на time, таким образом интервалы будут лидировать в соединении, время диапазона будет использоваться внутри вложенных циклов. Это потребует сортировки по времени .
Вы можете создать пространственный индекс на интервалах (доступно в MySQL, используя хранилище MyISAM), который будет включать в себя start и end в одном столбце геометрии. Таким образом, меры могут привести к соединению, и сортировка не потребуется.
Пространственные индексы, однако, более медленные, поэтому это будет эффективно только в том случае, если у вас мало мер, но много интервалов.
Поскольку у вас мало интервалов, но много мер, просто убедитесь, что у вас есть индекс на measures.time:
CREATE INDEX ix_measures_time ON measures (time)
Обновление:
Вот пример сценария для тестирования:
BEGIN
DBMS_RANDOM.seed(20091223);
END;
/
CREATE TABLE intervals (
entry_time NOT NULL,
exit_time NOT NULL
)
AS
SELECT TO_DATE('23.12.2009', 'dd.mm.yyyy') - level,
TO_DATE('23.12.2009', 'dd.mm.yyyy') - level + DBMS_RANDOM.value
FROM dual
CONNECT BY
level <= 1500
/
CREATE UNIQUE INDEX ux_intervals_entry ON intervals (entry_time)
/
CREATE TABLE measures (
time NOT NULL,
measure NOT NULL
)
AS
SELECT TO_DATE('23.12.2009', 'dd.mm.yyyy') - level / 720,
CAST(DBMS_RANDOM.value * 10000 AS NUMBER(18, 2))
FROM dual
CONNECT BY
level <= 1080000
/
ALTER TABLE measures ADD CONSTRAINT pk_measures_time PRIMARY KEY (time)
/
CREATE INDEX ix_measures_time_measure ON measures (time, measure)
/
Этот запрос:
SELECT SUM(measure), AVG(time - TO_DATE('23.12.2009', 'dd.mm.yyyy'))
FROM (
SELECT *
FROM (
SELECT /*+ ORDERED USE_NL(intervals measures) */
*
FROM intervals
JOIN measures
ON measures.time BETWEEN intervals.entry_time AND intervals.exit_time
ORDER BY
time
)
WHERE rownum <= 500000
)
использует NESTED LOOPS и возвращается в 1. 7 секунд.
Этот запрос:
SELECT SUM(measure), AVG(time - TO_DATE('23.12.2009', 'dd.mm.yyyy'))
FROM (
SELECT *
FROM (
SELECT /*+ ORDERED USE_MERGE(intervals measures) */
*
FROM intervals
JOIN measures
ON measures.time BETWEEN intervals.entry_time AND intervals.exit_time
ORDER BY
time
)
WHERE rownum <= 500000
)
использует MERGE JOIN и мне пришлось остановить его через 5 минут.
Обновление 2:
Скорее всего, вам придется заставить движок использовать правильный порядок следования таблиц в соединении, используя подсказку вроде этой:
SELECT /*+ LEADING (intervals) USE_NL(intervals, measures) */
measures.measure as measure,
measures.time as time,
intervals.entry_time as entry_time,
intervals.exit_time as exit_time
FROM intervals
JOIN measures
ON measures.time BETWEEN intervals.entry_time AND intervals.exit_time
ORDER BY
time ASC
Оптимизатор Oracle не достаточно умен, чтобы увидеть, что интервалы не пересекаются. Поэтому он, скорее всего, будет использовать measures в качестве ведущей таблицы (что было бы разумным решением, если бы интервалы пересекались).
Обновление 3:
WITH splits AS
(
SELECT /*+ MATERIALIZE */
entry_range, exit_range,
exit_range - entry_range + 1 AS range_span,
entry_time, exit_time
FROM (
SELECT TRUNC((entry_time - TO_DATE(1, 'J')) * 2) AS entry_range,
TRUNC((exit_time - TO_DATE(1, 'J')) * 2) AS exit_range,
entry_time,
exit_time
FROM intervals
)
),
upper AS
(
SELECT /*+ MATERIALIZE */
MAX(range_span) AS max_range
FROM splits
),
ranges AS
(
SELECT /*+ MATERIALIZE */
level AS chunk
FROM upper
CONNECT BY
level <= max_range
),
tiles AS
(
SELECT /*+ MATERIALIZE USE_MERGE (r s) */
entry_range + chunk - 1 AS tile,
entry_time,
exit_time
FROM ranges r
JOIN splits s
ON chunk <= range_span
)
SELECT /*+ LEADING(t) USE_HASH(m t) */
SUM(LENGTH(stuffing))
FROM tiles t
JOIN measures m
ON TRUNC((m.time - TO_DATE(1, 'J')) * 2) = tile
AND m.time BETWEEN t.entry_time AND t.exit_time
Этот запрос разделяет ось времени на диапазоны и использует HASH JOIN для объединения мер и временных меток на значениях диапазона, с последующей точной фильтрацией.
Смотрите эту статью в моем блоге для более детального объяснения того, как она работает:
Подводя итог: ваш запрос выполняется с полным набором МЕРОПРИЯТИЙ. Время каждой записи MEASURES совпадает с временем записи INTERVALS. Если окно времени INTERVALS примерно похоже на окно MEASURES, то Ваш запрос также выполняется против полного набора INTERVALS, в противном случае он выполняется против подмножества.
Почему это важно, потому что это уменьшает ваши возможности для настройки, так как полное сканирование таблицы, скорее всего, будет самым быстрым способом получить все строки. Таким образом, если ваши реальные MEASURES или INTERVALS таблицы имеют гораздо больше столбцов, чем вы даете нам, маловероятно, что любые индексы даст много преимуществ.
Возможные стратегии:
- нет индексов вообще
- индекс на MEASURES (ВРЕМЯ,МЕРА)
- индекс на MEASURES (ВРЕМЯ)
- нет индекса на MEASURES
- индекс на INTERVALS (ENTRY_TIME, EXIT_TIME)
- индекс на INTERVALS (ENTRY_TIME)
- нет индекса на INTERVALS
- параллельный запрос
Я не буду представлять тестовые случаи для всех перестановок, так как результаты оказались практически такими, какими мы ожидали. Вот тестовые данные. Как видите, я использую несколько большие наборы данных. Окно INTERVALS больше, чем окна MEASURES, но не на много. Интервал составляет 10000 секунд, а меры принимаются каждые 15 секунд.
SQL> select min(entry_time), max(exit_time), count(*) from intervals;
MIN(ENTRY MAX(EXIT_ COUNT(*)
--------- --------- ----------
01-JAN-09 20-AUG-09 2001
SQL> select min(ts), max(ts), count(*) from measures;
MIN(TS) MAX(TS) COUNT(*)
--------- --------- ----------
02-JAN-09 17-JUN-09 1200001
SQL>
NB В своих тестовых данных я предположил, что INTERVAL записи не пересекаются. Это имеет важное коррозионное: запись MEASURES присоединяется только к одному INTERVAL.
Benchmark
Here is the benchmark with no indexes.
SQL> exec dbms_stats.gather_table_stats(user, 'MEASURES', cascade=>true)
PL/SQL procedure successfully completed.
SQL> exec dbms_stats.gather_table_stats(user, 'INTERVALS', cascade=>true)
PL/SQL procedure successfully completed.
SQL> set timing on
SQL>
SQL> select m.measure
2 , m.ts as "TIME"
3 , i.entry_time
4 , i.exit_time
5 from
6 intervals i
7 inner join
8 measures m
9 on ( m.ts between i.entry_time and i.exit_time )
10 order by m.ts asc
11 /
1200001 rows selected.
Elapsed: 00:05:37.03
SQL>
MEASURES tests
Теперь давайте построим уникальный индекс на INTERVALS (ENTRY_TIME, EXIT_TIME) и попробуем различные стратегии индексации MEASURES. Во-первых, индекс MEASURES ВРЕМЯ только столбец.
SQL> create index meas_idx on measures (ts)
2 /
Index created.
SQL> exec dbms_stats.gather_table_stats(user, 'MEASURES', cascade=>true)
PL/SQL procedure successfully completed.
SQL>
SQL> set autotrace traceonly exp
SQL>
SQL> set timing on
SQL>
SQL> select m.measure
2 , m.ts as "TIME"
3 , i.entry_time
4 , i.exit_time
5 from
6 intervals i
7 inner join
8 measures m
9 on ( m.ts between i.entry_time and i.exit_time )
10 order by m.ts asc
11 /
1200001 rows selected.
Elapsed: 00:05:20.21
SQL>
Теперь давайте индекс MEASURES.TIME и MEASURE столбцов
SQL> drop index meas_idx
2 /
Index dropped.
SQL> create index meas_idx on measures (ts, measure)
2 /
Index created.
SQL> exec dbms_stats.gather_table_stats(user, 'MEASURES', cascade=>true)
PL/SQL procedure successfully completed.
SQL> select m.measure
2 , m.ts as "TIME"
3 , i.entry_time
4 , i.exit_time
5 from
6 intervals i
7 inner join
8 measures m
9 on ( m.ts between i.entry_time and i.exit_time )
10 order by m.ts asc
11 /
1200001 rows selected.
Elapsed: 00:05:28.54
SQL>
Теперь без индекса на MEASURES (но все же индекс на INTERVALS)
SQL> drop index meas_idx
2 /
Index dropped.
SQL> exec dbms_stats.gather_table_stats(user, 'MEASURES', cascade=>true)
PL/SQL procedure successfully completed.
SQL> select m.measure
2 , m.ts as "TIME"
3 , i.entry_time
4 , i.exit_time
5 from
6 intervals i
7 inner join
8 measures m
9 on ( m.ts between i.entry_time and i.exit_time )
10 order by m.ts asc
11 /
1200001 rows selected.
Elapsed: 00:05:24.81
SQL>
Так какая разница делает параллельный запрос ?
SQL> select /*+ parallel (4) */
2 m.measure
3 , m.ts as "TIME"
4 , i.entry_time
5 , i.exit_time
6 from
7 intervals i
8 inner join
9 measures m
10 on ( m.ts between i.entry_time and i.exit_time )
11 order by m.ts asc
12 /
1200001 rows selected.
Elapsed: 00:02:33.82
SQL>
MEASURES Вывод
Не так уж и много различий в истекшем времени для различных индексов. Я был немного удивлен, что построение индекса на MEASURES (TS, MEASURE) привело к полному сканированию таблицы и несколько медленнее время выполнения. С другой стороны, неудивительно, что параллельный запрос выполняется намного быстрее. Таким образом, если у вас есть Enterprise Edition и у вас есть свободные процессоры, использование PQ определенно сократит истекшее время, хотя это не сильно изменит стоимость ресурсов (и на самом деле делает лот больше сортировки).
INTERVALS тесты
Так какая разница может быть между различными индексами на INTERVALS? В следующих тестах мы сохраним индекс на MEASURES (TS). Прежде всего, мы опустим первичный ключ на обоих столбцах INTERVALS и заменим его ограничением только на INTERVALS (ENTRY_TIME).
SQL> alter table intervals drop constraint ivl_pk drop index
2 /
Table altered.
SQL> alter table intervals add constraint ivl_pk primary key (entry_time) using index
2 /
Table altered.
SQL> exec dbms_stats.gather_table_stats(user, 'INTERVALS', cascade=>true)
PL/SQL procedure successfully completed.
SQL> select m.measure
2 , m.ts as "TIME"
3 , i.entry_time
4 , i.exit_time
5 from
6 intervals i
7 inner join
8 measures m
9 on ( m.ts between i.entry_time and i.exit_time )
10 order by m.ts asc
11 /
1200001 rows selected.
Elapsed: 00:05:38.39
SQL>
Наконец, без индекса на INTERVALS вообще
SQL> alter table intervals drop constraint ivl_pk drop index
2 /
Table altered.
SQL> exec dbms_stats.gather_table_stats(user, 'INTERVALS', cascade=>true)
PL/SQL procedure successfully completed.
SQL> select m.measure
2 , m.ts as "TIME"
3 , i.entry_time
4 , i.exit_time
5 from
6 intervals i
7 inner join
8 measures m
9 on ( m.ts between i.entry_time and i.exit_time )
10 order by m.ts asc
11 /
1200001 rows selected.
Elapsed: 00:05:29.15
SQL>
INTERVALS вывод
Индекс на INTERVALS делает небольшую разницу. То есть индексирование (ENTRY_TIME, EXIT_TIME) приводит к более быстрому выполнению. Это происходит потому, что при этом происходит быстрое полное индексирование, а не полное табличное сканирование. Это было бы более важным, если бы временное окно, очерченное INTERVALS, было значительно шире, чем окно MEASURES.
Overall Conclusions
Поскольку мы выполняем полные табличные запросы, ни один из индексов существенно не изменил время исполнения. Таким образом, если у вас есть Enterprise Edition и несколько параллельных запросов к процессорам, то вы получите наилучшие результаты. В противном случае самыми лучшими индексами будут INTERVALS(ENTRY_TIME, EXIT_TIME) и MEASURES(TS) . Решение "Вложенных циклов" определенно быстрее, чем Parallel Query - см. ниже Edit 4.
Если бы вы боролись с подмножеством MEASURES (скажем, за неделю), то наличие индексов оказало бы большее влияние, скорее всего, те два, которые я рекомендовал в предыдущем абзаце, останутся наиболее эффективными,
Последнее наблюдение: Я прогнал это на болотном стандартном двухъядерном ноутбуке с SGA всего 512M. Однако все мои запросы заняли менее шести минут. Если ваш запрос действительно занимает час, то у вашей базы данных есть некоторые серьезные проблемы. Хотя это длительное время может быть артефактом перекрытия ИНТЕРВАЛОВ, что может привести к появлению картезианского продукта.
**Правка **
Первоначально я включил вывод из
SQL> set autotrace traceonly stat exp
, но увы, SO сильно укоротила мой пост. Так что я переписал его, но без исполнения и статистики. Тем, кто хочет проверить мои выводы, придется запустить themselevs запросов.
Edit 4 (предыдущая редакция удалена из соображений экономии места)
С третьей попытки я смог воспроизвести улучшение производительности для решения Квасного.
SQL> set autotrace traceonly stat exp
SQL>
SQL> set timing on
SQL>
SQL> select
2 /*+ LEADING (i) USE_NL(i, m) */
3 m.measure
4 , m.ts as "TIME"
5 , i.entry_time
6 , i.exit_time
7 from
8 intervals i
9 inner join
10 measures m
11 on ( m.ts between i.entry_time and i.exit_time )
12 order by m.ts asc
13 /
1200001 rows selected.
Elapsed: 00:00:18.39
Execution Plan
----------------------------------------------------------
Plan hash value: 974071908
---------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes |TempSpc| Cost (%CPU)| Time |
---------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 6003K| 257M| | 973K (1)| 03:14:46 |
| 1 | SORT ORDER BY | | 6003K| 257M| 646M| 973K (1)| 03:14:46 |
| 2 | NESTED LOOPS | | | | | | |
| 3 | NESTED LOOPS | | 6003K| 257M| | 905K (1)| 03:01:06 |
| 4 | TABLE ACCESS FULL | INTERVALS | 2001 | 32016 | | 2739 (1)| 00:00:33 |
|* 5 | INDEX RANGE SCAN | MEAS_IDX | 60000 | | | 161 (1)| 00:00:02 |
| 6 | TABLE ACCESS BY INDEX ROWID| MEASURES | 3000 | 87000 | | 451 (1)| 00:00:06 |
---------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
5 - access("M"."TS">="I"."ENTRY_TIME" AND "M"."TS"<="I"."EXIT_TIME")
Statistics
----------------------------------------------------------
66 recursive calls
2 db block gets
21743 consistent gets
18175 physical reads
0 redo size
52171689 bytes sent via SQL*Net to client
880416 bytes received via SQL*Net from client
80002 SQL*Net roundtrips to/from client
0 sorts (memory)
1 sorts (disk)
1200001 rows processed
SQL>
Так что Вложенные Петли - это определенно путь, по которому надо идти.
Полезные уроки из упражнения
- Выполнение диагностических тестов - это гораздо больше. ценнее, чем догадки и теоретизирование
- Понимание данных имеет решающее значение
- Даже при 11g мы все равно будем иногда нужно использовать подсказки, чтобы проткнуть Оптимизатор в некоторых случаях
Вы не можете оптимизировать свое утверждение - оно и так довольно простое.
Что Вы могли бы сделать, так это изучить, помогут ли Вам некоторые индексы.
Вы выбираете на интервалах.enter_time, intervals.exit_time, measures.time - индексируются ли эти столбцы?
Первое, что я сделаю, это заставлю ваш инструмент базы данных сгенерировать план выполнения, который вы сможете просмотреть (это "Control-L" в MSSQL, но я не уверен, как это сделать в Oracle) - который попытается указать на медленные части и, в зависимости от вашего Сервера/Редактора, может даже порекомендовать некоторые базовые индексы. Как только у вас есть план выполнения, вы можете искать любые таблицы сканирования внутренних соединений цикла, оба из которых действительно медленно - индексы могут помочь с таблицей сканирования, и вы можете добавить дополнительные предикаты соединения, чтобы помочь облегчить соединения цикла.
Моя догадка была бы MEASURES нужен индекс на ВРЕМЯ столбца, и вы можете включить столбец MEASURE, а также для ускорения поиска. Попробуйте это:
CREATE INDEX idxMeasures_Time ON Measures ([Time]) INCLUDES (Measure)
Кроме того, хотя это не изменит ваш план выполнения или ускорить ваш запрос, это может сделать вашу оговорку о присоединении немного легче читать:
ON measures.time BETWEEN intervals.entry_time AND intervals.exit_time
Это просто объединяет ваши два <= и >= в одном операторе.
.попробуйте параллельный запрос
alter session enable parallel query; select /*+ parallel */ ... same as before;
Можно также создать материализованное представление, возможно, с помощью приведенной выше параллельной подсказки. Создание MV может занять много времени, но после его создания его можно запросить повторно
.Может быть очень эффективный способ записи этого запроса, если интервалы являются детерминированными, так как запрос может быть преобразован в экви-join, который может быть более эффективно соединён с хэшем.
Например, если интервалы все часовые:
ENTRY_TIME EXIT_TIME
2000-01-15 09:00:00 2000-01-15 09:59:59
2000-01-15 10:00:00 2000-01-15 10:59:59
2000-01-15 11:00:00 2000-01-15 11:59:59
2000-01-15 12:00:00 2000-01-15 12:59:59
....
Тогда соединение может быть записано как:
intervals.entry_time=trunc(measures.time,'HH')
Это уменьшит стоимость всего, вплоть до соединения, вплоть до полного сканирования каждой из таблиц.
Однако, так как у вас там есть операция ORDER BY, я думаю, что сортировщик все равно может обойти ее, так как запрос записывается прямо сейчас, потому что оптимизатор отсортирует для сортировки меньший набор данных, чем для соединения хэшей (потому что в последнем случае ему придется отсортировать больше столбцов данных). Вы можете обойти это, структурировав запрос так:
select
measures.measure as measure,
measures.time as time,
intervals.entry_time as entry_time,
intervals.exit_time as exit_time
from
intervals inner join
(select time, measure from measures order by time) measures
on intervals.entry_time=trunc(measures.time,'HH')
/
Это дает более низкую оценку стоимости, чем сортировка на моем тестовом примере 10.2.0.4, но я бы посчитал это немного рискованным.
Так что я бы искал сортировщик или переписывал его, чтобы по возможности использовать хэш-соединение.
.Не зная, какая система и версия БД, я бы сказал, что (отсутствие) индексации и пункта присоединения может вызвать проблему.
Для каждой записи в таблице измерений можно иметь несколько записей в интервальной таблице (interval.entry_time<=measures.time), а для каждой записи в интервальной таблице можно иметь несколько записей в интервальной таблице измерений (measures.time <=intervals.exit_time). результирующее соотношение от одной к нескольким и много к одному, вызываемое соединением, означает сканирование нескольких таблиц для каждой записи. Я сомневаюсь, что декартовый продукт является правильным термином, но он довольно близок.
Индексирование определенно помогло бы, но еще больше помогло бы, если бы вы смогли найти лучший ключ для соединения двух таблиц. Если отношения один-ко-многим идут только в одном направлении, то это определенно ускорило бы обработку, так как не пришлось бы сканировать каждую таблицу/индекс дважды для каждой записи.
В этом случае вы получите большую часть строк из обеих таблиц, плюс у вас есть своего рода.
Вопрос в том, действительно ли процессу вызова нужны все строки, или только первые? Это изменит то, как я буду оптимизировать запрос.
Я предполагаю, что ваш вызывающий процесс хочет ВСЕ строки. Так как предикат join не на равенстве, я бы сказал, что MERGE JOIN может быть лучшим подходом для достижения цели. Объединение требует сортировки источников данных, поэтому если мы можем избежать сортировки, то запрос должен выполняться как можно быстрее (за исключением более интересных подходов, таких как специализированные индексы или материализованные представления).
Чтобы избежать операций SORT на интервалах и интервалах , можно добавить индексы на интервалах , интервалах ) и интервалах [entry_time, интервалах [exit_time). База данных может использовать индекс, чтобы избежать сортировки, и это будет быстрее, потому что не нужно будет посещать блоки таблиц.
Или, если у вас есть индекс только по measures.time, запрос все равно может идти нормально без добавления еще одного большого индекса - он будет идти медленнее, потому что, вероятно, придется прочитать много блоков таблиц, чтобы получить measures.measure для пункта SELECT.