Natural (human alpha-numeric) sort in Microsoft SQL Server

7
votes

Thank you for taking time to read all this, its a lot! Appreciate all you fellow enthusiasts!

How to natural sort?

ie. order a set of alpha numeric data to appear as: 

Season 1, Season 2, Season 10, Season 20

instead of 

Season 1, Season 10, Season 2, Season 20

I use a very practical example of tv seasons in a very practical format as case.

I am looking to accomplish the following:

  1. Share my working solution for others
  2. Ask your help in figuring how to shorten it (or find better solution) to my solution
  3. Can you solve criteria 7 below?

I spent about 2 hours researching online and another 3 hours building this solution. Some of the reference material came from:

Some of the solutions found on SO and other sites only work for 90% of cases. However, most/all do NOT work if you have multiple numeric values in your text, or will cause SQL error if there isn't a number found in the text at all.

I have created this SQLFiddle link to play around with (includes all below code).

Here is the create statement:

create table tvseason
(
    title varchar(100)
);

insert into tvseason (title)
values ('100 Season 03'), ('100 Season 1'),
       ('100 Season 10'), ('100 Season 2'),
       ('100 Season 4'), ('Show Season 1 (2008)'),
       ('Show Season 2 (2008)'), ('Show Season 10 (2008)'),
       ('Another Season 01'), ('Another Season 02'),
       ('Another 1st Anniversary Season 01'),
       ('Another 2nd Anniversary Season 01'),
       ('Another 10th Anniversary Season 01'),
       ('Some Show Another No Season Number'),
       ('Some Show No Season Number'),
       ('Show 2 Season 1'),
       ('Some Show With Season Number 1'),
       ('Some Show With Season Number 2'),
       ('Some Show With Season Number 10');

Here is my working solution (only unable to solve criteria #7 below):

select 
    title, "index", titleLeft,
    convert(int, coalesce(nullif(titleRightTrim2, ''), titleRight)) titleRight
from
    (select 
         title, "index", titleLeft, titleRight, titleRightTrim1,
         case 
            when PATINDEX('%[^0-9]%', titleRightTrim2) = 0 
               then titleRightTrim2
               else left(titleRightTrim2, PATINDEX('%[^0-9]%', titleRightTrim2) - 1)
         end as titleRightTrim2
     from
         (select
              title, 
              len(title) - PATINDEX('%[0-9] %', reverse(title)) 'index',
              left(title, len(title) - PATINDEX('%[0-9] %', reverse(title))) titleLeft,
              ltrim(right(title, PATINDEX('%[0-9] %', reverse(title)))) titleRight,
              ltrim(right(title, PATINDEX('%[0-9] %', reverse(title)))) titleRightTrim1,
              left(ltrim(right(title, PATINDEX('%[0-9] %', reverse(title)))), PATINDEX('% %', ltrim(right(title, PATINDEX('%[0-9] %', reverse(title)))))) titleRightTrim2
          from
              tvseason) x) y
order by 
    titleLeft, titleRight

Criteria to consider:

  1. Text contains no numbers
  2. Text contains numbers at beginning and end
  3. Text contains numbers at beginning only
  4. Text contains numbers at end only
  5. Text may contain (YYYY) at end
  6. Text may end with single digit OR double digit (ex. 1 or 01)
  7. Optional: Any combination of above, plus numbers in middle of text

Here is the output:

title
100 Season 1
100 Season 2
100 Season 03
100 Season 4
100 Season 10
**Case 7 here**
Another 10th Anniversary Season 01
Another 1st Anniversary Season 01
Another 2nd Anniversary Season 01
Another Season 01
Another Season 02
Show (2008) Season 1
Show (2008) Season 2
Show 2 The 75th Anniversary Season 1
Show Season 1 (2008)
Show Season 2 (2008)
Show Season 10 (2008)
Some Show Another No Season Number
Some Show No Season Number
Some Show With Season Number 1
Some Show With Season Number 2
Some Show With Season Number 10
4
sqlsql-serversortingnatural-sort

4 Answers

5
votes

I think this will do the trick... I simply recognizes changes from non-numeric to numeric. I haven't done any large scale testing but It should be reasonably fast.

SET QUOTED_IDENTIFIER ON;
GO
SET ANSI_NULLS ON;
GO

ALTER FUNCTION dbo.tfn_SplitForSort
/* ===================================================================
11/11/2018 JL, Created: Comments    
=================================================================== */
--===== Define I/O parameters
(
    @string VARCHAR(8000)
)
RETURNS TABLE WITH SCHEMABINDING AS
RETURN 
    WITH 
        cte_n1 (n) AS (SELECT 1 FROM (VALUES (1),(1),(1),(1),(1),(1),(1),(1),(1),(1)) n (n)), 
        cte_n2 (n) AS (SELECT 1 FROM cte_n1 a CROSS JOIN cte_n1 b),
        cte_Tally (n) AS (
            SELECT TOP (LEN(@string))
                ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
            FROM
                cte_n2 a CROSS JOIN cte_n2 b
            ),
        cte_split_string AS (
            SELECT 
                col_num = ROW_NUMBER() OVER (ORDER BY t.n) + CASE WHEN LEFT(@string, 1) LIKE '[0-9]' THEN 0 ELSE 1 END,
                string_part = SUBSTRING(@string, t.n, LEAD(t.n, 1, 8000) OVER (ORDER BY t.n) - t.n)
            FROM
                cte_Tally t
                CROSS APPLY ( VALUES (SUBSTRING(@string, t.n, 2)) ) s (str2)
            WHERE 
                t.n = 1
                OR SUBSTRING(@string, t.n - 1, 2) LIKE '[0-9][^0-9]'
                OR SUBSTRING(@string, t.n - 1, 2) LIKE '[^0-9][0-9]'
            )

    SELECT 
        so_01 = ISNULL(MAX(CASE WHEN ss.col_num = 1 THEN CONVERT(FLOAT, ss.string_part) END), 99999999),
        so_02 = MAX(CASE WHEN ss.col_num = 2 THEN ss.string_part END),
        so_03 = MAX(CASE WHEN ss.col_num = 3 THEN CONVERT(FLOAT, ss.string_part) END),
        so_04 = MAX(CASE WHEN ss.col_num = 4 THEN ss.string_part END),
        so_05 = MAX(CASE WHEN ss.col_num = 5 THEN CONVERT(FLOAT, ss.string_part) END),
        so_06 = MAX(CASE WHEN ss.col_num = 6 THEN ss.string_part END),
        so_07 = MAX(CASE WHEN ss.col_num = 7 THEN CONVERT(FLOAT, ss.string_part) END),
        so_08 = MAX(CASE WHEN ss.col_num = 8 THEN ss.string_part END),
        so_09 = MAX(CASE WHEN ss.col_num = 9 THEN CONVERT(FLOAT, ss.string_part) END),
        so_10 = MAX(CASE WHEN ss.col_num = 10 THEN ss.string_part END)
    FROM
        cte_split_string ss;
GO

The function in use...

SELECT 
    ts.*
FROM
    #tvseason ts
    CROSS APPLY dbo.tfn_SplitForSort (ts.title) sfs
ORDER BY
    sfs.so_01,
    sfs.so_02,
    sfs.so_03,
    sfs.so_04,
    sfs.so_05,
    sfs.so_06,
    sfs.so_07,
    sfs.so_08,
    sfs.so_09,
    sfs.so_10;

Results:

id          title
----------- ------------------------------------------
2           100 Season 1
4           100 Season 2
1           100 Season 03
5           100 Season 4
3           100 Season 10
11          Another 1st Anniversary Season 01
12          Another 2nd Anniversary Season 01
13          Another 10th Anniversary Season 01
9           Another Season 01
10          Another Season 02
16          Show 2 Season 1
6           Show Season 1 (2008)
7           Show Season 2 (2008)
8           Show Season 10 (2008)
14          Some Show Another No Season Number
15          Some Show No Season Number
17          Some Show With Season Number 1
18          Some Show With Season Number 2
19          Some Show With Season Number 10

--=====================================================================

[Edit 2020-09-23] I was looking back at some of my old posts and when I came across this one and wanted to see if I could get to work with a single value output. Adding 10 columns to the ORDER BY is just clunky... After a bit of thought, it occurred to me that converting the FLOATs to BINARY and the BINARY back to VARCHAR, I could reassemble the string with the STRING_AGG() function. The net result would be string that produces the desired sort.

CREATE FUNCTION dbo.human_sort_string
/* ===================================================================
09/23/2020 JL, Created: Just a test 
=================================================================== */
--===== Define I/O parameters
(
    @string varchar(8000)
)
RETURNS TABLE WITH SCHEMABINDING AS
RETURN
    WITH 
        cte_n1 (n) AS (SELECT 1 FROM (VALUES (1),(1),(1),(1),(1),(1),(1),(1),(1),(1)) n (n)),   -- 10
        cte_n2 (n) AS (SELECT 1 FROM cte_n1 a CROSS JOIN cte_n1 b),                             -- 100
        cte_Tally (n) AS (
            SELECT TOP (LEN(@string))
                ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
            FROM
                cte_n2 a CROSS JOIN cte_n2 b                                                    -- 10,000
            ),
        cte_Parsed AS (
            SELECT 
                t.n,
                parsed_val = SUBSTRING(@string, ISNULL(NULLIF(t.n, 1), 0) + 1, LEAD(t.n, 1, 8000) OVER (ORDER BY t.n) - ISNULL(NULLIF(t.n, 1), 0))
            FROM 
                cte_Tally t
                CROSS APPLY ( VALUES (SUBSTRING(@string, t.n, 2)) ) sv (sub_val)
            WHERE 
                t.n = 1
                OR 
                sv.sub_val LIKE '[0-9][^0-9]'
                OR 
                sv.sub_val LIKE '[^0-9][0-9]'
            )
    SELECT 
        sort_string = STRING_AGG(ISNULL(CONVERT(varchar(8000), CONVERT(binary(8), TRY_CONVERT(float, p.parsed_val)), 2), p.parsed_val), '') WITHIN GROUP (ORDER BY p.n)
    FROM
        cte_Parsed p;
GO

Now, the outer query looks like this...

SELECT 
    ts.id,
    td.title
FROM
    #tvseason ts
    CROSS APPLY dbo.human_sort_string(ts.title) hss
ORDER BY
    hss.sort_string;

The actual results are identical to the previous function.

2
votes

Personally, I would try to avoid doing complex string manipuluation in SQL. I would probably dump it out to a text file and process it using a regular expression in something like C# or Python. Then write it back to the DB in a separate column. SQL is notoriously bad at string manipulation.

However here's my stab at a SQL approach. The idea is basically to first eliminate any rows which don't have the string Season [number] in them. That handles the case where there are no seasons to parse. I chose to include them with nulls, but you could just as easily omit them in your where clause, or give them some default value. I use the stuff() function to cut off everything up to the string Season [number], so it's easier to work with.

Now we have the string starting with the season number, and potentially ending in some garbage. I use a case statement to see if there is garbage (anything non-numeric) and if there is, i take the leftmost numeric characters and throw away the rest. If there is only numeric to begin with, I just leave it as it is.

Finally, cast it as an int, and sort by it.

if object_id('tempdb.dbo.#titles') is not null drop table #titles
create table #titles (Title varchar(100))
insert into #titles (TItle)
select title = '100 Season 1'
union all select '100 Season 2'
union all select '100 Season 03'
union all select '100 Season 4'
union all select '100 Season 10'
union all select 'Another 10th Anniversary Season 01'
union all select 'Another 1st Anniversary Season 01'
union all select 'Another 2nd Anniversary Season 01'
union all select 'Another Season 01'
union all select 'Another Season 02'
union all select 'Show (2008) Season 1'
union all select 'Show (2008) Season 2'
union all select 'Show 2 The 75th Anniversary Season 1'
union all select 'Show Season 1 (2008)'
union all select 'Show Season 2 (2008)'
union all select 'Show Season 10 (2008)'
union all select 'Some Show Another No Season Number'
union all select 'Some Show No Season Number'
union all select 'Some Show With Season Number 1'
union all select 'Some Show With Season Number 2'
union all select 'Some Show With Season Number 10'

;with src as
(
    select 
        Title, 
        Trimmed = case when Title like '%Season [0-9]%' 
                       then stuff(title, 1, patindex('%season [0-9]%', title) + 6, '')
                       else null
                  end
    from #titles
)
select 
    Season = cast(case when Trimmed like '%[^0-9]%' then left(Trimmed, patindex('%[^0-9]%', Trimmed))
         else Trimmed
    end as int),
    Title
from src
order by Season
2
votes

This question requirement is complex. So it can't be achieved by a simple query. So my solution is below: First I create a sample data which will be use in this query.

CREATE TABLE #TVSEASON (TITLE VARCHAR(100));
INSERT INTO #TVSEASON (TITLE) VALUES 
('100'),
('100 SEASON 03'),
('100 SEASON 1'),
('100 SEASON 10'),
('100 SEASON 2'),
('100 SEASON 4'),
('SHOW (2008) SEASON 1'),
('SHOW (2008) SEASON 2'),
('SHOW SEASON 1 (2008)'),
('SHOW SEASON 2 (2008)'),
('SHOW SEASON 10 (2008)'),
('ANOTHER 1ST ANNIVERSARY SEASON 01'),
('ANOTHER 2ND ANNIVERSARY SEASON 01'),
('ANOTHER 10TH ANNIVERSARY SEASON 01'),
('ANOTHER SEASON 01'),
('ANOTHER SEASON 02'),
('SOME SHOW ANOTHER NO SEASON NUMBER'),
('SOME SHOW NO SEASON NUMBER'),
('SHOW 2 THE 75TH ANNIVERSARY SEASON 1'),
('SOME SHOW WITH SEASON NUMBER 1'),
('SOME SHOW WITH SEASON NUMBER 2'),
('SOME SHOW WITH SEASON NUMBER 10')

For the achieved desired result I create a function for split all words and numbers from the text. (Note: I also remove st from 1st, nd from 2nd etc through function after trim the spaces between 1 st for safe side if any user mistakely type spaces between 1st, so if you think there is no chance of error then you remove LTRIM from that function, because for removing that values it is also remove th if text has value like "1 the title" which will be convert into 1 e title)

--CREATE SPLIT FUNCTION
CREATE FUNCTION [dbo].[SplitAlphaNumeric]
(
    @LIST NVARCHAR(2000)
) 
RETURNS @RTNVALUE TABLE
(

    ID INT IDENTITY(1,1),
    WORDS NVARCHAR(100),
    NUMBERS INT
)
AS 
BEGIN
    WHILE (PATINDEX('%[0-9]%',@LIST) > 0)
    BEGIN
        INSERT INTO @RTNVALUE (WORDS, NUMBERS)
        SELECT  CASE    WHEN PATINDEX('%[0-9]%',@LIST) = 0 THEN @LIST
                        WHEN (PATINDEX('%[0-9]%',@LIST) = 1 AND PATINDEX('%[^0-9]%',@LIST) = 0) THEN ''
                        WHEN PATINDEX('%[0-9]%',@LIST) = 1 THEN ''
                        ELSE SUBSTRING(@LIST, 1, PATINDEX('%[0-9]%',@LIST) - 1) 
                END,
                CASE    WHEN PATINDEX('%[0-9]%',@LIST) = 0 THEN NULL
                        WHEN (PATINDEX('%[0-9]%',@LIST) = 1 AND PATINDEX('%[^0-9]%',@LIST) = 0) THEN CAST(LTRIM(RTRIM(@LIST)) AS INT)
                        WHEN PATINDEX('%[0-9]%',@LIST) = 1 THEN SUBSTRING(@LIST, 1, PATINDEX('%[^0-9]%',@LIST) - 1) 
                        ELSE NULL
                END

            SET @LIST = LTRIM(RTRIM(CASE    WHEN PATINDEX('%[0-9]%',@LIST) = 0 OR (PATINDEX('%[0-9]%',@LIST) = 1 AND PATINDEX('%[^0-9]%',@LIST) = 0) THEN ''
                                            WHEN PATINDEX('%[0-9]%',@LIST) = 1 THEN 
                                                    CASE    WHEN LTRIM(SUBSTRING(@LIST, PATINDEX('%[^0-9]%',@LIST), LEN(@LIST)-PATINDEX('%[^0-9]%',REVERSE(@LIST)))) LIKE 'ST%' THEN SUBSTRING(LTRIM(SUBSTRING(@LIST, PATINDEX('%[^0-9]%',@LIST), LEN(@LIST)-PATINDEX('%[^0-9]%',REVERSE(@LIST)))),3, LEN(LTRIM(SUBSTRING(@LIST, PATINDEX('%[^0-9]%',@LIST), LEN(@LIST)-PATINDEX('%[^0-9]%',REVERSE(@LIST))))))
                                                            WHEN LTRIM(SUBSTRING(@LIST, PATINDEX('%[^0-9]%',@LIST), LEN(@LIST)-PATINDEX('%[^0-9]%',REVERSE(@LIST)))) LIKE 'ND%' THEN SUBSTRING(LTRIM(SUBSTRING(@LIST, PATINDEX('%[^0-9]%',@LIST), LEN(@LIST)-PATINDEX('%[^0-9]%',REVERSE(@LIST)))),3, LEN(LTRIM(SUBSTRING(@LIST, PATINDEX('%[^0-9]%',@LIST), LEN(@LIST)-PATINDEX('%[^0-9]%',REVERSE(@LIST))))))
                                                            WHEN LTRIM(SUBSTRING(@LIST, PATINDEX('%[^0-9]%',@LIST), LEN(@LIST)-PATINDEX('%[^0-9]%',REVERSE(@LIST)))) LIKE 'RD%' THEN SUBSTRING(LTRIM(SUBSTRING(@LIST, PATINDEX('%[^0-9]%',@LIST), LEN(@LIST)-PATINDEX('%[^0-9]%',REVERSE(@LIST)))),3, LEN(LTRIM(SUBSTRING(@LIST, PATINDEX('%[^0-9]%',@LIST), LEN(@LIST)-PATINDEX('%[^0-9]%',REVERSE(@LIST))))))
                                                            WHEN LTRIM(SUBSTRING(@LIST, PATINDEX('%[^0-9]%',@LIST), LEN(@LIST)-PATINDEX('%[^0-9]%',REVERSE(@LIST)))) LIKE 'TH%' THEN SUBSTRING(LTRIM(SUBSTRING(@LIST, PATINDEX('%[^0-9]%',@LIST), LEN(@LIST)-PATINDEX('%[^0-9]%',REVERSE(@LIST)))),3, LEN(LTRIM(SUBSTRING(@LIST, PATINDEX('%[^0-9]%',@LIST), LEN(@LIST)-PATINDEX('%[^0-9]%',REVERSE(@LIST))))))
                                                            ELSE LTRIM(SUBSTRING(@LIST, PATINDEX('%[^0-9]%',@LIST), LEN(@LIST)-PATINDEX('%[^0-9]%',REVERSE(@LIST))))
                                                    END
                                            ELSE SUBSTRING(@LIST, PATINDEX('%[0-9]%',@LIST), LEN(@LIST)-PATINDEX('%[0-9]%',REVERSE(@LIST))) 
                                    END))
    END
    INSERT INTO @RTNVALUE (WORDS)
    SELECT VALUE = LTRIM(RTRIM(@LIST))
    RETURN
END

In third step I use cross apply on calling function because function return table against given string value. On select query I insert all columns into temp table for sort values as per requirement in next step.

SELECT  T.TITLE, A.ID, A.NUMBERS, A.WORDS INTO #FINAL
FROM    #TVSEASON T
        CROSS APPLY dbo.SplitAlphaNumeric(TITLE) A

From the temp table #Final I use stuff for concate all words to make title again without any number occurence in the text, and then use that values to order the title.

You can change that query for order in any sequence like if you want to order against the text then you order first textval column then numbers, but if you want to order against summation of all the numbers which are used in title then order numbers first after sum like I do or else if you want to order on simple number without sum then don't use group by clause and subquery and directly order against numbers. In short you can achieved all the sequences respected to alpha numeric values after modify that below query and the upper one are the base query for all the goals.

SELECT  A.TITLE--, A.NUMBERS, A.TEXTVAL
FROM    (
            SELECT  A.TITLE, 
                    STUFF((
                        SELECT  ' ' + B.WORDS 
                        FROM    #FINAL B
                        WHERE   B.TITLE = A.TITLE
                        FOR XML PATH(''),TYPE).VALUE('(./TEXT())[1]','VARCHAR(MAX)')
                    ,1,1,'') TEXTVAL,
                    SUM(ISNULL(A.NUMBERS,0)) NUMBERS
            FROM    #FINAL A
            GROUP BY A.TITLE
        ) A 
ORDER BY A.TEXTVAL, A.NUMBERS

DROP TABLE #FINAL
DROP TABLE #TVSEASON

In last I drops both temp table from memory. I think it is the query for sorting values which you want because if anyone have different order requirement agains alphanumeric values they can achieved their requirement after litle bit modify that query.

0
votes

My answer takes advantage of OPEN_JSON to split each title into words, it then replaces numbers with the same number of 'a's. e.g. 2 becomes aa and 10 becomes aaaaaaaa. This leaves us with a set of rows, 1 for each word. I then join these back together again using STRING_AGG within each title to create a new title containing the numbers replaced with a's. I then sort by this and report the original title:

with Words1 as 
(
    select title, REPLACE(REPLACE(value, '(', ''), ')', '') word, [key] as RowN
    from tvseason
   CROSS APPLY OPENJSON('["' +  
      REPLACE(REPLACE(REPLACE(title,' ','","'),'\','\\"'),'"','\"') + 
      '"]')
),
Words2
AS
(
    SELECT title,
           CASE 
                WHEN ISNUMERIC(word) = 1 THEN Replicate('a', CAST(Word as INT))
                WHEN word like '%st' AND ISNUMERIC(LEFT(word, LEN(Word)-2)) = 1
                   THEN Replicate('a', CAST(LEFT(Word, LEN(Word)-2) as INT))
                WHEN word like '%nd' AND ISNUMERIC(LEFT(word, LEN(Word)-2)) = 1
                   THEN Replicate('a', CAST(LEFT(Word, LEN(Word)-2) as INT))
                WHEN word like '%rd' AND ISNUMERIC(LEFT(word, LEN(Word)-2)) = 1
                   THEN Replicate('a', CAST(LEFT(Word, LEN(Word)-2) as INT))
                WHEN word like '%th' AND ISNUMERIC(LEFT(word, LEN(Word)-2)) = 1
                   THEN Replicate('a', CAST(LEFT(Word, LEN(Word)-2) as INT))
                else Word 
                END As Word,
                rowN
    from words1
),
Words3
AS
(
    SELECT title, STRING_AGG(Word, ' ') WITHIN GROUP (Order By rowN ASC) AS TitleLong
    FROM Words2
    GROUP BY Title
)
SELECT title
FROM Words3
ORDER BY TitleLong

This gives the following results:

**title**
100 Season 1
100 Season 2
100 Season 03
100 Season 4
100 Season 10
Another 1st Anniversary Season 01
Another 2nd Anniversary Season 01
Another 10th Anniversary Season 01
Another Season 01
Another Season 02
Show 2 Season 1
Show Season 1 (2008)
Show Season 2 (2008)
Show Season 10 (2008)
Some Show Another No Season Number
Some Show No Season Number
Some Show With Season Number 1
Some Show With Season Number 2
Some Show With Season Number 10