Is SQL order by clause guaranteed to be stable ( by Standards)
The sort is not guaranteed to be stable. I think the SQL Server documentation has a good explanation of how to achieve a stable sort:
To achieve stable results between query requests using OFFSET and
FETCH, the following conditions must be met:
The underlying data that is used by the query must not change. That is, either the rows touched
by the query are not updated or all requests for pages from the query
are executed in a single transaction using either snapshot or
serializable transaction isolation. For more information about these
transaction isolation levels, see SET TRANSACTION ISOLATION LEVEL
(Transact-SQL). The ORDER BY clause contains a column or combination
of columns that are guaranteed to be unique.
The simplest way to understand that a sort is not stable is to go back to the definition of a table. Tables are inherently unordered in SQL. So, there is no ordering to fall back on for "stability".
As a second consideration, the sorting may be implemented in parallel. In most parallel sorts, common keys are brought together with no information about their original order (unless that is implemented in the sort key, either explicitly or implicitly).
In SQL Server, can I guarantee an order without an explicit ORDER BY clause when an index seek is forced on a table with only a clustered index?
- Am I right that it will guarantee the order in this case without an order by clause?
No. A Flow Distinct that preserves order (allowing ORDER BY without a sort) is not implemented in SQL Server today. It is possible to do in principle, but then many things are possible if we are allowed to change the SQL Server source code. If you can make a good case for this development work, you could suggest it to Microsoft.
- If not, is there another method to force a plan that is as fast as Solution A, preferably one that avoids sorts?
Yes. (Table & query hints only required when using the pre-2014 cardinality estimator):
-- Additional index
CREATE UNIQUE NONCLUSTERED INDEX i
ON #Orders (StoreID, CustID, Amount, OrderID);
-- Query
SELECT TOP (500)
O.CustID,
O.Amount
FROM #Orders AS O
WITH (FORCESEEK(IX (StoreID)))
WHERE O.StoreID = 1
AND NOT EXISTS
(
SELECT NULL
FROM #Orders AS O2
WITH (FORCESEEK(i (StoreID, CustID, Amount)))
WHERE
O2.StoreID = O.StoreID
AND O2.CustID = O.CustID
AND O2.Amount >= O.Amount
AND
(
O2.Amount > O.Amount
OR
(
O2.Amount = O.Amount
AND O2.OrderID > O.OrderID
)
)
)
ORDER BY
O.Amount DESC
OPTION (MAXDOP 1);
(500 row(s) affected)
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 4 ms.
SQL CLR solution
The following script shows using a SQL CLR table-valued function to meet the stated requirements. I am not a C# expert, so the code may bear improvement:
USE Sandpit;
GO
-- Ensure SQLCLR is enabled
EXECUTE sys.sp_configure
@configname = 'clr enabled',
@configvalue = 1;
RECONFIGURE;
GO
-- Lazy, but effective to allow EXTERNAL_ACCESS
ALTER DATABASE Sandpit
SET TRUSTWORTHY ON;
GO
-- The CLR assembly
CREATE ASSEMBLY FlowDistinctOrder
AUTHORIZATION dbo
FROM 0x4D5A90000300000004000000FFFF0000B800000000000000400000000000000000000000000000000000000000000000000000000000000000000000800000000E1FBA0E00B409CD21B8014CCD21546869732070726F6772616D2063616E6E6F742062652072756E20696E20444F53206D6F64652E0D0D0A2400000000000000504500004C010300881F94540000000000000000E00002210B010B000010000000060000000000004E2F0000002000000040000000000010002000000002000004000000000000000400000000000000008000000002000000000000030040850000100000100000000010000010000000000000100000000000000000000000FC2E00004F00000000400000C802000000000000000000000000000000000000006000000C000000C42D00001C0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200000080000000000000000000000082000004800000000000000000000002E74657874000000540F0000002000000010000000020000000000000000000000000000200000602E72737263000000C8020000004000000004000000120000000000000000000000000000400000402E72656C6F6300000C0000000060000000020000001600000000000000000000000000004000004200000000000000000000000000000000302F00000000000048000000020005009C210000280C000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001B300300CB00000001000011280700000A730800000A730900000A0A730A00000A0B071F0A6F0B00000A07026F0C00000A07166F0D00000A07036F0E00000A07176F0F00000A076F1000000A731100000A0C086F1200000A086F1300000A0D0972010000706F1400000A096F1500000A13062B321106166F1600000A13041106176F1700000A13050611056F1800000A2D1406110511046F1900000A066F1A00000A6A042E0911066F1B00000A2DC5DE0C11062C0711066F1C00000ADCDE0A092C06096F1C00000ADCDE0A082C06086F1C00000ADC062A0001280000020066003FA5000C000000000200530060B3000A000000000200460079BF000A00000000133002001A0000000200001102A50500001B0A031200281D00000A54041200281E00000A572A1E02281F00000A2A3A02281F00000A02037D2000000A2A3A027B2000000A04036F2100000A2A42534A4201000100000000000C00000076322E302E35303732370000000005006C000000EC020000237E000058030000FC03000023537472696E67730000000054070000300200002355530084090000100000002347554944000000940900009402000023426C6F620000000000000002000001571702080906000000FA25330016000001000000160000000300000001000000050000000900000001000000210000000600000002000000060000000100000003000000010000000100000000000A0001000000000006005700500006007B00600006009A0087000A000901EE0006005A013B0106008C0179011B00A00100000600CF01AF010600EF01AF010A000D02EE000600220260000E00390260000A0062024C020A00E702D4020A0016034C020A002403D4020A0036034C020A004F03D4020A0069034C020A008503D4020600C40350000600D80360000000000001000000000001000100010010002000000005000100010003011000350000000500010004002100C60026005020000000009600A600110001005021000000009600B800190004007621000000008618C000220007007E21000000008618C0002E0007008D2100000000E601CF003800080000000100D700000002001B0100000300280100000100300102000200340102000300670100000100C600000001006E01000002007301030006002100C00022002900C00022003100C00053004100C00059004900C00022005100C000220014002D02E1011C00C0002E002400C0002E006900C000220069007D02590069009002F70169009F02FC016900AA02F7016900BD02FC017100010301027900C000F70181003103220079004103050291005903F701890077030A02A10092030F02A1009B0314022400A50319022400B1031F022400B5032702A100BF032B02A900D00322002C00E70349022C00F1034E020900C00022003400C60026000C00CF003800200033005E0024000B0040002E001B0063022E0023006C022E002B00750244000B0040002F0253020A00DB01EA01F00142025C02048000000000000000000000000000000000A600000002000000000000000000000001004700000000000200000000000000000000000100E200000000000200000000000000000000000100500000000000030002000000000006005E000000003C4D6F64756C653E00466C6F7744697374696E63744F726465722E646C6C0055736572446566696E656446756E6374696F6E730052657665727365436F6D70617265726031006D73636F726C69620053797374656D004F626A65637400540053797374656D2E436F6C6C656374696F6E732E47656E657269630049436F6D706172657260310053797374656D2E436F6C6C656374696F6E730049456E756D657261626C6500466C6F7744697374696E63744F726465720046696C6C526F77002E63746F72006F726967696E616C00436F6D70617265005365727665724E616D650053797374656D2E44617461004D6963726F736F66742E53716C5365727665722E5365727665720053716C46616365744174747269627574650044617461626173654E616D65004D6178526F7773006F626A004375737449440053797374656D2E52756E74696D652E496E7465726F705365727669636573004F757441747472696275746500416D6F756E74006C6566740072696768740053797374656D2E446961676E6F73746963730044656275676761626C6541747472696275746500446562756767696E674D6F6465730053797374656D2E52756E74696D652E436F6D70696C6572536572766963657300436F6D70696C6174696F6E52656C61786174696F6E734174747269627574650052756E74696D65436F6D7061746962696C6974794174747269627574650053716C46756E6374696F6E41747472696275746500436F6D70617265726031006765745F44656661756C7400536F7274656444696374696F6E61727960320053797374656D2E446174612E53716C436C69656E740053716C436F6E6E656374696F6E537472696E674275696C646572007365745F436F6E6E65637454696D656F7574007365745F44617461536F75726365007365745F456E6C697374007365745F496E697469616C436174616C6F67007365745F496E746567726174656453656375726974790053797374656D2E446174612E436F6D6D6F6E004462436F6E6E656374696F6E537472696E674275696C646572006765745F436F6E6E656374696F6E537472696E670053716C436F6E6E656374696F6E004462436F6E6E656374696F6E004F70656E0053716C436F6D6D616E6400437265617465436F6D6D616E64004462436F6D6D616E64007365745F436F6D6D616E64546578740053716C4461746152656164657200457865637574655265616465720044624461746152656164657200476574496E74333200476574446F75626C6500436F6E7461696E734B657900416464006765745F436F756E7400526561640049446973706F7361626C6500446973706F7365004B657956616C7565506169726032006765745F56616C7565006765745F4B65790000000000822D0D000A0020002000200020002000200020002000200020002000200020002000200020002000200020002000530045004C004500430054000D000A002000200020002000200020002000200020002000200020002000200020002000200020002000200020002000200020004F002E004300750073007400490044002C0020000D000A002000200020002000200020002000200020002000200020002000200020002000200020002000200020002000200020004F002E0041006D006F0075006E0074000D000A0020002000200020002000200020002000200020002000200020002000200020002000200020002000460052004F004D002000640062006F002E004F007200640065007200730020004100530020004F000D000A00200020002000200020002000200020002000200020002000200020002000200020002000200020005700480045005200450020000D000A002000200020002000200020002000200020002000200020002000200020002000200020002000200020002000200020004F002E00530074006F00720065004900440020003D002000310020000D000A00200020002000200020002000200020002000200020002000200020002000200020002000200020004F00520044004500520020004200590020000D000A002000200020002000200020002000200020002000200020002000200020002000200020002000200020002000200020004F002E0041006D006F0075006E00740020004400450053004300008E8B082F3050554B858E01B56306C38B0008B77A5C561934E08906151209011300070003120D0E0E0A080003011C1008100D03200001070615120901130009200101151209011300072002081300130012010001005408074D617853697A658000000005200101111D0420010108817B010004005455794D6963726F736F66742E53716C5365727665722E5365727665722E446174614163636573734B696E642C2053797374656D2E446174612C2056657273696F6E3D322E302E302E302C2043756C747572653D6E65757472616C2C205075626C69634B6579546F6B656E3D623737613563353631393334653038390A446174614163636573730100000054557F4D6963726F736F66742E53716C5365727665722E5365727665722E53797374656D446174614163636573734B696E642C2053797374656D2E446174612C2056657273696F6E3D322E302E302E302C2043756C747572653D6E65757472616C2C205075626C69634B6579546F6B656E3D623737613563353631393334653038391053797374656D4461746141636365737300000000540E1146696C6C526F774D6574686F644E616D650746696C6C526F77540E0F5461626C65446566696E6974696F6E2643757374494420696E7465676572204E554C4C2C20416D6F756E7420666C6F6174204E554C4C0515122D010D08000015122D0113000515120C010D06151231020D08042001010E04200101020320000E0420001245042000124D04200108080420010D0805200102130007200201130013010320000803200002120707151231020D081235123D1245080D124D06151159020D0804200013010420001300080701151159020D080615120C0113000801000200000000000801000800000000001E01000100540216577261704E6F6E457863657074696F6E5468726F77730100000000881F945400000000020000001C010000E02D0000E00F00005253445388411786AC332241BCB71A9315A6D3DD07000000633A5C55736572735C5061756C2057686974655C446F63756D656E74735C56697375616C2053747564696F20323031335C50726F6A656374735C466C6F7744697374696E63744F726465725C466C6F7744697374696E63744F726465725C6F626A5C52656C656173655C466C6F7744697374696E63744F726465722E70646200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000242F000000000000000000003E2F0000002000000000000000000000000000000000000000000000302F0000000000000000000000005F436F72446C6C4D61696E006D73636F7265652E646C6C0000000000FF250020001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001000000018000080000000000000000000000000000001000100000030000080000000000000000000000000000001000000000048000000584000006C02000000000000000000006C0234000000560053005F00560045005200530049004F004E005F0049004E0046004F0000000000BD04EFFE00000100000000000000000000000000000000003F000000000000000400000002000000000000000000000000000000440000000100560061007200460069006C00650049006E0066006F00000000002400040000005400720061006E0073006C006100740069006F006E00000000000000B004CC010000010053007400720069006E006700460069006C00650049006E0066006F000000A801000001003000300030003000300034006200300000002C0002000100460069006C0065004400650073006300720069007000740069006F006E000000000020000000300008000100460069006C006500560065007200730069006F006E000000000030002E0030002E0030002E00300000004C001600010049006E007400650072006E0061006C004E0061006D006500000046006C006F007700440069007300740069006E00630074004F0072006400650072002E0064006C006C0000002800020001004C006500670061006C0043006F0070007900720069006700680074000000200000005400160001004F0072006900670069006E0061006C00460069006C0065006E0061006D006500000046006C006F007700440069007300740069006E00630074004F0072006400650072002E0064006C006C000000340008000100500072006F006400750063007400560065007200730069006F006E00000030002E0030002E0030002E003000000038000800010041007300730065006D0062006C0079002000560065007200730069006F006E00000030002E0030002E0030002E003000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000C000000503F00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
WITH PERMISSION_SET = EXTERNAL_ACCESS;
GO
-- The CLR TVF with order guarantee
CREATE FUNCTION dbo.FlowDistinctOrder
(
@ServerName nvarchar(128),
@DatabaseName nvarchar(128),
@MaxRows bigint
)
RETURNS TABLE
(
CustID integer NULL,
Amount float NULL
)
ORDER (Amount DESC)
AS EXTERNAL NAME FlowDistinctOrder.UserDefinedFunctions.FlowDistinctOrder;
Test table and sample data from the question:
-- Test table
CREATE TABLE dbo.Orders
(
OrderID integer NOT NULL IDENTITY(1,1),
CustID integer NOT NULL,
StoreID integer NOT NULL,
Amount float NOT NULL
);
GO
-- Sample data
WITH
Cte0 AS (SELECT 1 AS C UNION ALL SELECT 1), --2 rows
Cte1 AS (SELECT 1 AS C FROM Cte0 AS A, Cte0 AS B),--4 rows
Cte2 AS (SELECT 1 AS C FROM Cte1 AS A ,Cte1 AS B),--16 rows
Cte3 AS (SELECT 1 AS C FROM Cte2 AS A ,Cte2 AS B),--256 rows
Cte4 AS (SELECT 1 AS C FROM Cte3 AS A ,Cte3 AS B),--65536 rows
Cte5 AS (SELECT 1 AS C FROM Cte4 AS A ,Cte2 AS B),--1048576 rows
FinalCte AS (SELECT ROW_NUMBER() OVER (ORDER BY C) AS Number FROM Cte5)
INSERT dbo.Orders
(CustID, StoreID, Amount)
SELECT
CustID = Number / 10,
StoreID = Number % 4,
Amount = 1000 * RAND(Number)
FROM FinalCte
WHERE
Number <= 1000000;
GO
-- Index
CREATE CLUSTERED INDEX IX
ON dbo.Orders
(StoreID ASC, Amount DESC, CustID ASC);
Function test:
-- Test the function
-- Run several times to ensure connection is cached
-- and CLR code fully compiled
DECLARE @Start datetime2 = SYSUTCDATETIME();
SELECT TOP (500)
FDO.CustID
FROM dbo.FlowDistinctOrder
(
@@SERVERNAME, -- For external connection
DB_NAME(), -- For external connection
500 -- Number of rows to return
) AS FDO
ORDER BY
FDO.Amount DESC;
SELECT DATEDIFF(MILLISECOND, @Start, SYSUTCDATETIME());
Execution plan (note the validation of the ORDER guarantee):
On my laptop, this typically executes in 80-100ms. This is nowhere near as fast as the T-SQL rewrite above, but it should show good performance stability in the face of different data distributions.
Source code:
using Microsoft.SqlServer.Server;
using System.Collections;
using System.Collections.Generic;
using System.Data.SqlClient;
public partial class UserDefinedFunctions
{
private sealed class ReverseComparer<T> : IComparer<T>
{
private readonly IComparer<T> original;
public ReverseComparer(IComparer<T> original)
{
this.original = original;
}
public int Compare(T left, T right)
{
return original.Compare(right, left);
}
}
[SqlFunction
(
DataAccess = DataAccessKind.Read,
SystemDataAccess = SystemDataAccessKind.None,
FillRowMethodName = "FillRow",
TableDefinition = "CustID integer NULL, Amount float NULL"
)
]
public static IEnumerable FlowDistinctOrder
(
[SqlFacet (MaxSize=128)]string ServerName,
[SqlFacet (MaxSize=128)]string DatabaseName,
long MaxRows
)
{
var list = new SortedDictionary<double, int>
(new ReverseComparer<double>(Comparer<double>.Default));
var csb = new SqlConnectionStringBuilder();
csb.ConnectTimeout = 10;
csb.DataSource = ServerName;
csb.Enlist = false;
csb.InitialCatalog = DatabaseName;
csb.IntegratedSecurity = true;
using (var conn = new SqlConnection(csb.ConnectionString))
{
conn.Open();
using (var cmd = conn.CreateCommand())
{
cmd.CommandText =
@"
SELECT
O.CustID,
O.Amount
FROM dbo.Orders AS O
WHERE
O.StoreID = 1
ORDER BY
O.Amount DESC";
int custid;
double amount;
using (var rdr = cmd.ExecuteReader())
{
while (rdr.Read())
{
custid = rdr.GetInt32(0);
amount = rdr.GetDouble(1);
if (!list.ContainsKey(amount))
{
list.Add(amount, custid);
if (list.Count == MaxRows)
{
break;
}
}
}
}
}
}
return list;
}
public static void FillRow(object obj, out int CustID, out double Amount)
{
var v = (KeyValuePair<double, int>)obj;
CustID = v.Value;
Amount = v.Key;
}
}
Is ORDER BY stable for several rows with the same key values?
Your ORDER BY logic should always be specific enough to sort the way you want. So if you want Kanna's record to appear first in the limit query, you should add a descending sort level on the name:
SELECT * FROM friends ORDER BY age DESC, name DESC LIMIT 1;
Even if Postgres' sort appears to be stable with regard to a certain order, the behavior could change as the underlying data changes. And also the behavior almost certainly varies across different databases.
How does order by clause works if two values are equal?
In relational databases, tables are sets and are unordered. The order by clause is used primarily for output purposes (and a few other cases such as a subquery containing rownum).
This is a good place to start. The SQL standard does not specify what has to happen when the keys on an order by are the same. And this is for good reason. Different techniques can be used for sorting. Some might be stable (preserving original order). Some methods might not be.
Focus on whether the same rows are in the sets, not their ordering. By the way, I would consider this an unfortunate example. The book should not have ambiguous sorts in its examples.
Is a stable function guaranteed to produce the same result in a query?
A query (statement) sees a consistent view of the database as it was at the point in time when the execution started - regardless of how many sub-queries or derived tables it contains.
Any concurrent modification to the table is not visible to the running query.
So yes, it is guaranteed that bot sub-queries will return the same count.
This has nothing to do with "volatile" or "stable" functions. Those attributes are typically only important for the optimizer to take shortcuts. E.g.: the database free to cache function results per value for functions declared as immutable or stable for the duration of the query. But this is independent of the content that the query (and the functions) see.
Btw (unrelated to your question): it is a myth that count(1) is faster than count(*). There is no database where this is true. In Postgres count(1) is even slightly slower.
Can SQL return different results for two runs of the same query using ORDER BY?
If you have ties when ordering the order by is not stable.
LiveDemo
CREATE TABLE #TestSort
(
Id INT NOT NULL IDENTITY (1, 1) PRIMARY KEY,
Value INT NOT NULL
) ;
DECLARE @c INT = 0;
WHILE @c < 100000
BEGIN
INSERT INTO #TestSort(Value)
VALUES ('2');
SET @c += 1;
END
Example:
SELECT TOP 10 *
FROM #TestSort
ORDER BY Value
OPTION (MAXDOP 4);
DBCC DROPCLEANBUFFERS; -- run to clear cache
SELECT TOP 10 *
FROM #TestSort
ORDER BY Value
OPTION (MAXDOP 4);
The point is I force query optimizer to use parallel plan so there is no guaranteed that it will read data sequentially like Clustered index probably will do when no parallelism is involved.
You cannot be sure how Query Optimizer will read data unless you explicitly force to sort result in specific way using ORDER BY Id, Value.
For more info read No Seatbelt - Expecting Order without ORDER BY.
Ordering by the order of values in a SQL IN() clause
Use MySQL's FIELD() function:
SELECT name, description, ...
FROM ...
WHERE id IN([ids, any order])
ORDER BY FIELD(id, [ids in order])
FIELD() will return the index of the first parameter that is equal to the first parameter (other than the first parameter itself).
FIELD('a', 'a', 'b', 'c')
will return 1
FIELD('a', 'c', 'b', 'a')
will return 3
This will do exactly what you want if you paste the ids into the IN() clause and the FIELD() function in the same order.
Is order in a subquery guaranteed to be preserved?
No, put the order by in the outer query:
SELECT name FROM
(SELECT name, age FROM people WHERE age >= 18) p
ORDER BY p.age DESC
LIMIT 10
The inner (sub) query returns a result-set. If you put the order by there, then the intermediate result-set passed from the inner (sub) query, to the outer query, is guaranteed to be ordered the way you designate, but without an order by in the outer query, the result-set generated by processing that inner query result-set, is not guaranteed to be sorted in any way.
Related Topics
Tsql: How to Retrieve the Last Date of Each Month Between Given Date Range
SQL Server Rounding Error, Giving Different Values
SQL Comma Delimted Column => to Rows Then Sum Totals
Split String into Several Rows
Anyway for Ado to Read Updated Data from a Read-Only Excel File Before Save? (Vba)
Select Query with Date Condition
Is SQL Order by Clause Guaranteed to Be Stable ( by Standards)
How to Use Like and in for a Where Statment
Strip Out Non-Numeric Characters in Select
How to Convert Hh:Mm:Ss to Seconds in SQL Server with More Than 24 Hours
Window Functions: Partition by One Column After Order by Another
How to Get Count() and Rows from One SQL Query in SQL Server
Ms Access Select Top N Query Grouped by Multiple Fields