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 $\sigma$ (kleines Sigma) bezeichnet und kann somit leicht mit dem Selektionsoperator der relationalen Algebra verwechselt werden, 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 $\sigma$ dieser Abfrage erfüllen. Seien nun

• $|\sigma _{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:

$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:

$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 Ergbnismenge keine Datensätze ausgefiltert werden, so dass die Kardinalität der Ergebnismenge und die der abgefragten Datenbnktabelle 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).

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 kategorieren 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.