Key/RID lookup – co to jest?

KeyRidLookup_sqlserver_00

Jednym z najprostszych do rozwiązania problemów wydajnościowych w SQL Server są tzw. lookupy o którym chciałbym opowiedzieć w niniejszym artykule – zapraszam do lektury.

Jak wiecie optymalizator SQL Server może zdecydować się na użycie indeksu jeżeli tylko będzie to dla niego w odpowiednim stopniu optymalne. Sam indeks może być odpytywany operacją pełnego skanowania (Index Scan) lub też operacjami odszukania (Index Seek) – mechanizmy te opisałem tutaj. Napiszmy proste zapytanie, które przeszuka tabelę operatorem Index Seek (za przykład posłuży nam tabela DimCustomer z bazy AdventureWorksDW2014):

Jak widać użyty został operator Index Seek na indeksie o nazwie IX_LastName. Przyjrzyjmy się bliżej temu indeksowi używając komendy sp_helpindex:

IX_LastName jako klucz indeksu ma zdefiniowaną jedynie kolumnę LastName. Jak więc będzie wyglądał plan wykonania w momencie gdy nasze zapytanie dodatkowo będzie potrzebowało kolumny Customer Key?

Odpowiedź może być nieco myląca:

Ponownie został wykonany Index Seek – dlaczego tak się dzieje? Ponieważ pamiętamy o tym, że oprócz klucza indeks zawiera również wskaźnik do głównej tabeli ( w tym przypadku wskaźnikiem do indeksu klastrowanego którego kluczem jest CustomerKey). Zmodyfikujmy nasze zapytanie tak aby oprócz dwóch powyższych kolumn pobierało również kolumnę FirstName:

Tym razem w planie pojawiły się dwa dodatkowe operatory Nested Loops oraz Key Lookup:

Nested Loops jest niczym innym jak algorytmem złączenia (o nim jak i o innych algorytmach złączenia powiemy sobie w ramach innego artykułu) – interesujący dla nas jest operator Key Lookup. Odpowiada on za pobranie z tabeli głównej (w tym wypadku indeksu klastrowanego) wartości kolumn, których indeks sam w sobie nie zawiera. Tak więc uproszczony algorytm działania wygląda tak:

  1. Z indeksu IX_LastName pobrane zostały te wiersze, których wartość jest równa ciągowi znaków ‘Carter’ wraz ze wskaźnikami do tabeli głównej tj. CustomerKey
  2. Dla każdego wiersza zwróconego przez Index Seek wyszukiwane (po kluczu) są pasujące rekordy w tabeli głównej
  3. Z pasujących rekordów wybierana jest wartość dla kolumny LastName i zwracana do użytkownika

Koszt takiej operacji był na tyle mały, że optymalizator zdecydował się na niego – w innym przypadku gdy np. nasz warunek WHERE nie byłby dostatecznie selektywny przeskanowanie całej tabeli może być mniej kosztowne niż wyszukanie rekordów, a następnie łączenie się do tabeli źródłowej aby pobrać brakujące wartości. W tym przypadku punkt graniczny nazywany jest Tipping Point – można go obliczyć ręcznie na podstawie pewnego wzoru, który z pewnością opiszę w jednym z przyszłych postów. W poście opisującym Index Seek i Index Scan wspomniałem, iż jest to punkt wyboru pomiędzy Scan i Seek – tutaj możemy to doprecyzować, że jest to punkt pomiędzy Scan i Seek + Lookup. Przykładem gdy Tipping Point został przekroczony jest poniższe bezwarunkowe zapytanie:

Jak widać w zapytaniach tego typu indeks został całkowicie zignorowany. Scenariusz ten jest niestety najgorszym z możliwych w naszym przypadku. Nie jest to problem gdy mamy małą tabelę – co jednak gdy mamy do czynienia z wielomilionową tabelą transakcji? No właśnie. W takim przypadku zarówno pełne skanowanie jak i lookup nie pomoże. Lekarstwem w tym przypadku jest indeks pokrywający czyli covering index. Jest to nic innego jak indeks, który zawiera wszystkie potrzebne w naszym zapytaniu kolumny. Tak więc stwórzmy sobie nowy indeks, który będzie spełniał cechy indeksu pokrywającego dla naszego zapytania:

Następnie wykonajmy nasze zapytanie i spójrzmy na plan wykonania:

Jak widać nie było potrzeby “sięgania” do tabeli źródłowej. Stworzony przez nas indeks będzie bardzo efektywny w przypadku gdy wyszukujemy informacje po kolumnie LastName lub po LastName i FirstName. Jeżeli chcemy zawrzeć kolumnę w indeksie jednakże wiemy, że nie będzie ona używana w klauzuli WHERE to lepszym wyjściem będzie jej zawarcie na poziomie liści indeksu używając słowa kluczowego INCLUDE. Kolumny zawarte w indeksie przy użyciu INCLUDE nie będą zawarte na poziomach innych niż liście czyli nie będą częścią klucza – dzięki temu nasz indeks będzie mniejszy. Analogiczna do powyższego składnia ze słowem kluczowym INCLUDE została zawarta poniżej:

Po wykonaniu zapytania naszym oczom powinien ukazać się plan jakiego oczekiwaliśmy:

Oprócz operatora Key Lookup możecie w swoich planach znaleźć również operator RID Lookup. Pełni on analogiczną funkcję z tym, że zamiast łączenia z indeksem zgrupowanym łączy się ze stertą tj. tabelą bez indeksu zgrupowanego.

Powyższy plan powinien dać nam do myślenia tj. powinniśmy się zastanowić czy występowanie sterty to coś czego na pewno potrzebujemy oraz czy nie powinniśmy stworzyć indeksu pokrywającego.

W przypadku występowania operacji lookup w naszym planie wykonania warto stworzyć indeks pokrywający aby przyspieszyć działanie całego zapytania. Dzięki temu możemy uniknąć niepotrzebnych operatorów tak jak wspomniany lookup czy też operator złączenia (Nested Loops). Warto podkreślić, że same operatory lookup nie są czymś z czym bezwzględnie trzeba walczyć – po prostu w bardzo wielu przypadkach można je wyeliminować odpowiednio dopasowanym indeksem. Ta prosta technika pozwala w znacznym stopniu przyspieszyć bardzo wiele zapytań – mam nadzieję, że okaże się dla was przydatna.

 

Adrian Chodkowski
Follow me

Adrian Chodkowski

SQL geek, Data enthusiast, Consultant & Developer
Adrian Chodkowski
Follow me

Latest posts by Adrian Chodkowski (see all)

6 Comments

  1. Gość

    Czyli chyba w ogóle lepiej jest zakładać indeksy przy użyciu INCLUDE? No bo wyobraźmy sobie sytuację, gdy tworzymy aplikację bazodanową np. dla sklepu internetowego. Na pewno klienci będą wyszukiwali produkty po ich nazwie, więc kolumnę “ProductName” warto dać jako klucz indeksu nieklastrowego. Ale klienci mogą też (nie muszą) wyszukiwać produkty dodając do filtracji ich inne atrybuty, takie jak: cenę towaru, jego wagę, nazwę producenta, jakieś opcje związane z promocjami i rabatami, itd. Odpowiadające im kolumny chyba warto dodać za pomocą INCLUDE, a nie robić z nich kluczy indeksu?

    Reply
    1. Adrian ChodkowskiAdrian Chodkowski (Post author)

      Jeżeli coś jest w INCLUDE to nie da się po tym wyszukiwać wartości – struktura ta jest potrzebna tylko po to aby tworzyć zapytania pokrywające. Do wyszukiwania wartości wykorzystywane są jedynie te wartości, które są zawarte w kluczu, a i to nie zawsze gwarantuje wykorzystania indeksu.

      Reply
      1. Gość

        “Jeżeli coś jest w INCLUDE to nie da się po tym wyszukiwać wartości – struktura ta jest potrzebna tylko po to aby tworzyć zapytania pokrywające”. Ale jeżeli kolumna(y) jest w INCLUDE i nie można jej wykorzystać do szukania wartości, to po co ona tam jest? Przecież po to dodajemy kolumny do definicji indeksu, aby wspomóc wyszukiwanie w nich. A te zapytania pokrywające, czy raczej indeksy pokrywające no to są własnie po to, aby za pomocą dodatkowo dołączonych kolumn zapewnić poszukiwanie brakujących wartości. W jaki sposób można wykorzystywać poszukiwanie wartości w kolumnie znajdującej się w INCLUDE (a przez to w indeksie który wspiera wyszukiwanie), skoro nie można wyszukiwać w niej wartości? Nie rozumiem tego, gdzieś to jest sprzeczność. SQL Server Management Studio standardowo proponuje tworzenie indeksów nieklastrowych z opcją INCLUDE, gdy wykryje że nie ma takiego indeksu.

        Reply
        1. Adrian ChodkowskiAdrian Chodkowski (Post author)

          Indeksy wspomagają operację wyszukiwania ale pełnią również inne funkcje. Np. w artykule w przykładzie gdzie LastName jest kluczem indeksu a FirstName jest w INCLUDE to przy zapytaniu “SELECT FirstName,LastName…” w planie zauważymy, że nie potrzeba było sięgać do źródłowej tabeli bo indeks zawierał już obie kolumny – tzn. indeks był pokyrwający dla tego zapytania. Jest to o tyle dobre, że cała tabela (czy to pod postacią sterty czy indeksu klastrowanego) zajmuje więcej miejsca niż taki indeks, który jest jej podzbiorem tak więc przy zapytaniach mniej stron danych jest odczytywanych, a więc zapytanie jest szybsze. Ponadto indeksy dają nam posortowany zbiór danych co też ma ogromny wpływ na wybór przez optymalizator algorytmu złączenia.

          Reply
          1. Gość

            No ale wcześniej napisałeś że kolumna zawarta w INCLUDE nie służy do szukania w niej brakujących wartości, a ten przykład o którym piszesz wskazuje że w tej kolumnie jednak następuje szukanie wartości.

          2. Adrian ChodkowskiAdrian Chodkowski (Post author)

            Kolumna INCLUDE powoduje, że na najniższym poziomie indeksu znajdują się dane zawarte w kolumnie podanej w tej klauzuli. Dla przykładu wyszukujemy osobę w tabeli po PESEL i mamy na tym polu indeks to zostanie on użyty aby znaleźć konkretny PESEL np. SELECT pesel FROM Tabela WHERE pesel=123. Jeżeli oprócz samego peselu chcemy wyświetlić nazwisko tj.SELECT nazwisko,pesel FROM Tabela WHERE pesel=123 to albo nazwisko musi być częścią klucza albo być zawarte na najniższym poziomie indeksu – w innym wypadku aby pobrać to nazwisko będzie trzeba zrobić lookup do tabeli. Tak więc mają coś w INCLUDE to ta kolumna jest tam tylko potrzebna aby zwrócić rezultat bez konieczności lookupu/łączenia się do tabeli.

Leave a Comment

Your email address will not be published. Required fields are marked *