Les arbres algébriques

[Glauben]

Bonjour,

Une requête peut avoir plusieurs arbres algébriques. Parmis ces arbres, il existe un qui est optimal.

Comment implémenter les arbres algébriques et comment choisir l'arbre optimal ?

Merci.

[Oishiiii]

Bonjour,

Ce que vous appelez un "arbre algébrique" est simplement une représentation graphique d'une opération algébrique ?

Envoyé par Glauben

Comment implémenter les arbres algébriques et comment choisir l'arbre optimal ?

Qu'est-ce que vous entendez par "implémenter" les arbres algébriques ?

Qu'entendez-vous par "optimal" ?
Vous ne faites certainement pas référence aux éventuelles performances d'exécution, puisqu'elle ne concernent pas le modèle relationnel (et son algèbre) mais l'implémentation (le SGBDR).
Si je devais choisir entre deux arbres produisant le même résultats, a priori je choisirai celui qui fait intervenir le moins d'opérateurs.

[Glauben]

Bonjour,

Envoyé par Oishiiii

Ce que vous appelez un "arbre algébrique" est simplement une représentation graphique d'une opération algébrique ?

L'arbre algébrique est une représentation graphique du plan d'exécution d'une requête SQL. Tous les plan d'exécution possible pour un requête donnée.

Envoyé par Oishiiii

Qu'est-ce que vous entendez par "implémenter" les arbres algébriques ?

Implémenter c-à-d construire un logiciel qui détecte tous les arbres algébriques d'une requête .

Je cherche la structure de données adéquat pour "représenter" les arbres algébriques d'une requête.

Envoyé par Oishiiii

Qu'entendez-vous par "optimal" ?
Vous ne faites certainement pas référence aux éventuelles performances d'exécution, puisqu'elle ne concernent pas le modèle relationnel (et son algèbre) mais l'implémentation (le SGBDR).
Si je devais choisir entre deux arbres produisant le même résultats, a priori je choisirai celui qui fait intervenir le moins d'opérateurs.

Je choisis l'arbre qui donne un temps de réponse court par rapport aux autres arbres algébriques.

Ma question: Est ce que c'est possible de construire un logiciel qui détecte les arbres algébriques en utilisant JAVA et Oracle par exemple !!!!!!!!!
si oui , comment faire ?

Vous pouvez trouver ci-joint un exemple d'une arbre algébrique.

[Sun22]

Bonjour,
avez vous trouvé la structure convenable pour les plans de requêtes ?

Merci ^^

[Glauben]

Envoyé par Sun22

Bonjour,
avez vous trouvez la structure convenable pour les plans de requêtes?

Merci ^^

Bonjour,

Pas encore

[SQLpro]

Envoyé par Glauben

Je choisis l'arbre qui donne un temps de réponse court par rapport aux autres arbres algébriques.

mais quels sont vos critères pour calculer un temps de réponse ?
Dans les SGBDR comme Oracle ou SQL Server, les critères sont :
1) la nature de l'opération et donc sa durée unitaire
2) l'estimation de cardinalité
3) le calcul de volumétrie résultant, basé sur la longueur de ligne moyenne
4) la possibilité d'utiliser le parallélisme.
Cela est du au fait que les SGBDR stockent des histogrammes statistiques sur les données des colonnes...

En effet, entre deux arbres de plan de requêtes, ce n'est pas toujours celui qui a le moins d'opérations qui sera le plus rapide, ni celui dont le coût global est minimal qui sera finalement retenu.
Par exemple avec le parallélisme, il n'est pas rare d'avoir un temps global d'exécution plus court, mais une durée CPU plus longue qu'avec une requête mono threadée... !
En particulier les opérations suivantes peuvent être parallélisées :

• SCAN
• GROUP BY
• ORDER BY
• et tous les calculs d'agrégats : COUNT, MAX, MIN, SUM, AVG...

A +

[Glauben]

Merci SQLpro, est ce que vous avez un document qui explique comment calculer le coût d'une requête SQL ?.

[pacmann]

Salut !

C'est une lourde tâche, et ça dépend pas mal du SGBD que tu choisis.

Exemple pour Oracle :
http://download.oracle.com/docs/cd/B...3/optimops.htm

Une fois que tu auras une bonne idée des différentes problématiques, il faudra que tu limites ton périmètre, car recoder un CBO (cost based optimizer), ça pourrait te prendre plusieurs centaines d'années

[SQLpro]

Envoyé par Glauben

Merci SQLpro, est ce que vous avez un document qui explique comment calculer le coût d'une requête SQL ?.

C'est tout a fait spécifique à chaque SGBDR....

Quelques éléments théoriques :
http://masters.donntu.edu.ua/2007/fv...processing.pdf (synthèse sur l'optimiseur de SQL Server)
http://infolab.stanford.edu/~hyunjun.../ioannidis.pdf
http://www.serc.iisc.ernet.in/gradua...es/atreyee.pdf (picasso et postGreSQL)
http://www.google.fr/url?sa=t&source...S8oU8g&cad=rja
http://research.ict.ru.ac.za/g01m1261/CSHnsThesis.pdf (comparaisons optimiseur MySQL et SQL Server)
http://research.microsoft.com/pubs/1..._profiling.pdf (SQL Server TPC-H)

A +

[Glauben]

Merci pour le lien.

Je cherche pour Oracle.

[Waldar]

Overview of the Optimizer

[skuatamad]

D'autres lectures qui pourront t'intéresser autour du CBO :

Comment l'optimiseur d'Oracle calcule le coût
Le site de Wolfgang Breitling notamment son papier intitulé :
A Look under the Hood of CBO: The 10053 Event
le blog de Jonathan Lewis

Ce qui t'interesse c'est la trace 10053, qui contient les différentes combinaisons de plans envisagées par Oracle.

Ma question: Est ce que c'est possible de construire un logiciel qui détecte les arbres algébriques en utilisant JAVA et Oracle par exemple !!!!!!!!!
si oui , comment faire ?

Je dirais non ou je n'en vois pas l'intérêt, en tout cas c'est plutôt à l'éditeur (Oracle corp) de proposer ce genre de soft, il y a peut être déjà des choses dans le tunning pack.
A ton niveau tu peux essayer de développer un parseur en java qui annalysera la trace 10053... bon courrage !

[pacmann]

Pas l'intérêt, pas l'intérêt, pour nous non...

...Mais peut être que c'est une espèce de projet scolaire ?

Si c'est le cas, il faut voir quel est l'énoncé du projet, afin d'avoir la bonne approche.

L'idée étant sûrement tout d'abord de créer un modèle générique de coût par étape. (genre définir cette notion d'arborescence avec étape mère / fille, associer un coût par étape, définir comment s'additionne / se multiplie le coût lors du parcours, ...)
... puis augmenter le périmètre au fur et mesure.

Ca a l'air bien drôle en tous cas

[Glauben]

Bonjour,

Oui, c'est un projet de fin d'étude.

Merci pour vos réponses, mais j'ai pas trouvé la réponse alors j'ai changé le thème complétement.

Je ne veux pas utiliser la tag Résolu par ce que je veux trouver une solution à ce problème avec vous.

Merci.