Предположим для простоты, что у меня есть следующая таблица в MySQL:

CREATE TABLE `events` (
    `pv_name` varchar(60) NOT NULL,
    `time_stamp` bigint(20) unsigned NOT NULL,
    `value` text,
    `value_valid` tinyint(1) NOT NULL,
    PRIMARY KEY (`pv_name`,`time_stamp`),
) ENGINE=InnoDB;

Я пытаюсь найти наиболее эффективный запрос для реализации эквивалента следующего:

Учитывая пару отметок времениt0 а такжеt1:

Для каждогоpv_name:

Получить значение из строки с этимpv_name и самый большойtime_stamp <= t0 (если таковой существует), Это значение переменной процесса в начале временного диапазона. Если это значение недопустимо, отмените его.

Получить набор значений из строк с этимpv_name иtime_stamp в(t0, t1) которые действительны(если таковые имеются).

Если среди объединенного набора значений от 1 до 2 имеется более одного отдельного значения, вернуть pv_name.

По сути, я пытаюсь найти, какие переменные процесса имели изменение в значении в данном временном интервале, включая изменение по сравнению со значением, которое имело в начале временного диапазона.

В таблице порядка миллиардов строк, и она будет продолжать расти. В таблице порядка 100 000 различных имен pv_name, и они останутся довольно статичными. Ожидается, что подавляющее большинство смежных значений (упорядоченных по time_stamp для каждого pv_name) будут разными.

РЕДАКТИРОВАТЬ

Если бы я собирался реализовать это с нуля, я бы сделал следующее: Набор имен pv_name будет храниться в дереве. Значение для каждого pv_name в дереве будет ссылкой на двоичное дерево поиска. Двоичное дерево поиска будет хранить пары ключ-значение (time_stamp, value). Значение в каждой из этих пар будет значением pv_name в соответствующей отметке времени.

Чтобы выяснить, какие имена pv_name имели изменение в значении для данного time_range (t0, t1), я бы сделал следующее: перебираем каждое имя pv_name в дереве и следуем по ссылке на его двоичное дерево поиска. Найдите наибольшую отметку времени в этом дереве, меньшую или равную t0. Если ничего не существует, найдите наименьшую отметку времени в этом дереве меньше t1. Если ничего из этого не существует, перейдите к следующему pv_name в дереве. В противном случае выполните итерации временных меток в порядке возрастания, сравнивая значение, связанное с текущей меткой времени, со значением, связанным с предыдущим. Если они различаются, распечатайте имя pv_name. Прекратите перебирать метки времени. Перейдите к следующему pv_name в дереве и повторите. Если получена временная метка, большая или равная t1, и различий не обнаружено, перейдите к следующему pv_name в дереве и повторите. Не используйте значение time_stamp t1 в сравнениях.

Simplified example:
pv_name | time_stamp | value
A       | 1.0        | 1.15
B       | 2.0        | 1.00
A       | 3.0        | 1.12
B       | 4.0        | 1.00
A       | 5.0        | 1.00
B       | 6.0        | 1.00
A       | 7.0        | 3.15
B       | 8.0        | 9.13
A       | 9.0        | 4.30
B       | 10.0       | 1.00
A       | 11.0       | 9.00
B       | 12.0       | 1.00

time range  | values of A      | values of B           | result
(0.0,0.5)   | NULL             | NULL                  | NULL
(1.5,2.0)   | 1.15             | NULL                  | NULL
(1.5,5.0)   | 1.15, 1.12       | NULL, 1.00, 1.00      | A
(4.0,9.0)   | 1.12, 1.00, 3.15 | 1.00, 1.00, 9.13      | A, B
(13.0,14.0) | 9.00             | 1.00                  | NULL

Могу ли я сделать эквивалент с той же или лучшей эффективностью в MySQL или другой базе данных, реляционной или другой?