[OSM-dev-fr] Trouver des objets ne possédant pas certains tags

[Philippe Verdy]

Ca c'est la théorie, mais certains moteurs SQL admettent dans leurs index
(pourvu qu'ils ne contiennent pas la restriction UNIQUE et donc acceptent
d'indexer les doublons) d'inclure les valeurs NULL.
On peut faire des jointures sur des valeurs NULL de façon efficace (et
d'ailleurs la construction d'une jointure externe impose justement de créer
un index non unique admettant des valeurs NULL, ce la se fait par tri de
chaque index à joindre, et une fusion linéaire des deux dans l'index final.
Ce qui est long c'est justement le fait de réaliser cette fusion de deux
index si les deux index à croiser sont longs. Un moteur SQL peut aussi
réaliser la fusion non pas linéairement mais par recherche indexée de l'un
dans l'autre sans créer d'index temporaire, en fonction des volumétrie
(possible si les deux index à croiser sont de taille très différente, et
surtout si le plus petit peut tenir en peu de pages mémoire; dans ce cas le
moteur fait le croisement en parcourant linéairement avec un curseur
interne le plus grand et effectuant une recherche indexée sur le plus petit
avant de faire ensuite l'inverse si c'est une jointure externe mixte).
Une jointure externe n'est donc pas nécessairement "longue" ou "coûteuse",
cela dépend des volumétries et ce n'est pas long si un des deux index est
très petit, et si le moteur SQL dispose d'un optimiseur statistique capable
d'estimer ces volumétries ; cela dépend aussi des formats d'index
supportés, de la taille de son cache de pages en mémoire, etc.
En effet, savoir si une valeur n'est pas présente dans un index a
exactement le même coût que de savoir si elle y est.

Les scans complets de la table complète (ou de la table ordonnée en index
primaire) n'ont lieu qu'en cas d'absence totale d'index secondaire
contenant la colonne recherchée (un bon optimiseur SQL ne lit pas forcément
la table complète mais peut se contenter de faire un full scan d'un index
secondaire contenant moins de colonnes, même si la colonne cherchée n'est
pas la première, si cet index secondaire sépare maintient la séparation des
colonnes (ce qui n'est pas le cas des index par hachage des colonnes
combinées : le format de l'index joue un rôle sur le fait qu'un moteur
pourra l'utiliser ou pas).

Enfin le choix des index peut varier d'une requête à l'autre en fonction
des éléments cherchés et de leur sélectivité estimée (autrement dit le
moteur peut estimer la sélectivité d'une clé sans parcourir l'index entier,
s'il gère dans la racine de son index des statistiques de sélectivité par
"tranche" de valeurs, et si ces statistiques sont maintenues à jour, ce qui
en général n'est pas instantané en cas de modification des contenus, car
cette mise à jour à un coût lors des insertions, mises à jour ou
suppression d'éléments dans une table et est souvent fait en arrière-plan,
soit par une tâche programmée, soit lorsque le moteur dispose de ressources
pour une tâche non prioritaire en file d'attente. Les plans d'exécution
effectifs pour une même requête avec les mêmes contenus dans les tables et
les même paramètres de requête peuvent donc varier dans le temps en
fonction de ces mises à jour des statistiques de sélectivité).

Mais si on emploie MySQL qui n'a pas de tel optimiseur statistique, alors
oui les jointures externes peuvent être coûteuses car les plans d'exécution
statiques ne sont pas optimum. car pas évolutifs selon les sélectivités
dynamiques. De ce point de vue-là, PostgreSQL est bien meilleur que MySQL
qui reste un moteur un peut trop simpliste où toute l'optimisation se fait
manuellement, selon la façon dont on a directement écrit la requête, sans
utiliser de table dynamique de sélectivité des clés pour chiosir parmi
plusieurs plans alternatifs lequel sera le plus optimal: pour les jointures
externes, MySQL ne sait pas faire autre chose que des scans complets et le
plus souvent uniquement sur les tables primaires et non sur les index
secondaires possibles pourtant plus petits (ça explique aussi la lourdeur
d'écriture des requêtes en MySQL dès qu'on fait des jointures externes car
il faut tout lui expliquer manuellement, il n'a pas d'autonomie pour faire
son choix dynamiquement comme peut le faire Oracle par exemple). MySQL
reste une version très "light" d'Oracle (un peu trop à mon goût), même si
Oracle l'a amélioré depuis l'acquisition de Sun (auteur initial de MySQL)
mais sans trop investir dessus.



Le 5 décembre 2013 23:05, Frédéric Rodrigo <fred.rodrigo at gmail.com> a écrit
:

> Le 05/12/2013 22:51, François Lacombe a écrit :
>
>  Bonsoir,
>>
>> Je souhaite savoir si dans le modèle de données retenu par OSM il est
>> possible de retrouver des objets ne possédant pas certains tags.
>> A partir d'Overpass API par exemple ?
>>
>> Dans OAPI, on peut tout a fait fixer une clause pour trouver des objets
>> qui possèdent un tag défini avec n'importe quelle valeur mais en
>> revanche le langage ne permet pas de définir le conjugué d'une telle
>> contrainte.
>> Est-ce un "oubli" ou une lacune profonde du modèle ?
>>
>>
>> L'objet de ma question ne trouve pas d'application concrète dans OSM.
>> OSM utilise comme beaucoup d'autres systèmes une modélisation EAV pour
>> le stockage des tags dans la base de données.
>> Je cherche actuellement à mettre au point une requête SQL qui retrouve
>> des enregistrements qui ne possèdent pas certaines clés.
>>
>>
>> Merci par avance pour vos indications.
>>
>
>
> Il faut utiliser un jointure externe ("left join" en sql) sur ton tag s'il
> est dans une table de jointure ou IS NULL si c'est une colonne ou un
> hstore... tu ne donnes pas le schéma que tu utilises...
>
> Pourquoi OAPI ne le fait pas ? Sûrement parce que ça coute cher. Pour
> trouver une données indexé il faut chercher dans l'index. Pour trouver une
> absence de données, il faut regarder partout.
>
> Frédéric.
>
>
> _______________________________________________
> dev-fr mailing list
> dev-fr at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/dev-fr
>
-------------- section suivante --------------
Une pièce jointe HTML a été nettoyée...
URL: <http://lists.openstreetmap.org/pipermail/dev-fr/attachments/20131206/eb2a3c56/attachment-0001.html>