Stronicowanie w SQL Server

Siła złego na jednego

Bazy danych i tabele w nich zawarte potrafią być naprawdę duże. Duże potrafią być również zestawy danych, które użytkownicy chcą pobierać i modyfikować. Jasne jest, że nie wyświetlimy użytkownikowi jednocześnie kilkuset rekordów. Trzeba wiedzieć, że kilkaset rekordów to raczej mała tabela. Patrząc na to z drugiej strony, nie będziemy pobierać na stronę tysięcy rekordów, generować dla nich tabeli aby uzyskać jedyną pewną reakcję użytkownika - przerażenie. A oprócz przerażenia - frustrację, bo musiał długo czekać na przesłanie tych danych i wyliczenie układu ogromnej tabeli przez przeglądarkę. To nie tędy droga.

Co się robi w takich przypadkach? Problem nie jest nowy, więc pojawiły się już różne rozwiązania. Wyszukiwarki internetowe nie pokazują po uruchomieniu wszystkich stron, lecz wyświetlają pole tekstowe które wstępnie przefiltruje dostępne rekordy (strony). Drugi etap to stronicowanie wyników. Rekordy, które pomyślnie przeszły pierwszą fazę filtrowania nie są pobierane w jednej paczce. Są pobierane w mniejszych, możliwych do ogarnięcia wzrokem grupach. To dlatego w wyszukiwarkach dostajemy 10, 20 czy 50 najbardziej trafnych wyników. Najczęściej też nigdy nie zaglądamy do kolejnych grup. Ten właśnie podział na grupy, zwany stronicowaniem lub paginacją (w niektórych kręgach pejdżowaniem, z angielskiego paging), będzie dzisiejszym tematem.

Tabela testowa z danymi

Żeby pokazać jakieś zapytania trzeba mieć tabelę. Najlepiej, żeby ta tabela była duża. W praktyce stronicowanie stosuje się częsciej do rezultatów będących złączeniem kilku-kilkunastu tabel, ale takie złączenia w zapytaniach zaciemniałyby obraz samej techniki. Wszystkie techniki operaują na podzapytaniach (tabelach pochodnych), które mogą być dowolną instrukcją SELECT. Nie ma znaczenia liczba tabel biorących udział w złączeniu. Popatrzmy zatem na przykładową tabelę:

CREATE TABLE Paging
(
  ID int IDENTITY CONSTRAINT PK_Paging_ID PRIMARY KEY CLUSTERED,
  Name varchar(36) NOT NULL CONSTRAINT DF_Paging_Name DEFAULT (CAST(NEWID() AS nvarchar(36))),
  TimeCreated datetime NOT NULL CONSTRAINT DF_Paging_TimeCreated DEFAULT (GETDATE()),
  GuidData uniqueidentifier NOT NULL CONSTRAINT DF_Paging_GuidData DEFAULT (NEWID()),
)

W zasadzie wszystkie kolumny generują się automatycznie. Pozwala to uzupełnić tabelę w następujący sposób:

SET NOCOUNT ON
DECLARE @id int=0;
BEGIN TRANSACTION
  WHILE @id<100000
  BEGIN
    INSERT INTO Paging DEFAULT VALUES;
    SET @id+=1;
  END
COMMIT

Pobranie pierwszych dziesięciu rekordów pozwala uzyskać taki oto rezultat:

ID	Name	TimeCreated	GuidData
1	89BB489D-59F1-47B2-80C4-91171A0BF4BB	2013-09-19 19:38:23.357	EE7598F2-1990-4E8D-AC9E-02F111ABB30E
2	06047658-FED4-488E-83B2-F200C4891A64	2013-09-19 19:38:23.357	100B6A17-CC3B-4A92-A9E4-D9B5C3F004E5
3	F52EADAD-85BC-481A-B1E1-DC757DD31008	2013-09-19 19:38:23.357	23952970-7745-4415-BD7E-E923C4E0201B
4	4EA674B5-CE7D-4ED3-8EAB-F527811FD309	2013-09-19 19:38:23.357	869C0632-9D21-4CEC-B5BA-9BCC4D5A96CC
5	1913D9AF-221C-421B-9A75-FBC97EEC2030	2013-09-19 19:38:23.357	650DE6E8-0738-4F0C-BC7E-A53B649CA09F
6	27705916-39E3-497B-A618-928CD52C819F	2013-09-19 19:38:23.357	3EB2D284-1956-4125-B201-BF4008560DD7
7	E79E2AA7-EA73-4DEF-9654-A9AD00571765	2013-09-19 19:38:23.357	790EF86E-5EB9-4BF5-9462-D56498C19A6A
8	1439B054-8F22-45DC-BEC0-87A2C9D1FA9C	2013-09-19 19:38:23.357	63279B65-B899-44BD-9282-3365078223AB
9	DD54473F-660A-4C76-B6AE-7F81A71D7501	2013-09-19 19:38:23.357	CC36845F-B0F7-4FB8-9E88-356ECD5300AC
10	18D214E6-ACAA-4E2D-B7E7-0A1860307185	2013-09-19 19:38:23.357	8A5F3798-0B48-4401-8077-4D3BC5B1E288

Aby przykład był ciekawszy, zamierzam w ciągłej sekwencji identyfikatorów stworzyć dziurę:

DELETE FROM Paging WHERE ID=15

Do danych nie warto przywiązywać większej wagi - istotny jest tylko identyfikator, który pozwoli nam zidentyfikować rekordy. Przejdźmy zatem do samych technik stronicowania.

Metoda tabeli pochodnej z numerowaniem

Pierwsza technika polega na ponumerowaniu wierszy i wybraniu tych, których numery znajdują się na wybranej stronie. Popatrzmy na poniższy przykład:

--Rozmiar strony
DECLARE @pageSize int = 10;
--Numer strony, indeksowane od 0
DECLARE @pageNumber int = 1000;

SELECT ID, Name, TimeCreated, GuidData FROM
(SELECT *, ROW_NUMBER() OVER (ORDER BY ID) RowNumber FROM Paging) Numbered
WHERE RowNumber BETWEEN @pageNumber*@pageSize+1 AND (@pageNumber+1)*@pageSize

SELECT TOP (@pageSize) ID, Name, TimeCreated, GuidData FROM
(SELECT *, ROW_NUMBER() OVER (ORDER BY ID) RowNumber FROM Paging) Numbered
WHERE RowNumber > @pageNumber*@pageSize

Oba zapytania można traktować prawie jako równoważne. Co prawda plan wykonania dla pierwszej z nich jest oceniany przez silnik SQL Server lepiej (40% do 60%), ale fizyczne wykonanie przebiega bardzo podobnie dokładnie tak samo. W pierwszym zapytaniu silnik bazy danych nakłada górne ograniczenie na dane przed zastosowaniem warunku ((@pageNumber+1)*@pageSize). Oznacza to, że SQL Server nigdy nie odczyta więcej danych, niż wynosi ta właśnie wartość i to właśnie przez ten drobny szczegół zapytania dla pierwszych kilkunastu stron będą działały minimalnie lepiej. W drugim przypadku najpierw wykonywane jest filtrowanie, a dopiero po tej operacji rekordy spełniające warunek przekazywane są do bloku TOP. Operacje odczytu przerywane są dopiero wtedy, gdy blok TOP osiągnie wymagana liczbę rekordów. Nie są to różnice duże, ale warto o nich wiedzieć. Zwłaszcza, o czym wspomniałem we wstępie, najczęsciej użytkownik zajmuje się pierwszą lub kilkoma początkowymi stronami.

Wspólne wyrażenie tablicowe z numerowaniem

Pokazana poniżej metoda jest bardzo podobna do poprzedniej. Różnica polega tylko na innym sposobie zdefiniowania źródła danych, do którego zostanie dodana numeracja. Wcześniej była to tabela pochodna, teraz będzie to wyrażenie CTE:

--Rozmiar strony
DECLARE @pageSize int = 10;
--Numer strony, indeksowane od 0
DECLARE @pageNumber int = 10;

WITH Numbered AS
(
SELECT *, ROW_NUMBER() OVER (ORDER BY ID) RowNumber FROM Paging
)
SELECT ID, Name, TimeCreated, GuidData FROM Numbered
WHERE RowNumber BETWEEN @pageNumber*@pageSize+1 AND (@pageNumber+1)*@pageSize;

WITH Numbered AS
(
SELECT *, ROW_NUMBER() OVER (ORDER BY ID) RowNumber FROM Paging
)
SELECT TOP (@pageSize) ID, Name, TimeCreated, GuidData FROM Numbered
WHERE RowNumber > @pageNumber*@pageSize;

Plany wykonania i samo fizyczne wykonanie jest dokładnie takie samo jak analogicznych metod wykorzystujących tabele pochodne.

Opcja OFFSET FETCH w standardzie SQL:2008

Znów co nieco o standardach. Relacyjny język SQL powstał dawno temu. Dawno temu powstał też pierwszy standard tego języka. Użytkownicy mają jednak swoje potrzeby, na które próbują odpowiedzieć twórcy silników baz danych. Jeżeli czegoś nie ma w standardzie i jest potrzeba, wtedy każdy z producentów stosuje swoje własne nazewnictwo. Dlatego mamy TOP w SQL Server, ROWNUM w Oracle i Limit w MySql. To dlatego stronicowanie w SQL wykonuje się korzystając z techniki z numerowaniem i tabelą pochodną, w ORACLE wstawia się warunek z ROWNUM. Każdy po swojemu. Gdy komitet standaryzacyjny uznaje, że funkcja jest przydatna, ustalają konkretną składnię.

Tak też stało się z opisywaną w tym podpunkcie techniką OFFSET FETCH. Dostępna jest ona od wersji SQL Server 2012, ale także w Oracle. Popatrzmy na przykładowy skrypt:

DECLARE @pageSize int = 10;
DECLARE @pageNumber int = 1;

SELECT * FROM Paging
ORDER BY ID
OFFSET @pageSize*@pageNumber ROWS
FETCH NEXT @pagesize ROWS ONLY;

Każda z pokazanych instrukcji powinna pobrać ten sam zestaw wyników. Druga dziesiątka rekordów powinna sie prezentować podobnie do pokazanych poniżej (pola czasu i globalne identyfikatory będą z pewnością inne):

ID	Name	TimeCreated	GuidData
11	14B92147-38B9-4A3E-93B1-B8E2FF160569	2013-09-19 14:15:41.120	62DB0BD9-3C2F-41A3-A961-4B2C649F8388
12	7E30AC2E-3ABA-40A1-A777-AB79D23319FC	2013-09-19 14:15:41.120	184BCBC4-DE15-427C-9C40-35ACC41AEDFE
13	AFC7B8CD-B047-4C4A-BA97-15E1BACE2703	2013-09-19 14:15:41.120	4AD1404B-9D01-4CF3-91D7-07D17DCB4B5D
14	3B4B1B9D-2926-4CD0-B8BE-EBAEDABA66CC	2013-09-19 14:15:41.147	18924ABB-E386-49AA-8635-6DB3DA25E4C1
16	1F3DA926-4A62-475E-9CD9-B1C56C0B5C9C	2013-09-19 14:15:41.147	39ADA127-7221-4364-ABEB-2FB9753ED347
17	1A7FE560-C5BC-4997-91DF-774D39ED02F0	2013-09-19 14:15:41.147	B8EF94F6-4FB1-4617-B950-EA812819F94D
18	BB526A1D-69C5-472C-B299-56FA8FDF9265	2013-09-19 14:15:41.157	8A6C4072-77FC-410B-B3F6-047836F289A4
19	1E726AC0-F3E4-4AED-8B8D-4072151307D3	2013-09-19 14:15:41.157	4041D799-2630-4E80-937A-C4137818ECEE
20	C62CCCAE-56B8-4FD0-918E-1A9E3F9C9C02	2013-09-19 14:15:41.157	2D162C4F-9C39-41E0-8C80-07BA10B98F25
21	94E21002-CAAB-4FA5-AF7C-C4D7E816AFD7	2013-09-19 14:15:41.157	E900BCC2-AB22-4620-B4F5-504C231AD02A

Warto zwrócić uwagę na usunięty rekord o identyfikatorze 15.

Nie mam po czym posortować

Wszystkie pokazane instrukcje stronicowania wymagają jakiegoś sposobu sortowania i w każdej z nich znajdują się słowa kluczowe ORDER BY. Czasami nie zależy nam na sortowaniu lub nie mamy żadnego indeksu klastrowanego (ewntualnie pokrywającego), który zapewni nam odpowiednie sortowanie rekordów. W takich przypadkach stronicowanie będzie wymagało dodatkowej operacji sortowania, która może być bardzo kosztowna. Jest na to sposób:

DECLARE @pageSize int = 10;
DECLARE @pageNumber int = 1;

SELECT * FROM Paging
ORDER BY (SELECT 0)
OFFSET @pageSize*@pageNumber ROWS
FETCH NEXT @pagesize ROWS ONLY;

WITH Numbered AS
(
SELECT *, ROW_NUMBER() OVER (ORDER BY (SELECT 0)) RowNumber FROM Paging
)
SELECT ID, Name, TimeCreated, GuidData FROM Numbered
WHERE RowNumber BETWEEN @pageNumber*@pageSize+1 AND (@pageNumber+1)*@pageSize;

Zamiast kolumny, po której wyniki mają być sortowane, wystarczy podać stałe wyrażenie SELECT. Każdy rekord będzie miał to samo, więc optymalizator SQL Server nie będzie wykonywał żadnej operacji sortowania.

Wymóg odpowiedniego sortowania rekordów nie jest przypadkowy. Załóżmy, że chcemy pobrać trzy dowolne rekordy spośród pięciu. Które SQL Server ma wyświetlić? Teoretycznie dowolne, ale w praktyce SQL Server wyświetli te, które najłatwiej mu odczytać. Jeżeli podamy kolejność stosując ORDER BY mamy już jakiś punkt zaczepienia. Nasze zadanie zmienia się w coś podobnego do: pobierz 3 pierwsze rekordy z najmniejszymi identyfikatorami (jako identyfikator może działać każdy zbiór kolumn jednoznacznie identyfikujący rekord). A co wtedy, gdy nie mamy żadnego kandydata na klucz główny lub pobierane przez nas kolumny mogą się powtarzać? W przypadku remisu SQL Server znów ma możliwość wyboru. Wybierze ten rekord, który mu najłatwiej odczytać. Standard SQL:2011 definiuje coś takiego jak OFFSET ... FETCH ... WITH TIES, które w przypadku remisu pobiera wszystkie rekordy. Dopiero to gwarantuje nam pełny determinizm. SQL Server 2012 niestety nie implementuje tej funkcjonalności.

Plany wykonania instrukcji

Wszytkie instrukcje pozwalają uzyskać ten sam zestaw danych wynikowych, ale ich przetwarzanie może się nieco różnić. Przyjrzyjmy się najpierw planowi wykonania wykorzystującemu tabelę pochodną i warunek BETWEEN (plan dla wyrażenia CTE będzie taki sam):

Rys. 1 - Plan wykonania dla stronicowania wykorzystującego tabelę pochodną i warunek BETWEEN. Plan dla analogicznej instrukcji wykorzystującej wyrażenie CTE będzie identyczny.

Dla konstrastu warto przyjrzeć się planowi wykonania instrukcji OFFSET FETCH:

Rys. 2 - Plan wykonania dla stronicowania wykorzystującego instrukcję OFFSET FETCH.

Już sam plan wykonania potwierdza, że lepiej, o ile mamy zainstalowany SQL Server 2012 lub wyższy, stosować instrukcję OFFSET FETCH. Jest to konstrukcja ze standardu SQL:2008, więc łatwiej będzie się przenieść na inne bazy, które również ten standard implementują. Jest jeszcze jedna zaleta tego rozwiązania wobec stosowanego wcześniej numerowania wierszy. Wiemy, że wewnętrzne wyrażenie numerujące dodaje nam kolumnę zawierającą kolejne liczby całkowite. Wyeliminowanie ich z wyniku wymaga ręcznego podania wszystkich kolumn, z pominięciem tej jednej, jedynej, potrzebnej tylko do filtrowania. Drobiazg, ale potrafi zirytować.

Najważniejszą zaletą, oprócz zysku wydajnościowego, jest czytelność samego zapytania. Kod odpowiedzialny za stronicowanie umieszczony jest na samym końcu zapytania i nie miesza się z kodem odpowiedzialnym za logikę zapytania.

I na koniec - jest to rozwiązanie wbudowane w sam silnik SQL Server. Jeżeli pojawi się jakaś wydajniejsza metoda stronicowania, w pierwszej kolejności zostanie zaimplementowana właśnie w miejsce instrukcji do tego właśnie przeznaczonej: OFFSET FETCH.

Kategoria:Common Table Expression Optymalizacja SQL SQL Server

Paweł Dyl, 2013-12-20

Spis treści: