edit

Interne Ebene

Heap

  • Eine DB-Tabelle wird in einem Heap (Collection) von Data Pages gespeichert
  • Jede Data-Page hat eine fixe Grösse, meist 8KB
  • Die Rows darin sind nicht sortiert

Table Scan

  • Scanning aller Pages einer Tabelle durch alle Rows
  • Extrahiere Rows, die Query-Bedinung erfüllen
  • Meist langsame Operation, soll durch Indexe verbessert werden
  • Wenn aber Resultatset 80% der Tabelle enthält, ist der Table Scan schneller als der Zugriff über ein Index

Indexe

  • Dienen der Beschleunigung der Suche
  • Braucht zusätzlich Speicher-Overhead

B-Trees

  • "Balanced Trees"
  • Eignet sich für Equality-Search (Filtern nach Gleichheitsbedigung) und Range-Search (Suchen in Wertebereich)
  • "B+-Baum" hat Daten nur in Blättern
  • Durch ausbalancierter Baum Zugriffe
  • Ein Knoten hat die Grösse einer Page
  • Visualisierung: https://www.cs.usfca.edu/~galles/visualization/BTree.html
  • In einem clustered Index enthalten die Blätter selbst die Daten-Rows
  • In einem unclustered Index halten die Blätter nur Referenzen auf die Rows im Heap

Hash-Index

  • Speichert Key-Value-pairs aufgrund einer Hash-funkion (wie hashmap)
  • Performance-Einbussen bei gleichen Hashes (gibt "overflow chain" - linked-List der Rows mit den gleichen hashes)

Bitmap Index

  • Speichert Attribute als Bitmuster
  • Nur geeignet, wenn Werte in Attribute kleinen Wertebereich haben (und diskret sind)
  • Wenn z.B. in einem Attribut immer nur die gleichen 2 Werte vorkommen, kann dies mit 1 Bit indexiert werden
  • Schnelle Abfragen mit ORs / ANDs

Indexe erstellen

  • convention (nicht standardisiert):
CREATE INDEX <IndexName>
ON <Table(attr)>;
  • Auf PK-Attributen werden automatisch Indices erstellt

Note

TODO

Query Processing

  • Eine Query wird geparst in einen Query-Tree
  • Vom Optimizer wird optimierter Ausführungsplan erstellt
  • Point Query: Suche Row mit bestimmten Wert, z.B. where id = 1024
  • Multipoint Query: Suche mehrere Rows mit bestimmten Wert, z.B. where balance = 1000
  • Range Query: Suche in einer Range, z.B. where income between 100 and 1000
  • Order Query: Query mit order by
  • Interpretation Postgres
    • Index wird nicht immer verwendet, vor allem wenn alle Rows durchgegangen werden (z.B. count(*))
    • Einfacher Select ist mit Index ca. 3-10x schneller