Supongamos por simplicidad que tengo la siguiente tabla en 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;

Estoy tratando de encontrar la consulta más eficiente para implementar el equivalente de lo siguiente:

Dado un par de marcas de tiempot0 yt1:

Para cadapv_name:

Obtenga el valor de la fila con estopv_name y el más grandetime_stamp <= t0 (si existe). Este es el valor de la variable de proceso al comienzo del rango de tiempo. Si este valor no es válido, deséchelo.

Obtenga el conjunto de valores de las filas con estopv_name y untime_stamp en(t0, t1) que son validos(si existe).

Si hay más de un valor distinto entre el conjunto combinado de valores de 1 y 2, devuelva pv_name.

En esencia, estoy tratando de encontrar qué variables de proceso tuvieron un cambio en el valor en el rango de tiempo dado, incluido un cambio del valor que tenía al comienzo del rango de tiempo.

Hay en el orden de miles de millones de filas en la tabla y seguirá creciendo. Hay en el orden de 100,000 nombres pv_ distintos en la tabla y permanecerán bastante estáticos. Se espera que la gran mayoría de los valores adyacentes (ordenados por time_stamp para cada pv_name) sean distintos.

EDITAR

Si fuera a implementar esto desde cero, haría lo siguiente: El conjunto de pv_names se almacenaría en un archivo. El valor para cada pv_name en el trie sería un enlace a un árbol de búsqueda binario. El árbol de búsqueda binario almacenaría pares de clave y valor de (time_stamp, value). El valor en cada uno de estos pares sería el valor de pv_name en el correspondiente time_stamp.

Para averiguar qué nombres de pv tuvieron un cambio de valor para un rango de tiempo determinado (t0, t1), haría lo siguiente: iterar a través de cada nombre de pv en el trie y seguir el enlace a su árbol de búsqueda binario. Encuentre el mayor time_stamp en este árbol menor o igual que t0. Si no existe ninguno, busque el sello de tiempo más pequeño en este árbol menor que t1. Si ninguno de estos existe, vaya al siguiente pv_name en el trie. De lo contrario, repita los sellos de tiempo en orden creciente comparando el valor asociado con el sello de tiempo actual con el valor asociado con el anterior. Si difieren, imprima el pv_name. Deja de iterar a través de los sellos de tiempo. Vaya al siguiente pv_name en el trie y repita. Si se llega a un sello de tiempo mayor o igual a t1, y no se han encontrado diferencias, entonces vaya al siguiente nombre de pv en el trie y repita. No use el valor para el time_stamp t1 en las comparaciones.

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

¿Puedo hacer el equivalente con la misma o mejor eficiencia en MySQL u otra base de datos, relacional o de otro tipo?