Как доказать отсутствие неявного порядка в базе данных?

Недавно я объяснял коллегам важность наличия столбца, по которому можно сортировать данные в таблице базы данных, если это необходимо, например, для хронологически упорядоченных данных. Это оказалось несколько сложным, потому что они могли просто повторять свой запрос, казалось бы, бесконечно, и он всегда возвращал бы один и тот же набор строк в одном и том же порядке.

Я заметил это раньше, и все, что я мог на самом деле сделать, - это настаивать, чтобы они доверяли мне, а не просто предполагали, что таблица базы данных будет вести себя как традиционный файл CSV или Excel.

Например, выполнение запроса (PostgreSQL)

create table mytable (
    id INTEGER PRIMARY KEY,
    data TEXT
);
INSERT INTO mytable VALUES
    (0, 'a'),
    (1, 'b'),
    (2, 'c'),
    (3, 'd'),
    (4, 'e'),
    (5, 'f'),
    (6, 'g'),
    (7, 'h'),
    (8, 'i'),
    (9, 'j');

создаст таблицу с четким концептуальным порядком. Выбор этих же данных самым простым способом будет:

SELECT * FROM mytable;

Всегда дает мне следующие результаты:

 id | data 
----+------
  0 | a
  1 | b
  2 | c
  3 | d
  4 | e
  5 | f
  6 | g
  7 | h
  8 | i
  9 | j
(10 rows)

Я могу делать это снова и снова, и он всегда будет возвращать мне одни и те же данные в одном и том же порядке. Однако я знаю, что этот неявный порядок может быть нарушен, я видел его раньше, особенно в больших наборах данных, где некоторое случайное значение, по-видимому, будет выброшено в «неправильное» место при выборе. Но мне пришло в голову, что я не знаю, как это происходит или как это воспроизвести. Мне трудно получить результаты в Google, потому что поисковый запрос имеет тенденцию просто возвращать общую справку по сортировке наборов результатов.

Итак, мои вопросы по сути следующие:

1. Как я могу наглядно и конкретно доказать, что порядок возврата строк в запросе без ORDER BYоператора ненадежен, предпочтительно, вызывая и показывая разбивку неявного порядка, даже если рассматриваемая таблица не обновляется и не редактируется ?

2. Имеет ли это какое-то значение, если данные вводятся только один раз, а затем никогда не обновляются?

Я бы предпочел ответ на основе postgres, поскольку он мне наиболее знаком, но меня больше интересует сама теория.

Я вижу три способа убедить их:

1. Пусть они попробуют тот же запрос, но с большей таблицей (с большим количеством строк) или когда таблица обновляется между выполнениями. Или новые строки вставляются, а некоторые старые удаляются. Или индекс добавляется или удаляется между выполнениями. Или стол пылесосится (в Postgres). Или индексы перестраиваются (в SQL Server). Или таблица меняется с кластерной на кучу. Или служба базы данных перезапущена.

2. Вы можете предложить им доказать, что разные казни будут возвращать один и тот же порядок. Могут ли они доказать это? Могут ли они предоставить серию тестов, доказывающих, что любой запрос даст результат в одном и том же порядке, независимо от того, сколько раз он выполняется?

3. Предоставить документацию по различным СУБД. Например:

PostgreSQL :

Сортировка строк

После того как запрос сгенерировал выходную таблицу (после обработки списка выбора), его можно при желании отсортировать. Если сортировка не выбрана, строки будут возвращены в неуказанном порядке. Фактический порядок в этом случае будет зависеть от типов планов сканирования и соединения и порядка на диске, но на него нельзя полагаться. Конкретный порядок вывода может быть гарантирован, только если шаг сортировки выбран явно.

SQL Server :

SELECT- ORDER BYпункт (Transact-SQL)

Сортирует данные, возвращаемые запросом в SQL Server. Используйте это предложение, чтобы:

Упорядочить результирующий набор запроса по указанному списку столбцов и, при желании, ограничить количество возвращаемых строк указанным диапазоном. Порядок, в котором строки возвращаются в наборе результатов, не гарантируется, если не указано ORDER BYусловие.

Оракул :

order_by_clause

Используйте ORDER BYпредложение, чтобы упорядочить строки, возвращаемые оператором. Без order_by_clause не существует никакой гарантии, что один и тот же запрос, выполненный более одного раза, получит строки в одном и том же порядке.

Это история черного лебедя снова и снова. Если вы еще не видели, это не значит, что они не существуют. Надеемся, что в вашем случае это не приведет к еще одному мировому финансовому кризису, просто к нескольким недовольным клиентам.

Документация Postgres говорит об этом явно:

Если ORDER BY не указан, строки возвращаются в любом порядке, который система сочтет наиболее быстрым.

«Система» в данном случае включает в себя сам демон postgres (включая реализацию его методов доступа к данным и оптимизатор запросов), базовую операционную систему, логическую и физическую структуру хранилища базы данных, возможно, даже кэши ЦП. Поскольку вы, как пользователь базы данных, не имеете никакого контроля над этим стеком, вы не должны полагаться на то, что он продолжает вести себя вечно так, как он ведет себя в эту самую минуту.

Ваши коллеги совершают поспешную ошибку обобщения . Чтобы опровергнуть их точку зрения, достаточно показать, что их допущение неверно только один раз, например, этим dbfiddle .

Рассмотрим следующий пример, где у нас есть три связанных таблицы. Заказы, пользователи и детали заказа. OrderDetails связан с внешними ключами для таблицы Orders и таблицы Users. По сути, это очень типичная установка для реляционных баз данных; возможно вся цель реляционной СУБД.

USE tempdb;

IF OBJECT_ID(N'dbo.OrderDetails', N'U') IS NOT NULL
DROP TABLE dbo.OrderDetails;

IF OBJECT_ID(N'dbo.Orders', N'U') IS NOT NULL
DROP TABLE dbo.Orders;

IF OBJECT_ID(N'dbo.Users', N'U') IS NOT NULL
DROP TABLE dbo.Users;

CREATE TABLE dbo.Orders
(
    OrderID int NOT NULL
        CONSTRAINT OrderTestPK
        PRIMARY KEY
        CLUSTERED
    , SomeOrderData varchar(1000)
        CONSTRAINT Orders_somedata_df
        DEFAULT (CRYPT_GEN_RANDOM(1000))
);

CREATE TABLE dbo.Users
(
    UserID int NOT NULL
        CONSTRAINT UsersPK
        PRIMARY KEY
        CLUSTERED
    , SomeUserData varchar(1000)
        CONSTRAINT Users_somedata_df
        DEFAULT (CRYPT_GEN_RANDOM(1000))
);

CREATE TABLE dbo.OrderDetails
(
    OrderDetailsID int NOT NULL
        CONSTRAINT OrderDetailsTestPK
        PRIMARY KEY
        CLUSTERED
    , OrderID int NOT NULL
        CONSTRAINT OrderDetailsOrderID
        FOREIGN KEY
        REFERENCES dbo.Orders(OrderID)
    , UserID int NOT NULL
        CONSTRAINT OrderDetailsUserID
        FOREIGN KEY
        REFERENCES dbo.Users(UserID)
    , SomeOrderDetailsData varchar(1000)
        CONSTRAINT OrderDetails_somedata_df
        DEFAULT (CRYPT_GEN_RANDOM(1000))
);

INSERT INTO dbo.Orders (OrderID)
SELECT TOP(100) ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
FROM sys.syscolumns sc;

INSERT INTO dbo.Users (UserID)
SELECT TOP(100) ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
FROM sys.syscolumns sc;

INSERT INTO dbo.OrderDetails (OrderDetailsID, OrderID, UserID)
SELECT TOP(10000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
    , o.OrderID
    , u.UserID
FROM sys.syscolumns sc
    CROSS JOIN dbo.Orders o
    CROSS JOIN dbo.Users u
ORDER BY NEWID();

CREATE INDEX OrderDetailsOrderID ON dbo.OrderDetails(OrderID);
CREATE INDEX OrderDetailsUserID ON dbo.OrderDetails(UserID);

Здесь мы запрашиваем таблицу OrderDetails, где UserID равен 15:

SELECT od.OrderDetailsID
    , o.OrderID
    , u.UserID
FROM dbo.OrderDetails od
    INNER JOIN dbo.Users u ON u.UserID = od.UserID
    INNER JOIN dbo.Orders o ON od.OrderID = o.OrderID
WHERE u.UserID = 15

Вывод запроса выглядит следующим образом:

╔════════════════╦═════════╦════════╗
║ OrderDetailsID ║ OrderID ║ UserID ║
╠════════════════╬═════════╬════════╣
║ 2200115 ║ 2 ║ 15 ║
30 630215 ║ 3 ║ 15 ║
║ 1990215 ║ 3 ║ 15 ║
60 4960215 ║ 3 ║ 15 ║
7 100715 ║ 8 ║ 15 ║
30 3930815 ║ 9 ║ 15 ║
║ 6310815 ║ 9 ║ 15 ║
41 4441015 ║ 11 ║ 15 ║
║ 2171315 ║ 14 ║ 15 ║
31 3431415 ║ 15 ║ 15 ║
7 4571415 ║ 15 ║ 15 ║
2 6421515 ║ 16 ║ 15 ║
║ 2271715 ║ 18 ║ 15 ║
01 2601715 ║ 18 ║ 15 ║
21 3521715 ║ 18 ║ 15 ║
18 221815 ║ 19 ║ 15 ║
║ 3381915 ║ 20 ║ 15 ║
7 4471915 ║ 20 ║ 15 ║
╚════════════════╩═════════╩════════╝

Как видите, порядок вывода строк не соответствует порядку строк в таблице OrderDetails.

Добавление явного ORDER BYгарантирует, что строки будут возвращены клиенту в желаемом порядке:

SELECT od.OrderDetailsID
    , o.OrderID
    , u.UserID
FROM dbo.OrderDetails od
    INNER JOIN dbo.Users u ON u.UserID = od.UserID
    INNER JOIN dbo.Orders o ON od.OrderID = o.OrderID
WHERE u.UserID = 15
ORDER BY od.OrderDetailsID;

╔════════════════╦═════════╦════════╗
║ OrderDetailsID ║ OrderID ║ UserID ║
╠════════════════╬═════════╬════════╣
15 3915 ║ 40 ║ 15 ║
7 100715 ║ 8 ║ 15 ║
18 221815 ║ 19 ║ 15 ║
99 299915 ║ 100 ║ 15 ║
82 368215 ║ 83 ║ 15 ║
38 603815 ║ 39 ║ 15 ║
30 630215 ║ 3 ║ 15 ║
28 728515 ║ 86 ║ 15 ║
22 972215 ║ 23 ║ 15 ║
201 992015 ║ 21 ║ 15 ║
7 1017115 ║ 72 ║ 15 ║
13 1113815 ║ 39 ║ 15 ║
╚════════════════╩═════════╩════════╝

Если порядок строк является обязательным, и ваши инженеры знают, что порядок является обязательным, им следует только захотеть использовать ORDER BYоператор, так как это может стоить им назначения, если произошла ошибка, связанная с неправильным порядком.

Во втором, возможно, более поучительном примере, используя OrderDetailsприведенную выше таблицу, где мы не объединяем никакие другие таблицы, но имеем простое требование найти строки, соответствующие как OrderID, так и UserID, мы видим проблему.

Мы создадим индекс для поддержки запроса, как вы, вероятно, сделали бы в реальной жизни, если производительность имеет какое-либо значение (когда это не так?).

CREATE INDEX OrderDetailsOrderIDUserID ON dbo.OrderDetails(OrderID, UserID);

Вот запрос:

SELECT od.OrderDetailsID
FROM dbo.OrderDetails od
WHERE od.OrderID = 15
    AND (od.UserID = 21 OR od.UserID = 22)

И результаты:

╔════════════════╗
║ OrderDetailsID ║
╠════════════════╣
║ 21421 ║
6 5061421 ║
║ 7091421 ║
14 691422 ║
7 3471422 ║
24 7241422 ║
╚════════════════╝

Добавление ORDER BYпредложения определенно гарантирует, что и здесь мы получим правильную сортировку.

Эти макеты являются просто простыми примерами, где строки не могут быть «в порядке» без явного ORDER BYутверждения. Подобных примеров гораздо больше, и поскольку код механизма СУБД меняется довольно часто, конкретное поведение может со временем меняться.

В качестве практического примера, в Postgres, порядок в данный момент изменяется при обновлении строки:

% SELECT * FROM mytable;
 id | data 
----+------
  0 | a
  1 | b
  2 | c
  3 | d
  4 | e
  5 | f
  6 | g
  7 | h
  8 | i
  9 | j
(10 rows)

% UPDATE mytable SET data = 'ff' WHERE id = 5;
UPDATE 1
% SELECT * FROM mytable;
 id | data 
----+------
  0 | a
  1 | b
  2 | c
  3 | d
  4 | e
  6 | g
  7 | h
  8 | i
  9 | j
  5 | ff
(10 rows)

Я не думаю, что правила этого существующего неявного упорядочения где-либо задокументированы, определенно могут быть изменены без предварительного уведомления, и, безусловно, не переносимы в ядрах БД.

не совсем демо, но слишком долго для комментария.

В больших таблицах некоторые базы данных будут выполнять чередующиеся параллельные сканирования:

Если два запроса хотят отсканировать одну и ту же таблицу и поступить почти одновременно, первый может быть частично пройден через таблицу при запуске второго.

Второй запрос может получать записи, начиная с середины таблицы (когда первый запрос завершается), а затем получать записи из начала таблицы.

Создайте кластерный индекс, который имеет «неправильный» порядок. Например, кластер на ID DESC. Это часто выводит обратный порядок (хотя это также не гарантируется).