Primary Key Sorting

Primary Key Sorting

Data is physically stored by clustered index, which is usually the primary key but doesn't have to be.

Data in SQL is not guaranteed to have order without an ORDER BY clause. You should always specify an ORDER BY clause when you need the data to be in a particular order. If the table is already sorted that way, the optimizer won't do any extra work, so there's no harm in having it there.

Without an ORDER BY clause, the RDBMS might return cached pages matching your query while it waits for records to be read in from disk. In that case, even if there is an index on the table, data might not come in in the index's order. (Note this is just an example - I don't know or even think that a real-world RDBMS will do this, but it's acceptable behaviour for an SQL implementation.)

EDIT

If you have a performance impact when sorting versus when not sorting, you're probably sorting on a column (or set of columns) that doesn't have an index (clustered or otherwise). Given that it's a time series, you might be sorting based on time, but the clustered index is on the primary bigint. SQL Server doesn't know that both increase the same way, so it has to resort everything.

If the time column and the primary key column are a related by order (one increases if and only if the other increases or stays the same), sort by the primary key instead. If they aren't related this way, move the clustered index from the primary key to whatever column(s) you're sorting by.

Why does primary key order matter?

It matters because the order of primary keys matter in the database. Since primary keys are (usually) clustered, and always indices, whether the key is ordered as First Name, Last Name, SSN or SSN, Last Name, First Name, makes a huge difference. If I only have the SSN when I'm querying the table, and the PK is the only index, I'll see GREAT performance with the latter, and a full table scan with the former.

How To Prevent Automatic Sorting On Primary Key in SQL Server

So there are two factors here which you may be confounding; the physical ordering of the data (i.e how your computer literally prints the bits onto your hard drive) and the logical ordering.

The physical ordering is always defined by your clustered index. 9 times out of 10, this also happens to be your primary key, but it doesn't have to be. Think of "Clustered Index" as "How it's physically sorted on my disk". You want it stored a different way, change how you "cluster" it (by the way, if you don't have a clustered index, that's called a "heap", and it doesn't guarantee the physical order of the data).

The logical ordering however, does not exist. SQL is based on relational algebra, and relational algebra operates on mathematical sets. The definition of a set contains no information about the inherent ordering of the set, only it's constituents.

Now when you query data out, you can specify an order by which will return the data to you in the order you asked for. However by default, there is no guarantee or assumption of any ordering (even that of how it's physically stored on disk; even if it happens to return in that order from time to time).

Why is a full TADIR select with ORDER BY PRIMARY KEY much slower than INTO sorted table?

I ran the test (several times) and got at least similar execution times for both statements.
The Application server sort version about 25% faster than HANA sort.
So my mileage was different.

That HANA sort isnt "faster" is only mildly surprising until you look at the table definition. Sorting the entire inverted hash index not what it was designed for. :)

Some "rules" are meant to be broken.

Sorting 5 Million keys with inverted hashes might a good example.
And now you have 5 Million records in memory, reading rows quickly by key will favor the internally sorted table. anyway ;)

DATA lt_tadir TYPE SORTED TABLE OF tadir WITH UNIQUE KEY pgmid object obj_name

is access friendly than the simple Standard Table anyway.
@Data(lt_tab)

There are known disadvantages with inverted hash indexes.
With typical access not normally noticed.
https://www.stechies.com/hana-inverted-individual-indexes-interview-questionsand-ans/

Are primay keys stored in sorted order or do they just appear sorted by SQL statement?

Well, primary keys aren't necessarily stored in sorted order on the disk. But clustered indexes are. And in the vast majority of cases the primary key is the clustered index. Though this doesn't necessarily guarantee sorting of results, it's just that results are usually sorted by the clustered index by default.

how can I store Guids in random order as primary key

GUIDs don't make for good clustered indexes for exactly this reason. SQL Server does have something called a Sequential GUID to address this. The resulting GUIDs won't be consecutive, but they will be sequential. It has some caveats, though:

Creates a GUID that is greater than any GUID previously generated by this function on a specified computer since Windows was started.

If the system reboots, the sequence is lost. If multiple systems create keys, the sequence is lost. Additionally, there's the problem that we're still relying on the SQL Server to generate the key, which kind of defeats a significant reason to use a GUID.

In general I would suggest not using a GUID as a clustered index. As an alternative one might use a normal IDENTITY key as the clustered index and create a separate GUID column (with potentially an index of its own, and even a unique constraint just to make sure applications don't try to re-insert an existing record). That separate column becomes a kind of "global identifier" in a more business-logic sense, and not so much in a data persistence implementation sense.

Sort order specified in primary key, yet sorting is executed on SELECT

For a non partitioned table I get the following plan

There is a single seek predicate on Seek Keys[1]: Prefix: DeviceId, SensorId = (3819, 53), Start: Date < 1339225010.

Meaning that SQL Server can perform an equality seek on the first two columns and then begin a range seek starting at 1339225010 and ordered FORWARD (as the index is defined with [Date] DESC)

The TOP operator will stop requesting more rows from the seek after the first row is emitted.

When I create the partition scheme and function

CREATE PARTITION FUNCTION PF (int)
AS RANGE LEFT FOR VALUES (1000, 1339225009 ,1339225010 , 1339225011);
GO
CREATE PARTITION SCHEME [MyPartitioningScheme]
AS PARTITION PF
ALL TO ([PRIMARY] );

And populate the table with the following data

INSERT INTO [dbo].[SensorValues]    
/*500 rows matching date and SensorId, DeviceId predicate*/
SELECT TOP (500) 3819,53,1, ROW_NUMBER() OVER (ORDER BY (SELECT 0))           
FROM master..spt_values
UNION ALL
/*700 rows matching date but not SensorId, DeviceId predicate*/
SELECT TOP (700) 3819,52,1, ROW_NUMBER() OVER (ORDER BY (SELECT 0))           
FROM master..spt_values
UNION ALL 
/*1100 rows matching SensorId, DeviceId predicate but not date */
SELECT TOP (1100) 3819,53,1, ROW_NUMBER() OVER (ORDER BY (SELECT 0)) + 1339225011      
FROM master..spt_values

The plan on SQL Server 2008 looks as follows.

The actual number of rows emitted from the seek is 500. The plan shows seek predicates

Seek Keys[1]: Start: PtnId1000 <= 2, End: PtnId1000 >= 1, 
Seek Keys[2]: Prefix: DeviceId, SensorId = (3819, 53), Start: Date < 1339225010

Indicating it is using the skip scan approach described here

the query optimizer is extended so that a seek or scan operation with
one condition can be done on PartitionID (as the logical leading
column) and possibly other index key columns, and then a second-level
seek, with a different condition, can be done on one or more
additional columns, for each distinct value that meets the
qualification for the first-level seek operation.

This plan is a serial plan and so for the specific query you have it seems that if SQL Server ensured that it processed the partitions in descending order of date that the original plan with the TOP would still work and it could stop processing after the first matching row was found rather than continuing on and outputting the remaining 499 matches.

In fact the plan on 2005 looks like it does take that approach

I'm not sure if it is straight forward to get the same plan on 2008 or maybe it would need an OUTER APPLY on sys.partition_range_values to simulate it.

MySQL order by primary key

MySQL generally pulls data out by insertion order which would be by primary key, but that aside you technically can do the same thing if you pull out the primary key column name and put it in an order by

SELECT whatever FROM table
ORDER BY
(   SELECT `COLUMN_NAME`
    FROM `information_schema`.`COLUMNS`
    WHERE (`TABLE_SCHEMA` = 'dbName')
      AND (`TABLE_NAME` = 'tableName')
      AND (`COLUMN_KEY` = 'PRI')
);

For composite keys you can use this

SELECT whatever FROM table
ORDER BY
(   SELECT GROUP_CONCAT(`COLUMN_NAME` SEPARATOR ', ')
    FROM `information_schema`.`COLUMNS`
    WHERE (`TABLE_SCHEMA` = 'dbName')
      AND (`TABLE_NAME` = 'tableName')
      AND (`COLUMN_KEY` = 'PRI')
);

Permission for information schema access from the DOCS

Each MySQL user has the right to access these tables, but
can see only the rows in the tables that correspond to objects for
which the user has the proper access privileges. In some cases (for
example, the ROUTINE_DEFINITION column in the
INFORMATION_SCHEMA.ROUTINES table), users who have insufficient
privileges see NULL. These restrictions do not apply for InnoDB
tables; you can see them with only the PROCESS privilege.

The same privileges apply to selecting information from
INFORMATION_SCHEMA and viewing the same information through SHOW
statements. In either case, you must have some privilege on an object
to see information about it.

SETUP:

CREATE TABLE some_stuff (
    firstID INT,
    secondID INT,
    username varchar(55),
    PRIMARY KEY (firstID, secondID)
) ;

QUERY:

SELECT GROUP_CONCAT(`COLUMN_NAME` SEPARATOR ', ')
FROM `information_schema`.`COLUMNS`
WHERE (`TABLE_SCHEMA` = 'dbName')
  AND (`TABLE_NAME` = 'some_stuff')
  AND (`COLUMN_KEY` = 'PRI');

OUTPUT:

+--------------------------------------------+
| GROUP_CONCAT(`COLUMN_NAME` SEPARATOR ', ') |
+--------------------------------------------+
|              firstID, secondID             |
+--------------------------------------------+

Does 'Select' always order by primary key?

No, if you do not use "order by" you are not guaranteed any ordering whatsoever. In fact, you are not guaranteed that the ordering from one query to the next will be the same. Remember that SQL is dealing with data in a set based fashion. Now, one database implementation or another may happen to provide orderings in a certain way but you should never rely on that.

Is a MySQL primary key already in some sort of default order

The short answer is yes, the primary key has an order, all indexes have an order, and a primary key is simply a unique index.

As you have rightly said, you should not rely on data being returned in the order the data is stored in, the optimiser is free to return it in any order it likes, and this will be dependent on the query plan. I will however attempt to explain why your query has worked for 12 years.

Your clustered index is just your table data, and your clustering key defines the order that it is stored in. The data is stored on the leaf, and the clustering key helps the root (and intermediate notes) act as pointers to quickly get to the right leaf to retrieve the data. A nonclustered index is a very similar structure, but the lowest level simply contains a pointer to the correct position on the leaf of the clustered index.

In MySQL the primary key and the clustered index are synonymous, so the primary key is ordered, however they are fundamentally two different things. In other DBMS you can define both a primary key and a clustered index, when you do this your primary key becomes a unique nonclustered index with a pointer back to the clustered index.

In it's simplest terms you can imagine a table with an ID column that is the primary key, and another column (A), your B-Tree structure for your clustered index would be something like:

Root Node
                                +---+
                                | 1 |
                                +---+
Intermediate Nodes

                    +---+       +---+       +---+
                    | 1 |       | 4 |       | 7 |
                    +---+       +---+       +---+

Leaf
            +-----------+   +-----------+   +-----------+
    ID ->   | 1 | 2 | 3 |   | 4 | 5 | 6 |   | 7 | 8 | 9 |
    A ->    | A | B | C |   | D | E | F |   | G | H | I |
            +-----------+   +-----------+   +-----------+

In reality the leaf pages will be much bigger, but this is just a demo. Each page also has a pointer to the next page and the previous page for ease of traversing the tree. So when you do a query like:

SELECT ID, A
FROM T
WHERE ID > 5
LIMIT 1;

you are scanning a unique index so it is very likely this will be a sequential scan. Very likely is not guaranteed though.

MySQL will scan the Root node, if there is a potential match it will move on to the intermediate nodes, if the clause had been something like WHERE ID < 0 then MySQL would know that there were no results without going any further than the root node.

Once it moves on to the intermediate node it can identify that it needs to start on the second page (between 4 and 7) to start searching for an ID > 5. So it will sequentially scan the leaf starting on the second leaf page, having already identified the LIMIT 1 it will stop once it finds a match (in this case 6) and return this data from the leaf. In such a simple example this behaviour appears to be reliable and logical. I have tried to force exceptions by choosing an ID value I know is at the end of a leaf page to see if the leaf will be scanned in the reverse order, but as yet have been unable to produce this behaviour, this does not however mean it won't happen, or that future releases of MySQL won't do this in the scenarios I have tested.

In short, just add an order by, or use MIN(ID) and be done with it. I wouldn't lose too much sleep trying to delve into the inner workings of the query optimiser to see what kind of fragmentation, or data ranges would be required to observe different ordering of the clustered index within the query plan.

---

Related Topics