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

21

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.


źródło
6
„Nigdy więcej nie pisałem ani nie aktualizowałem” - dlaczego to jest tabela? Brzmi jak plik. Lub wyliczenie. Lub coś, co nie musi znajdować się w bazie danych. Jeśli jest chronologiczna, czy nie ma kolumny z datami, według których można by zamówić? Jeśli chronologia ma znaczenie, pomyślałbyś, że te informacje byłyby wystarczająco ważne, aby je znaleźć w tabeli. W każdym razie plany mogą ulec zmianie z powodu upuszczenia lub utworzenia nowego indeksu lub zdarzeń, takich jak zmiany pamięci, flagi śledzenia lub inne czynniki. Ich argument brzmi: „Nigdy nie zapinam pasów i nigdy nie przeszedłem przez przednią szybę, więc nadal nie zapinam pasów.” :-(
Aaron Bertrand
9
Niektórych problemów logicznych nie da się rozwiązać technicznie lub bez udziału HR. Jeśli Twoja firma chce zezwolić na praktyki deweloperskie, które polegają na wierze w voodoo i ignorowaniu dokumentacji, a Twój przypadek użycia naprawdę ogranicza się do niewielkiego stołu, który nigdy nie jest nigdy aktualizowany, po prostu pozwól mu mieć sposób i zaktualizuj swoje CV. Nie warto się kłócić.
Aaron Bertrand
1
Nie masz podstaw, by twierdzić, że „zawsze”. Możesz tylko twierdzić, że „zawsze”, „kiedy zaznaczyłem”. Język ma definicję - jest to umowa z użytkownikiem.
philipxy
10
Ciekawe, dlaczego ci koledzy są przeciwni dodawaniu order byklauzuli do swoich zapytań? Czy próbują zaoszczędzić na pamięci kodu źródłowego? zużycie klawiatury? ile czasu zajmuje wpisanie przerażającej klauzuli?
mustaccio
2
Zawsze uważałem, że silniki baz danych powinny losowo permutować pierwsze kilka wierszy zapytań, dla których semantyka nie gwarantuje uporządkowania, aby ułatwić testowanie.
Doug McClean

Odpowiedzi:

30

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.

ypercubeᵀᴹ
źródło
W przypadku bardzo małych tabel, które nie są modyfikowane, takie zachowanie może być widoczne. Tego się spodziewamy. Ale nie jest to również zagwarantowane. Kolejność może ulec zmianie, ponieważ dodałeś indeks, zmodyfikowałeś go lub ponownie uruchomiłeś bazę danych i być może wiele innych przypadków.
ypercubeᵀᴹ
6
Jeśli zamówienie ma znaczenie, kto kiedykolwiek jest odpowiedzialny za sprawdzenie swojego kodu, powinien odrzucić, dopóki nie użyje ORDER BY. Deweloperzy DBMS (Oracle, SQL Server, Postgres) wszyscy mówią to samo o tym, co ich gwarancja na produkt, a co nie (i płacą o wiele więcej niż ja, więc wiedzą, co mówią, oprócz tego, że zbudowali te cholerne rzeczy).
ypercubeᵀᴹ
1
Nawet jeśli zamówienie wygląda teraz tak samo, czy jest pewne, że te tabele nigdy nie będą aktualizowane przez cały okres użytkowania tworzonego oprogramowania? Że już nigdy nie zostaną wstawione wiersze?
ypercubeᵀᴹ
1
Czy istnieje gwarancja, że ​​ten stół będzie zawsze taki mały? Czy istnieje gwarancja, że ​​nie zostaną dodane żadne kolumny? Widzę dziesiątki różnych przypadków, w których tabela może ulec zmianie w przyszłości (a niektóre z tych zmian mogą wpływać na kolejność wyniku zapytania). Sugeruję, aby poprosić ich o odpowiedź na wszystkie te pytania. Czy mogą zagwarantować, że nic takiego się nie wydarzy? I dlaczego nie dodadzą prostego ORDER BY, który zagwarantuje zamówienie, bez względu na to, jak zmieni się stół ? Dlaczego nie dodać sejfu, który nie szkodzi?
ypercubeᵀᴹ
10
Dokumentacja powinna być wystarczająca. Cokolwiek innego jest zgadywaniem, a w każdym razie nigdy nie będzie postrzegane jako ostateczne, bez względu na to, co udowodnisz. Zawsze będzie to coś, co zrobiłeś i da się wyjaśnić, prawdopodobnie na twój koszt, a nie coś, co jest . Uzbrojony w dokumentację, prześlij swoją „gwarancję” na piśmie i po prostu szukaj pisemnej zgody, aby nie zwracać wierszy w wymaganej kolejności (nie dostaniesz jej).
19

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 .

mustaccio
źródło
12

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.

Max Vernon
źródło
10

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.

JoL
źródło
Jest to udokumentowane: odpowiedź ypercube cytuje dokumentację mówiącą, że zamówienie nie jest określone.
Lekkość ściga się z Moniką
@LightnessRacesinOrbit Przyjąłbym to, ponieważ dokumentacja wyraźnie mówi nam, że nie jest udokumentowana. To znaczy, prawdą jest również to, że wszystko, czego nie ma w dokumentacji, nie jest określone. To rodzaj tautologii. W każdym razie zredagowałem tę część odpowiedzi, aby była bardziej szczegółowa.
JoL
3

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.

Jasen
źródło
2

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

usr
źródło