IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Développement SQL Server Discussion :

Calcul de chemin le plus court


Sujet :

Développement SQL Server

  1. #1
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2009
    Messages
    118
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 118
    Points : 27
    Points
    27
    Par défaut Calcul de chemin le plus court
    Bonjour à tous,

    J'ai un souci avec la performance d'une requête de calcul de chemin le plus court.

    Tout d'abord, je vous expose le contexte : je souhaite modéliser un graphe orienté multiple. Voila pour la théorie.
    Dans la pratique, cela peut s'apparenter à un GPS. J'ai une liste de sommets (les villes) et des arêtes (les routes). Mes routes sont unidirectionnelles et ont une longueur. Il existe des boucles. De plus il existe aussi des villes reliées entre elles par deux routes distinctes (mais n'ayant pas la même longueur).

    Je connais la ville de départ de toutes mes excursions et je cherche a rallier mon point d'arrivée qui est connu à l'avance. Mais attention, je dois impérativement passer par certaines 'routes' et je ne reviens jamais au point de départ (ce n'est pas un cycle)

    Voici un exemple de graphe que je modélise :

    (Je n'ai pas pu représenter les routes multiples)

    Pour modéliser tout cela, j'ai deux tables fixes : la table des villes et la table des routes. Une route a une ville de départ, une ville d'arrivée et une longueur
    J'ai par ailleurs une table dynamique qui contient une ligne par passage dans une route

    Ma technique utilisée pour résoudre le problème :
    Je calcule l'ensemble des chemins possibles entre la ville de départ et la ville d'arrivée. Avant de partir, je calcule la liste des chemins qui passent par toutes les routes qui m’intéressent et je prend le plus court.
    Je me suis aidé de l'excellent papier sur les requêtes récursives http://sqlpro.developpez.com/cours/s...te-recursives/.

    Dans ma base j'ai 32 villes et 60 routes.

    Le problème est que depuis le point de départ de mon périple vers la dernière ville me donne presque 70 000 possibilités de chemins (en presque 3 minutes).

    Or maintenant on me demande d'effectuer le calcul en temps réel (cad en moins d'environ 100ms) et cela pour n'importe quel point.
    En gros une fois que j'arrive dans une ville, je dois recalculer le chemin le plus court pour aller vers la dernière ville, tout en passant par les routes obligatoires et en éliminant celles déjà visitées.

    La requête récursive me donne une liste de chemins possibles. Chaque chemin comporte un varchar avec les routes empruntées séparées par une virgule. Si je décompose cette liste en lignes pour faciliter la comparaison avec les routes obligatoires, j’obtiens une liste de prés de 2milions de lignes, ce qui est incompatible avec ma performance.

    Pouvez vous m'aider sur la méthode employée ? Trouvez vous la technique viable ou bien dois je repenser la structure pour améliorer la performance ?

    Si vous le souhaitez je peux donner des définitions de tables et les requêtes utilisées pour générer tout cela.

    Merci d'avance !

    (Désolé pour la longueur)

  2. #2
    Modérateur
    Avatar de Waldar
    Homme Profil pro
    Customer Success Manager @Vertica
    Inscrit en
    Septembre 2008
    Messages
    8 452
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Customer Success Manager @Vertica
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2008
    Messages : 8 452
    Points : 17 814
    Points
    17 814
    Par défaut
    Le problème du voyageur de commerce ! La solution réside plutôt dans les l'optimisation linéaire ou les algorithmes génétiques dont le code est plus efficace je pense dans les langages de programmation classiques.

    Probablement faisable en SQL, mais en 100ms j'en doute un peu !
    Néanmoins, c'est un bon sujet !

  3. #3
    Rédacteur

    Avatar de SQLpro
    Homme Profil pro
    Expert bases de données / SQL / MS SQL Server / Postgresql
    Inscrit en
    Mai 2002
    Messages
    21 741
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Expert bases de données / SQL / MS SQL Server / Postgresql
    Secteur : Conseil

    Informations forums :
    Inscription : Mai 2002
    Messages : 21 741
    Points : 52 454
    Points
    52 454
    Billets dans le blog
    5
    Par défaut
    Oubliez la programmation génétique et autres folklore du genre... Vous n'irez pas plus vite.

    Plusieurs éléments doivent être pris en considération :
    1) comment la table est-elle indexée ?
    2) au lieu de stocker les noms des villes dans les chemins, préférez stockez les ID des villes
    3) toutes ces données étant statiques, il suffit de les calculer une bonne fois pour toute puis mettre un trigger sur INSERT, UPDATE, DELETE pour lancer le calcul en bacth de nuit.

    Pour ce faire j'aurais modélisé comme suit :
    1) tables des "puits" villes :
    T_VILLE_VIL
    (VIL_ID, VIL_NOM)
    2) table des "arcs" route :
    T_ROUTE_RTE
    (RTE_ID, VIL_ID_DEPART, VIL_ID_ARRIVE, RTE_DISTANCE_ALLER, RTE_DISTANCE_RETOUR)
    3) table des trajets :
    T_TRAJET_TRJ
    (TRJ_ID, VIL_ID_DEPART, VIL_ID_ARRIVE, TRJ_DISTANCE, TRJ_OK)
    4) table du détail des trajets :
    T_TRAJET_CHEMIN_CHM
    (CHM_ID, TRJ_ID, VIL_ID, CHM_ORDRE, CHM_DISTANCE)

    Les deux dernières tables étant calculées via les triggers mais indirectement. En gros le trigger insère des lignes dans la table T_TRAJET_TRJ avec la ville de départ et d'arrivée avec TRJ_OK = 0 pour signaler que ce trajet est à calculer.

    A +
    Frédéric Brouard - SQLpro - ARCHITECTE DE DONNÉES - expert SGBDR et langage SQL
    Le site sur les SGBD relationnels et le langage SQL: http://sqlpro.developpez.com/
    Blog SQL, SQL Server, SGBDR : http://blog.developpez.com/sqlpro
    Expert Microsoft SQL Server - M.V.P. (Most valuable Professional) MS Corp.
    Entreprise SQL SPOT : modélisation, conseils, audit, optimisation, formation...
    * * * * * Expertise SQL Server : http://mssqlserver.fr/ * * * * *

  4. #4
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2009
    Messages
    118
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 118
    Points : 27
    Points
    27
    Par défaut
    Merci pour vos réponses

    Citation Envoyé par SQLpro Voir le message
    Plusieurs éléments doivent être pris en considération :
    1) comment la table est-elle indexée ?
    Je n'ai pas encore mis d'index sur la table car la volumétrie me parait dèjà et à priori démesurée (voir plus bas)

    Citation Envoyé par SQLpro Voir le message
    2) au lieu de stocker les noms des villes dans les chemins, préférez stockez les ID des villes
    Pas de problème la dessus, je ne travaille jamais avec des chaines variables ou non. En réalité le problème ne concerne pas du tout des villes, mais comme c'est assez compliqué à expliquer, j'ai préféré faire cette analogie qui me parait plus parlante.
    Dans mon cas, les villes sont des points de décision et les routes sont des convoyeurs.

    Citation Envoyé par SQLpro Voir le message
    3) toutes ces données étant statiques, il suffit de les calculer une bonne fois pour toute puis mettre un trigger sur INSERT, UPDATE, DELETE pour lancer le calcul en bacth de nuit.
    Je suis d'accord avec cela. Mon modèle est même mieux que ça, la liste des villes et des routes est totalement fixe. Mais je travaille sur un progiciel et les villes et les routes font partie de la configuration.

    Citation Envoyé par SQLpro Voir le message
    Pour ce faire j'aurais modélisé comme suit :
    1) tables des "puits" villes :
    T_VILLE_VIL
    (VIL_ID, VIL_NOM)
    J'ai ca :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
     
    CREATE TABLE [dbo].[POINT_DECISION](
    	[NO_POINT_DECISION] [int] IDENTITY(1,1) NOT FOR REPLICATION NOT NULL,
    	[DATE_CREATION] [datetime] NOT NULL,
    	[LIBELLE] [varchar](50) NULL,
    	[DEBUT_CONVOYAGE] [bit] NOT NULL,
    	[FIN_CONVOYAGE] [bit] NOT NULL,
    	[NO_POINT_DECISION_EQUIVALENT] [int] NULL,
    	[NB_PASSAGES_CHEMIN] [int] NOT NULL,
     CONSTRAINT [PK_POINT_DECISION] PRIMARY KEY CLUSTERED 
    (
    	[NO_POINT_DECISION] ASC
    )WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
    ) ON [PRIMARY]
    Citation Envoyé par SQLpro Voir le message
    2) table des "arcs" route :
    T_ROUTE_RTE
    (RTE_ID, VIL_ID_DEPART, VIL_ID_ARRIVE, RTE_DISTANCE_ALLER, RTE_DISTANCE_RETOUR)
    A noter que mes routes sont toutes unidirectionnelles
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
     
    CREATE TABLE [dbo].[CONVOYEUR](
    	[NO_CONVOYEUR] [int] NOT NULL,
    	[NO_CONFIGURATION] [int] NOT NULL,
    	[NO_POINT_DECISION_FROM] [int] NOT NULL,
    	[NO_POINT_DECISION_TO] [int] NOT NULL,
    	[DATE_CREATION] [datetime] NOT NULL,
    	[LIBELLE] [varchar](50) NULL,
    	[LONGUEUR] [int] NULL,
    	[VITESSE] [int] NULL,
    	[CORRECTIF] [int] NULL,
     CONSTRAINT [PK_CONVOYEUR] PRIMARY KEY CLUSTERED 
    (
    	[NO_CONVOYEUR] ASC
    )WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
    ) ON [PRIMARY]

    Citation Envoyé par SQLpro Voir le message
    3) table des trajets :
    T_TRAJET_TRJ
    (TRJ_ID, VIL_ID_DEPART, VIL_ID_ARRIVE, TRJ_DISTANCE, TRJ_OK)
    La je ne suis plus très sûr. Je ne vois pas très bien ce que tu mes dans cette table. As tu toutes les possibilités selon toutes les villes du graphe et vers toutes les autres ? Si oui alors le nombre de possibilité est vraiment énorme !

    Pour ma part, j'ai calculé cela :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    CREATE TABLE [dbo].[CHEMIN](
    	[NO_CHEMIN] [bigint] NULL,
    	[LISTE_POINT_DECISION] [varchar](max) NULL,
    	[DISTANCE] [int] NULL,
    	[TEMPS_PARCOURS] [float] NULL,
    	[LISTE_CONVOYEURS] [varchar](max) NULL
    ) ON [PRIMARY]
    Tous mes chemins partent du (ou des) point(s) de décision qui ont le flag DEBUT_CONVOYAGE et vont vers le(s) point(s) qui ont le flag FIN_CONVOYAGE. Mais je n'ai pas les trajets 'internes' dans cette table (c'est peut etre là que se situe mon problème). Par trajet interne j’entends que cette table ne contient pas de chemin entre deux points qui ne sont pas ni un début ni une fin.
    Les données que je possède, me donnent déjà près de 71000 chemins possibles. (pour mémoire, j'ai seulement 32 points de décision et 60 convoyeurs).
    MAIS : comme mon graphe n'est pas simple, il est possible qu'un chemin nécessite de passer plusieurs fois par le même point de décision pour atteindre la sortie. J'ai donc ajouté une colonne NB_PASSAGES_CHEMIN pour limiter le nombre de fois de passage et ainsi ne pas exploser la récursivité de mon CTE.

    Citation Envoyé par SQLpro Voir le message
    4) table du détail des trajets :
    T_TRAJET_CHEMIN_CHM
    (CHM_ID, TRJ_ID, VIL_ID, CHM_ORDRE, CHM_DISTANCE)
    Cela aussi j'ai fait :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    CREATE TABLE [dbo].[CONVOYEUR_CHEMIN](
    	[NO_CHEMIN] [bigint] NULL,
    	[ORDRE] [int] NOT NULL,
    	[NO_CONVOYEURS] int NULL
    ) ON [PRIMARY]
    Mais c'est là que cela me parait coincer : j'ai 2 millions de lignes dans cette table. Et je dois chercher le plus court en faisant le rapprochement avec une autre table contenant la liste des convoyeurs imposés (les endroits par ou je dois impérativement passer).

    Citation Envoyé par SQLpro Voir le message
    Les deux dernières tables étant calculées via les triggers mais indirectement. En gros le trigger insère des lignes dans la table T_TRAJET_TRJ avec la ville de départ et d'arrivée avec TRJ_OK = 0 pour signaler que ce trajet est à calculer.
    Pas de souci de trigger, comme je le disais plus haut, toutes mes données sont fixes. Seul les points de passage imposés varient.

    Mon problème est que trouver le bon chemin ne doit pas prendre de temps car la réponse doit venir en 'temps réel' (cad environ 100ms maxi de temps de réponse) et ce sur n'importe quel point de décision du graphe.
    La requête de recherche du chemin doit selon moi faire un produit cartésien sur les CONVOYEUR_CHEMIN et ma table de chemins imposés. Puis trouver le chemin qui correspond en faisant un 'count' du nombre de convoyeurs du chemin et trouver ceux qui on le même nombre que le nombre de mes étapes imposées. (Je sais pas si c'est très clair). Bref cette requête est à ma portée, mais faire cela avec 2M de lignes, c'est vraiment chaud pour un temps de réponse très très court.
    Pour l'instant, je n'ai pas évalué le temps que cela prend sur mon serveur de test. Je n'ai pas non plus ajouté le moindre index sur les tables que je vous ai présenté. J'en suis encore à la phase de modélisation et d'écriture des requêtes. Mais si cela n'est pas possible en faisant de cette manière, alors je devrais peut être revoir ma structure de données. Cela ne me pose pas de problème de tout casser pour faire différemment.


    Citation Envoyé par SQLpro Voir le message
    A +
    Merci de ton aide !

  5. #5
    Membre expert Avatar de iberserk
    Homme Profil pro
    Architecte de base de données
    Inscrit en
    Novembre 2004
    Messages
    1 795
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Architecte de base de données
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Novembre 2004
    Messages : 1 795
    Points : 3 173
    Points
    3 173
    Par défaut
    Je n'ai pas encore mis d'index sur la table car la volumétrie me parait dèjà et à priori démesurée (voir plus bas)
    Justement...
    Prendre conscience, c'est transformer le voile qui recouvre la lumière en miroir.
    MCTS Database Development
    MCTS Database Administration

  6. #6
    Rédacteur

    Avatar de SQLpro
    Homme Profil pro
    Expert bases de données / SQL / MS SQL Server / Postgresql
    Inscrit en
    Mai 2002
    Messages
    21 741
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Expert bases de données / SQL / MS SQL Server / Postgresql
    Secteur : Conseil

    Informations forums :
    Inscription : Mai 2002
    Messages : 21 741
    Points : 52 454
    Points
    52 454
    Billets dans le blog
    5
    Par défaut
    Citation Envoyé par Batou69 Voir le message
    Je n'ai pas encore mis d'index sur la table car la volumétrie me parait dèjà et à priori démesurée
    JUSTEMENT ! Les index n'ont d'intérêt que si la volumétrie est importante puisque leur but est de faire passer un traitement qui a cout linéaire à un cout logarithmique...
    Déjà, au moins :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    CREATE INDEX X_CON_FROM_TO_LONG ON dbo.CONVOYEUR (NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, LONGUEUR);
    La je ne suis plus très sûr. Je ne vois pas très bien ce que tu mes dans cette table. As tu toutes les possibilités selon toutes les villes du graphe et vers toutes les autres ? Si oui alors le nombre de possibilité est vraiment énorme !
    Énorme ne veut rien dire en matière de bases de données. On parle volume... Sachant qu'une base de données de quelques Go c'est une petite base. Une base moyenne c'est de 30 à 300 Go, une grosse entre 300 et 1 To, une très grosse au dessus du To, et une fois indexé la plupart du temps la recherche d'une données consiste à lire 3 pages de 8 ko !!!
    Faisons un calcul, avec 10 000 villes l'ensemble des trajets fait 10000x10000 = 100 000 000.
    Or dans cette table on ne conserve que 4 entiers, soit 32 octets.
    32 octets par 100 millions, cela fait 3 Go pour la table. Bref du pipi de chat !

    Pour ma part, j'ai calculé cela :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    CREATE TABLE [dbo].[CHEMIN](
    	[NO_CHEMIN] [bigint] NULL,
    	[LISTE_POINT_DECISION] [varchar](max) NULL,
    	[DISTANCE] [int] NULL,
    	[TEMPS_PARCOURS] [float] NULL,
    	[LISTE_CONVOYEURS] [varchar](max) NULL
    ) ON [PRIMARY]
    Ca c'est stupide!!!
    1) c'est pas relationnel : viol de la 1FN : les données doivent être atomique
    2) ça va effectivement générer des centaines de Go

    Commence par revoir cela on discute ensuite.

    1) table des trajet
    2 table des détails de trajets

    A +
    Frédéric Brouard - SQLpro - ARCHITECTE DE DONNÉES - expert SGBDR et langage SQL
    Le site sur les SGBD relationnels et le langage SQL: http://sqlpro.developpez.com/
    Blog SQL, SQL Server, SGBDR : http://blog.developpez.com/sqlpro
    Expert Microsoft SQL Server - M.V.P. (Most valuable Professional) MS Corp.
    Entreprise SQL SPOT : modélisation, conseils, audit, optimisation, formation...
    * * * * * Expertise SQL Server : http://mssqlserver.fr/ * * * * *

  7. #7
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2009
    Messages
    118
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 118
    Points : 27
    Points
    27
    Par défaut
    Citation Envoyé par SQLpro Voir le message
    JUSTEMENT ! Les index n'ont d'intérêt que si la volumétrie est importante puisque leur but est de faire passer un traitement qui a cout linéaire à un cout logarithmique...
    Déjà, au moins :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    CREATE INDEX X_CON_FROM_TO_LONG ON dbo.CONVOYEUR (NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, LONGUEUR);
    Je suis tout à fait d'accord sur l'intérêt des indexes, mais cette table ne fait que 60 lignes, et en plus la requête de calcul des chemin utilise toutes les lignes. Je sors d'un cours d'administration sql et nous avons évoqué l'optimisation. Je connais les avantages des indexes et les utilise dans la plupart des cas, mais pour une table si petite, je n'ai pas compris l’intérêt d'un index sur les convoyeurs. En fait la table tient dans une page.
    Ce point n'étant pas mon problème principal, j'ai suivi ce conseil et mis un index.


    Citation Envoyé par SQLpro Voir le message
    Ca c'est stupide!!!
    1) c'est pas relationnel : viol de la 1FN : les données doivent être atomique
    2) ça va effectivement générer des centaines de Go

    Commence par revoir cela on discute ensuite.

    1) table des trajet
    2 table des détails de trajets
    Alors je crois que je n'ai pas correctement expliqué ce que je veux faire et comment je le fais, car ma table me parait être la seule solution à mon problème.

    La table CHEMIN contient la liste des chemins depuis le point de départ jusqu’à l'arrivée. C'est une table intermédiaire. Je ne m'en sert que pour calculer le détail des chemins.
    Pour faire simple, dans la table chemin j'ai (extrait parmi les 71000 lignes) :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    NO_CHEMIN	LISTE_POINT_DECISION	DISTANCE	TEMPS_PARCOURS	LISTE
    _CONVOYEUR
    1	36,24,20,13,1,2,3,4,5,22,12,16,23,27,18,32,33	301189	7,30017835497835	2,8,9,12,17,55,56,57,58,23,24,59,42,44,46,48
    2	36,24,20,13,1,2,3,4,5,22,12,16,23,27,18,32,33	292954	7,72035692640693	2,8,9,12,17,55,56,57,58,23,24,41,42,44,46,48
    3	36,24,20,13,1,2,3,4,5,22,12,16,23,27,18,32,33	287152	7,51314264069264	2,8,9,12,17,55,56,57,22,23,24,59,42,44,46,48
    Tous mes chemins partent du convoyeur numero 2 et se terminent au 48, c'est bien le but recherché.

    et dans la table du détail des chemins j'ai :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
     
    NO_DETAIL_CHEMIN	NO_CHEMIN	NO_ORDRE	NO_CONVOYEUR
    1	1	1	2
    2	1	2	8
    3	1	3	9
    4	1	4	12
    5	1	5	17
    6	1	6	55
    7	1	7	56
    8	1	8	57
    9	1	9	58
    10	1	10	23
    11	1	11	24
    12	1	12	59
    13	1	13	42
    14	1	14	44
    15	1	15	46
    16	1	16	48
    La table chemin n'est là que pour générer le détail des chemins. Le détail des chemins contient presque 2millions de lignes

    Bien sûr j'ai fait des indexes sur tout cela :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    CREATE NONCLUSTERED INDEX [IX_NO_CONVOYEUR] ON [dbo].[DETAIL_CHEMIN] 
    (
    	[NO_CONVOYEUR] ASC
    )
    INCLUDE ( [NO_CHEMIN]) WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
    GO
    Tout cela fonctionne plutôt bien si je cherche tous les chemins d'un convoyeur X vers un convoyeur Y. Mais la difficulté est que je cherche tous les chemins qui vont de X vers Y et qui passent par une liste donnée. Et la pour faire cela, j'ai ça :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
     
    with 
    	up_con as ( 
    	-- cette partie est la une partie simplifiée de la selection de la liste des 
    	-- convoyeurs imposés. Elle fait appel à d'autre tables que je n'ai pas décrites
    	select
    		no_convoyeur
    	from 
    		convoyeur con
    	where 
    		no_convoyeur in ( 9, 50, 51, 52, 53, 54, 55, 56, 57, 58 )
    	-- fin de la partie simplifiée
    	)
    	, up_nb_con as (
    	select
    		count(*) nb_convoyeur
    	from
    		up_con
    	)
    	, coc_up_con as (
    	select
    		no_chemin
    		, count(*) nb_convoyeur
    	from
    		convoyeur_chemin coc
    	inner join
    		up_con
    	on
    		coc.no_convoyeur = up_con.no_convoyeur
    	group by
    		no_chemin
    	)
    select 
    	* 
    from 
    	coc_up_con
    inner join
    	up_nb_con
    on
    	coc_up_con.nb_convoyeur = up_nb_con.nb_convoyeur
    inner join
    	chemin che
    on 
    	coc_up_con.no_chemin = che.no_chemin
    Voilà.
    Je veux pas vous noyer avec le code, alors j'ai simplifié la requête de dessus. La partie simplifiée est marquée avec un commentaire. Ce que je constate, c'est que la requete ci dessus -telle quelle- est vraiment rapide. La partie que j'ai simplifié est relativement simple et -si je l'éxécute toute seule-, est aussi très rapide. En revanche, lorsque je met les deux ensemble, cela devient vraiment lent.
    Ce n'est pas la première fois que je constate ce genre de phénomène. Vous prenez un requête qui semble optimisée et rapide, vous la collez dans un cte qui lui aussi est rapide tout seul, et le tout devient vraiment lent.

    Je peux fournir la partie simplifiée si cela est pertinent.

    Pour finir, j'en revient à ce que tu disais :
    Citation Envoyé par SQLpro Voir le message
    Ca c'est stupide!!!
    1) c'est pas relationnel : viol de la 1FN : les données doivent être atomique
    2) ça va effectivement générer des centaines de Go

    Commence par revoir cela on discute ensuite.

    1) table des trajet
    2 table des détails de trajets
    Il me semble que c'est ce que j'ai fait. Je comprend que la table que j'ai faite n'est pas relationelle, mais je ne sais pas faire autrement. Comment faire une table des trajets ?

  8. #8
    Rédacteur

    Avatar de SQLpro
    Homme Profil pro
    Expert bases de données / SQL / MS SQL Server / Postgresql
    Inscrit en
    Mai 2002
    Messages
    21 741
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Expert bases de données / SQL / MS SQL Server / Postgresql
    Secteur : Conseil

    Informations forums :
    Inscription : Mai 2002
    Messages : 21 741
    Points : 52 454
    Points
    52 454
    Billets dans le blog
    5
    Par défaut
    C'est justement cette table là qui ne vas pas du tout :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    NO_CHEMIN	LISTE_POINT_DECISION	DISTANCE	TEMPS_PARCOURS	LISTE
    _CONVOYEUR
    1	36,24,20,13,1,2,3,4,5,22,12,16,23,27,18,32,33	301189	7,30017835497835	2,8,9,12,17,55,56,57,58,23,24,59,42,44,46,48
    2	36,24,20,13,1,2,3,4,5,22,12,16,23,27,18,32,33	292954	7,72035692640693	2,8,9,12,17,55,56,57,58,23,24,41,42,44,46,48
    3	36,24,20,13,1,2,3,4,5,22,12,16,23,27,18,32,33	287152	7,51314264069264	2,8,9,12,17,55,56,57,22,23,24,59,42,44,46,48
    Elle viole la 1FN puisque dans une colonne vous avez plusieurs valeurs.

    Commencer par la décomposer en deux :

    Entête avec les données relationnelles, puis détail (peut être deus tables détails d'ailleurs) en reprenant la clef de la première à titre de FK et en décomposant vos LISTE_POINT_DECISION et LISTE
    _CONVOYEUR (comme il y en a 2 et que je ne voit pas de lien entre les deux, alors vous aurez 2 tables détail.

    A +
    Frédéric Brouard - SQLpro - ARCHITECTE DE DONNÉES - expert SGBDR et langage SQL
    Le site sur les SGBD relationnels et le langage SQL: http://sqlpro.developpez.com/
    Blog SQL, SQL Server, SGBDR : http://blog.developpez.com/sqlpro
    Expert Microsoft SQL Server - M.V.P. (Most valuable Professional) MS Corp.
    Entreprise SQL SPOT : modélisation, conseils, audit, optimisation, formation...
    * * * * * Expertise SQL Server : http://mssqlserver.fr/ * * * * *

  9. #9
    Modérateur
    Avatar de Waldar
    Homme Profil pro
    Customer Success Manager @Vertica
    Inscrit en
    Septembre 2008
    Messages
    8 452
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Customer Success Manager @Vertica
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2008
    Messages : 8 452
    Points : 17 814
    Points
    17 814
    Par défaut
    Citation Envoyé par Batou69 Voir le message
    Dans ma base j'ai 32 villes et 60 routes.
    Ce qui serait super ce serait de fournir les données !
    Comme ça on pourrait vraiment s'amuser.

  10. #10
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2009
    Messages
    118
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 118
    Points : 27
    Points
    27
    Par défaut
    Citation Envoyé par Waldar Voir le message
    Ce qui serait super ce serait de fournir les données !
    Comme ça on pourrait vraiment s'amuser.
    Alors là, il n'y a pas, mais vraiment pas, de problème. Quel format ?

  11. #11
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2009
    Messages
    118
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 118
    Points : 27
    Points
    27
    Par défaut
    Citation Envoyé par SQLpro Voir le message
    Commencer par la décomposer en deux :

    Entête avec les données relationnelles, puis détail (peut être deus tables détails d'ailleurs) en reprenant la clef de la première à titre de FK et en décomposant vos LISTE_POINT_DECISION et LISTE
    _CONVOYEUR (comme il y en a 2 et que je ne voit pas de lien entre les deux, alors vous aurez 2 tables détail.

    A +
    Je suis désolé mais je ne comprend pas ce que vous voulez dire.... Car ma seconde table est -elle- tout ce qu'il y a de relationnel et c'est sur cette deuxieme table que je fais mes recherches, celle que vous citez n'est qu'intermédiaire. Peut etre un exemple de lignes obtenues dans les deux tables m'aiderait à comprendre ??

    Merci

  12. #12
    Modérateur
    Avatar de Waldar
    Homme Profil pro
    Customer Success Manager @Vertica
    Inscrit en
    Septembre 2008
    Messages
    8 452
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Customer Success Manager @Vertica
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2008
    Messages : 8 452
    Points : 17 814
    Points
    17 814
    Par défaut
    Citation Envoyé par Batou69 Voir le message
    Alors là, il n'y a pas, mais vraiment pas, de problème. Quel format ?
    Un script SQL classique :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    Create table <...>
    Insert into <...> values <...>

  13. #13
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2009
    Messages
    118
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 118
    Points : 27
    Points
    27
    Par défaut
    Voila :

    J'ai ajoute la table ETAPES qui contient la liste des convoyeurs imposés pour ce cas.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
     
    CREATE TABLE [dbo].[POINT_DECISION](
    	[NO_POINT_DECISION] [int] NOT NULL,
    	[DATE_CREATION] [datetime] NOT NULL,
    	[LIBELLE] [varchar](50) NULL,
    	[DEBUT_CONVOYAGE] [bit] NOT NULL,
    	[FIN_CONVOYAGE] [bit] NOT NULL,
    	[NO_POINT_DECISION_EQUIVALENT] [int] NULL,
    	[NB_PASSAGES_CHEMIN] [int] NOT NULL,
     CONSTRAINT [PK_POINT_DECISION] PRIMARY KEY CLUSTERED 
    (
    	[NO_POINT_DECISION] ASC
    )WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
    ) ON [PRIMARY]
     
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  1, getdate(), 'Transfert T2', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  2, getdate(), 'Transfert T3', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  3, getdate(), 'Transfert T4', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  4, getdate(), 'Transfert T5', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  5, getdate(), 'Transfert T6', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  6, getdate(), 'Transfert T8', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  7, getdate(), 'Transfert T9', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  8, getdate(), 'Transfert T10', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES(  9, getdate(), 'Transfert T11', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 10, getdate(), 'Transfert T12', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 11, getdate(), 'Transfert T202', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 12, getdate(), 'Bras déviateur B251', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 13, getdate(), 'Transfert T203', 0,0,NULL,2 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 14, getdate(), 'Transfert T205', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 15, getdate(), 'Transfert T206', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 16, getdate(), 'Transfert T207', 0,0,NULL,1 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 17, getdate(), 'Transfert T208', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 18, getdate(), 'Transfert T212', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 19, getdate(), 'Balance B1 Dyna-Trad', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 20, getdate(), 'Balance B2 Magauto', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 21, getdate(), 'Balance B4 Dyna', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 22, getdate(), 'Balance B5 Trad', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 23, getdate(), 'Balance B6 finale', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 24, getdate(), 'PUM Magauto', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 25, getdate(), 'PUM Dyna-Trad', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 26, getdate(), 'Secteur Froid T322', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 27, getdate(), 'Ticket adresse T210', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 28, getdate(), 'Ticket adresse T211', 0,0,27,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 29, getdate(), 'Ticket erreur Rappel', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 30, getdate(), 'Ticket erreur Mag 1', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 31, getdate(), 'Ticket erreur Mag 2', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 32, getdate(), 'Pose Facture', 0,0,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 33, getdate(), 'Trieur', 0,1,NULL,0 )
    INSERT POINT_DECISION( NO_POINT_DECISION, DATE_CREATION, LIBELLE, DEBUT_CONVOYAGE, FIN_CONVOYAGE, NO_POINT_DECISION_EQUIVALENT, NB_PASSAGES_CHEMIN ) VALUES( 36, getdate(), 'Lancement', 1,0,NULL,0 )
     
    CREATE TABLE [dbo].[CONVOYEUR](
    	[NO_CONVOYEUR] [int] NOT NULL,
    	[NO_POINT_DECISION_FROM] [int] NOT NULL,
    	[NO_POINT_DECISION_TO] [int] NOT NULL,
    	[DATE_CREATION] [datetime] NOT NULL,
    	[LIBELLE] [varchar](50) NULL,
    	[LONGUEUR] [int] NULL,
    	[VITESSE] [int] NULL,
    	[CORRECTIF] [int] NULL,
     CONSTRAINT [PK_CONVOYEUR] PRIMARY KEY CLUSTERED 
    (
    	[NO_CONVOYEUR] ASC
    )WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
    ) ON [PRIMARY]
     
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  1,36,25,getdate(),'conv 1',    2820, 40,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  2,36,24,getdate(),'conv 2',   12291, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  3,25,19,getdate(),'conv 3',    3564, 40,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  4,19,11,getdate(),'conv 4',    2926, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  5,11, 1,getdate(),'conv 5',    4305, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  6,11, 2,getdate(),'conv 6',    9806, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  7,11,26,getdate(),'conv 7',   82603, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  8,24,20,getdate(),'conv 8',    6547, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES(  9,20,13,getdate(),'conv 9',   38576, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 10,13,30,getdate(),'conv 10',   1823, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 11,13,31,getdate(),'conv 11',   1823, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 12,13, 1,getdate(),'conv 12',  11028, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 13,13,17,getdate(),'conv 13',  75934, 49,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 14,30,13,getdate(),'conv 14',   1823, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 15,31,13,getdate(),'conv 15',   1823, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 16,26,17,getdate(),'conv 16', 140383, 41,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 17, 1, 2,getdate(),'conv 17',   6187, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 18, 1, 6,getdate(),'conv 18',  22824, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 19, 2, 3,getdate(),'conv 19',  12600, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 20, 3, 4,getdate(),'conv 20',  12600, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 21, 4, 5,getdate(),'conv 21',  12684, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 22, 5,22,getdate(),'conv 22',   5963, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 23,22,12,getdate(),'conv 23',   2116, 33,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 24,12,16,getdate(),'conv 24',  19760, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 25,12,17,getdate(),'conv 25',  12918, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 26, 6, 7,getdate(),'conv 26',   9817, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 27, 7, 8,getdate(),'conv 27',  10606, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 28, 8, 9,getdate(),'conv 28',   9798, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 29, 9,10,getdate(),'conv 29',   9838, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 30,10,21,getdate(),'conv 30',   7816, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 31,21,14,getdate(),'conv 31',  18795, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 32,14,15,getdate(),'conv 32',  16873, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 33,14,27,getdate(),'conv 33',  30288, 36,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 34,14,28,getdate(),'conv 34',  30689, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 35,17,15,getdate(),'conv 35',  10953, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 36,17,27,getdate(),'conv 36',  27532, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 37,17,28,getdate(),'conv 37',  27817, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 38,15,16,getdate(),'conv 38',   8595, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 39,15, 2,getdate(),'conv 39',  54870, 60,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 40,16,29,getdate(),'conv 40',   1302, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 41,16,23,getdate(),'conv 41',  11765, 28,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 42,23,27,getdate(),'conv 42',  46830, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 43,23,28,getdate(),'conv 43',  47230, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 44,27,18,getdate(),'conv 44',   3108, 40,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 45,28,18,getdate(),'conv 45',   3108, 40,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 46,18,32,getdate(),'conv 46',   6546, 40, 30 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 47,18,33,getdate(),'conv 47',  54059, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 48,32,33,getdate(),'conv 48',  48200, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 49,29,16,getdate(),'conv 49',  11113, 30,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 50, 6, 7,getdate(),'conv 50',  20000,  1,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 51, 7, 8,getdate(),'conv 51',  20000,  1,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 52, 8, 9,getdate(),'conv 52',  20000,  1,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 53, 9,10,getdate(),'conv 53',  20000,  1,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 54,10,21,getdate(),'conv 54',  20000,  1,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 55, 2, 3,getdate(),'conv 55',  20000,  1,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 56, 3, 4,getdate(),'conv 56',  20000,  1,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 57, 4, 5,getdate(),'conv 57',  20000,  1,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 58, 5,22,getdate(),'conv 58',  20000,  1,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 59,16,23,getdate(),'conv 59',  20000,  1,  0 )
    INSERT CONVOYEUR( NO_CONVOYEUR, NO_POINT_DECISION_FROM, NO_POINT_DECISION_TO, DATE_CREATION, LIBELLE, LONGUEUR, VITESSE, CORRECTIF ) VALUES( 60,26,26,getdate(),'conv 60',  20000,  1,  0 )
     
    CREATE TABLE [dbo].[ETAPES](
    	[NO_ETAPE] [int] NOT NULL,
    	[NO_CONVOYEUR] [int] NOT NULL,
     CONSTRAINT [PK_ETAPES] PRIMARY KEY CLUSTERED 
    (
    	[NO_ETAPE] ASC
    )WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
    ) ON [PRIMARY]
     
    INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  1,  9 )
    INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  2, 50 )
    INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  3, 51 )
    INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  4, 52 )
    INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  5, 53 )
    INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  6, 54 )
    INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  7, 55 )
    INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  8, 56 )
    INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES (  9, 57 )
    INSERT ETAPES( NO_ETAPE, NO_CONVOYEUR ) VALUES ( 10, 58 )

  14. #14
    Modérateur
    Avatar de Waldar
    Homme Profil pro
    Customer Success Manager @Vertica
    Inscrit en
    Septembre 2008
    Messages
    8 452
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Customer Success Manager @Vertica
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2008
    Messages : 8 452
    Points : 17 814
    Points
    17 814
    Par défaut
    J'ai pu jouer avec vos données.

    Je suis parti sur une solution calculée à la volée, pas sur la solution de SQLPro qui - puisqu'elle consiste à distribuer le calcul en tâche planifiée la nuit pour ne plus faire qu'une simple lecture en journée - sera beaucoup plus performante dès lors que la volumétrie augmentera.

    En fait, la requête dynamique répond mieux que ce que je ne pensais, comme vous je suis parti sur une CTE récursive.
    Par contre, je ne retrouve pas vos 70000 ou 2M de lignes dans les étapes intermédiaires (en fait mes étapes intermédiaires sont présentes dans le select, je n'ai rien en plus du script que vous avez fourni).

    Je ne suis pas tombé à 100 ms comme vous le souhaitez, mais c'est déjà pas trop mal :
    j'ai tronqué les 0 des "lob physical reads" et "lob read-ahead reads" pour conserver la mise en page
    SQL Server parse and compile time: 
       CPU time = 47 ms, elapsed time = 82 ms.
    
    (8 ligne(s) affectée(s))
    Table 'Worktable'     . Scan count   2, logical reads  3726, physical reads 0, read-ahead reads 0, lob logical reads 1954.
    Table 'POINT_DECISION'. Scan count   1, logical reads  1416, physical reads 0, read-ahead reads 0, lob logical reads    0.
    Table 'ETAPES'        . Scan count 355, logical reads 42836, physical reads 0, read-ahead reads 0, lob logical reads    0.
    Table 'CONVOYEUR'     . Scan count 354, logical reads   708, physical reads 0, read-ahead reads 0, lob logical reads    0.
    
    SQL Server Execution Times:
       CPU time = 266 ms,  elapsed time = 289 ms.
    Le meilleur chemin ramené par ma requête sur vos données est celui-ci :
    chemin                                                      longueur
    ----------------------------------------------------------- -----------
    36,24,20,13,1,6,7,8,9,10,21,14,15,2,3,4,5,22,12,17,27,18,33 461537
    Déjà, est-ce que vous avez trouvé la même chose ?

    Si oui, comment procède-t-on : je vous donne ma solution brut de fonderie ou j'essaie de vous y amener à partir de votre solution ?

  15. #15
    Membre expert Avatar de iberserk
    Homme Profil pro
    Architecte de base de données
    Inscrit en
    Novembre 2004
    Messages
    1 795
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Architecte de base de données
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Novembre 2004
    Messages : 1 795
    Points : 3 173
    Points
    3 173
    Par défaut
    289 ms

    Ca reste inperceptible pour l'utilisateur...
    Prendre conscience, c'est transformer le voile qui recouvre la lumière en miroir.
    MCTS Database Development
    MCTS Database Administration

  16. #16
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2009
    Messages
    118
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 118
    Points : 27
    Points
    27
    Par défaut
    Citation Envoyé par Waldar Voir le message
    Le meilleur chemin ramené par ma requête sur vos données est celui-ci :
    chemin                                                      longueur
    ----------------------------------------------------------- -----------
    36,24,20,13,1,6,7,8,9,10,21,14,15,2,3,4,5,22,12,17,27,18,33 461537
    Déjà, est-ce que vous avez trouvé la même chose ?
    OUI !!

    mais moi j'ai plutot ca :

    SQL Server \endash  Temps d'exécution*:
    , Temps UC = 0 ms, temps écoulé = 1 ms.
    Temps d'analyse et de compilation de SQL Server : 
    , Temps UC = 0 ms, temps écoulé = 1 ms.
    
    (100*ligne(s) affectée(s))
    Table 'CHEMIN'. Nombre d'analyses 1, lectures logiques 1301, lectures physiques 0, lectures anticipées 0
    Table 'Worktable'. Nombre d'analyses 0, lectures logiques 0, lectures physiques 0, lectures anticipées 0
    Table 'DETAIL_CHEMIN'. Nombre d'analyses 10, lectures logiques 1055, lectures physiques 0, lectures anticipées 0
    Table 'ETAPES'. Nombre d'analyses 2, lectures logiques 4, lectures physiques 0, lectures anticipées 0
    
    SQL Server \endash  Temps d'exécution*:
    , Temps UC = 453*ms, temps écoulé = 450*ms.
    
    Alors je peux vous donner les trois requetes utilisées pour arriver à ce résultat, mais je vous demande de l'indulgence car je ne suis pas non plus le plus grand expert du coin !!

    Les trois étapes sont :

    • 1 - requête récursive pour calculer l'ensemble des chemins possibles entre la gare de départ et la gare d'arrivée : résultat placé dans la table CHEMIN avec un numéro comme clef (70968 lignes). J'ai suivi l'excellent tutoriel : http://sqlpro.developpez.com/cours/s...te-recursives/
      Cela me donne des chemins avec un varchar contenant les points de décision et les convoyeurs dans l'ordre de parcours pour chaque chemin.
      (Aie c'est la que je sens que je vais faire hurler les puristes)
      A noter que cette table est 'statique', comme mes convoyeurs sont des données fixes, elle est calculée une seule fois
    • 2 - Eclatement de la table chemin en une table DETAIL_CHEMIN contenant une ligne par chemin et par convoyeur (1786536 lignes)
    • 3 - recherche des chemins qui m'intéressent dans la table précédente en faisant un produit croisé avec la table ETAPES puis en filtrant les chemins qui ont le nombre d'étapes demandées (soit 10 ici)
      A noter que je doute moi même de la fiabilité de l'algo basé sur un comptage sans s'assurer que l'on compte bien les même convoyeurs


    Le tout me donne le résultat....

    Citation Envoyé par Waldar Voir le message
    Si oui, comment procède-t-on : je vous donne ma solution brut de fonderie ou j'essaie de vous y amener à partir de votre solution ?
    En effet je préfèrerais vous présenter ma solution et vous m'expliquiez où sont mes erreurs, cela sera formateur...

  17. #17
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2009
    Messages
    118
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 118
    Points : 27
    Points
    27
    Par défaut
    La table CHEMIN et DETAIL_CHEMIN

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
     
    CREATE TABLE [dbo].[CHEMIN](
    	[NO_CHEMIN] [bigint] NOT NULL,
    	[LISTE_POINT_DECISION] [varchar](max) NULL,
    	[DISTANCE] [int] NULL,
    	[TEMPS_PARCOURS] [float] NULL,
    	[LISTE_CONVOYEURS] [varchar](max) NULL
    ) ON [PRIMARY]
     
    CREATE TABLE [dbo].[DETAIL_CHEMIN](
    	[NO_DETAIL_CHEMIN] [bigint] NOT NULL,
    	[ORDRE] [int] NOT NULL,
    	[NO_CHEMIN] [int] NOT NULL,
    	[NO_CONVOYEUR] int NOT NULL
    ) ON [PRIMARY]
    Avec les indexes qui vont bien :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
     
    ALTER TABLE [dbo].[CHEMIN] ADD  CONSTRAINT [PK_CHEMIN] PRIMARY KEY CLUSTERED 
    (
    	[NO_CHEMIN] ASC
    )WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
    GO
    ALTER TABLE [dbo].[DETAIL_CHEMIN] ADD  CONSTRAINT [PK_DETAIL_CHEMIN] PRIMARY KEY CLUSTERED 
    (
    	[NO_DETAIL_CHEMIN] ASC
    )WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
    GO
     
    CREATE NONCLUSTERED INDEX [IX_NO_CONVOYEUR] ON [dbo].[DETAIL_CHEMIN] 
    (
    	[NO_CONVOYEUR] ASC
    )
    INCLUDE ( [NO_CHEMIN]) WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
    GO
    (édité à la main donc pas certain qu'ils passent tous)

  18. #18
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2009
    Messages
    118
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 118
    Points : 27
    Points
    27
    Par défaut
    LA requête pour construire la table CHEMIN :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
     
    WITH
    	CONVOYEUR_CTE
    	AS (
    		SELECT DISTINCT 
    			PTD.NO_POINT_DECISION NO_POINT_DECISION_TO
    			, 0 ETAPES
    			, CAST( NO_POINT_DECISION AS VARCHAR(MAX) ) CHEMIN
    			, 0 DISTANCE
    			, CAST( 0.0 AS float ) TEMPS_PARCOURS
    			, CAST( '' AS VARCHAR(MAX) ) CONVOYEURS
    		FROM
    			dbo.POINT_DECISION PTD
    		WHERE
    			PTD.DEBUT_CONVOYAGE = 1
    		UNION ALL
    		SELECT 
    			CON.NO_POINT_DECISION_TO
    			, CON_CTE.ETAPES + 1
    			, CON_CTE.CHEMIN + ',' + CONVERT( VARCHAR(10), CON.NO_POINT_DECISION_TO )
    			, CON_CTE.DISTANCE + CON.LONGUEUR
    			, CON_CTE.TEMPS_PARCOURS + 
    			  CASE 
    				WHEN CON.VITESSE = 0  THEN 0 
    				ELSE CON.LONGUEUR / ( 1000.0 * CON.VITESSE ) + COALESCE( CON.CORRECTIF, 0 ) / 60.0
    			END
    			, CASE
    				WHEN CON_CTE.CONVOYEURS = '' THEN CAST( CON.NO_CONVOYEUR AS VARCHAR(MAX) )
    				ELSE CON_CTE.CONVOYEURS + ',' + CAST( CON.NO_CONVOYEUR AS VARCHAR(MAX) )
    			END
    		FROM
    			dbo.CONVOYEUR CON --arrival
    		INNER JOIN
    			CONVOYEUR_CTE CON_CTE --departure
    		ON
    			CON_CTE.NO_POINT_DECISION_TO = CON.NO_POINT_DECISION_FROM
    		INNER JOIN
    			dbo.POINT_DECISION PTD
    		ON
    			CON.NO_POINT_DECISION_TO = PTD.NO_POINT_DECISION
    		WHERE
    			dbo.ufn_CountString( ',' + CON_CTE.CHEMIN + ',', ',' + CONVERT( VARCHAR(10), PTD.NO_POINT_DECISION ) + ',' ) <= PTD.NB_PASSAGES_CHEMIN
    	)
    INSERT
    	CHEMIN(NO_CHEMIN,LISTE_POINT_DECISION, DISTANCE, TEMPS_PARCOURS,LISTE_CONVOYEURS)
    SELECT
    	row_number() over (order by CON_CTE.CHEMIN ) NO_CHEMIN
    	, CON_CTE.CHEMIN LISTE_POINT_DECISION
    	, CON_CTE.DISTANCE
    	, CON_CTE.TEMPS_PARCOURS
    	, CON_CTE.CONVOYEURS LISTE_CONVOYEURS
    FROM
    	CONVOYEUR_CTE CON_CTE
     
    INNER JOIN
    	dbo.POINT_DECISION PTD
    ON
    	PTD.NO_POINT_DECISION = CON_CTE.NO_POINT_DECISION_TO
    	AND PTD.FIN_CONVOYAGE = 1
    Où la fonction ufn_CountString compte le nombre d’occurrences d'une chaine dans une autre

    Temps d’exécution : (sans l'insert) !!
    Temps d'analyse et de compilation de SQL Server : 
    , Temps UC = 0*ms, temps écoulé = 1*ms.
    
    SQL Server \endash  Temps d'exécution*:
    , Temps UC = 0*ms, temps écoulé = 1*ms.
    Temps d'analyse et de compilation de SQL Server : 
    , Temps UC = 47*ms, temps écoulé = 54*ms.
    
    (70968*ligne(s) affectée(s))
    Table 'Worktable'. Nombre d'analyses 2, lectures logiques 5799963, lectures physiques 0, lectures anticipées 0, lectures logiques de données d'objets volumineux 2193336
    Table 'POINT_DECISION'. Nombre d'analyses 1, lectures logiques 878863, lectures physiques 0, lectures anticipées 0, lectures logiques de données d'objets volumineux 0
    Table 'CONVOYEUR'. Nombre d'analyses 1, lectures logiques 432555, lectures physiques 0, lectures anticipées 0, lectures logiques de données d'objets volumineux 0
    
    SQL Server \endash  Temps d'exécution*:
    , Temps UC = 132046*ms, temps écoulé = 135647*ms.
    (SQLPro va pas être content de voir cette table)

  19. #19
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2009
    Messages
    118
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 118
    Points : 27
    Points
    27
    Par défaut
    La requete pour construire la table DETAIL_CHEMIN

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
     
    WITH 
    	CTE
    	AS (
        SELECT 
    		NO_CHEMIN
    		, 0 POS
    		, convert( bigint, 1 ) POS_BEGIN
    		, CHARINDEX( ',', LISTE_CONVOYEURS + ',' ) POS_END
    		, LISTE_CONVOYEURS
    	FROM
    		CHEMIN
        UNION ALL
        SELECT 
    		NO_CHEMIN
    		, POS + 1
    		, POS_END + 1
    		, CHARINDEX( ',', LISTE_CONVOYEURS + ',', pos_end + 1 ) 
    		, LISTE_CONVOYEURS
    	FROM 
    		CTE
    	WHERE 
    		CHARINDEX( ',', LISTE_CONVOYEURS + ',', pos_end + 1 ) > 0 )
    insert
    	detail_chemin(no_detail_chemin,position,no_chemin,no_convoyeur)
    SELECT 
    	row_number() over (order by NO_CHEMIN ) NO_CHEMIN
    	, pos + 1 ORDRE
    	, NO_CHEMIN
    	, convert( int, SUBSTRING( LISTE_CONVOYEURS, pos_begin , pos_end - pos_begin ) ) NO_CONVOYEUR
    FROM
    	CTE
    order by no_chemin,pos
    OPTION ( MAXRECURSION 0 )
    Celle là elle prend environ 15 minutes, je l'ai pas ré exécutée. Elle génère 1,7milllion de lignes.
    Mais la encore je ne l’exécute qu'une seule fois..

  20. #20
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Octobre 2009
    Messages
    118
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 118
    Points : 27
    Points
    27
    Par défaut
    Enfin la requête finale qui me donne le chemin le plus court selon les étapes dans la table ETAPES:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
     
    with 
    	up_con as ( 
    	select no_convoyeur from etapes
    	)
    	, up_nb_con as (
    	select
    		count(*) nb_convoyeur
    	from
    		up_con
    	)
    	, coc_up_con as (
    	select
    		no_chemin
    		, count(*) nb_convoyeur
    	from
    		detail_chemin coc
    	inner join
    		up_con
    	on
    		coc.no_convoyeur = up_con.no_convoyeur
    	group by
    		no_chemin
    	)
    select 
    	* 
    from 
    	coc_up_con
    inner join
    	up_nb_con
    on
    	coc_up_con.nb_convoyeur = up_nb_con.nb_convoyeur
    inner join
    	chemin che
    on 
    	coc_up_con.no_chemin = che.no_chemin
    order by 
    	distance asc
    Ouf !!

    L'intérêt c'est que je ne fait que la derniere requête à chaque fois que je dois trouver le meilleur chemin. De plus la table ETAPES dépend de chaque élément sur mon convoyage, je doit donc connaitre le chemin pour d'autres étapes imposées sans tout recalculer....

Discussions similaires

  1. 2D C++ : Améliorer Recherche chemin le plus court
    Par Julien_C++ dans le forum Développement 2D, 3D et Jeux
    Réponses: 1
    Dernier message: 04/11/2006, 14h58
  2. chemin le plus court
    Par fabetvince dans le forum Algorithmes et structures de données
    Réponses: 21
    Dernier message: 01/06/2006, 01h14
  3. Trouver le chemin le plus court
    Par poly128 dans le forum Langage
    Réponses: 8
    Dernier message: 24/04/2006, 09h28
  4. chemin le plus court
    Par fabetvince dans le forum Algorithmes et structures de données
    Réponses: 13
    Dernier message: 21/04/2006, 14h38
  5. algorithme de Ford (recherche chemin le plus court)
    Par abstraite dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 19/05/2005, 11h39

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo