Suponha, por simplicidade, que possua a seguinte tabela no 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;

Estou tentando encontrar a consulta mais eficiente para implementar o equivalente ao seguinte:

Dado um par de carimbos de horat0 et1:

Para cadapv_name:

Obtenha o valor da linha com estepv_name e o maiortime_stamp <= t0 (se houver). Este é o valor da variável de processo no início do intervalo de tempo. Se esse valor não for válido, descarte-o.

Obtenha o conjunto de valores das linhas com estepv_name e umtime_stamp no(t0, t1) que são válidos(se houver).

Se houver mais de um valor distinto entre o conjunto combinado de valores de 1 e 2, retorne o pv_name.

Em essência, estou tentando descobrir quais variáveis de processo tiveram uma alteração no valor no intervalo de tempo especificado, incluindo uma alteração no valor que ela possuía no início do intervalo de tempo.

Existem da ordem de bilhões de linhas na tabela e ele continuará a crescer. Existem na ordem de 100.000 nomes de pv distintos na tabela e eles permanecerão razoavelmente estáticos. Espera-se que a grande maioria dos valores adjacentes (ordenados por time_stamp para cada pv_name) sejam distintos.

EDITAR

Se eu fosse implementar isso do zero, faria o seguinte: O conjunto de pv_names seria armazenado em um trie. O valor para cada pv_name na tentativa seria um link para uma árvore de pesquisa binária. A árvore de pesquisa binária armazenaria pares de chaves e valores (time_stamp, value). O valor em cada um desses pares seria o valor do pv_name no time_stamp correspondente.

Para descobrir quais nomes de pv tiveram uma alteração no valor para um determinado intervalo de tempo (t0, t1), faça o seguinte: Itere cada nome de pv no trie e siga o link para sua árvore de pesquisa binária. Encontre o maior carimbo de tempo nesta árvore menor ou igual a t0. Se não houver, encontre o menor carimbo de tempo nesta árvore menor que t1. Se nenhum deles existir, vá para o próximo pv_name na tentativa. Caso contrário, itere através dos time_stamps em ordem crescente, comparando o valor associado ao time_stamp atual ao valor associado ao anterior. Se eles diferirem, imprima o nome do pv. Pare de iterar pelos time_stamps. Vá para o próximo pv_name na tentativa e repita. Se um carimbo de tempo maior ou igual a t1 for alcançado e nenhuma diferença for encontrada, vá para o próximo pv_name na tentativa e repita. Não use o valor para o time_stamp t1 nas comparações.

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

Posso fazer o equivalente com a mesma ou melhor eficiência no MySQL ou em outro banco de dados, relacional ou não?