Естественная (человеческая буквенно-цифровая) сортировка в Microsoft SQL 2005
У нас есть большая база данных, в которой мы разбиваем страницы на БД. Это быстро, возвращая страницу из 50 строк из миллионов записей за небольшую долю секунды.
Пользователи могут определять свой собственный вид, в основном выбирая, по какому столбцу сортировать. Столбцы являются динамическими - некоторые имеют числовые значения, некоторые даты и некоторый текст.
В то время как большинство сортирует, как и ожидалось, текст сортируется тупо. Ну, я говорю глупо, это имеет смысл для компьютеров, но расстраивает пользователей.
Например, сортировка по идентификатору строковой записи дает что-то вроде:
rec1
rec10
rec14
rec2
rec20
rec3
rec4
...и так далее.
Я хочу, чтобы это учитывало число, поэтому:
rec1
rec2
rec3
rec4
rec10
rec14
rec20
Я не могу контролировать ввод (иначе я бы просто отформатировал первые тысячи), и я не могу полагаться на один формат - некоторые вещи, такие как "{alpha code}-{dept code}-{rec id}".
Я знаю несколько способов сделать это в C#, но не могу обработать все записи, чтобы отсортировать их, так как это может привести к замедлению.
Кто-нибудь знает способ быстрого применения естественной сортировки на сервере Sql?
Мы используем:
ROW_NUMBER() over (order by {field name} asc)
И тогда мы пейджинговали этим.
Мы можем добавить триггеры, хотя мы не будем. Все их входные данные параметризованы и тому подобное, но я не могу изменить формат - если они вставят "rec2" и "rec10", они ожидают, что они будут возвращены просто так и в естественном порядке.
У нас есть действительный пользовательский ввод, который соответствует различным форматам для разных клиентов.
Можно было бы пойти rec1, rec2, rec3, ... rec100, rec101
В то время как другой может пойти: grp1rec1, grp1rec2, ... grp20rec300, grp20rec301
Когда я говорю, что мы не можем контролировать ввод, я имею в виду, что мы не можем заставить пользователей изменить эти стандарты - они имеют значение, например grp1rec1, и я не могу переформатировать его как grp01rec001, так как это изменило бы что-то, используемое для поиска и связь с внешними системами.
Эти форматы сильно различаются, но часто представляют собой смесь букв и цифр.
Сортировать их в C# легко - просто разбить на { "grp", 20, "rec", 301 } а затем сравнить значения последовательности по очереди.
Однако, может быть миллионы записей и данные разбиты на страницы, мне нужно сделать сортировку на сервере SQL.
SQL-сервер сортирует по значению, а не по сравнению - в C# я могу разделить значения для сравнения, но в SQL мне нужна логика, которая (очень быстро) получает одно значение, которое последовательно сортируется.
@moebius - ваш ответ может сработать, но это выглядит как уродливый компромисс для добавления ключа сортировки для всех этих текстовых значений.
14 ответов
Большинство основанных на SQL решений, которые я видел, ломаются, когда данные становятся достаточно сложными (например, более одного или двух чисел в нем). Первоначально я пытался реализовать функцию NaturalSort в T-SQL, которая отвечала моим требованиям (помимо прочего, обрабатывает произвольное число чисел в строке), но производительность была слишком низкой.
В конечном счете, я написал скалярную функцию CLR в C# для естественной сортировки, и даже с неоптимизированным кодом производительность, вызывающая его из SQL Server, невероятно высока. Он имеет следующие характеристики:
- отсортирует первые 1000 символов или около того правильно (легко изменяется в коде или превращается в параметр)
- правильно сортирует десятичные дроби, поэтому 123.333 предшествует 123.45
- из-за вышеизложенного, скорее всего, НЕ будет сортировать такие вещи, как IP-адреса; если вы хотите другое поведение, измените код
- поддерживает сортировку строки с произвольным числом чисел в ней
- будет правильно сортировать числа длиной до 25 цифр (легко изменяется в коде или превращается в параметр)
Код здесь:
using System;
using System.Data.SqlTypes;
using System.Text;
using Microsoft.SqlServer.Server;
public class UDF
{
[SqlFunction(DataAccess = DataAccessKind.None, IsDeterministic=true)]
public static SqlString Naturalize(string val)
{
if (String.IsNullOrEmpty(val))
return val;
while(val.Contains(" "))
val = val.Replace(" ", " ");
const int maxLength = 1000;
const int padLength = 25;
bool inNumber = false;
bool isDecimal = false;
int numStart = 0;
int numLength = 0;
int length = val.Length < maxLength ? val.Length : maxLength;
//TODO: optimize this so that we exit for loop once sb.ToString() >= maxLength
var sb = new StringBuilder();
for (var i = 0; i < length; i++)
{
int charCode = (int)val[i];
if (charCode >= 48 && charCode <= 57)
{
if (!inNumber)
{
numStart = i;
numLength = 1;
inNumber = true;
continue;
}
numLength++;
continue;
}
if (inNumber)
{
sb.Append(PadNumber(val.Substring(numStart, numLength), isDecimal, padLength));
inNumber = false;
}
isDecimal = (charCode == 46);
sb.Append(val[i]);
}
if (inNumber)
sb.Append(PadNumber(val.Substring(numStart, numLength), isDecimal, padLength));
var ret = sb.ToString();
if (ret.Length > maxLength)
return ret.Substring(0, maxLength);
return ret;
}
static string PadNumber(string num, bool isDecimal, int padLength)
{
return isDecimal ? num.PadRight(padLength, '0') : num.PadLeft(padLength, '0');
}
}
Чтобы зарегистрировать это, чтобы вы могли вызывать его из SQL Server, выполните следующие команды в Query Analyzer:
CREATE ASSEMBLY SqlServerClr FROM 'SqlServerClr.dll' --put the full path to DLL here
go
CREATE FUNCTION Naturalize(@val as nvarchar(max)) RETURNS nvarchar(1000)
EXTERNAL NAME SqlServerClr.UDF.Naturalize
go
Затем вы можете использовать его так:
select *
from MyTable
order by dbo.Naturalize(MyTextField)
Примечание: если вы получаете сообщение об ошибке в SQL Server по линиивыполнения пользовательского кода в.NET Framework отключается.Включить опцию конфигурации "clr enabled". следуйте инструкциям здесь, чтобы включить его. Убедитесь, что вы учитываете последствия для безопасности, прежде чем делать это. Если вы не являетесь администратором db, обязательно обсудите это со своим администратором, прежде чем вносить какие-либо изменения в конфигурацию сервера.
Примечание 2: Этот код неправильно поддерживает интернационализацию (например, предполагается, что десятичный маркер равен ".", Не оптимизирован по скорости и т. Д. Приветствуются предложения по его улучшению!)
Редактировать: переименовал функцию в Naturalize вместо NaturalSort, так как она не выполняет никакой реальной сортировки.
order by LEN(value), value
Не идеально, но хорошо работает во многих случаях.
Я знаю, что это старый вопрос, но я только столкнулся с ним, и так как он не получил принятого ответа.
Я всегда использовал способы, подобные этому:
SELECT [Column] FROM [Table]
ORDER BY RIGHT(REPLICATE('0', 1000) + LTRIM(RTRIM(CAST([Column] AS VARCHAR(MAX)))), 1000)
Единственные распространенные случаи, когда это имеет проблемы, это если ваш столбец не будет приведен к VARCHAR(MAX), или если LEN([Column]) > 1000 (но вы можете изменить это 1000 на что-то другое, если хотите), но вы Можно использовать эту грубую идею для того, что вам нужно.
Кроме того, это намного хуже производительности, чем обычный ORDER BY [Column], но дает результат, запрошенный в OP.
Изменить: просто чтобы уточнить, это выше не будет работать, если у вас есть десятичные значения, такие как 1, 1.15 а также 1.5, (они будут сортировать как {1, 1.5, 1.15}) поскольку это не то, что запрашивается в ОП, но это легко сделать:
SELECT [Column] FROM [Table]
ORDER BY REPLACE(RIGHT(REPLICATE('0', 1000) + LTRIM(RTRIM(CAST([Column] AS VARCHAR(MAX)))) + REPLICATE('0', 100 - CHARINDEX('.', REVERSE(LTRIM(RTRIM(CAST([Column] AS VARCHAR(MAX))))), 1)), 1000), '.', '0')
Результат: {1, 1.15, 1.5}
И все же все целиком в SQL. Это не будет сортировать IP-адреса, потому что теперь вы получаете очень конкретные комбинации чисел, а не просто текст + число.
Ответ RedFilter отлично подходит для наборов данных разумного размера, где индексация не критична, однако, если вы хотите индекс, требуется несколько настроек.
Во-первых, пометьте функцию как не имеющую доступа к данным, которая будет детерминированной и точной:
[SqlFunction(DataAccess = DataAccessKind.None,
SystemDataAccess = SystemDataAccessKind.None,
IsDeterministic = true, IsPrecise = true)]
Далее, MSSQL имеет ограничение в 900 байт на размер ключа индекса, поэтому, если натурализованное значение является единственным значением в индексе, оно должно содержать не более 450 символов. Если индекс включает несколько столбцов, возвращаемое значение должно быть еще меньше. Два изменения:
CREATE FUNCTION Naturalize(@str AS nvarchar(max)) RETURNS nvarchar(450)
EXTERNAL NAME ClrExtensions.Util.Naturalize
и в коде C#:
const int maxLength = 450;
Наконец, вам нужно добавить вычисляемый столбец в вашу таблицу, и он должен быть сохранен (потому что MSSQL не может доказать это Naturalize является детерминированным и точным), что означает, что натурализованное значение фактически сохраняется в таблице, но все еще поддерживается автоматически:
ALTER TABLE YourTable ADD nameNaturalized AS dbo.Naturalize(name) PERSISTED
Теперь вы можете создать индекс!
CREATE INDEX idx_YourTable_n ON YourTable (nameNaturalized)
Я также внес несколько изменений в код RedFilter: использование символов для ясности, включение удаления дубликата пространства в основной цикл, выход после того, как результат превысил ограничение, установка максимальной длины без подстроки и т. Д. Вот результат:
using System.Data.SqlTypes;
using System.Text;
using Microsoft.SqlServer.Server;
public static class Util
{
[SqlFunction(DataAccess = DataAccessKind.None, SystemDataAccess = SystemDataAccessKind.None, IsDeterministic = true, IsPrecise = true)]
public static SqlString Naturalize(string str)
{
if (string.IsNullOrEmpty(str))
return str;
const int maxLength = 450;
const int padLength = 15;
bool isDecimal = false;
bool wasSpace = false;
int numStart = 0;
int numLength = 0;
var sb = new StringBuilder();
for (var i = 0; i < str.Length; i++)
{
char c = str[i];
if (c >= '0' && c <= '9')
{
if (numLength == 0)
numStart = i;
numLength++;
}
else
{
if (numLength > 0)
{
sb.Append(pad(str.Substring(numStart, numLength), isDecimal, padLength));
numLength = 0;
}
if (c != ' ' || !wasSpace)
sb.Append(c);
isDecimal = c == '.';
if (sb.Length > maxLength)
break;
}
wasSpace = c == ' ';
}
if (numLength > 0)
sb.Append(pad(str.Substring(numStart, numLength), isDecimal, padLength));
if (sb.Length > maxLength)
sb.Length = maxLength;
return sb.ToString();
}
private static string pad(string num, bool isDecimal, int padLength)
{
return isDecimal ? num.PadRight(padLength, '0') : num.PadLeft(padLength, '0');
}
}
Вот решение, написанное для SQL 2000. Возможно, оно может быть улучшено для более новых версий SQL.
/**
* Returns a string formatted for natural sorting. This function is very useful when having to sort alpha-numeric strings.
*
* @author Alexandre Potvin Latreille (plalx)
* @param {nvarchar(4000)} string The formatted string.
* @param {int} numberLength The length each number should have (including padding). This should be the length of the longest number. Defaults to 10.
* @param {char(50)} sameOrderChars A list of characters that should have the same order. Ex: '.-/'. Defaults to empty string.
*
* @return {nvarchar(4000)} A string for natural sorting.
* Example of use:
*
* SELECT Name FROM TableA ORDER BY Name
* TableA (unordered) TableA (ordered)
* ------------ ------------
* ID Name ID Name
* 1. A1. 1. A1-1.
* 2. A1-1. 2. A1.
* 3. R1 --> 3. R1
* 4. R11 4. R11
* 5. R2 5. R2
*
*
* As we can see, humans would expect A1., A1-1., R1, R2, R11 but that's not how SQL is sorting it.
* We can use this function to fix this.
*
* SELECT Name FROM TableA ORDER BY dbo.udf_NaturalSortFormat(Name, default, '.-')
* TableA (unordered) TableA (ordered)
* ------------ ------------
* ID Name ID Name
* 1. A1. 1. A1.
* 2. A1-1. 2. A1-1.
* 3. R1 --> 3. R1
* 4. R11 4. R2
* 5. R2 5. R11
*/
ALTER FUNCTION [dbo].[udf_NaturalSortFormat](
@string nvarchar(4000),
@numberLength int = 10,
@sameOrderChars char(50) = ''
)
RETURNS varchar(4000)
AS
BEGIN
DECLARE @sortString varchar(4000),
@numStartIndex int,
@numEndIndex int,
@padLength int,
@totalPadLength int,
@i int,
@sameOrderCharsLen int;
SELECT
@totalPadLength = 0,
@string = RTRIM(LTRIM(@string)),
@sortString = @string,
@numStartIndex = PATINDEX('%[0-9]%', @string),
@numEndIndex = 0,
@i = 1,
@sameOrderCharsLen = LEN(@sameOrderChars);
-- Replace all char that have the same order by a space.
WHILE (@i <= @sameOrderCharsLen)
BEGIN
SET @sortString = REPLACE(@sortString, SUBSTRING(@sameOrderChars, @i, 1), ' ');
SET @i = @i + 1;
END
-- Pad numbers with zeros.
WHILE (@numStartIndex <> 0)
BEGIN
SET @numStartIndex = @numStartIndex + @numEndIndex;
SET @numEndIndex = @numStartIndex;
WHILE(PATINDEX('[0-9]', SUBSTRING(@string, @numEndIndex, 1)) = 1)
BEGIN
SET @numEndIndex = @numEndIndex + 1;
END
SET @numEndIndex = @numEndIndex - 1;
SET @padLength = @numberLength - (@numEndIndex + 1 - @numStartIndex);
IF @padLength < 0
BEGIN
SET @padLength = 0;
END
SET @sortString = STUFF(
@sortString,
@numStartIndex + @totalPadLength,
0,
REPLICATE('0', @padLength)
);
SET @totalPadLength = @totalPadLength + @padLength;
SET @numStartIndex = PATINDEX('%[0-9]%', RIGHT(@string, LEN(@string) - @numEndIndex));
END
RETURN @sortString;
END
Я знаю, что на данный момент это немного устарело, но в поисках лучшего решения я наткнулся на этот вопрос. В настоящее время я использую функцию для заказа. Он отлично работает для моей цели сортировки записей, имена которых имеют смешанные буквенно-цифровые символы ("элемент 1", "элемент 10", "элемент 2" и т. Д.)
CREATE FUNCTION [dbo].[fnMixSort]
(
@ColValue NVARCHAR(255)
)
RETURNS NVARCHAR(1000)
AS
BEGIN
DECLARE @p1 NVARCHAR(255),
@p2 NVARCHAR(255),
@p3 NVARCHAR(255),
@p4 NVARCHAR(255),
@Index TINYINT
IF @ColValue LIKE '[a-z]%'
SELECT @Index = PATINDEX('%[0-9]%', @ColValue),
@p1 = LEFT(CASE WHEN @Index = 0 THEN @ColValue ELSE LEFT(@ColValue, @Index - 1) END + REPLICATE(' ', 255), 255),
@ColValue = CASE WHEN @Index = 0 THEN '' ELSE SUBSTRING(@ColValue, @Index, 255) END
ELSE
SELECT @p1 = REPLICATE(' ', 255)
SELECT @Index = PATINDEX('%[^0-9]%', @ColValue)
IF @Index = 0
SELECT @p2 = RIGHT(REPLICATE(' ', 255) + @ColValue, 255),
@ColValue = ''
ELSE
SELECT @p2 = RIGHT(REPLICATE(' ', 255) + LEFT(@ColValue, @Index - 1), 255),
@ColValue = SUBSTRING(@ColValue, @Index, 255)
SELECT @Index = PATINDEX('%[0-9,a-z]%', @ColValue)
IF @Index = 0
SELECT @p3 = REPLICATE(' ', 255)
ELSE
SELECT @p3 = LEFT(REPLICATE(' ', 255) + LEFT(@ColValue, @Index - 1), 255),
@ColValue = SUBSTRING(@ColValue, @Index, 255)
IF PATINDEX('%[^0-9]%', @ColValue) = 0
SELECT @p4 = RIGHT(REPLICATE(' ', 255) + @ColValue, 255)
ELSE
SELECT @p4 = LEFT(@ColValue + REPLICATE(' ', 255), 255)
RETURN @p1 + @p2 + @p3 + @p4
END
Тогда позвони
select item_name from my_table order by fnMixSort(item_name)
Он легко утраивает время обработки для простого чтения данных, поэтому это может быть не идеальное решение.
Вот еще одно решение, которое мне нравится: http://www.dreamchain.com/sql-and-alpha-numeric-sort-order/
Это не Microsoft SQL, но, поскольку я оказался здесь, когда искал решение для Postgres, я подумал, что добавление этого здесь поможет другим.
Для следующих varchar данные:
BR1
BR2
External Location
IR1
IR2
IR3
IR4
IR5
IR6
IR7
IR8
IR9
IR10
IR11
IR12
IR13
IR14
IR16
IR17
IR15
VCR
Это сработало лучше для меня:
ORDER BY substring(fieldName, 1, 1), LEN(fieldName)
Просто вы сортируете по
ORDER BY
cast (substring(name,(PATINDEX('%[0-9]%',name)),len(name))as int)
##
Если у вас возникли проблемы с загрузкой данных из БД для сортировки в C#, то я уверен, что вы будете разочарованы любым подходом к программированию в БД. Когда сервер собирается сортировать, он должен каждый раз вычислять "воспринимаемый" порядок так же, как вы бы это сделали.
Я бы предложил добавить дополнительный столбец для хранения предварительно обработанной сортируемой строки, используя некоторый метод C#, когда данные впервые вставляются. Например, вы можете попытаться преобразовать числа в диапазоны фиксированной ширины, чтобы "xyz1" превратился в "xyz00000001". Тогда вы можете использовать обычную сортировку SQL Server.
Рискуя своим собственным рогом, я написал статью CodeProject, в которой реализована проблема, изложенная в статье CodingHorror. Не стесняйтесь воровать из моего кода.
Я как обычно опаздываю на вечеринку. Тем не менее, вот моя попытка ответа, который, кажется, работает хорошо (я бы сказал так). Он предполагает текст с цифрами в конце, как в данных исходного примера.
Во-первых, функция, которая в ближайшее время не выиграет в конкурсе "красивый SQL".
CREATE FUNCTION udfAlphaNumericSortHelper (
@string varchar(max)
)
RETURNS @results TABLE (
txt varchar(max),
num float
)
AS
BEGIN
DECLARE @txt varchar(max) = @string
DECLARE @numStr varchar(max) = ''
DECLARE @num float = 0
DECLARE @lastChar varchar(1) = ''
set @lastChar = RIGHT(@txt, 1)
WHILE @lastChar <> '' and @lastChar is not null
BEGIN
IF ISNUMERIC(@lastChar) = 1
BEGIN
set @numStr = @lastChar + @numStr
set @txt = Substring(@txt, 0, len(@txt))
set @lastChar = RIGHT(@txt, 1)
END
ELSE
BEGIN
set @lastChar = null
END
END
SET @num = CAST(@numStr as float)
INSERT INTO @results select @txt, @num
RETURN;
END
Затем назовите его, как показано ниже:
declare @str nvarchar(250) = 'sox,fox,jen1,Jen0,jen15,jen02,jen0004,fox00,rec1,rec10,jen3,rec14,rec2,rec20,rec3,rec4,zip1,zip1.32,zip1.33,zip1.3,TT0001,TT01,TT002'
SELECT tbl.value --, sorter.txt, sorter.num
FROM STRING_SPLIT(@str, ',') as tbl
CROSS APPLY dbo.udfAlphaNumericSortHelper(value) as sorter
ORDER BY sorter.txt, sorter.num, len(tbl.value)
С результатами: fox fox00 Jen0 jen1 jen02 jen3 jen0004 jen15 rec1 rec2 rec3 rec4 rec10 rec14 rec20 sox TT01 TT0001 TT002 zip1zip1.3zip1.32 zip1.33
Я только что прочитал статью где-то о такой теме. Ключевой момент: вам нужно только целочисленное значение для сортировки данных, в то время как строка 'rec' принадлежит пользовательскому интерфейсу. Вы можете разделить информацию на два поля, скажем, alpha и num, отсортировать по alpha и num (отдельно) и затем показать строку, составленную из alpha + num. Вы можете использовать вычисляемый столбец для составления строки или представления. Надеюсь, поможет
Вы можете использовать следующий код для решения проблемы:
Select *,
substring(Cote,1,len(Cote) - Len(RIGHT(Cote, LEN(Cote) - PATINDEX('%[0-9]%', Cote)+1)))alpha,
CAST(RIGHT(Cote, LEN(Cote) - PATINDEX('%[0-9]%', Cote)+1) AS INT)intv
FROM Documents
left outer join Sites ON Sites.IDSite = Documents.IDSite
Order BY alpha, intv
С уважением, rabihkahaleh@hotmail.com
Я до сих пор не понимаю (возможно, из-за моего плохого английского).
Вы можете попробовать:
ROW_NUMBER() OVER (ORDER BY dbo.human_sort(field_name) ASC)
Но это не сработает для миллионов записей.
Поэтому я предложил использовать триггер, который заполняет отдельный столбец человеческой ценностью.
Более того:
- встроенные функции T-SQL работают очень медленно, и Microsoft предлагает вместо этого использовать функции.NET.
- человеческая ценность постоянна, поэтому нет смысла вычислять ее каждый раз, когда выполняется запрос.