Optimiser SQL qui utilise entre clause
https://stackoverflow.com/questions/557425
-
05-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Considérez les 2 tableaux suivants:
Table A:
id
event_time
Table B
id
start_time
end_time
Chaque enregistrement de la table A est mappée sur exactement une fiche dans le tableau B. Cela signifie que la table B n'a pas de périodes qui se chevauchent. De nombreux enregistrements de la table A peut être mis en correspondance avec le même enregistrement dans le tableau B.
J'ai besoin d'une requête qui renvoie toutes les paires A.id, b.id. Quelque chose comme:
SELECT A.id, B.id
FROM A, B
WHERE A.event_time BETWEEN B.start_time AND B.end_time
J'utilise MySQL et je ne peux pas optimiser cette requête. Avec ~ 980 dossiers dans le tableau A et 130.000 dans le tableau B cela prend pour toujours. Je comprends cela doit effectuer 980 requêtes, mais en prenant plus de 15 minutes sur une machine costaud est étrange. Toutes les suggestions?
P.S. Je ne peux pas changer le schéma de base de données, mais je peux ajouter des index. Cependant, un index (avec 1 ou 2 champs) sur les champs de temps ne permet pas.
La solution
Vous pouvez essayer quelque chose comme ceci
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
Si vous avez un index sur la Start_Time, les champs de END_TIME B, alors cela devrait fonctionner assez bien.
Autres conseils
Je ne suis pas sûr que cela peut être optimisé entièrement. Je l'ai essayé sur MySQL 5.1.30. J'ai aussi ajouté un index sur {B.start_time, B.end_time} comme suggéré par d'autres personnes. Ensuite, je suis un rapport de EXPLAIN, mais le mieux que je puisse obtenir est un Méthode d'accès :
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) |
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------------------------+
Voir la note à l'extrême droite. L'optimiseur pense qu'il peut pouvoir utiliser l'index sur {B.start_time, B.end_time} mais il a fini par décider de ne pas utiliser cet indice. Vos résultats peuvent varier, parce que votre distribution de données est plus représentatif.
Comparer avec l'utilisation d'index si vous comparez A.event_time à une plage 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 |
+----+-------------+-------+-------+---------------+------------+---------+------+------+-------------+
Et comparer avec ce qui semble rendre plus efficace l'utilisation des indices sous forme de sous-requête dépendante donnée par @Luke et @Kibbee,:
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 |
+----+--------------------+-------+-------+---------------+---------+---------+------+------+-------------+
Weirdly, listes EXPLIQUER possible_keys comme NULL (à savoir pas d'index peut être utilisé) mais décide d'utiliser la clé primaire après tout. Peut-être une idiosyncrasie du rapport EXPLIQUER de MySQL?
Je ne recommanderais pas normalement une question comme ça, mais ...
Puisque vous avez spécifié que le tableau A a seulement environ 980 lignes et que chaque carte de ligne à exactement une ligne dans le tableau B, alors que vous pourriez faire ce qui suit et il sera très probablement beaucoup plus vite qu'un cartésienne rejoindre:
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
J'ai fait quelques tests pour un problème similaire - le calcul d'un pays à partir d'une adresse IP (donnée en nombre). Voici mes données et les résultats:
- Tableau A (qui contient les utilisateurs et les adresses IP) contient environ 20 enregistrements.
- Tableau B (qui contient les plages d'adresses IP pour chaque pays) contient environ 100 000 dossiers.
La requête JOIN en utilisant « entre » prend environ 10 secondes; SELECT dans une requête SELECT, en utilisant « entre », prend environ 5,5 secondes; La SELECT à l'intérieur d'une requête SELECT, en utilisant un index spatial, prend environ 6,3 secondes. La requête JOIN à l'aide d'un index spatial prend 0 secondes!
Notez que lors de l'exécution de cette requête, vous créez en fait 980x130000 enregistrements dans la mémoire avant d'appliquer la condition. Une telle jointure est très recommandé, et je ne vois pas pourquoi ça va vous donner des problèmes de performance.
Si vous ne pouvez pas modifier le schéma -. En particulier, si vous ne pouvez pas ajouter un index sur a.event_time, je ne vois pas beaucoup de place à l'amélioration au niveau SQL
Je serais plus enclin à le faire dans le code.
- lire toutes les lignes B début / fin / id dans une liste, triée sur le temps de démarrage
- lire tous les événements A
- pour chaque Un événement
-
- trouver le plus grand temps de démarrage <= heure de l'événement (recherche binaire fera l'affaire)
-
- si le temps de l'événement est <= heure de fin, ajoutez à cette liste de B d'événements
-
- autre ce B n'a pas la maison
En ne changeant pas le schéma ne signifie que vous ne pouvez pas ajouter un index? Essayez un index de plusieurs colonnes sur start_time et end_time.
Donner un essai utilisant l'opérateur de comparaison standard (
Je vois que vous faites une jointure croisée de deux tables. Ce n'est pas très bon, et SGBD prendra beaucoup de temps pour exécuter cette opération. Jointure croisée est l'opération la plus exepensive dans SQL. La raison de tant de temps d'exécution pourrait être cela.
faire sur cette façon, il pourrait résoudre ...
SELECT A.id, B.id À partir de A, B OÙ A.id = B.id ET A.event_time ENTRE B.start_time ET B.end_time
J'espère que cela vous aide:)
Y at-il un index sur B (start_time, end_time)? Dans le cas contraire, peut-être ajouter un pourrait accélérer la mise en correspondance des lignes B à A lignes?
Rappelez-vous, si vous ne pouvez pas modifier le schéma, vous pouvez peut-être pas créer de nouveaux index soit?
La seule façon que vous avez à accélérer l'exécution de cette requête est en utilisant des indices.
Prenez soin de mettre dans un index de votre A.event_time puis mettre dans un autre indice B.start_time et B.end_time.
Si, comme vous l'avez dit est la seule condition qui lie les deux entités ensemble, je pense que c'est la seule solution que vous pouvez prendre.
Fede
Daremon, cette réponse est basée sur un de vos commentaires où vous avez dit chaque enregistrement de la table des cartes A à un seul enregistrement dans le tableau B,
Pouvez-vous ajouter une table supplémentaire à votre schéma? Si oui, vous pouvez pré-calculer le résultat de cette requête et le stocker dans une autre table. Vous devrez également garder cette table précalculée en phase avec les changements aux tables A et B
Sur la base de vos commentaires que chaque entrée A correspond à exactement une entrée en B, la solution la plus simple serait de supprimer la AUTOINCREMENT de la colonne id B, remplacer tous les ids de B avec les ids de A.
Mettre un index sur B.start_time descendant puis utilisez cette requête:
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
Comme les seaux de temps en B sont disjoints cela vous donne le premier seau de temps correspondant und vous débarrasser de l'entre, mais en ayant la sous-requête il. y compris peut-être le B.id dans l'index vous donnera une petite augmentation de performance supplémentaire. (Disclaimer: pas sûr de la syntaxe MySQL)
Je ne peux pas penser à la raison pour vous d'avoir une table avec 130.000 lignes avec des intervalles de temps. Quoi qu'il en soit, il doit y avoir une bonne raison de cette conception, et si oui, vous devez éviter d'essayer de calculer une telle se joindre à chaque fois. Alors, voici ma suggestion. Je voudrais ajouter une référence à B.id dans le tableau A (A.B_ID) et utiliser des triggers pour maintenir la cohérence. Chaque fois que vous ajoutez un nouvel enregistrement (déclencheur d'insertion) ou les changements de colonne de even_time (déclencheur de mise à jour), vous recalculer la référence à B que ce temps correspond à. Votre instruction select serait réduite à un seul select * from A.
MySQL ne vous permet pas d'utiliser INDEX ORDER BY WITH RANGE dans les requêtes dérivées.
Voilà pourquoi vous devez créer une fonction définie par l'utilisateur.
Notez que si vos gammes se chevauchent, la requête ne sélectionnera un (qui a commencé la dernière).
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)
Personnellement, si vous possediez relation un à plusieurs et chaque enregistrement de la table un ne porte que sur un enregistrement dans le tableau b, je stocker la table b id dans le tableau une puis effectuez une jointure normale pour obtenir les données. Ce que vous avez actuellement est une mauvaise conception qui ne peut jamais être vraiment efficace.
Il y a deux mises en garde à ma solution:
1) Vous avez dit que vous pouvez ajouter des index mais pas modifier le schéma, donc je ne suis pas sûr que cela fonctionnerait pour vous ou non que vous ne pouvez pas avoir des indices à base de fonction dans MySQL et vous devez créer un supplément colonne du tableau B. 2) L'autre mise en garde à cette solution est que vous devez utiliser le moteur MyISAM pour le tableau B. Si vous ne pouvez pas utiliser MyISAM alors cette solution ne fonctionnera pas parce que MyISAM est pris en charge pour les index spatiaux.
Donc, en supposant que les deux ci-dessus ne sont pas un problème pour vous, ce qui suit devrait fonctionner et vous donner une bonne performance:
Cette solution utilise le support de MySQL pour les données spatiales (voir documentation ). Les types de données spatiales peuvent être ajoutées à une variété de moteurs de stockage, que MyISAM est pris en charge pour les index spatiaux R-Tree (voir documentation ) qui sont nécessaires afin d'obtenir les performances nécessaires. Une autre limitation est que les types de données spatiales ne fonctionnent qu'avec des données numériques de sorte que vous ne pouvez pas utiliser cette technique avec des requêtes de gamme à base de chaîne.
Je vais pas entrer dans les détails de la théorie derrière comment les types spatiale travail et la façon dont l'index spatial est utile, mais vous devriez regarder l'explication de Jeremy Cole en ce qui concerne l'utilisation de types de données spatiales et index pour les recherches. GeoIP Regardez aussi les commentaires qu'ils soulèvent des points utiles et alternative si vous avez besoin de performances brutes et peut renoncer à une certaine précision.
Le principe de base est que nous pouvons prendre le départ / fin et utiliser les deux d'entre eux pour créer quatre points distincts, un pour chaque coin d'un rectangle centré autour de 0,0 sur une grille xy, puis effectuez une recherche rapide dans l'index spatial pour déterminer si le point particulier dans le temps que nous nous soucions est dans le rectangle ou non. Comme mentionné précédemment, voir l'explication de Jeremy Cole pour un aperçu plus approfondi de la façon dont cela fonctionne.
Dans votre cas particulier, nous devrons faire ce qui suit:
1) Modifier la table pour une table MyISAM (note vous ne devriez pas le faire à moins que vous êtes pleinement conscient des conséquences d'un tel changement, comme le manque de transactions et le comportement de verrouillage de table qui sont associés à MyISAM).
alter table B engine = MyISAM;
2) Ensuite, nous ajoutons la nouvelle colonne qui contiendra les données spatiales. Nous utiliserons le type de données de polygones que nous devons être en mesure de tenir un rectangle plein.
alter table B add column time_poly polygon NOT NULL;
3) Ensuite, nous remplissons la nouvelle colonne avec les données (s'il vous plaît garder à l'esprit que tous les processus de mise à jour ou insérer dans le tableau B devront se modifier pour vous assurer qu'ils sont peuplant la nouvelle colonne aussi). Étant donné que les plages de début et de fin des temps, nous devons les convertir en chiffres avec la fonction unix_timestamp (voir documentation ici comment cela fonctionne).
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) Ensuite, nous ajoutons l'index spatial à la table (comme mentionné précédemment, cela ne fonctionne que pour une table MyISAM et produira l'erreur « ERROR 1464 (HY000): Le type de table utilisé ne prend pas en charge les index SPATIAL » ).
alter table B add SPATIAL KEY `IXs_time_poly` (`time_poly`);
5) Ensuite, vous devrez utiliser les éléments suivants de sélection afin d'utiliser l'index spatial lors de l'interrogation des données.
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)));
L'indice de force est là pour faire 100% sûr que MySQL utilise l'index pour la recherche. Si tout va bien expliquer l'exécution d'une au-dessus de sélectionner devrait afficher quelque chose de similaire à ce qui suit:
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)
S'il vous plaît se référer à l'analyse de Jeremy Cole pour plus de détails about les avantages de performance de cette méthode par rapport à un entre l'article.
Laissez-moi savoir si vous avez des questions.
Merci,
-Dipin
quelque chose comme ça?
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
