Selektivität (Informatik)

Selektivität ist ein Maß, das in der Informatik bei Datenbankabfragen auf Datenbanktabellen in relationalen Datenbankensystemen gebraucht wird; sie bestimmt den Anteil der Datensätze, die bei einer Abfrage nicht durch eine Selektivitätsbedingung aus der Ergebnismenge ausgefiltert werden, relativ zur Gesamtzahl der Datensätze des Datenbestandes, welcher der Abfrage zugrunde liegt. Bei der am weitesten verbreiteten Abfragesprache für relationale Datenbanken, SQL, werden Selektivitätsbedingungen in der WHERE-Klausel der Abfrage spezifiziert.

Definition

Selektivität wird in der Literatur häufig mit σ (kleines Sigma) bezeichnet und kann somit leicht mit dem Selektionsoperator der relationalen Algebra verwechselt werden^[1], weshalb auch das Kürzel sel verwendet wird.

Formal bezeichnet die Selektivität den Anteil der qualifizierenden Tupel (Datensätze) einer Datenbanktabelle, die das Prädikat P (ein Vergleichsausdruck) der Selektion σ dieser Abfrage erfüllen. Seien nun

• | σ_P(A) | die Anzahl der Datensätze, die das Selektionsprädikat P einer Datenbankabfrage erfüllen und
• | A | die Anzahl der Datensätze der dieser Abfrage zugrunde liegenden Datenbanktabelle,

dann gilt folgende Formel zur Berechnung der Selektivität sel^[1]:

$sel_P = \dfrac{|\sigma_P(A)|}{|A|}$         

Bei einem Join zweier Datenbanktabellen B und C wird bei der Berechnung der Selektivität der Anteil der Tupel, die sich für die Ergebnismenge qualifizieren, relativ zur Gesamtzeichenzahl des Kreuzproduktes von B und C wiedergegeben^[1]:

$sel_{BC} = \dfrac{|B \bowtie C|}{|B \times C|} = \dfrac{|B \bowtie C|}{|B| \cdot |C|}$

Da ein Selektionsprädikat die Ergebnismenge gegenüber der abgefragten Datenmenge stets einschränkt, ist sel ein Wert zwischen 0 und 1, kann also als Prozentsatz derjenigen Datensätze, die bei einer Abfrage nicht durch eine Bedingung ausgefiltert werden, relativ zur Gesamtzahl der Datensätze des Datenbestandes, welcher der Abfrage zugrunde liegt, interpretiert werden.

Beispiele

Eine relationale Datenbank habe folgende Tabelle KUNDEN mit 1000 Einträgen:

ID	NAME
1	Müller
2	Schmitt
3	Schulz
...	...
999	Schneider
1000	Meier

Nun wird folgende Abfrage mit SQL gestellt:

 SELECT *
 FROM   kunden

In diesem Fall ist die Selektivität bei der obigen Abfrage gleich 1, da in der Abfrage keine Selektionsbedingung spezifiziert ist und von der zugrunde liegenden Datenbanktabelle bei der Generierung der Ergebnismenge keine Datensätze ausgefiltert werden, so dass die Kardinalität der Ergebnismenge und die der abgefragten Datenbanktabelle gleich sind:

$sel = \dfrac{|\sigma_P(KUNDE)|}{|KUNDE|} = \dfrac{1000}{1000} = 1$

Nun wird dieselbe Abfrage mit einer WHERE-Klausel ergänzt, die eine Selektivitätsbedingung darstellt, welche die Ergebnismenge durch Filtern der Datensätze in der abgefragten Tabelle einschränkt:

 SELECT *
 FROM   kunden
 WHERE  id < 221

220 Datensätze der Tabelle KUNDEN passieren den Filter dieser Abfrage; ihre Selektivität ist somit 0,22 (220 dividiert durch 1000).

Schließlich ist bei der Abfrage

  SELECT *
  FROM   kunden
  WHERE  id > 1000

die Ergebnismenge leer, das heißt, sämtliche Datensätze des zugrunde liegenden Datenbestandes werden mittels des Selektionsprädikats aus der Ergebnismenge ausgefiltert, so dass die Selektivität gleich 0 ist (0 dividiert durch 1000).

Die absolute Zahl der Datensätze in der von einer Abfrage generierten Ergebnismenge spielt bei der Bestimmung der Selektivität im Allgemeinen keine Rolle, wie die folgende Abfrage zeigt:

  SELECT COUNT(*)
  FROM   kunden
  WHERE  id < 401

Hier wird von der Abfrage aufgrund der Aggregierung durch die SQL-Funktion count nur ein Datensatz als Ergebnis generiert, die Selektivität der Abfrage ist aber 0,4 (400 Datensätze passieren den Filter des Selektionsprädikats und 400 dividiert durch 1000 ist 0,4).

  SELECT *
  FROM   kunden
  WHERE  id = 300

Das Prädikat ID = 300 hat eine Selektivität von 1 / 1000 = 0,001, da nur ein Satz von den 1000 vorhandenen Sätzen der Tabelle ermittelt wird.

  SELECT *
  FROM   kunden
  WHERE  name = 'Maier'

Hier muss berücksichtigt werden, dass auch mehrere Kunden den Namen Maier tragen können. Wenn es 5 Kunden mit diesem Namen gibt, dann beträgt die Selektivität der Abfrage 5 / 1000 = 0,005.

Abschätzung der Selektivität bei DBMS

Viele Datenbankmanagementsysteme (DBMS) haben einen kostenbasierten Anfrageoptimierer, der versucht, zu einer Datenbankabfrage die optimale Zugriffsstrategie unter anderem anhand einer Abschätzung der Selektivität der einzelnen Prädikate der Abfrage zu finden. Die Selektivität wird vom Anfrageoptimierer, weil es zu aufwändig wäre, nicht exakt bestimmt, sondern nur anhand von statistischen Daten abgeschätzt. Zu den Statistiken, die von einem DBMS erhoben werden, zählen zum Beispiel Angaben über die Gesamtzeilenzahl einer Tabelle, über die Anzahl unterschiedlicher Werte in den Tabellenspalten (Kardinalität), Anzahl der NULL-Werte in einer Spalte, etc.

Bei einem Prädikat der Form Spalte = Wert kann − vorausgesetzt, dass in den Statistik-Daten die Kardinalität der betreffenden Spalte bekannt ist – die Selektivität dieses Prädikats mit $sel = \dfrac{1}{c}$ abgeschätzt werden, wobei c der Kardinalität der Spalte entspricht. Die Abschätzung der Selektivität ist in diesem Fall korrekt, falls eine Gleichverteilung der Werte in der betreffenden Spalte vorliegt.

Wenn mehrere einzelne Prädikate miteinander durch logische Operatoren verknüpft werden oder ein einzelnes Prädikat negiert wird, dann kann die Selektivität der gesamten Bedingung aus der Abschätzung der Selektivitäten der einzelnen Prädikate berechnet werden; seien dafür sel₁ die Selektivität des Prädikats P₁ und sel₂ die Selektivität des Prädikats P₂:

• Bei einer Verknüpfung der beiden Prädikate mittels einer AND-Verknüpfung (Konjunktion), kann die Selektivität der Verknüpfung durch Multiplikation der Einzel-Selektivitäten abgeschätzt werden:

$sel(P_1\;AND\;P_2) = sel_1 * sel_2$

• Bei einer OR-Verknüpfung (Disjunktion) kann die Selektivität der Verknüpfung durch Addition der Einzel-Selektivitäten abgeschätzt werden. Davon muss allerdings die Schnittmenge noch subtrahiert werden:

$sel(P_1\;OR\;P_2) = sel_1 + sel_2 - sel_1 * sel_2$

• Wird ein Prädikat mit NOT negiert, kann die Selektivität durch Subtrahieren der Selektivität von 1 abgeschätzt werden:

$sel(NOT\;P_1) = 1 - sel_1$

Starke vs. schwache Selektivität

Wenn die Selektivität hoch ist, das heißt, ihr Wert ist nahe oder gleich 1, dann spricht man von schwacher Selektivität; ist der Wert niedrig, das heißt nahe oder gleich 0, dann spricht man von starker Selektivität. Die Grenze zwischen starker und schwacher Selektivität ist fließend.

In der Praxis ist es für Softwareentwickler, Datenbankadministratoren und den Anfrageoptimierer eines Datenbanksystems notwendig, die Selektivität einer Abfrage in starke und schwache Selektivität kategorisieren zu können. Um eine gute Performance bei einer Abfrage zu erzielen, ist es wichtig, die Anzahl der Datenblöcke, die von der Festplatte gelesen werden, möglichst gering zu halten. Bei Abfragen mit starker Selektivität eignen sich andere Zugriffsmöglichkeiten auf die Daten der Festplatte als bei solchen mit schwacher Selektivität:

• Bei SQL-Abfragen mit schwacher Selektivität ist ein Scan der gesamten Tabelle (Full Table Scan) am effizientensten: da durch ein Selektionsprädikat nur wenige Datensätze der abgefragten Tabelle ausgefiltert werden, qualifizieren sich sehr viele Datensätze für die Ergebnismenge; das bedeutet, ein sehr großer Prozentsatz der Datenblöcke, welche die Datensätze der abgefragten Tabelle speichern, muss ohnehin von der Festplatte in den Hauptspeicher gelesen werden; das zusätzliche Lesen von Datenblöcken eines Datenbankindexes würde in diesem Fall einen unnötigen Overhead bedeuten. In Spezialfällen, wenn ein Datenbankindex alle Daten enthält, die abgefragt werden, kann anstatt eines Full Table Scans auch ein Full Index Scan vorgenommen werden.

• Bei SQL-Abfragen mit starker Selektivität greift man am besten mittels eines passenden Datenbankindexes auf die Daten zu. Wenn beispielsweise nur ein Datensatz der abgefragten Tabelle das Selektionsprädikat der Abfrage erfüllt, dann wäre es nicht effizient, alle Blöcke mit allen Datensätzen dieser Tabelle mittels eines Full Table Scans in den Hauptspeicher zu lesen. Stattdessen müssen bei einem Indexzugriff nur sehr wenige Blöcke gelesen werden, das heißt, einige wenige Indexblöcke und von abgefragten Tabelle nur derjenige Block, der den gesuchten Datensatz speichert.

Der Anfrageoptimierer versucht deshalb bei jeder Abfrage, deren Selektivität abzuschätzen und die optimale Zugriffsmethode auszuwählen. Entwickler und Datenbankadministratoren wiederum müssen mittels der Selektivität und Häufigkeit von Abfragen entscheiden, welche Indexe angelegt werden müssen, deren sich der Anfrageoptimierer bei der Ausführung der Abfrage dann bedienen kann.

Einzelnachweise

1. ↑ ^{a b c} Alfons Kemper, André Eickler:: Datenbanksysteme. Oldenbourg Verlag 2004, ISBN 3-486-25706-4, Seite 254