Оптимизировать запрос, выбирая период

Question

С учетом следующей таблицы:

Table events
id
start_time
end_time

Есть ли способ быстрого поиска константы?

* 1006 Е.Г. *

SELECT *
FROM events
WHERE start_time<='2009-02-18 16:27:12' 
AND     end_time>='2009-02-18 16:27:12'

Я использую MySQL. Наличие индекса в любом поле все еще должно проверять диапазон. Более того, индекс по обоим полям не будет иметь значения (будет использоваться только первое).

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

P.S. Необходимость в этом возникла из-за этого вопроса: Оптимизировать SQL, который используется между предложением

Answer 1

В моем решении есть одна оговорка:

1) Предостережение в этом решении заключается в том, что вы должны использовать движок MyISAM для таблицы событий. Если вы не можете использовать MyISAM, то это решение не будет работать, поскольку для пространственных индексов поддерживается только MyISAM.

Итак, при условии, что вышеприведенное не является для вас проблемой, следующее должно работать и обеспечивать хорошую производительность:

В этом решении используется поддержка MySQL для пространственных данных (см. документацию здесь ). Хотя пространственные типы данных могут быть добавлены к различным механизмам хранения, только MyISAM поддерживается для пространственных индексов R-дерева (см. документация здесь ), которые необходимы для получения необходимой производительности. Еще одно ограничение заключается в том, что пространственные типы данных работают только с числовыми данными, поэтому вы не можете использовать эту технику при запросах диапазона на основе строк.

Я не буду вдаваться в детали теории о том, как работают пространственные типы и как полезен пространственный индекс, но вы должны взглянуть на объяснение Джереми Коула здесь относительно того, как использовать пространственные типы данных и индексы для поиска GeoIP. Также посмотрите на комментарии, так как они поднимают некоторые полезные моменты и альтернативу, если вам нужна грубая производительность и вы можете отказаться от некоторой точности.

Основная предпосылка заключается в том, что мы можем взять начало / конец и использовать две из них для создания четырех различных точек, по одной для каждого угла прямоугольника с центром в районе 0,0 на сетке xy, а затем выполнить быстрый поиск в пространственный индекс, чтобы определить, находится ли конкретный момент времени, о котором мы заботимся, внутри прямоугольника или нет. Как упоминалось ранее, см. Объяснение Джереми Коула для более подробного обзора того, как это работает.

В вашем конкретном случае нам нужно будет сделать следующее:

1) Измените таблицу на таблицу MyISAM (обратите внимание, что вам не следует делать это, если вы не в полной мере осведомлены о последствиях такого изменения, таких как отсутствие транзакций и поведение блокировки таблиц, связанных с MyISAM).

alter table events engine = MyISAM;

2) Затем мы добавляем новый столбец, который будет содержать пространственные данные. Мы будем использовать тип данных многоугольника, так как нам нужно уметь удерживать полный прямоугольник.

alter table events add column time_poly polygon NOT NULL;

3) Затем мы заполняем новый столбец данными (имейте в виду, что любые процессы, которые обновляют или вставляют в события таблицы, необходимо изменить, чтобы убедиться, что они также заполняют новый столбец). Поскольку начальный и конечный диапазоны являются временами, нам необходимо преобразовать их в числа с помощью функции unix_timestamp (см. Документацию здесь , чтобы узнать, как она работает).

update events set time_poly := LINESTRINGFROMWKB(LINESTRING(
    POINT(unix_timestamp(start_time), -1),
    POINT(unix_timestamp(end_time), -1),
    POINT(unix_timestamp(end_time), 1),
    POINT(unix_timestamp(start_time), 1),
    POINT(unix_timestamp(start_time), -1)
  ));

4) Затем мы добавляем пространственный индекс в таблицу (как упоминалось ранее, это будет работать только для таблицы MyISAM и приведет к ошибке «ОШИБКА 1464 (HY000): используемый тип таблицы не поддерживает ПРОСТРАНСТВЕННЫЕ индексы») ).

alter table events add SPATIAL KEY `IXs_time_poly` (`time_poly`);

5) Затем вам нужно будет использовать следующий выбор, чтобы использовать пространственный индекс при запросе данных.

SELECT * 
FROM events force index (IXs_time_poly)
WHERE MBRCONTAINS(events.time_poly, POINTFROMWKB(POINT(unix_timestamp('2009-02-18 16:27:12'), 0)));

Индекс силы предназначен для 100% уверенности, что MySQL будет использовать этот индекс для поиска. Если все прошло хорошо, объяснение вышеупомянутого выбора должно показать что-то похожее на следующее:

mysql> explain SELECT *
    -> FROM events force index (IXs_time_poly)
    -> on MBRCONTAINS(events.time_poly, POINTFROMWKB(POINT(unix_timestamp('2009-02-18 16:27:12'), 0)));
+----+-------------+-------+-------+---------------+---------------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key           | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+---------------+---------+------+------+-------------+
|  1 | SIMPLE      | B     | range | IXs_time_poly | IXs_time_poly | 32      | NULL |    1 | Using where | 
+----+-------------+-------+-------+---------------+---------------+---------+------+------+-------------+
1 row in set (0.00 sec)

Пожалуйста, обратитесь к анализу Джереми Коула для деталей о преимуществах производительности этого метода по сравнению с предложением между ними.

Дайте мне знать, если у вас есть какие-либо вопросы.

Спасибо

-Dipin

Answer 2

Нет эффективного способа сделать именно этот запрос в MySQL.

Если ваши диапазоны не перекрываются, вы можете просто использовать start_time <= const вместе с ORDER BY start_time DESC LIMIT 1 и дополнительно проверять end_time >= const.

Вам нужно будет сделать это в функции, поскольку MySQL по некоторым причинам не использует INDEX RANGE SCAN для ORDER BY в подзапросе, если условие диапазона взято из суперзапроса.

CREATE UNIQUE INDEX ux_b_start ON b (start_date);

CREATE FUNCTION `fn_get_last_b`(event_date TIMESTAMP) RETURNS int(11)
BEGIN
  DECLARE id INT;
  SELECT b.id
  INTO id
  FROM b
  FORCE INDEX (ux_b_start)
  WHERE b.start_time <= event_date
  ORDER BY
    b.start_time DESC
  LIMIT 1;
  RETURN id;
END;

SELECT COUNT(*) FROM a;

1000


SELECT COUNT(*) FROM b;

200000

SELECT *
FROM (
  SELECT fn_get_last_b(a.event_time) AS bid,
         a.*
  FROM a
) ao, b FORCE INDEX (PRIMARY)
WHERE b.id = ao.bid
  AND b.end_time >= ao.event_time

1000 rows fetched in 0,0143s (0,1279s)

Answer 3

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

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

SELECT *
FROM events
WHERE 
   ( start_time BETWEEN ( 'search_start' - INTERVAL 2 DAY ) and 'search_end' )
   AND end_time >= 'search_start'

... у вас будет индекс для start_time.

(Примечание: в моей таблице миллионы событий, разбросанных за 4 года, без записи более чем за 24 часа ... Я понятия не имею, как это работает по отношению к подходу пространственного поиска, так как мне придется идти попробуй сам.)

Answer 4

У вас в основном есть запрос с двумя отчетливо отдельными условиями диапазона. Вы используете> =, для MySQL это всегда сканирование диапазона. Здесь есть документация здесь для оптимизации сканирования диапазона.

Суть в том, что MySQL выполняет дополнительную проверку для фильтрации строк, которые удовлетворяют условию диапазона, а затем удовлетворяет остальной части предложения WHERE, что в вашем случае является другим условием диапазона.

Answer 5

У меня нет большого опыта работы с MySQL, но на MS SQL Server добавление индекса по обоим столбцам позволило получить время поиска и возврата индекса для таблицы строк размером 1 МБ с 1-2 секунд до миллисекунд. *

Кажется, вы видите разные результаты. Интересно, если ограничение имеет значение. У меня есть проверочное ограничение для принудительного запуска этого start_time

Answer 6

В одной таблице вы мало что можете сделать. Если оптимизация этих запросов 1) необходима 2) должна быть выполнена на уровне SQL, то вам нужно будет создать производную таблицу:

Table event_times
id
event_id
mark_time

и добавьте в него запись для каждой единицы времени, охватываемой каждым событием. Тогда вы просто

SELECT *
FROM events
LEFT JOIN event_times ON event_id = events.id
WHERE mark_time = '2009-02-18 16:27:12'

Вы можете сделать эту таблицу менее смешной, если определите «единицу времени», т.е. если вы ограничите разрешение mark_time минутами или часами, а не секундами.