Optimierung der Histogrammbalancierung zwischen Optimalität und Praktikabilität zur Schätzung der Größe von Abfrageergebnissen

Viele aktuelle Datenbanksysteme verwenden Histogramme, um die Häufigkeitsverteilung von Werten in den Attributen von Relationen zu approximieren und darauf basierend die Größen von Abfrageergebnissen und die Kosten von Zugriffsplänen zu schätzen. Bei der Auswahl zwischen den verschiedenen Histogrammen muss man ein Gleichgewicht zwischen zwei sich widersprechenden Zielen finden: Optimalität, damit die erzeugten Schätzungen den geringsten Fehler aufweisen, und Praktikabilität, damit Histogramme effizient erstellt und gepflegt werden können. In diesem Papier präsentieren wir sowohl theoretische als auch experimentelle Ergebnisse zu mehreren Fragen im Zusammenhang mit diesem Kompromiss. Unser Gesamtergebnis ist, dass der effektivste Ansatz darin besteht, sich auf die Klasse von Histogrammen zu konzentrieren, die die Häufigkeiten von wenigen Attributwerten genau beibehalten und für die übrigen eine gleichmäßige Verteilung annehmen, und für jede Relation das Histogramm in dieser Klasse auszuwählen, das für eine Selbstverknüpfungsabfrage optimal ist.