Query to concatenate and remove common prefix

Question

A bit of history to this : I posted this question elsewhere about 12 months ago, and got some very interesting and useful answers, but now I want to see what the wonderful community here can come up with.

--- In SQL 2005, I have some data

id    ref
==   ==========
1    3536757616
1    3536757617
1    3536757618

and want to get the result

1    3536757616/7/8

so essentially the data is aggregated on id, with the refs concatenated together, separated by a slash '/', but with any common prefix removed so if the data was like

id    ref
==   ==========
2    3536757628
2    3536757629
2    3536757630

I would want to get the result

2    3536757629/28/30

I know I can simply concatenate the refs by using

SELECT distinct
    id,
    stuff ( ( SELECT
                  '/ ' + ref 
              FROM
                  tableA tableA_1
              where tableA_1.id = tableA_2.id
    FOR XML PATH ( '' ) ) , 1 , 2 , '' )
from TableA tableA_2

to give

1   3536757616/ 3536757617/ 3536757618
2   3536757628/ 3536757629/ 3536757630

but it's the bit that removes the common element that I'm after.....

expected result

1   3536757616/7/8
2   3536757628/29/30

--- Code for test data :

create table tableA (id int, ref varchar(50))

insert into tableA
      select 1, 3536757616
union select 1, 3536757617
union select 1, 3536757618

union select 2, 3536757628
union select 2, 3536757629
union select 2, 3536757630

union select 3, 3536754000
union select 3, 3536755000
union select 3, 3536756000
union select 3, 3536757000

union select 4, 1999999999
union select 4, 1199999999
union select 4, 1119999999
union select 4, 1111999999

expected results

1   3536757616/7/8
2   3536757628/29/30
3   3536754000/5000/6000/7000
4   1111999999/119999999/199999999/999999999

Answer 1

This is a bit clunky... :)

Edited to include reference to a static tally table...
Edit 2 -> to include ORDER BY clauses
Edit 3 -> now simplified quite a lot
Edit 4 -> simplified even more - now 33.6 seconds on 8192 sets

DECLARE @tableA TABLE (
id  INT         ,
ref VARCHAR (50));

INSERT  INTO @tableA
    select 1, 3536757616
union select 1, 3536757617
union select 1, 3536757618

union select 2, 3536757628
union select 2, 3536757629
union select 2, 3536757630

union select 3, 3536754000
union select 3, 3536755000
union select 3, 3536756000
union select 3, 3536757000

union select 4, 1999999999
union select 4, 1199999999
union select 4, 1119999999
union SELECT 4, 1111999999
;

WITH   -- get the maximum length, min ref and max ref per group
maxlengths
AS     (SELECT   [id],
                 MAX(LEN(ref)) AS maxreflen,
                 MIN([ref]) AS firstref,
                 MAX([ref]) AS lastref
        FROM     @tableA AS [ta]
        GROUP BY [id]),
       -- get the maximums and find all matching roots for first and last ref
       roots
AS     (SELECT [m].[id],
               [m].[firstref],
               [N]
        FROM   [maxlengths] [m]
               INNER JOIN [dbo].[tally] ON [dbo].[tally].[n] < [m].[maxreflen]
        WHERE  LEFT([m].[firstref], [N]) = LEFT([m].[lastref], [N])),
       -- now get for each id the index and root text
       optimalCombinations
AS     (SELECT id,
               MAX([N]) + 1 AS ind,
               LEFT(MAX([firstref]), MAX([N])) AS root
        FROM   roots
        GROUP BY id)
        -- and select out
SELECT id,
       [mcl].[root] + stuff((SELECT '/' + SUBSTRING([ref], mcl.ind, 1000)
                         FROM   @tableA AS tableA_1                                
                         WHERE  tableA_1.id = mcl.id
                         ORDER BY [tableA_1].[ref]
                         FOR    XML PATH ('')), 1, 1, '')
FROM   optimalCombinations AS mcl
       ORDER BY [mcl].[id];

Answer 2

-- Query
; with 
-- Input Data, include row_no for identifying the 1st (min) ref of the id
data as 
(
    select id, ref, row_no = row_number() over (partition by id order by ref)
    from   @tableA
),
-- cross join to tally table (numbers) to find possible the common length
cte as
(
    select id, num
    from   data a
       cross join numbers n
    where  n.num    between 1 and len(a.ref)
    group by id, num
    having min(left(ref, n.num)) = max(left(ref, n.num))
),
-- get the max common length
cte2 as
(
    select id, c = max(num)
    from   cte
    group by id
)
-- product the result using for xml to concatenate
select  id, ref = stuff(ref, 1, 1, '')
from    cte2 c
    cross apply
    (
       select    '/' + case when x.row_no = 1 then x.ref else stuff(x.ref, 1, c.c, '') end
       from  data x
       where x.id    = c.id
       for xml path('')
    ) r (ref)

/*
id          ref                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              
----------- -----------------------------------------
1           3536757616/7/8
2           3536757628/29/30
3           3536754000/5000/6000/7000
4           1111999999/119999999/199999999/999999999

(4 row(s) affected)
*/

Answer 3

As promised here's the answer I got originally, thanks to Quassnoi over at StackOverflow

Matt assures me that his solution is faster over a large enough data set, although I still marvel at the simplicity if this solution!

;WITH hier(cnt) AS
        (
        SELECT  1
        UNION ALL
        SELECT  cnt + 1
        FROM    hier
        WHERE   cnt <= 100
        )
SELECT  id,(
        SELECT  CASE WHEN ROW_NUMBER() OVER (ORDER BY a2.ref) = 1 THEN ref ELSE '/' + SUBSTRING(ref, mc + 1, LEN(ref)) END 
        FROM    tableA a2
        WHERE   a2.id = q2.id
        FOR XML PATH('')
        )
FROM    (
        SELECT  id, MIN(common) AS mc
        FROM    (
                SELECT  a.id,
                        (
                        SELECT  MAX(cnt)
                        FROM    hier
                        WHERE   SUBSTRING(i.initref, 1, cnt) = SUBSTRING(a.ref, 1, cnt)
                                AND cnt <= LEN(ref)
                        ) AS common
                FROM    (
                        SELECT  id, MIN(ref) AS initref
                        FROM    tableA
                        GROUP BY
                                id
                        ) i
                JOIN    tableA a
                ON      i.id = a.id
                ) q
        GROUP BY
                id
        ) q2

Answer 4

I hope I understood you right, so here is my go at it. (v1.0 Lunchtime hack done in about 10 minutes and only tested on your example data).

Edit 14:37 CET - Fix added to comply with Kev's comment (extra CTE called MatchPos)

Edit 15:25 CET - Final fix so I really comply with Kev ;o)

Edit 15:39 CET - Kev really is playing with us! :o) Those repeating numbers made me reverse the position finding in the CTE LeftMostMatch, but it works now.

Edit 24-09-2010 09:26 - Made a further change to make sure that the results come out in the right order, even for permanent tables as opposed to table variables (order by added to the XML concatenation). The solution as a whole can be sped up by moving SplitRef into a permanent table (Is that allowed?).

DECLARE @TableA TABLE (id int, ref varchar(50))

INSERT  INTO @tableA
    select 1, 3536757616
union select 1, 3536757617
union select 1, 3536757618

union select 2, 3536757628
union select 2, 3536757629
union select 2, 3536757630

union select 3, 3536754000
union select 3, 3536755000
union select 3, 3536756000
union select 3, 3536757000

union select 4, 1999999999
union select 4, 1199999999
union select 4, 1119999999
union select 4, 1111999999
;
WITH    
        SplitRef
          /* Breaks the string down for comparisons across an id */ 
          AS (SELECT    id,
                        ref,
                        SUBSTRING(ref, n, 1) refChar,
                        N refPos
              FROM      @TableA A
              CROSS JOIN SqlAdministration.dbo.Tally T
              WHERE     t.N < LEN(ref) + 1)
              ,
        LeftMostMatch
          /* Finds the left-most position where the digits are still the same */ 
          AS (SELECT    baseref = MIN(cur.ref),
                        rest.ref,
                        MIN(rest.refpos) matchpos
              FROM      SplitRef cur
              LEFT JOIN SplitRef rest ON cur.id = rest.id
                                         AND cur.refPos = rest.refPos
                                         AND cur.ref < rest.ref
                                         AND cur.refChar <> rest.refChar
              WHERE     rest.ref IS NOT NULL
              GROUP BY  rest.ref)

              ,
        ExtendedMatch
        /* Poor hack to force the grouping - otherwise a grouping higher than 
           1 digit on the right won't work */
          AS (SELECT    baseref,
                        MIN(matchpos) matchpos
              FROM      LeftMostMatch
              GROUP BY  baseref),
        Concatenation
          /* Does the concatenation */ 
          AS (SELECT    id,
                        MIN(a.ref) + 
                        (SELECT '/' + SUBSTRING(hm.ref,em.matchpos,(LEN(hm.ref)))
                         FROM      LeftMostMatch hm
                         INNER JOIN ExtendedMatch em ON hm.baseref = em.baseref
                         WHERE     hm.baseref = MIN(a.ref)
                        FOR           XML PATH('')) Result
              FROM      @TableA a
              GROUP BY  id)
    SELECT  *
    FROM    Concatenation ;

Answer 5



create table #temp ( id int, ref varchar(50) )

insert  into #temp
        select  1,
                3536757616
        union
        select  1,
                3536757617
        union
        select  1,
                3536757618
        union
        select  2,
                3536757628
        union
        select  2,
                3536757629
        union
        select  2,
                3536757630
                



SELECT  ID,
        REF + '/' + REPLACE(C3,
                            SUBSTRING(REF, 1,
                                      LEN(REf) - StrLen - CHARINDEX('0', REVERSE(C3))),
                            '')
FROM    ( SELECT    *,
                    ( SELECT TOP 1
                                LEN(CONVERT(VARCHAR, CONVERT(BIGINT, t2.Ref)
                                    - CONVERT(BIGINT, t1.ref))) t
                      FROM      #Temp t2
                      WHERE     t2.ID = t1.ID
                                AND t2.Ref > t1.ref
                      ORDER BY  LEN(CONVERT(VARCHAR, CONVERT(BIGINT, t2.Ref)
                                    - CONVERT(BIGINT, t1.ref))) DESC
                    ) StrLen,
                    STUFF(( SELECT  '/' + ref AS 'data()'
                            FROM    #Temp t2
                            WHERE   t2.ID = t1.ID
                                    AND t2.Ref > t1.ref
                          FOR
                            XML PATH('')
                          ), 1, 1, '') C3
          FROM      ( SELECT    ID,
                                MIN(Ref) Ref
                      FROM      #Temp
                      GROUP BY  ID
                    ) T1
        ) FT

Query to concatenate and remove common prefix

Follow this question

Related Questions