Dédoublonnage et comptage de lignes identiques consécutives

L’auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour,

Je cherche une requête capable de dédoublonner et si possible comptabiliser les doublons, mais uniquement sur des lignes consécutives.

Par exemple étant donné cette table, simplifiée au maximum (l’originale est bien plus complexe évidemment):

create table test (
id int unsigned not null auto_increment,
source varchar(255),
target varchar(255),
date datetime,
primary key(id)
);

ET les données (j’ai omis l’ID parce qu’on s’en fiche complètement ici):

source, target, date
A, B, 2019-08-20 10:00:00
A, B, 2019-08-20 09:00:00
A, B, 2019-08-20 08:00:00
B, C, 2019-08-20 07:45:00
A, C, 2019-08-20 07:30:00
A, B, 2019-08-20 07:00:00
A, B, 2019-08-20 06:00:00

J’aimerais obtenir un résultat dans ce genre:

source, target, date, count
A, B, 2019-08-20 10:00:00, 3
B, C, 2019-08-20 07:45:00, 1
A, C, 2019-08-20 07:30:00, 1
A, B, 2019-08-20 07:00:00, 2

Autrement dit grouper les lignes avec source et target identiques, et idéalement les compter, mais uniquement si elles sont chronologiquement consécutives. Le tout bien évidemment globalement classé par ordre anti-chronologique.

Un simple group by ne fonctionne pas:

select source, target, max(date) as date, count(*) as count
from test
group by source, target

Ne classe plus nécessairement par date globalement (et order by intervenant avant group by, il n’a aucun effet). Quant à:

select source, target, date, count from (
  select source, target, max(date) as date, count(*) as count
  from test
  group by source, target
) as tmp
order by date desc

Règle le problème du tri global mais ne me donne quand même pas le résultat que je souhaite, les lignes non consécutives sont groupées:

source, target, date, count
A, B, 2019-08-20 10:00:00, 5
B, C, 2019-08-20 07:45:00, 1
A, C, 2019-08-20 07:30:00, 1

Est-ce que quelqu’un a une idée ?

Au cas où ça a une importance, je fonctionne avec MariaDB.

Merci.

Ma plateforme avec 23 jeux de société classiques en 6 langues et 13000 joueurs: http://qcsalon.net/ | Apprenez à faire des sites web accessibles http://www.openweb.eu.org/

+0 -0

Salut,

Je pense que tu peux essayer de faire quelque chose avec ROW_NUMBER().

Assez des salamis, je passe au jambon — Je fais un carnage si ce car nage car je nage, moi, Karnaj ! — Le comble pour un professeur de mathématique ? Mourir dans l’exercice de ses fonctions.

+0 -0

Salut, ça faisait longtemps que j’avais pas fait de SQL. Je suis parti de l’hypothèse que 2 lignes n’ont pas la même date. Des lignes consécutives sont des lignes avec les mêmes données hors date et id pour lesquelles il n’existe pas de ligne avec une date entre les deux et une source ou une target différentes.

J’en viens à compter le nombre de lignes correspondant à ces critères et dont la date est inférieure pour chaque ligne de la table de façon à avoir le count le plus haut sur la ligne la plus récente de chaque groupe… Puis j’exclus toutes les lignes qui ne sont pas une borne haute en sachant que les bornes hautes sont les lignes pour lesquelles il n’y a pas de date plus haute dans le même groupe :

SELECT source,
       target,
       date,
       (SELECT COUNT(*)
        FROM Test t_inf
        WHERE t_inf.source = t.source
          AND t_inf.target = t.target
          AND t_inf.date <= t.date
          AND NOT EXISTS(SELECT 1
                         FROM Test t_between
                         WHERE (t_between.source <> t.source
                             OR t_between.target <> t.target)
                           AND t_inf.date < t_between.date
                           AND t_between.date <= t.date)) c
FROM Test t
WHERE NOT EXISTS(SELECT 1
                 FROM Test t_max
                 WHERE t_max.source = t.source
                   AND t_max.target = t.target
                   AND t_max.date > t.date
                   AND NOT EXISTS(SELECT 1
                                  FROM Test t_between2
                                  WHERE (t_between2.source <> t.source
                                      OR t_between2.target <> t.target)
                                    AND t.date < t_between2.date
                                    AND t_between2.date <= t_max.date))
ORDER BY date DESC;

Note : J’ai fait ça parce que c’est marrant mais c’est sûrement plus approprié d’utiliser une proc avec un curseur pour des lignes consécutives :lol:

Édité par Chinoisfurax

+0 -0

Si par hasard ChinoisFurax s’est planté, voici une autre piste (pas finalisée), avec les mots clés LAG ou LEAD :

select source , target, date , lag(source,1,0) over (order by date asc) as source1, 
lag(target,1,0) over (order by date) as target1
from test

A vérifier si il faut utiliser LAG ou LEAD, et order by …ASC ou DESC.

Puis :

select source, target, date from 
(
select source , target, date , lag(source,1,0) over (order by date asc) as source1, 
lag(target,1,0) over (order by date) as target1
from test
)
where source1 <> source or target1 <> target

Reste à ajouter la 4ème colonne.

+0 -0
Auteur du sujet

Bonjour,

@Chinoisfurax

Ca a l’air de fonctionner, mais à condition qu’il n’y ait pas plusieurs fois exactement la même date. Sinon je me retrouve avec autant de lignes en double qu’il n’y a de dates identiques. Problème, ce n’est pas totalement improbable que plusieurs enregistrements se fassent à la même seconde… c’est même assez vraisemblable.

Par contre c’est super lent comme requête… au moins 5 fois plus lent que le group by simple, et je n’ai pas testé avec beaucoup d’enregistrements (à peine 50). Du coup je me demande si je ne vais pas abandonner l’idée et faire les regroupements manuellement dans le langage client.

@elegance:

TA solution ne fonctionne pas, ni avec 'lag' ni avec 'lead’. Dans les deux cas j’obtiens:

Erreur de syntaxe près de '0) over (order by date asc) as source1, lag(target,1,0) over (order by date) ' à la ligne 1

Je ne connais pas du tout ces fonctions. Après une rapide recherche, il semblerait que ce soit spécifique Microsoft, or je suis sous MariaDB.

Merci pour vos réponses

Ma plateforme avec 23 jeux de société classiques en 6 langues et 13000 joueurs: http://qcsalon.net/ | Apprenez à faire des sites web accessibles http://www.openweb.eu.org/

+0 -0

Je les connaissais sous Oracle, j’ai vérifié que ce n’était pas spécifique à Oracle … mais je ne suis pas allé plus loin.

Si tu peux avoir des doublons sur la colonne date, tu vas avoir des grosses difficultés.

Avec ces données :

source, Target, Date 
A, B, 00000
A, B, 00001
C, D, 00001 
A, B, 00002

Tu peux obtenir indifféremment ce résultat :

source, Target, Date 
A, B, 00000 , 1
C, D, 00001 , 1
A, B, 00002 , 2

Ou celui-ci :

source, Target, Date 
A, B, 00001 , 2
C, D, 00001 , 1
A, B, 00002 , 1

Et tu n’as pas de raison valable de préférer l’un plutôt que l’autre … Sauf à dire : Si 2 enregistrements on la même date/seconde, on les ordonne en se basant sur l’ordre alphabétique sur les colonnes Source/Target.

Du code côté client, c’est à éviter au maximum.

Si tu as la possibilité de modifier le modèle de données (=Ajouter une colonne subtile dans cette table), c’est la meilleure piste.

Sinon, il faut trouver la requête magique, et c’est trouvable.

+0 -0

Ca a l’air de fonctionner, mais à condition qu’il n’y ait pas plusieurs fois exactement la même date. Sinon je me retrouve avec autant de lignes en double qu’il n’y a de dates identiques. Problème, ce n’est pas totalement improbable que plusieurs enregistrements se fassent à la même seconde… c’est même assez vraisemblable.

Par contre c’est super lent comme requête… au moins 5 fois plus lent que le group by simple, et je n’ai pas testé avec beaucoup d’enregistrements (à peine 50). Du coup je me demande si je ne vais pas abandonner l’idée et faire les regroupements manuellement dans le langage client.

QuentinC

Yes, tu peux utiliser les IDs à la place des dates mais la condition est que les dates et les IDs soient strictement dans le même ordre au sens prêt, mais fonctionnellement @elegance a complètement raison, en ordonnant ensuite par source et target tu vas favoriser les regroupements pour ton dédoublonnage, je vais donc partir du principe que c’est ce qu’on veut faire pour les solutions plus bas…

Sinon oui, c’était juste parce que c’est drôle, je me doute bien que sur un bon jeu de données c’est pourri x) J’ai pas l’habitude d’écrire des procs et encore moins pour MySQL, d’ailleurs c’est peut-être ma première pour MySQL, mais niveau perf ça devrait être très efficace :

CREATE OR REPLACE PROCEDURE delete_duplicated_links()
BEGIN

    DECLARE v_id VARCHAR(255);
    DECLARE v_source VARCHAR(255);
    DECLARE v_target VARCHAR(255);
    DECLARE v_previous_source VARCHAR(255) DEFAULT NULL;
    DECLARE v_previous_target VARCHAR(255) DEFAULT NULL;
    DECLARE v_done INT DEFAULT 0;

    DEClARE links_cursor CURSOR FOR
        SELECT t.id, t.source, t.target
        FROM Test t
        ORDER BY t.date DESC, t.source DESC, t.target DESC, t.id DESC;
    DECLARE CONTINUE HANDLER FOR NOT FOUND SET v_done = 1;

    OPEN links_cursor;

    links_loop: LOOP
        FETCH links_cursor INTO v_id, v_source, v_target;
        IF v_done THEN
            LEAVE links_loop;
        END IF;
        IF v_source = v_previous_source AND v_target = v_previous_target THEN
            DELETE FROM Test WHERE id = v_id;
        END IF;
        SET v_previous_source = v_source, v_previous_target = v_target;
    END LOOP;

    CLOSE links_cursor;
END$$

ou pour ton select :

CREATE OR REPLACE PROCEDURE list_duplicated_links()
BEGIN

    DECLARE v_id VARCHAR(255);
    DECLARE v_source VARCHAR(255);
    DECLARE v_target VARCHAR(255);
    DECLARE v_date DATETIME;
    DECLARE v_previous_source VARCHAR(255) DEFAULT NULL;
    DECLARE v_previous_target VARCHAR(255) DEFAULT NULL;
    DECLARE v_previous_date DATETIME;
    DECLARE v_count INT DEFAULT 0;
    DECLARE v_done INT DEFAULT 0;

    DEClARE links_cursor CURSOR FOR
        SELECT t.id, t.source, t.target, t.date
        FROM Test t
        ORDER BY t.date, t.source, t.target, t.id;
    DECLARE CONTINUE HANDLER FOR NOT FOUND SET v_done = 1;

    DROP TEMPORARY TABLE IF EXISTS t_duplicated_links;
    CREATE TEMPORARY TABLE IF NOT EXISTS t_duplicated_links
    (
        source VARCHAR(255),
        target VARCHAR(255),
        date   DATETIME,
        count  INT
    );

    OPEN links_cursor;

    links_loop:
        REPEAT
            FETCH links_cursor INTO v_id, v_source, v_target, v_date;

            IF v_done OR v_source <> v_previous_source OR v_target <> v_previous_target THEN
                INSERT INTO t_duplicated_links (source, target, date, count)
                VALUES (v_previous_source, v_previous_target, v_previous_date, v_count);
                SET v_count = 1;
            ELSE
                SET v_count = v_count + 1;
            END IF;

            SET v_previous_source = v_source, v_previous_target = v_target, v_previous_date = v_date;
        UNTIL v_done END REPEAT;

    CLOSE links_cursor;

    SELECT * FROM t_duplicated_links;
    DROP TABLE t_duplicated_links;
END;

CALL list_duplicated_links;

Attention dans les deux je ne trie pas dans le même ordre car les lignes que je garde dans le select ne sont pas celles que je veux supprimer dans la première proc.

Je ne connaissais pas LAG et LEAD, ça fait un truc assez pratique comme base pour un DELETE :

WITH t_nexts AS (
    SELECT t.id,
           t.source,
           t.target,
           t.date,
           LEAD(t.source, 1) OVER (ORDER BY t.date, t.source, t.target, t.id) next_source,
           LEAD(t.target, 1) OVER (ORDER BY t.date, t.source, t.target, t.id) next_target
    FROM Test t)
SELECT tp.id, tp.source, tp.target, tp.date
FROM t_nexts tp
WHERE tp.source <> tp.next_source
   OR tp.target <> tp.next_target
   OR tp.next_source IS NULL AND tp.next_target IS NULL;

Pour le COUNT, c’est plus compliqué mais pas impossible, j’ai une solution, sûrement pas optimale, qui consiste à créer des groupes identifiés uniquement à partir des bornes inf et sup puis de compter le nombre de lignes dans chaque groupe :

WITH t_followings AS (
    SELECT t.id,
           t.source,
           t.target,
           t.date,
           LAG(t.source, 1) OVER (ORDER BY t.date, t.source, t.target, t.id)  previous_source,
           LAG(t.target, 1) OVER (ORDER BY t.date, t.source, t.target, t.id)  previous_target,
           LEAD(t.source, 1) OVER (ORDER BY t.date, t.source, t.target, t.id) next_source,
           LEAD(t.target, 1) OVER (ORDER BY t.date, t.source, t.target, t.id) next_target
    FROM Test t),
     t_lasts AS (
         SELECT tp.id,
                tp.source,
                tp.target,
                tp.date,
                ROW_NUMBER() OVER (ORDER BY tp.source, tp.target, tp.date, tp.id) group_nb
         FROM t_followings tp
         WHERE tp.source <> tp.next_source
            OR tp.target <> tp.next_target
            OR tp.next_source IS NULL AND tp.next_target IS NULL
     ),
     t_firsts AS (
         SELECT tp.id,
                tp.source,
                tp.target,
                tp.date,
                ROW_NUMBER() OVER (ORDER BY tp.source, tp.target, tp.date, tp.id) group_nb
         FROM t_followings tp
         WHERE tp.source <> tp.previous_source
            OR tp.target <> tp.previous_target
            OR tp.previous_source IS NULL AND tp.previous_target IS NULL
     ),
     t_groups AS (
         SELECT tf.source, tf.target, tf.date first_date, tl.date last_date
         FROM t_firsts tf
                  INNER JOIN t_lasts tl ON tl.group_nb = tf.group_nb
     )
SELECT tg.source, tg.target, tg.last_date, COUNT(*)
FROM Test t
         INNER JOIN t_groups tg
                    ON t.date BETWEEN tg.first_date AND tg.last_date AND t.source = tg.source AND t.target = tg.target
GROUP BY tg.source, tg.target, tg.last_date
ORDER BY tg.last_date;

Sans faire de benchmark, je pense que la meilleure solution est celle de la proc, qui devrait être sauf erreur de ma part la plus performante, surtout qu’elle n’a qu’à lire une fois le contenu d’un simple select.

Édité par Chinoisfurax

+0 -0

Voici une requête qui devrait également faire le job. Je l’ai tapée dans notepad, sans le moindre test, donc il peut y avoir des ratés.

with data as 
(
select source , target, date from test  order by  date , source, target
),
data_number as 
(
select source, target, date, rownum  as num from data
),
last_per_block as 
(
select a.source, a.target , a.date , a.num 
from data_number a, data_number b
where b.num(+) = a.num+1 
and ( nvl(b.source, 'XXX' ) <> a.source or nvl(b.target, 'XXX') <> a.target )
order by a.num
) ,
blocks as (
select c.source , c.target, c.date, c.num, rownum as num2
 from last_per_block c
)
select  c.source, c.target, c.date, c.num - nvl(d.num,0) as nbr 
from blocks c, blocks d 
where d.num2 (+)= c.num2 -1

En terme de performance, je serais très curieux de savoir si cette requête est plus ou moins performante par rapport à la procédure proposée par chinoisfurax…. pour une table test qui aurait 1 Million de lignes par exemple.

Si la solution de chinoisfurax est plus performante, ça m’ouvre des horizons nouveaux :)

PS : j’ai finalement testé cette requête sur une table de 3 Millions de lignes, sans index particulier, sur un serveur puissant, et la réponse est arrivée sous 20 secondes

PS2 : J’ai aussi testé la procédure de chinoisfurax. Performances comparables :)

Sauf que la procédure zappe la dernière ligne. Il manque un insert après la ligne 47.

+0 -0

Sauf que la procédure zappe la dernière ligne. Il manque un insert après la ligne 47.

elegance

Pourtant dans mon test elle la prend bien en compte :o Tu es sûr ? Je l’ai testée sur MariaDB au départ et MySQL ensuite (d’ailleurs il faut enlever les OR REPLACE sur MySQL en fait), d’ailleurs ça renvoie la même chose que ta requête réécrite en-dessous.

Ton code n’était pas du code MySQL mais du Oracle. J’ai dû le traduire pour le faire fonctionner, j’en ai profité pour donner des alias un peu plus explicites. C’est bien vu de se baser sur la numérotation d’une seule ligne par groupe pour éviter de compter les lignes !

WITH test_numbered AS (
    SELECT source, target, date, ROW_NUMBER() OVER (ORDER BY date, source, target) num
    FROM Test
),
     last_per_block AS (
         SELECT n.source, n.target, n.date, n.num
         FROM test_numbered n
                  LEFT JOIN test_numbered n_next
                            ON n_next.num = n.num + 1
         WHERE (IFNULL(n_next.source, 'XXX') <> n.source OR IFNULL(n_next.target, 'XXX') <> n.target)
     ),
     blocks AS (
         SELECT l.source, l.target, l.date, l.num, ROW_NUMBER() OVER (ORDER BY l.num) AS num_block
         FROM last_per_block l
     )
SELECT b.source, b.target, b.date, b.num - IFNULL(b_prev.num, 0) AS nbr
FROM blocks b
         LEFT JOIN blocks b_prev
                   ON b_prev.num_block = b.num_block - 1

Ta requête est meilleure que la proc sur la dernière version de MySQL, le problème de la proc est probablement sa manipulation de la table tempo comparativement. À noter que le IFNULL(x, 'XXX') / NVL est indispensable pour avoir de bonnes perfs mais il laisse toujours passer un cas foireux si on veut vraiment être carré, ça donne toujours l’impression de bidouiller :(

Édité par Chinoisfurax

+0 -0

Tu as raison sur la dernière ligne manquante/non-manquante.

J’ai réécrit la procédure pour Oracle, en changeant pas grand chose, mais c’est effectivement moi qui ai créé le bug à ce moment là.

Oui, la valeur fictive 'XXX' que j’introduis, ce n’est pas très beau, et il faut que ce soit une valeur 'hors catalogue’.

Moi, le côté bidouille ne me dérange pas, je suis un adepte du quick-and-dirty, mais si on veut faire plus propre, on peut remplacer cette clause :

(IFNULL(n_next.source, 'XXX') <> n.source OR IFNULL(n_next.target, 'XXX') <> n.target) 

par :

(    n_next.source <> n.source or n_next.target <> n.target 
  or n_next.source is null or n_next.target is null ) 
+0 -0
Auteur du sujet

Bonjour,

Merci pour vos dernières réponses, ça fonctionne bien avec la procédure stockée ou la vue. Je passe donc le sujet en résolu. Entre les deux les performances sont comparables (les différences ne me paraissent pas significatives). Ca ne me surprend pas, dans le sens où ni l’un ni l’autre ne font l’objet d’optimisations spécifiques dans MySQL/MariaDB. Je suppose que la vue doit être un peu plus rapide que la procédure avec Oracle ?

Yes, tu peux utiliser les IDs à la place des dates mais la condition est que les dates et les IDs soient strictement dans le même ordre au sens prêt, mais fonctionnellement

C’est le cas, les ID sont chronologiquement strictement croissants.

Si tu peux avoir des doublons sur la colonne date, tu vas avoir des grosses difficultés. […] Et tu n’as pas de raison valable de préférer l’un plutôt que l’autre … Sauf à dire : Si 2 enregistrements on la même date/seconde, on les ordonne en se basant sur l’ordre alphabétique sur les colonnes Source/Target.

Tu as raison, mais en pratique ça n’a pas beaucoup d’importance si j’obtiens un résultat plutôt que l’autre, les deux conviennent très bien. Ces résultats ne sont pas remachinés par la suite, ils sont seulement affichés comme une sorte de log.

Mais bon, en fonctionnant avec les ID on élimine ce problème de toute façon; et sans effet secondaire.

Merci ! Sujet résolu donc.

Ma plateforme avec 23 jeux de société classiques en 6 langues et 13000 joueurs: http://qcsalon.net/ | Apprenez à faire des sites web accessibles http://www.openweb.eu.org/

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte