Jak udowodnić brak niejawnego porządku w bazie danych?

Niedawno wyjaśniłem kolegom, jak ważne jest posiadanie kolumny do sortowania danych w tabeli bazy danych, jeśli jest to konieczne, na przykład w przypadku danych uporządkowanych chronologicznie. Okazało się to nieco trudne, ponieważ mogli po prostu ponownie uruchomić zapytanie pozornie bez końca i zawsze zwracałby ten sam zestaw wierszy w tej samej kolejności.

Zauważyłem to wcześniej i wszystko, co naprawdę mogłem zrobić, to nalegać, aby mi zaufali, a nie tylko zakładać, że tabela bazy danych będzie zachowywać się jak tradycyjny plik CSV lub Excel.

Na przykład wykonanie zapytania (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');

utworzy tabelę z wyraźnym porządkiem pojęciowym. Wybór tych samych danych w najprostszy sposób to:

SELECT * FROM mytable;

Zawsze daje mi następujące wyniki:

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

Mogę to robić w kółko i zawsze będą mi zwracać te same dane w tej samej kolejności. Wiem jednak, że ten dorozumiany porządek może zostać złamany, widziałem go już wcześniej, szczególnie w dużych zestawach danych, gdzie jakaś losowa wartość zostanie najwyraźniej wyrzucona w „niewłaściwe” miejsce po wybraniu. Ale przyszło mi do głowy, że nie wiem, jak to się dzieje i jak to odtworzyć. Trudno mi uzyskać wyniki w Google, ponieważ wyszukiwane hasło zwykle zwraca ogólną pomoc w sortowaniu zestawów wyników.

Tak więc moje pytania są zasadniczo następujące:

1. Jak mogę w sposób wyraźny i konkretny udowodnić, że kolejność zwrotu wierszy z zapytania bez ORDER BYinstrukcji nie jest wiarygodna, najlepiej przez spowodowanie i pokazanie podziału niejawnej kolejności, nawet jeśli tabela nie jest aktualizowana ani edytowana ?

2. Czy w ogóle ma to znaczenie, jeśli dane są wstawiane tylko raz masowo, a następnie nigdy nie aktualizowane?

Wolałbym odpowiedź opartą na postgresie, ponieważ jest to ta, którą znam najlepiej, ale bardziej interesuje mnie sama teoria.

Widzę trzy sposoby, aby przekonać ich:

1. Pozwól im wypróbować to samo zapytanie, ale z większą tabelą (większa liczba wierszy) lub gdy tabela jest aktualizowana między wykonaniami. Lub wstawiane są nowe wiersze, a niektóre stare są usuwane. Lub indeks jest dodawany lub usuwany między wykonaniami. Lub stół jest odkurzany (w Postgres). Lub indeksy są przebudowywane (w SQL Server). Lub tabela zostanie zmieniona z klastrowej na stertę. Lub usługa bazy danych jest restartowana.

2. Możesz zasugerować, że udowodnią, że różne egzekucje zwrócą to samo zamówienie. Czy mogą to udowodnić? Czy mogą zapewnić serię testów, które dowodzą, że każde zapytanie da wynik w tej samej kolejności, bez względu na to, ile razy zostanie wykonane?

3. Dostarcz dokumentację różnych DBMS w tym zakresie. Na przykład:

PostgreSQL :

Sortowanie wierszy

Po wygenerowaniu zapytania przez tabelę wyjściową (po przetworzeniu listy wyboru) można ją opcjonalnie posortować. Jeśli sortowanie nie zostanie wybrane, wiersze zostaną zwrócone w nieokreślonej kolejności. Rzeczywista kolejność w takim przypadku będzie zależeć od typu skanowania i planu dołączania oraz kolejności na dysku, ale nie można na nim polegać. Szczególne uporządkowanie wyjściowe może być zagwarantowane tylko wtedy, gdy zostanie wyraźnie wybrany krok sortowania.

SQL Server :

SELECT- ORDER BYKlauzula (Transact-SQL)

Sortuje dane zwrócone przez zapytanie w SQL Server. Użyj tej klauzuli, aby:

Uporządkuj zestaw wyników zapytania według określonej listy kolumn i opcjonalnie ogranicz wiersze zwrócone do określonego zakresu. Kolejność zwracania wierszy w zestawie wyników nie jest gwarantowana, chyba że określono ORDER BYklauzulę.

Oracle :

order_by_clause

Użyj ORDER BYklauzuli, aby uporządkować wiersze zwrócone przez instrukcję. Bez klauzuli order_by_clause nie ma gwarancji, że to samo zapytanie wykonane więcej niż jeden raz pobierze wiersze w tej samej kolejności.

To znowu historia czarnego łabędzia. Jeśli jeszcze go nie widziałeś, to nie znaczy, że nie istnieją. Mamy nadzieję, że w twoim przypadku nie doprowadzi to do kolejnego ogólnoświatowego kryzysu finansowego, a jedynie do kilku niezadowolonych klientów.

Dokumentacja Postgres mówi to wyraźnie:

Jeśli nie podano ORDER BY, wiersze są zwracane w dowolnej kolejności, którą system najszybciej znajdzie.

„System” w tym przypadku obejmuje samego demona Postgres (w tym implementację jego metod dostępu do danych i optymalizatora zapytań), podstawowy system operacyjny, logiczny i fizyczny układ pamięci bazy danych, a nawet pamięć podręczną procesora. Ponieważ jako użytkownik bazy danych nie masz kontroli nad tym stosem, nie powinieneś polegać na tym, że będzie zachowywał się tak samo, jak w tej chwili.

Twoi koledzy popełniają pospieszny błąd generalizacji . Aby obalić ich punkt wystarczy wykazać, że ich założenie jest błędne tylko raz, np. Przez ten dbfiddle .

Rozważ następujący przykład, w którym mamy trzy powiązane tabele. Zamówienia, użytkownicy i szczegóły zamówienia. OrderDetails jest powiązany z kluczami obcymi do tabeli Zamówienia i tabeli użytkowników. Jest to zasadniczo bardzo typowa konfiguracja relacyjnych baz danych; prawdopodobnie cały cel relacyjnego DBMS.

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);

Tutaj sprawdzamy tabelę OrderDetails, gdzie identyfikator użytkownika to 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

Dane wyjściowe zapytania wyglądają następująco:

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

Jak widać, kolejność wyjściowa wierszy nie zgadza się z kolejnością wierszy w tabeli OrderDetails.

Dodanie jawnego ORDER BYgwarantuje, że wiersze zostaną zwrócone do klienta w żądanej kolejności:

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 ║
╠════════════════╬═════════╬════════╣
║ 3915 ║ 40 ║ 15 ║
║ 100715 ║ 8 ║ 15 ║
║ 221815 ║ 19 ║ 15 ║
║ 299915 ║ 100 ║ 15 ║
║ 368215 ║ 83 ║ 15 ║
║ 603815 ║ 39 ║ 15 ║
║ 630215 ║ 3 ║ 15 ║
║ 728515 ║ 86 ║ 15 ║
║ 972215 ║ 23 ║ 15 ║
║ 992015 ║ 21 ║ 15 ║
║ 1017115 ║ 72 ║ 15 ║
║ 1113815 ║ 39 ║ 15 ║
╚════════════════╩═════════╩════════╝

Jeśli kolejność wierszy jest bezwzględna, a inżynierowie wiedzą, że porządek jest bezwzględny, powinni zawsze chcieć użyć ORDER BYinstrukcji, ponieważ może oznaczać koszt ich oznaczenia, jeśli wystąpi awaria związana z nieprawidłową kolejnością.

Drugi, być może bardziej pouczający przykład, wykorzystując OrderDetailstabelę z góry, dokąd nie dołączeniem innych tabel, ale mają prosty wymóg, aby znaleźć wiersze spełniające zarówno OrderID oraz identyfikator użytkownika, widzimy problem.

Stworzymy indeks do obsługi zapytania, tak jak w prawdziwym życiu, gdyby wydajność była w jakikolwiek sposób ważna (kiedy nie jest?).

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

Oto zapytanie:

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

A wyniki:

╔════════════════╗
║ Identyfikator zamówienia ║
╠════════════════╣
║ 21421 ║
║ 5061421 ║
║ 7091421 ║
║ 691422 ║
║ 3471422 ║
║ 7241422 ║
╚════════════════╝

Dodanie ORDER BYklauzuli z pewnością zapewni nam również prawidłowy sort.

Te makiety to tylko proste przykłady, w których nie można zagwarantować, że wiersze są „w porządku” bez wyraźnego ORDER BYoświadczenia. Jest o wiele więcej takich przykładów, a ponieważ kod silnika DBMS zmienia się dość często, określone zachowanie może z czasem ulec zmianie.

Jako praktyczny przykład w Postgres kolejność zmienia się w chwili aktualizacji wiersza:

% 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)

Nie sądzę, aby zasady tego istniejącego niejawnego zamówienia były nigdzie udokumentowane, z pewnością mogą ulec zmianie bez powiadomienia i zdecydowanie nie są przenośnym zachowaniem w silnikach DB.

nie do końca demo, ale za długo na komentarz.

Na dużych tabelach niektóre bazy danych wykonują przeplatane równoległe skanowanie:

Jeśli dwa zapytania chcą zeskanować tę samą tabelę i dotrzeć prawie w tym samym czasie, pierwsze może być częścią tabeli, gdy rozpocznie się drugie.

Drugie zapytanie może odbierać rekordy od środka tabeli (gdy kończy się pierwsze zapytanie), a następnie otrzymywać rekordy od początku tabeli.

Utwórz indeks klastrowy, który ma „niewłaściwą” kolejność. Na przykład włącz klaster ID DESC. Często będzie to generować odwrotną kolejność (chociaż nie jest to również gwarantowane).