These Rows Are Made for Sorting and That's Just What We'll Do

Zusammenfassung

Sortieren gehört zu den am besten untersuchten Problemen der Informatik und ist eine zentrale Operation relationaler Datenbanksysteme. Trotzdem wurde wenig dazu veröffentlicht, wie sich ein effizienter relationaler Sortieroperator implementieren lässt. Diese Lücke wollen wir schließen. Mit Mikrobenchmarks untersuchen wir, wie sich relationale Daten für analytische Datenbanksysteme effizient sortieren lassen, und berücksichtigen dabei unterschiedliche Query-Execution-Engines sowie zeilen- und spaltenorientierte Datenformate. Wir zeigen, dass unabhängig von architektonischen Unterschieden zwischen Query-Engines das Sortieren von Zeilen fast immer effizienter ist als das Sortieren spaltenorientierter Daten – selbst wenn dafür die Daten von Spalten in Zeilen und zurück umgewandelt werden müssen. Effizientes Sortieren von Zeilen ist für Systeme mit interpretierter Execution Engine anspruchsvoll, weil das Interpretieren von Zeilen zur Laufzeit Overhead verursacht. Wir zeigen, dass sich dieser Overhead mit mehreren bestehenden Techniken überwinden lässt. Auf Grundlage unserer Ergebnisse implementieren wir einen stark optimierten zeilenbasierten Sortieransatz in DuckDB, dem Open-Source-In-Process-OLAP-DBMS mit vektorisierter interpretierter Query Engine. Wir vergleichen DuckDB mit vier analytischen Datenbanksystemen und stellen fest, dass DuckDBs Sortierimplementierung Query-Engines übertrifft, die in einem spaltenorientierten Format sortieren, und kompilierte Query-Engines erreicht oder übertrifft, die in einem zeilenorientierten Format sortieren.