SQLreduce: Große SQL-Queries auf Minimum reduzieren

Entwicklern begegnen oft große SQL-Queries, die einen Fehler werfen. SQLreduce ist ein Tool, mit dem diese Komplexität auf eine minimale Query reduziert wird.

SQLsmith generiert zufällige SQL-Queries

SQLsmith ist ein Tool, das zufällige SQL-Queries generiert und diese gegen einen PostgreSQL-Server laufen lässt (und andere DBMS-Typen). Die Idee ist, dass im Query-Parser und -Executor mit Fuzz-Testing Corner-Case-Bugs gefunden werden können, die mit manuellen Testen oder der festen Menge an Queries aus der PostgreSQL-Regression-Testsuite nicht gefunden worden wären. Es hat sich als effektives Tool bewährt, das seit 2015 über 100 Bugs in verschiedenen Teilen des PostgreSQL-Servers und anderen Produkten gefunden hat, darunter Security-Bugs, von Executor-Bugs bis zu Segfaults in Typ- und Index-Methoden.

2018 fand SQLsmith beispielsweise, dass die folgende Query einen Segfault in PostgreSQL verursacht:

select
  case when pg_catalog.lastval() < pg_catalog.pg_stat_get_bgwriter_maxwritten_clean() then case when pg_catalog.circle_sub_pt(
          cast(cast(null as circle) as circle),
          cast((select location from public.emp limit 1 offset 13)
             as point)) ~ cast(nullif(case when cast(null as box) &> (select boxcol from public.brintest limit 1 offset 2)
                 then (select f1 from public.circle_tbl limit 1 offset 4)
               else (select f1 from public.circle_tbl limit 1 offset 4)
               end,
          case when (select pg_catalog.max(class) from public.f_star)
                 ~~ ref_0.c then cast(null as circle) else cast(null as circle) end
            ) as circle) then ref_0.a else ref_0.a end
       else case when pg_catalog.circle_sub_pt(
          cast(cast(null as circle) as circle),
          cast((select location from public.emp limit 1 offset 13)
             as point)) ~ cast(nullif(case when cast(null as box) &> (select boxcol from public.brintest limit 1 offset 2)
                 then (select f1 from public.circle_tbl limit 1 offset 4)
               else (select f1 from public.circle_tbl limit 1 offset 4)
               end,
          case when (select pg_catalog.max(class) from public.f_star)
                 ~~ ref_0.c then cast(null as circle) else cast(null as circle) end
            ) as circle) then ref_0.a else ref_0.a end
       end as c0,
  case when (select intervalcol from public.brintest limit 1 offset 1)
         >= cast(null as "interval") then case when ((select pg_catalog.max(roomno) from public.room)
             !~~ ref_0.c)
        and (cast(null as xid) <> 100) then ref_0.b else ref_0.b end
       else case when ((select pg_catalog.max(roomno) from public.room)
             !~~ ref_0.c)
        and (cast(null as xid) <> 100) then ref_0.b else ref_0.b end
       end as c1,
  ref_0.a as c2,
  (select a from public.idxpart1 limit 1 offset 5) as c3,
  ref_0.b as c4,
    pg_catalog.stddev(
      cast((select pg_catalog.sum(float4col) from public.brintest)
         as float4)) over (partition by ref_0.a,ref_0.b,ref_0.c order by ref_0.b) as c5,
  cast(nullif(ref_0.b, ref_0.a) as int4) as c6, ref_0.b as c7, ref_0.c as c8
from
  public.mlparted3 as ref_0
where true;

Allerdings sind die zufälligen Queries von SQLsmith wie in diesem 40-Zeilen, 2,2kB Beispiel oft sehr groß und enthalten viel Rauschen, das zum eigentlichen Fehler nicht beiträgt. Bisher musste die Query manuell inspiziert und aufwändig bearbeitet werden, um das Beispiel auf einen minimalen Reproducer zu reduzieren, der von Entwicklern benutzt werden kann, das Problem zu beheben.

Komplexität reduzieren mit SQLreduce

Dieses Problem wird von SQLreduce gelöst. SQLreduce nimmt eine beliebige SQL-Query als Eingabe und lässt sie gegen einen PostgreSQL-Server laufen. Verschiedene Vereinfachungsschritte werden angewandt und nach jedem Schritt überprüft, ob die vereinfachte Query immer noch den gleichen Fehler im PostgreSQL-Server verursacht. Das Endergebnis ist eine Query mit minimaler Komplexität.

SQLreduce kann die Queries aus den Original-Bugreports von SQLsmith effektiv auf Queries reduzieren, die manuell reduzierten Queries gleichen. Beispielsweise kann SQLreduce die riesen Query von oben auf diese Zeile reduzieren:

SELECT pg_catalog.stddev(NULL) OVER () AS c5 FROM public.mlparted3 AS ref_0

Dabei versucht SQLreduce nicht, eine Query zu erzeugen, die semantisch identisch zum Original ist, oder das gleiche Query-Ergebnis liefert. Die Eingabequery ist sowieso fehlerbehaftet, und es wird eine minimale Query gesucht, die die gleiche Fehlermeldung provoziert, wenn sie gegen PostgreSQL läuft. Sollte die Eingabequery keinen Fehler werfen, so findet SQLreduce einfach SELECT als minimale Query.

Wie es funktioniert

Wir benutzen eine einfachere Query, um zu zeigen, wie SQLreduce arbeitet, und welche Schritte genommen werden, um das Rauschen aus der Eingabe zu entfernen. Diese Query ist fehlerhaft und enthält einige Teile, die entfernt werden sollen:

$ psql -c 'select pg_database.reltuples / 1000 from pg_database, pg_class where 0 < pg_database.reltuples / 1000 order by 1 desc limit 10'
ERROR:  column pg_database.reltuples does not exist

Wir geben die Query an SQLreduce:

$ sqlreduce 'select pg_database.reltuples / 1000 from pg_database, pg_class where 0 < pg_database.reltuples / 1000 order by 1 desc limit 10'

SQLreduce parst die Eingabe mit pglast und libpg_query, die den original PostgreSQL-Parse als Bibliothek mit Python-Bindings bereitstellen. Das Ergebnis ist ein Parsetree, der die Basis für die nächsten Schritte bildet. Der Parsetree sieht so aus:

selectStmt
├── targetList
│   └── /
│       ├── pg_database.reltuples
│       └── 1000
├── fromClause
│   ├── pg_database
│   └── pg_class
├── whereClause
│   └── <
│       ├── 0
│       └── /
│           ├── pg_database.reltuples
│           └── 1000
├── orderClause
│   └── 1
└── limitCount
    └── 10

Pglast enthält außerdem einen Query-Renderer, der den Parsetree wieder in SQL übersetzen kann, unten als regenerierte Query gezeigt. Die Eingabequery wird mit PostgreSQL ausgeführt, um das Ergebnis zu erhalten, in diesem Fall ERROR: column pg_database.reltuples does not exist.

Input query: select pg_database.reltuples / 1000 from pg_database, pg_class where 0 < pg_database.reltuples / 1000 order by 1 desc limit 10
Regenerated: SELECT pg_database.reltuples / 1000 FROM pg_database, pg_class WHERE 0 < ((pg_database.reltuples / 1000)) ORDER BY 1 DESC LIMIT 10
Query returns: ✔ ERROR:  column pg_database.reltuples does not exist

SQLreduce erzeugt neue Parsetrees, die strukturell einfacher sind, generiert davon SQL, und lässt diese Queries mit PostgreSQL laufen. Die ersten Vereinfachungsschritte passieren auf dem Toplevel-Knoten, wo SQLreduce versucht, ganze Teilbäume zu entfernen, um schnell zu Ergebnissen zu kommen. Der erste Reduktions-Versuch ist, LIMIT 10 zu entfernen:

SELECT pg_database.reltuples / 1000 FROM pg_database, pg_class WHERE 0 < ((pg_database.reltuples / 1000)) ORDER BY 1 DESC ✔

Das Query-Ergebnis ist immer noch ERROR: column pg_database.reltuples does not exist, angezeigt durch ein ✔ Häkchen. Als nächstes wird ORDER BY 1 entfernt, wiederum erfolgreich:

SELECT pg_database.reltuples / 1000 FROM pg_database, pg_class WHERE 0 < ((pg_database.reltuples / 1000)) ✔

Nun wird die gesamte Target-Liste entfernt:

SELECT FROM pg_database, pg_class WHERE 0 < ((pg_database.reltuples / 1000)) ✔

Bezogen auf die Fehlermeldung von PostgreSQL ist diese kürzere Query immer noch äquivalent zur Original-Query. Nun wird der erste nicht erfolgreiche Reduktionsschritt versucht, das Entfernen der FROM-Klausel:

SELECT WHERE 0 < ((pg_database.reltuples / 1000)) ✘ ERROR:  missing FROM-clause entry for table "pg_database"

Diese Query ist ebenfalls fehlerhaft, aber verursacht eine andere Fehlermeldung, daher wird der bisherige Parsetree beibehalten. Wiederrum wird ein ganzer Teilbaum entfernt, diesmal die WHERE-Klausel:

SELECT FROM pg_database, pg_class ✘ no error

Wir haben die Eingabe nun so weit reduziert, dass gar kein Fehler mehr entsteht. Der bisherige Parsetree wird weiter beibehalten. Er sieht nun so aus:

selectStmt
├── fromClause
│   ├── pg_database
│   └── pg_class
└── whereClause
    └── <
        ├── 0
        └── /
            ├── pg_database.reltuples
            └── 1000

SQLreduce beginnt nun, in den Baum abzusteigen. In der FROM-Klausel sind mehrere Einträge, also versucht es, die Liste zu kürzen. Als erstes wird pg_database entfernt, was nicht funktioniert, also wird stattdessen pg_class entfernt:

SELECT FROM pg_class WHERE 0 < ((pg_database.reltuples / 1000)) ✘ ERROR:  missing FROM-clause entry for table "pg_database"
SELECT FROM pg_database WHERE 0 < ((pg_database.reltuples / 1000)) ✔

Da wir nun eine neue minimale Query gefunden haben, beginnt die Rekursion erneut beim Toplevel mit einem neuen Versuch, die WHERE-Klausel zu entfernen. Da das nicht funktioniert, versucht es, den Ausdruck durch NULL zu ersetzen, aber das funktioniert auch nicht:

SELECT FROM pg_database ✘ no error
SELECT FROM pg_database WHERE NULL ✘ no error

Nun wird eine neue Art von Schritt versucht: Expression Pull-Up. Wir steigen in die WHERE-Klausel ab, wo wir A < B zunächst durch A und dann durch B ersetzen:

SELECT FROM pg_database WHERE 0 ✘ ERROR:  argument of WHERE must be type boolean, not type integer
SELECT FROM pg_database WHERE pg_database.reltuples / 1000 ✔
SELECT WHERE pg_database.reltuples / 1000 ✘ ERROR:  missing FROM-clause entry for table "pg_database"

Der erste Versuch funktionierte nicht, aber der zweite. Da die Query vereinfacht wurde, beginnen wir erneut beim Toplevel mit einem Versuch, die FROM-Klausel zu entfernen, aber die wird weiterhin benötigt.

In A / B können wir nun A hochziehen:

SELECT FROM pg_database WHERE pg_database.reltuples ✔
SELECT WHERE pg_database.reltuples ✘ ERROR:  missing FROM-clause entry for table "pg_database"

SQLreduce hat die minimale Query gefunden, die immer noch ERROR: column pg_database.reltuples does not exist verursacht. Der Parsetree ist nun:

selectStmt
├── fromClause
│   └── pg_database
└── whereClause
    └── pg_database.reltuples

Am Ende des Laufs wird die Query mit ein paar Statistiken ausgedruckt:

Minimal query yielding the same error:
SELECT FROM pg_database WHERE pg_database.reltuples

Pretty-printed minimal query:
SELECT
FROM pg_database
WHERE pg_database.reltuples

Seen: 15 items, 915 Bytes
Iterations: 19
Runtime: 0.107 s, 139.7 q/s

Diese minimale Query kann nun benutzt werden, um den Bug in PostgreSQL oder der Anwendung zu fixen.

Über credativ

Die credativ GmbH ist ein herstellerunabhängiges Beratungs- und Dienstleistungsunternehmen mit Standort in Mönchengladbach. Mit über 22+ Jahren an Entwicklungs- und Dienstleistungserfahrung im Open Source Bereich, kann die credativ GmbH Sie mit einem beispiellosen und individuell konfigurierbaren Support professionell Begleiten und Sie in allen Fragen bei Ihrer Open Source Infrastruktur voll und ganz unterstützen.

Seit dem erfolgreichen Merger mit Instaclustr 2021 ist die credativ GmbH das europäische Hauptquartier der Instaclustr Gruppe und hilft Unternehmen bei der Realisierung eigener Applikationen im großen Umfang dank Managed-Plattform-Solutions für Open Source Technologien wie zum Beispiel Apache Cassandra®, Apache Kafka®, Apache Spark™, Redis™, OpenSearch™, Apache ZooKeeper™, PostgreSQL® und Cadence.
Instaclustr kombiniert eine komplette Dateninfrastruktur-Umgebung mit praktischer Expertise, Support und Consulting um eine kontinuierliche Leistung und Optimierung zu gewährleisten. Durch Beseitigung der Komplexität der Infrastruktur, wird es Unternehmen ermöglicht, ihre internen Entwicklungs- und Betriebsressourcen auf die Entwicklung innovativer kundenorientierter Anwendungen zu geringeren Kosten zu konzentrieren. Zu den Kunden von Instaclustr gehören einige der größten und innovativsten Fortune-500-Unternehmen.