Wikipedia · einfach zusammengefasst · Stand
Selektivität (Informatik)
Selektivität ist ein Maß, das in der Informatik bei Datenbankabfragen auf Datenbanktabellen in relationalen Datenbankensystemen gebraucht wird; sie bestimmt …
Inhalt4 Abschnitte
Begriff und Berechnung
Selektivität ist in relationalen Datenbanksystemen ein Maß dafür, welcher Anteil der Datensätze einer Tabelle eine Selektionsbedingung erfüllt und deshalb in die weitere Verarbeitung eingeht. In SQL stehen solche Bedingungen gewöhnlich in der WHERE-Klausel. Die Selektivität wird häufig mit σ bezeichnet; um eine Verwechslung mit dem Selektionsoperator der relationalen Algebra zu vermeiden, wird auch das Kürzel sel verwendet.
Ein Prädikat P ist ein Vergleichsausdruck, der für jeden Datensatz geprüft wird. Sind |σ_P(A)| die Anzahl der Datensätze aus Tabelle A, die P erfüllen, und |A| die Gesamtzahl ihrer Datensätze, gilt:
sel_P = |σ_P(A)| / |A|
Die Selektivität liegt zwischen 0 und 1. Der Wert 0 bedeutet, dass kein Datensatz die Bedingung erfüllt; bei 1 erfüllen alle Datensätze die Bedingung. Der Wert lässt sich auch als Prozentsatz der nicht ausgefilterten Datensätze verstehen.
Bei einem Join, also der Verknüpfung zweier Tabellen B und C, wird die Anzahl der qualifizierenden Ergebnistupel auf die Gesamtzahl der möglichen Kombinationen im Kreuzprodukt bezogen:
sel_BC = |B ⋈ C| / |B × C| = |B ⋈ C| / (|B| · |C|)
Typische SQL-Beispiele
Eine Tabelle KUNDEN enthält 1000 Datensätze. Die Abfrage „select * from kunden“ besitzt keine Selektionsbedingung und filtert nichts aus. Daher gilt sel = 1000 / 1000 = 1.
Bei „select * from kunden where id < 221“ passieren 220 Datensätze den Filter. Die Selektivität beträgt 220 / 1000 = 0,22. Dagegen liefert „select * from kunden where id > 1000“ eine leere Ergebnismenge; alle Datensätze werden ausgefiltert und die Selektivität ist 0 / 1000 = 0.
Entscheidend ist die Anzahl der Datensätze, die das Selektionsprädikat erfüllen, nicht unbedingt die Zahl der tatsächlich ausgegebenen Ergebniszeilen. Die Abfrage „select count(*) from kunden where id < 401“ gibt wegen der Aggregatfunktion count nur eine Ergebniszeile aus. Dennoch passieren 400 Datensätze den Filter, sodass die Selektivität 400 / 1000 = 0,4 beträgt.
Bei „where id = 300“ wird genau einer von 1000 Datensätzen ermittelt: sel = 1 / 1000 = 0,001. Bei „where name = 'Maier'“ können mehrere Datensätze passen. Gibt es fünf Kunden dieses Namens, beträgt die Selektivität 5 / 1000 = 0,005.
Abschätzung durch das Datenbanksystem
Viele Datenbankmanagementsysteme (DBMS) verwenden einen kostenbasierten Anfrageoptimierer. Er schätzt unter anderem die Selektivität der einzelnen Prädikate, um eine möglichst günstige Zugriffsstrategie für eine Abfrage zu wählen. Eine exakte Bestimmung wäre häufig zu aufwendig. Deshalb nutzt der Optimierer statistische Daten, beispielsweise die Gesamtzeilenzahl einer Tabelle, die Anzahl unterschiedlicher Werte in einer Spalte, die als Kardinalität bezeichnet wird, und die Anzahl der NULL-Werte.
Für ein Prädikat der Form „Spalte = Wert“ kann die Selektivität als sel = 1 / c geschätzt werden, wenn c die bekannte Kardinalität der Spalte ist. Diese Schätzung ist korrekt, wenn die Werte der Spalte gleichmäßig verteilt sind.
Für zusammengesetzte oder negierte Bedingungen können aus den geschätzten Einzelselektivitäten sel₁ und sel₂ weitere Schätzungen gebildet werden:
• Konjunktion mit AND: sel(P₁ AND P₂) = sel₁ · sel₂
• Disjunktion mit OR: sel(P₁ OR P₂) = sel₁ + sel₂ − sel₁ · sel₂. Der letzte Term zieht die Schnittmenge ab, damit sie nicht doppelt gezählt wird.
• Negation mit NOT: sel(NOT P₁) = 1 − sel₁
Starke und schwache Selektivität
Eine hohe Selektivität nahe oder gleich 1 heißt schwache Selektivität: Sehr viele Datensätze erfüllen die Bedingung, sodass nur wenige ausgefiltert werden. Eine niedrige Selektivität nahe oder gleich 0 heißt starke Selektivität: Nur wenige Datensätze erfüllen die Bedingung. Die Grenze zwischen beiden Kategorien ist fließend.
Diese Unterscheidung ist wichtig, weil die Datenbank für eine gute Leistung möglichst wenige Datenblöcke von der Festplatte lesen soll. Bei schwacher Selektivität ist meistens ein Full Table Scan, also das vollständige Durchsuchen der Tabelle, am effizientesten. Da ohnehin ein großer Teil der Datensätze benötigt wird, müssen sehr viele Datenblöcke gelesen werden. Zusätzliche Zugriffe auf die Blöcke eines Datenbankindexes würden dann unnötigen Aufwand verursachen. Enthält ein Index in einem Spezialfall alle abgefragten Daten, kann stattdessen ein Full Index Scan verwendet werden.
Bei starker Selektivität ist der Zugriff über einen passenden Datenbankindex meist günstiger. Erfüllt beispielsweise nur ein Datensatz das Prädikat, wäre das Einlesen aller Tabellenblöcke ineffizient. Beim Indexzugriff müssen nur wenige Indexblöcke sowie der Tabellenblock mit dem gesuchten Datensatz gelesen werden.
Der Anfrageoptimierer schätzt deshalb für jede Abfrage die Selektivität und wählt darauf aufbauend eine Zugriffsmethode. Softwareentwickler und Datenbankadministratoren berücksichtigen außerdem Selektivität und Häufigkeit von Abfragen, wenn sie entscheiden, welche Indexe angelegt werden sollen.
