Jacek Fiok, 23.10.2002r.
Przygotowano na użytek seminarium magisterskiego Bazy Danych 2 na wydziale MIM UW.

Wstęp: świat, w którym się poruszamy.

Bazujemy na modelu pamięci drugiego poziomu (dysków) zbudowanych z bloków.

Atrybuty - to stałe lub zmiennej długości sekwencje bajtów - tworzą pola.
Pola danej krotki razem - rekordy.
Rekordy razem - bloki.

Całość - czyli relacja, lub zbiór obiektów należących do klasy - plik.

Przydatne też będą różne struktury danych. Np. żeby było można szybciej wyszukiwać/modyfikować, na plik nakłada się indeksy. (--> r. 13 i 14).

Co niniejsza praca ma wyjaśnić:

• jak reprezentujemy:
  • typy jako pola.
  • krotki jako rekordy
  • zbiory rekordów, na dysku i w pamięci
• jak reprezentujemy i przechowujemy całe relacje
• jak radzimy sobie z:
  • rekordami zmiennej długości
  • rekordami nie ładującymi się równo w bloki (małe-średnie-ogromne)
• co będzie z aspektami obiektowymi (jak chociażby wskaźniki/referencje).

Wstęp o obiektowości w bazach danych:

Obiekt to też krotka. Jego zmienne instancyjne - to atrybuty.

Różnice między obiektem a krotką:

• metody: kod metod jest częścią "schematu" bazy
• unikalny identyfikator obiektu. Tj. adres w jakiejś przestrzeni.

Obiekty mogą też mieć związki z innymi obiektami, co może być reprezentowane przez wskaźniki lub listy wskaźników.

Metody są zazwyczaj przechowane ze schematem. Bo należą do bazy jako do całości, a nie do każdego obiektu (to ideologia) - ale przede wszystkim dlatego, że powtarzanie byłoby bez sensu.

Zazwyczaj będzie tak, że każdy obiekt będzie miał wskaźnik/pole mówiące do jakiej klasy należy.

Oczywiście reprezentacje związków "cokolwiek-wiele" mają zmienną długość.

Reprezentacja pól.

• Liczby, daty (jeśli decydujemy, że mają stałą długość) - kwestia oczywista.
• Stringi stałej długości - CHAR(n) - albo null-terminated, albo jak w Pascalu (długość + treść).
• Mamy też typ VARCHAR(n), ale zamierzoną (wg kogo?) implementacją dla niego jest też pole stałej długości (n+1).
• Daty i czasy, jeżeli ktoś sobie życzy, bo chce móc robić np. bardzo albo mniej bardzo precyzyjnie - mogą być w polach zmiennej długości.
• Są też bity BIT(n) oraz BOOLEAN, oczywiste.
• Typy wyliczeniowe - również oczywiste (najwyżej kwestia teoretycznej optymalizacji, że czasem by wystarczył np. jeden bajt zamiast dwóch - ale to i tak ostatecznie nie ma znaczenia - bo: patrz dalej).

Rekordy.

Element relacji - ma pola.

Schemat = { nazwy, typy }.

Teraz trzeba dodać kolejność, czyli de facto "offsety". I więzy spójności (constrainty).

Często architektury maszyn są takie, że szybciej się dostać do pola, jeśli jest ono pod adresem podzielnym przez 4 lub przez 8 (64-bit). Czasami niektóre typy (np. Int32) wręcz muszą być pod takim adresem. Przy przenoszeniu bloku z dysku do pamięci ta własność będzie zachowana. Koniec końców - zwykle wszystkie offsety (zarówno rekordu w bloku, jak i pola w rekordzie) - będą podzielne przez 4/8.

Nagłówek rekordu:

Oczywiście nie trzeba trzymać schematu z każdym rekordem. Zwykle mamy pole typu. A po co w ogóle cokolwiek? Przydatne, gdy mamy obiekty, podtypy, czy w ogóle dopuszczalne rekordy różnych typów a'la unie w C.

Natomast na pewno trzymamy rzeczy już różne dla potencjalnie każdego rekordu:

• długość (znowu: czasem wynika ze schematu: ale po pierwsze, może być zmienna, a po drugie, czasem kiedy np. potrzebujemy zobaczyć tylko następny rekord, to możemy sobie oszczędzić odczyt bloku).
• jakieś stemple czasowe (tzn. timestampy; atime/mtime...).

Dalej rekordy są pakowane w bloki. Kiedy potrzebujemy dostać się do danych, bloki są przesyłane do pamięci. Opcjonalnie blok również może mieć nagłówek, w którym będą informacje takie jak:

• linki do innych bloków w jakiś sposób powiązanych (przydaje się do indeksów, patrz następny referat)
• informacje o roli tego bloku w grupie
• informacje o tym, z której relacji są rekordy w bloku
• offsety wszystkich rekordów w tym bloku
• block ID (patrz dalej)
• stemple czasowe.

Adresowanie.

Przed reprezentacją złożonych struktur musimy nauczyć się jeszcze adresować; różne adresy będą często potrzebne w złożonych rekordach.

Adresem bloku po załadowaniu do pamięci jest adres wirtualny w przestrzeni aplikacji (od tej pory zapominamy o różnicy między wirtualnym, a rzeczywistym - na naszym poziomie już nie będzie nas to obchodzić; patrzymy na adres wirtualny jak na po prostu adres w pamięci).

Na poziomie dyskowym musimy adresować jakoś inaczej. Coś w stylu: <id urządzenia, numer cylindra...>. Wtedy rekord ma adres <fizyczny bloku, offset w tym bloku>.

Na marginesie: trend "brokerów obiektowych" pozwala na niezależne i jednoczesne tworzenie/utrzymywanie obiektów przez różne systemy (środowisko rozproszone? CORBA?). Obiekty to też krotki - nie w tym problem; ważne jest to, że takie systemy potrzebują dodatkowych rozwiązań w kwestiach adresowych.

Typowy system bazodanowy jest w modelu klient-serwer. Tzn. koniec końców wszystko sprowadza się do tego, że klienci dostają rekordy, o które proszą. I te rekordy lądują w przestrzeniach adresowych ich aplikacji. Klienci mogą być na różnych maszynach.

Na poziomie serwera możemy adresować bloki w sposób:

• od razu fizyczny <[host], id dysku, cylinder, ścieżka, blok [, offset pierwszego rekordu]>
• logiczny: jakiś napis, który mapuje się w dyskowe adresy fizyczne. Wtedy potrzebny jest też odpowiednik tablicy stron dla RAM-u - mapujący adresy dyskowe logiczne w fizyczne.

Analiza tych rozwiązań:

• (plus dla logicznych) Dyskowe adresy fizyczne są długie. 8 bajtów to minimum. Niektóre systemy używają 16. [tu obliczenia o bazie, która ma wytrzymać 100 lat i zmieścić 2^77 rekordów...]
• wada adresów logicznych: dwa odczyty na dostęp (do mapy + do bloku; być może mapę można mieć na stałe w pamięci - znowu analogia z TLB w cache procesora - wtedy mniejszy problem. Różnica tego i tablicy stron: tu wszystkie bloki są reprezentowane; nie tylko ramki aktualnie w pamięci. ).
• następna zaleta adresów logicznych: elastyczność (można przenosić rekordy fizycznie bez zmian adresów logicznych - wszystkie wskaźniki są logiczne i już).

Można też rozważać kombinacje obu rozwiązań - "structured address". Np. adres fizyczny bloku plus klucz rekordu w bloku (tzn. nie offset w bajtach). Ale - po co zaraz klucz. Dobrym rozwiązaniem jest nie klucz, tylko logiczny numer rekordu w bloku. Układajmy rekordy od końca bloku. W ten sposób nie musimy alokować stałej ilości pamięci na nagłówek (nie wiemy, ile rekorów się zmieści w bloku!).

Inne zalety:

• możemy przesuwać rekordy w obrębie bloku zmieniając jedynie tablicę offsetów w tym bloku,
• możemy nawet pozwolić na przesunięcie do innego bloku (ale trzeba uważać - patrz dalej).
• jeśli rekord był skasowany, to możemy zrobić nagrobek.zamiast wskaźnika do rekordu. Nagrobek to jakaś specjalna wartość. Gdyby nie nagrobek, to jeśli ktoś poszedłby po wskaźniku skądś do tego miejsca, to byłby problem.

Mieszanie wskaźników ("pointer swizzling").

Wskażniki - gdzie?

• bywają częścią rekordów. Może nie jest to typowe dla relacji, ale na pewno - dla obiektów (no i współczesne systemy relacyjno-obiektowe też).
• ale również indeksy: zazwyczaj są złożone z bloków, w których są wskaźniki.

blok/rekord/obiekt - wszystko może mieć 2 adresy: w pamięci [typowo 4B] i na dysku [typowo 8B].

Kiedy blok (analogia: strona) leży na dysku, wszystkie wskaźniki są oczywiście dyskowe. Ale kiedy w pamięci - możemy się odwołać tak, albo tak. Przy czym wydajniej jest przez pamięć - wtedy możemy się tam dostać pojedynczą instrukcją procesora.

Jeśli chcemy móc odnajdywać bloki po adresie dyskowym w pamięci - potrzebna jest tablica mapująca adresy dyskowe w pamięciowe.

Czyli znowu podobnie do tablicy stron.

W mapie występują tylko bloki w pamięci.

Zeby uniknąć ciągłego patrzenia w tablicę, możemy zrobić coś co nazywa się mieszaniem. Ogólna zasada: kiedy blok jest wczytywany do pamięci, wskaźniki w nim mogą być "przerobione" - tzn. przetłumaczone na aktualny adres w pamięci.

Zatem wskaźnik musi składać się z:

• indykatora, czy jest to wskaźnik bazodanowy, czy pamięciowy
• właściwego adresu.

Możemy sobie wyobrazić różne strategie:

1. mieszanie automatyczne - tzn. zawsze, kiedy blok jest ładowany do pamięci.

   Po pierwsze, po załadowaniu wpisujemy nasz blok do tablicy. Teraz patrzymy na blok - czy są w nim wskaźniki? Skąd to wiemy?

   • zwykle wiemy z jakiego schematu są rekordy - i już,
   • jeśli blok jest używany do indeksu - będą w wiadomych miejscach
   • ew. możemy trzymać listy lokacji wskaźników w nagłówku.

   Linki wewnątrzblokowe możemy przetłumaczyć od razu.

   Na resztę patrzymy w tablicę: jeśli jest wpis, to tłumaczymy, wpp zostawiamy.

   Zawsze kiedy próbujemy iść po referencji dyskowej, próbujemy zrobić to samo: jeśli okazuje się, że dany blok jest już w pamięci, to go mieszamy. Jeśli nie ma, to trzeba załadować blok do pamięci, po czym też można "zamieszać".

2. mieszanie "na żądanie"

   Zostaw wszystkie wskaźniki przy ładowaniu bloku nietknięte. Jedynie dopisz ten blok do tablicy.

   Próbuj mieszać wtedy, kiedy idziesz po jakiejś referencji.

   To "odkłada tę pracę w czasie". Trzeba rozważyć, jak ma się zysk z tego, że w systemie automatycznym zrobimy wszystko od razu do tego, że być może niektórych referencji nie użyjemy nigdy (czyli automat tracił czas).

   Możemy zrobić taki manewr, że adresy dyskowe będą wyglądały jak złe adresy pamięciowe. Po czym każdy wskaźnik traktujemy tak samo. Jeśli trafiliśmy na dyskowy, dostajemy błąd braku strony (INT 14). Którą to procedurę przerwania trzeba przedefiniować na być może załadowanie bloku + mieszanie. Zysk jest taki, że chodzenie po referencjach jest robione jedną instrukcją.

3. Bez mieszania. Dalej musimy mieć tablicę bloki->pamięć. Zaleta: rekordy nigdy nie będą "przybite" w jakimś miejscu pamięci. (patrz dalej).
4. Można rozważyć implementacje z "podpowiedziami" użytkownika. Programista (który być może wie lepiej, czy będzie używał wskaźników dużo, czy mało) mógłby powiedzieć, czy chce mieć mieszanie automatyczne, czy na żądanie.

Zwrot bloku na dysk: wszystkie wskaźniki przetłumacz z powrotem.

Tablica musi być więc asocjacyjna w obie strony (w obie strony wydajnie).

Rekordy/bloki "przybite" (pinned).

Blok jest przybity, jeśli w danym momencie nie może być bezpiecznie zapisany na dysk (a jego strona zwolniona z pamięci). Informację o tym, czy tak jest, możemy przechowywać w nagłówku. Aby tak się stało, wystarczy, że pewien blok B1 ma jakiś wskaźnik na B2. I wtedy trzeba uważać z usunięciem B2. Blok B2 jest przybity.

Zatem usuwając stronę musimy nie tylko unswizzle wszystkie wskaźniki na niej, ale dodatkowo "odpinezkować się" z pamięci: trzeba "unswizzle" wszystkie referencje pokazujące na naszą stronę.

Czyli musi istnieć tablica, trzymająca dla każdego adresu bazodanowego w pamięci, miejsca gdzie istnieją na nią wskaźniki. Możliwe podejścia do problemu:

1. trzymaj listę referencji do bloku jako listę dołączoną do informacji o nim w tablicy translacji baza<->pamięć.
2. jeśli adresy pamięciowe są co najmniej 2x krótsze niż dyskowe, możemy tworzyć tą listę "w miejscu". Tj. w miejscu każdego wskaźnika dyskowego w momencie "swizzle" wpisujemy:

   <wskaźnik pamięciowy, wskaźnik będący częścią listy jego wystąpień>.

Zarys działania list referencji "in situ":

Mamy blok dyskowy X, będący w pamięci w Y.
Blok Z ma referencję na Y =>
	- jeśli to pierwsza referencja: wpisz do tablicy: ; link w Z := <Y, NULL>
	- następne: formuj dłuższą listę.

Dane i rekordy zmiennej długości.

Oczywiście, że możemy tak reprezentować stringi. Co jeszcze?

• pola typu zbiorowego (część "-wiele" relacji w bazie obiekowej)
• rekordy zmiennej długości (z jakiegokolwiek wymienionego już powodu)
• wielkie pola (typu film MPEG) - upada założenie o mieszczeniu się w bloku.

Nagłówek rekordu musi znać:

• długość rekordu
• wskaźniki do początków wszystkich pól zmiennej długości.

(przy czym jeśli zmienne pola upakujemy na końcu, to pierwszy wskaźnik jest niepotrzebny - będzie po polach stałych).

Podobnie z polami wielokrotnymi (tzn. element pola ma stałą długość, ale pole zmienną ilość elementów). W nagłówku dajemy wskaźnik na pierwszy element, oraz albo też na ostatni, albo podajemy ilość wystąpień.

NA MARGINESIE: warto przemyśleć zmienną reprezentację pól, które często są NULL. Np. null napis => moglibyśmy dawać null wskaźnik, oszczędzając całe miejsce.

Alternatywne rozwiązanie: trzymaj rekordy stałej długości, a części zmienne - na innych blokach. W rekordzie trzymaj wskaźniki do początków pól i do końców pól (albo odpowiednie ilości wystąpień).

Wady i zalety:

• rekord stałej długości jest szybciej wyszukiwalny
• minimalizuje narzut na nagłówki
• ułatwia przenoszenie po blokach (nie ma problemu nierównych podziałów itp.)
• ALE: potencjalnie zwiększa się potrzebna ilość dostępów dyskowych.

Możliwy kompromis - w ustalonym, stałym rozmiarze pamięci zrób miejsce na:

• jakąś sensowną ilość extra miejsca na dynamiczne dane
• wskaźnik na miejsce poza rekordem/blokiem, gdzie mogą być trzymane te, które się już nie mieszczą
• ilość nie mieszczących się danych.

(to wszystko jest na poziomie rekordu - czyli taki rekord jest widziany jako stałej długości).

Rekordy zmiennego formatu:

Może być tak, że nie mamy stałego schematu. Albo chcemy pozwolić na trzymanie w jednej "relacji" pól różnych typów. Najprostsza reprezentacja - oznacz rekordy, tj. trzymaj z każdym polem (!):

• nazwę
• typ [i opcjonalnie długość]
• wartość.

Powody do używania czegoś takiego:

• integracja różnych aplikacji: kiedy relacja była skonstruowana w kilku źródeł, a jest ogromna i konwersja byłaby problemem; albo pojawiło by się mnóstwo NULL-i i już lepiej zrobić 2 podtypy oszczędzając dużo miejsca.
• rekordy z bardzo zmiennym schematem. Np. wyobraźmy sobie rekord medyczny o pacjencie: może zawierać informacje o bardzo wielu możliwych badaniach, ale zazwyczaj pacjent ma wyniki najwyżej kilku z nich.

<kod nazwy> <kod typu> <długość> <wartość> | <kod nazwy2> ...

Rekordy, które nie mieszczą się w bloku.

Przydatne nawet, jeśli by się zmieściły, ale byśmy tracili dużo miejsca (fragmentacja wewn.).

Ogólnie: pozwól rekordowi rozdzielić się na różne bloki.

Czyli mamy fragmenty; rekord, który ma 2+ fragmenty - dzielony ("spanned").

Tu z kolei pojawia się analogia do fragmentów IP.

Jeśli rekordy mogą być dzielone, to rekord i fragment rekordu musi mieć extra w nagłówku:

• bit mówiący czy to jest fragment
• jeśli fragment, to czy pierwszy lub ostatni
• jeśli istnieje poprzedni/następny fragment, to wskaźniki na te fragmenty.

BLOB - binary large data objects (wielkie obiekty binarne).

• po pierwsze, często chcemy, żeby bloki szły po kolei i na jednym cylindrze
  (można też na zwykłej liście bloków - ale będzie wolniej)
• czasem wymagane jest żeby można było bardzo szybko czytać - wtedy trzeba rozrzucić obiekt po kilku dyskach - striping. I czytać równolegle.
• upada też założenie, że klientowi przesyła się cały rekord. W wypadku BLOB powinno się umożliwić użytkownikowi czytanie po kawałku. I być może "45. minutę filmu" (tj. niekoniecznie sekwencyjnie).

Modyfikacje rekordów

Ogólnie: najgorzej jest, kiedy rekord zmienia długość.

Insert.

Wkładamy nowe rekordy do relacji. Jeśli trzymane są byle jak: znajdź blok z wolnym miejscem, lub zaalokuj nowy; zapisz.

Jeśli chcemy, żeby rekordy były trzymane w jakiś posortowany sposób (a jest dobry powód: przyspieszenie niektórych zapytań patrz r. 13) - trzeba:

• znaleźć dobry blok
• ew. poprzesuwać rekordy w jego obrębie (bo też mają być posortowane).
  Tu jest właśnie miejsce do używania structured addressing <dyskowy bloku, indeks rekordu w bloku>.

  Jeśli nie ma miejsca w naszym bloku - możliwości:

  • znajdź miejsce na innym bliskim bloku. wymaga obsługiwania offsetów adresujących poza blok. zazwyczaj zwiększa narzut nagłówkowy (takie offsety mogą być większe).
  • stwórz "blok nadmiarowy". każdy blok ma wskaźnik na blok nadmiarowy. W razie potrzeby przestaje on być NULL. Tam wkładamy rekordy, które teoretycznie "powinny" być w naszym bloku. Rekordy nadmiarowe mogą mieć dalsze nadmiary.

Delete.

Usunięcie rekordu --> chcemy odzyskiwać miejsce.

Jeśli mamy offsety w blokach - to już wystarczy, będzie można poprzesuwać w razie czego, jeśli będzie potrzeba włożyć nowy rekord.

Jeśli nie możemy przesuwać - trzeba utrzymywać listę wolnych miejsc na poziomie bloku. Można utrzymywać tę listę w tychże samych wolnych miejscach - nie ma narzutu na nagłówek.

Czasem zwolnienie daje możliwość usunięcia bloku nadmiarowego, być może po poprzesuwaniu kilku rekordów w okolicy.

Zawsze natomiast trzeba pamiętać, że do naszego rekordu mogły iść wskaźniki. W tym momencie używana jest technologia nagrobków.

Zamiast rekordu - połóź bit mówiący "rekord umarł". Czyli robimy zawsze na początku każdego rekordu 1 bit, normalnie 0, po skasowaniu 1.

Po usunięciu rekordu ten 1 bit będzie zmarnowany na bycie nagrobkiem.

Nagrobek jest permanentny - pozostanie do czasu rekonstrukcji całej bazy.

Jeśli mamy offsety w bloku ("rekord 2 -> offset 117") - nagrobek może być NULL-em. (wskaźniki pokazywały na "rekord 2"; teraz wartością będzie ten NULL).

Jeśli mamy globalną mapę adresów logicznych w fizyczne - nagrobkiem może być NULL zamiast adresu fizycznego.

Update.

Jeśli długość rekordu jest niezmieniona --> bez problemu.

Zmienia się --> wszystkie problemy dodawania i usuwania, z wyjątkiem, że nigdy nie będzie potrzebny nagrobek.

Nowy jest dłuższy --> potrzebne miejsce --> przesuwanie, lub blok nadmiarowy.
(gdyby zmienne części na osobnych blokach --> być może nowe bloki).

Analogicznie, gdy rozmiar się zmniejsza --> odzyskiwanie miejsca tak, jak po usunięciu.

PODSUMOWANIE.

• rekord w bazie to pola + nagłówek.
• jeśli rekord zawiera jakieś pola zmiennej długości, lub krotności - to potrzebuje dodatkowych struktur. Katalog wskaźników w nagłówku rekordu pokazuje miejsca, gdzie zaczynają się kolejne pola. Alternatywnie, można wyrzucić całą zmienność na inne bloki - wskaźniki są stałej długości, więc rekord "główny" też będzie.
• bloki generalnie są zbiorami rekordów. istnieje nagłówek bloku.
• rekordy sfragmentowane: zapobiegają marnotrawstwu miejsca, albo powstają z konieczności (bo za duże). Wszystkie fragmenty muszą się wiązać listą.
• BLOB-y, czyli mega-rekordy, mają jeszcze pewne dodatkowe wymagania.
• aby wspierać insert/delete i rekordy zmiennej długości, możemy dać tablicę offsetów rekordów do nagłówka bloku i adresować po numerze rekordu wewnątrz bloku.
• bloki nadmiarowe: powstają przy dodawaniu danych. Dane z nich "logicznie" powinny należeć do bloku głównego.
• adresy bazodanowe: fizyczne-długie lub logiczne - z całościową mapą.
• adresy struktualizowane: fizyczny bloku + indeks rekordu.
• pointer swizzling: technika tłumaczenia adresów bazodanowych na adresy w pamięci wirtualnej.
• nagrobki: powstają przy usuwaniu rekordów.
• blok "przybity" -- powstaje z różnych przyczyn, m.in. wtedy, kiedy istnieją inne bloki, które mają do niego "swizzled pointers".

Jacek Fiok
23.10.2002r.