Optimize SQL que utiliza entre cláusula

Question

Considere as 2 tabelas a seguir:

Table A:
id
event_time

Table B
id
start_time
end_time

Cada registro na tabela A é mapeada para exatamente 1 registro na tabela B. Isto significa tabela B não tem sobreposição de períodos. Muitos registros da tabela A pode ser mapeado para o mesmo registro na tabela B.

Eu preciso de uma consulta que retorna todos os pares A.id, b.id. Algo como:

SELECT A.id, B.id 
FROM A, B 
WHERE A.event_time BETWEEN B.start_time AND B.end_time

Estou usando o MySQL e eu não posso optimizar esta consulta. Com ~ 980 registros na tabela A e 130.000 na tabela B este leva uma eternidade. Eu entendo que isso tem que realizar 980 consultas, mas tendo mais de 15 minutos em uma máquina beefy é estranho. Alguma sugestão?

P.S. Eu não posso mudar o esquema de banco de dados, mas posso adicionar índices. No entanto um índice (com 1 ou 2 campos) sobre os campos de hora não ajuda.

Answer 1

Você pode querer tentar algo como isto

Select A.ID,
(SELECT B.ID FROM B
WHERE A.EventTime BETWEEN B.start_time AND B.end_time LIMIT 1) AS B_ID
FROM A

Se você tiver um índice na Start_Time, campos end_time para B, então isso deve funcionar muito bem.

Answer 2

Eu não estou certo de que este pode ser totalmente otimizado. Eu tentei no MySQL 5.1.30. Eu também adicionei um índice em {B.start_time, B.end_time} como sugerido por outras pessoas. Então eu tenho um relatório do EXPLAIN, mas o melhor que eu poderia conseguir é um Gama Método de acesso :

EXPLAIN SELECT A.id, B.id FROM A JOIN B 
ON A.event_time BETWEEN B.start_time AND B.end_time;

+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra                                          |
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------------------------+
|  1 | SIMPLE      | A     | ALL  | event_time    | NULL | NULL    | NULL |    8 |                                                | 
|  1 | SIMPLE      | B     | ALL  | start_time    | NULL | NULL    | NULL |   96 | Range checked for each record (index map: 0x4) | 
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------------------------+

Veja a nota na extrema direita. O otimizador pensa que pode ser capaz de usar o índice na {B.start_time, B.end_time} mas acabou decidindo não usar esse índice. Os resultados podem variar, porque a sua distribuição de dados é mais representativa.

Comparar com o uso do índice se você comparar A.event_time a uma gama constante:

EXPLAIN SELECT A.id FROM A
WHERE A.event_time BETWEEN '2009-02-17 09:00' and '2009-02-17 10:00';

+----+-------------+-------+-------+---------------+------------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key        | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+------------+---------+------+------+-------------+
|  1 | SIMPLE      | A     | range | event_time    | event_time | 8       | NULL |    1 | Using where | 
+----+-------------+-------+-------+---------------+------------+---------+------+------+-------------+

E comparar com a forma sub-consulta dependente dada pelo @Luke e @Kibbee, que parece fazer uso de índices de forma mais eficaz:

EXPLAIN SELECT A.id AS id_from_a,
    (
        SELECT B.id
        FROM B
        WHERE A.id BETWEEN B.start_time AND B.end_time
        LIMIT 0, 1
    ) AS id_from_b
FROM A;

+----+--------------------+-------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type        | table | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+----+--------------------+-------+-------+---------------+---------+---------+------+------+-------------+
|  1 | PRIMARY            | A     | index | NULL          | PRIMARY | 8       | NULL |    8 | Using index | 
|  2 | DEPENDENT SUBQUERY | B     | ALL   | start_time    | NULL    | NULL    | NULL |  384 | Using where | 
+----+--------------------+-------+-------+---------------+---------+---------+------+------+-------------+

Estranhamente, EXPLICAR listas possible_keys como NULL (ou seja, nenhum índice poderia ser usado), mas então decide usar a chave primária depois de tudo. Poderia ser uma idiossincrasia do relatório EXPLAIN do MySQL?

Answer 3

Eu não recomendo normalmente uma consulta como esta, mas ...

Uma vez que você tenha especificado que a tabela A tem apenas cerca de 980 linhas e que cada linha mapeia para exatamente uma linha na tabela B, então você poderia fazer o seguinte e ele provavelmente será muito mais rápido do que uma junção cartesiana:

SELECT A.id AS id_from_a,
    (
        SELECT B.id
        FROM B
        WHERE A.event_time BETWEEN B.start_time AND B.end_time
        LIMIT 0, 1
    ) AS id_from_b
FROM A

Answer 4

Eu fiz alguns testes para um problema semelhante - cálculo de um país com base em um endereço IP (dado como um número). Aqui estão os meus dados e resultados:

• Tabela A (que contém os usuários e endereços IP) contém cerca de 20 registros.
• Tabela B (que contém as faixas de IP para cada país) contém cerca de 100000 registros.

A consulta JOIN usando "entre" leva cerca de 10 segundos; O SELECT dentro de uma consulta SELECT, usando "entre", leva cerca de 5,5 segundos; O SELECT dentro de uma consulta SELECT, usando um índice espacial, leva cerca de 6,3 segundos. A consulta JOIN utilizando um índice espacial leva 0 segundos!

Answer 5

Observe que ao executar essa consulta, você realmente criar 980x130000 registros na memória antes de aplicar a condição. Tal Cadastre não é muito recomendado, e eu posso ver porque ele vai dar-lhe problemas de desempenho.

Answer 6

Se você não pode alterar o esquema -., Em particular, se você não pode adicionar um índice em a.event_time, não vejo muito espaço para melhorias no nível SQL

Eu estaria mais inclinado a fazê-lo no código.

• ler todas as tuplas B de início / fim / id em uma lista, ordenada por horário de início
• leia todos os eventos A
• para cada evento A
• • encontrar o maior tempo de início <= hora do evento (busca binária vai fazer bem)
• • Se a hora do evento é <= tempo do fim, adicione um para a lista deste B de eventos
• • else este B não tem casa

Answer 7

Por não alterar o esquema quero dizer que você não pode adicionar um índice? Tente um índice multi coluna sobre start_time e end_time.

Answer 8

Dê uma tentativa usando operador de comparação padrão ().

Answer 9

Eu vejo que você está fazendo uma cruz junção de duas tabelas. Isso não é muito bom, e DBMS vai ter um monte de tempo para executar essa operação. CROSS JOIN é a operação mais exepensive em SQL. A razão de tanto tempo de execução poderia ser isso.

Do nessa forma, ele poderia resolver ...

SELECIONAR A.id, B.id De A, B ONDE A.id = B.id E A.event_time ENTRE B.start_time E B.end_time

Espero que isso ajuda você:)

Answer 10

Existe um índice em B (start_time, end_time)? Se não, talvez adicionando um pode acelerar a correspondência de linhas B para linhas A?

Mind você, se você não pode mudar o esquema, talvez você não pode criar novos índices quer?

Answer 11

A única saída que você tem que acelerar a execução dessa consulta é através da utilização de índices.

Tome cuidado de colocar em um índice seu A.event_time e, em seguida, colocado em outro B.start_time índice e B.end_time.

Se, como você disse que esta é a única condição que se liga as duas entidades em conjunto, penso que esta é a única solução que você pode tomar.

Fede

Answer 12

Daremon, esta resposta é baseado em um de seus comentários onde você disse que cada registro na tabela Um mapeia para um único registro na tabela B,

Você pode adicionar uma tabela adicional para o seu esquema? Se sim, você pode pré-computar o resultado desta consulta e armazená-lo em outra tabela. Você também terá que manter esta tabela pré-calculado em sincronia com alterações nas tabelas A e B

Answer 13

Com base no seu comentário de que cada entrada corresponde à exatamente uma entrada no B, a solução mais fácil seria a remover o AUTOINCREMENT da coluna ID do B, em seguida, substituir todos os ids de B com os ids de A.

Answer 14

Coloque um índice em B.start_time descendente e, em seguida, use esta consulta:

 SELECT A.id AS idA,
 (SELECT B.id FROM B WHERE A.event_time > B.start_time LIMIT 0, 1
 ORDER BY B.start_time DESC) AS idB
 FROM A

Como os baldes de tempo no B são disjuntos isto lhe daria o primeiro balde de tempo correspondente und lo a se livrar do meio, mas continua a ter a sub-consulta lá. Talvez incluindo o B.id no índice iria dar-lhe um pequeno impulso adicional desempenho. (Disclaimer: não tenho certeza sobre a sintaxe MySQL)

Answer 15

Eu não posso pensar da razão para que você tenha uma tabela com 130.000 linhas com intervalos de tempo. De qualquer forma, deve haver uma boa razão para tal projeto, e se assim for, você tem que evitar a tentar calcular como uma junção everytime. Então aqui está a minha sugestão. Gostaria de acrescentar uma referência ao B.id na tabela A (A.B_ID) e usar gatilhos para manter a consistência. Sempre que você adicionar um novo registro (insert trigger) ou as alterações de coluna even_time (disparador de atualização), você teria recalcular a referência a B que desta vez corresponde. Sua instrução select seria reduzida a um único * Selecionar de uma.

Answer 16

MySQL não permite que você use INDEX ORDER BY WITH RANGE em consultas derivados.

É por isso que você precisa para criar uma função definida pelo usuário.

Note que, se seus intervalos se sobrepõem, a consulta só irá selecionar um (que começou passado).

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 17

Pessoalmente, se você havea relação um para muitos e cada registro na tabela a única relaciona-se com um registro na tabela b, gostaria de armazenar o ID da tabela b na tabela A e, em seguida, fazer um regular juntar-se para obter os dados. O que você tem atualmente é um projeto ruim que nunca pode ser verdadeiramente eficaz.

Answer 18

Há duas ressalvas a minha solução:

1) Você disse que você pode adicionar índices, mas não alterar o esquema para que eu não tenho certeza se isso iria trabalhar para você ou não, como você não pode ter índices baseados função no MySQL e você precisaria criar um extra coluna na Tabela B. 2) A outra ressalva a esta solução é que você deve estar usando o motor MyISAM para Tabela B. Se você não pode usar MyISAM em seguida, esta solução não vai funcionar porque só MyISAM é suportada por índices espaciais.

Assim, supondo que o acima dois não são um problema para você, o seguinte deve funcionar e dar-lhe um bom desempenho:

Esta solução faz uso do suporte do MySQL para Dados Espaciais (veja documentação aqui ). Enquanto tipos de dados espaciais podem ser adicionados a uma variedade de mecanismos de armazenamento, única MyISAM é suportada para Índices Espaciais R-Tree (veja documentação aqui ) os quais são necessários a fim de obter o desempenho necessário. Outra limitação é que tipos de dados espaciais só funcionam com dados numéricos que você não pode usar esta técnica com consultas gama de cordas base.

Eu não vou entrar em detalhes da teoria por trás como tipos espacial funcionam e como o índice espacial é útil, mas você deve olhar para explicação de Jeremy Cole aqui no que diz respeito a como usar tipos de dados espaciais e índices para pesquisas GeoIP. Também olhar para os comentários como eles levantar alguns pontos úteis e alternativa se você precisar de desempenho bruto e pode dar-se alguma precisão.

A premissa básica é que podemos tomar o início / fim e usar os dois para criar quatro pontos distintos, um para cada canto de um retângulo centrado em torno de 0,0 em uma grade xy, e, em seguida, fazer uma pesquisa rápida para o índice espacial para determinar se o ponto específico no tempo que nos interessa é dentro do retângulo ou não. Como mencionado anteriormente, ver a explicação de Jeremy Cole para uma visão mais completa de como isso funciona.

No seu caso particular, será necessário fazer o seguinte:

1) alterar a tabela para ser uma tabela MyISAM (note que você não deve fazer isso a menos que você está plenamente consciente das consequências de uma tal mudança como a falta de transações e o comportamento de bloqueio tabela que estão associados com MyISAM).

alter table B engine = MyISAM;

2) Em seguida, adicionar a nova coluna que irá armazenar os dados espacial. Nós vamos usar o tipo de dados polígono como precisamos ser capazes de manter um retângulo completo.

alter table B add column time_poly polygon NOT NULL;

3) Em seguida, preencher a nova coluna com os dados (por favor, tenha em mente que todos os processos que atualização ou inserção na tabela B vai precisar de ter modificado para se certificar que estão preenchendo a nova coluna também). Desde as faixas iniciais e finais são momentos, vamos precisar convertê-los para números com a função unix_timestamp (veja documentação aqui de como ele funciona).

update B 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) Em seguida, adicione o índice espacial para a mesa (como mencionado anteriormente, isto só irá funcionar para uma tabela MyISAM e irá produzir o erro "ERROR 1464 (HY000): O tipo de tabela utilizado não suporta índices espaciais" ).

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

5) Em seguida, você precisará usar a seguinte escolha, a fim de fazer uso do índice espacial ao consultar os dados.

SELECT A.id, B.id 
FROM A inner join B force index (IXs_time_poly)
ON MBRCONTAINS(B.time_poly, POINTFROMWKB(POINT(unix_timestamp(A.event_time), 0)));

O índice de força está lá para fazer 100% de certeza que o MySQL usará o índice para a pesquisa. Se tudo correu bem executando um explicar sobre o acima selecionar deve mostrar algo semelhante ao seguinte:

mysql> explain SELECT A.id, B.id
    -> FROM A inner join B force index (IXs_time_poly)
    -> on MBRCONTAINS(B.time_poly, POINTFROMWKB(POINT(unix_timestamp(A.event_time), 0)));
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------------------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows    | Extra                                           |
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------------------------------------------+
|  1 | SIMPLE      | A     | ALL  | NULL          | NULL | NULL    | NULL |    1065 |                                                 | 
|  1 | SIMPLE      | B     | ALL  | IXs_time_poly | NULL | NULL    | NULL | 7969897 | Range checked for each record (index map: 0x10) | 
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------------------------------------------+
2 rows in set (0.00 sec)

Por favor, referir-se a análise de Jeremy Cole para detalhes about os benefícios deste método de desempenho em comparação com um entre cláusula.

Deixe-me saber se você tiver quaisquer perguntas.

Obrigado,

-Dipin

Answer 19

algo assim?

SELECT A.id, B.id 
FROM A
JOIN B ON A.id =  B.id 
WHERE A.event_time BETWEEN B.start_time AND B.end_time