MySQL Zeilengenerator

Ein Zeilengenerator ist eine Methode um Zeilen nach Bedarf zu erzeugen. Zeilengeneratoren können mit reinem Standard SQL und rekursiven common table expressions (CTE bzw. die with-Klausel) umgesetzt werden. Falls du noch nie etwas von der with-Klausel gehört hast, liegt das bestimmt daran, dass MySQL diesen Teil des SQL-99 Standards nicht unterstützt (feature Anfrage aus 2006). Dieser Artikel stellt eine Sammlung von Zeilengenerator views für MySQL vor. Nicht so leistungsfähig wie CTEs, aber gut genug für die meisten Fälle. Aber bevor wir uns die Implementierung ansehen, werde ich erst einmal zeigen, wofür man Zeilengeneratoren überhaupt benutzt.

Zeilengeneratoren sind praktisch um Lücken in Ergebnissen zu füllen. Zum Beispiel im folgenden Fall:

SELECT COUNT(*), sale_date
  FROM sales
 WHERE sale_date > CURDATE() - INTERVAL 1 MONTH
 GROUP BY sale_date
 ORDER BY sale_date;

Das Ergebnis wird keine Zeilen für Tage ohne SALES Einträge beinhalten. Diese können jedoch mit einem Zeilengenerator ergänzt werden.

Stell dir einen view vor, GENERATOR, der nummerierte Zeilen liefert:

SELECT n
  FROM generator
 WHERE n < 31;

+-----+
|  n  |
+-----+
|   0 | 
|   1 | 
. . . .
|  29 | 
|  30 | 
+-----+
31 rows in set (0.00 sec)

Das ist die Grundfunktion eines Zeilengenerators. Damit lässt sich leicht eine Abfrage bauen die alle Tage seit einem Monat liefert:

SELECT CURDATE() - INTERVAL n DAY dt
  FROM generator
 WHERE CURDATE() - INTERVAL n DAY 
     > CURDATE() - INTERVAL 1 MONTH;

+------------+
| dt         |
+------------+
| 2011-07-29 | 
| 2011-07-28 | 
. . . . . . . 
| 2011-07-01 |
| 2011-06-30 | 
+------------+
30 rows in set (0.00 sec)

Diese Liste kann mittels eines OUTER JOINs mit dem ursprünglichen Ergebnis verbunden werden:

SELECT IFNULL(sales, 0) sales, dt sale_date
  FROM
     ( SELECT CURDATE() - INTERVAL n DAY dt
         FROM generator
        WHERE CURDATE() - INTERVAL n DAY 
            > CURDATE() - INTERVAL 1 MONTH
     ) dates
  LEFT OUTER JOIN
     ( SELECT COUNT(*) sales, sale_date
         FROM sales
        WHERE sale_date > CURDATE() - INTERVAL 1 MONTH
        GROUP BY sale_date
     ) sales
    ON (sales.sale_date = dates.dt)
 ORDER BY dt;

Die linke Seite der join Operation beinhaltet alle Tage im fraglichen Zeitraum. Tage, zu denen es keinen SALES Eintrag gibt, werden mit NULL ergänzt. Daher wird IFNULL verwendet, um die Zahl „0“ für diese Tage zu erhalten.

So weit, so gut. Das Problem ist nur, dass es in MySQL keine Möglichkeit gibt, einen solchen GENERTOR view zu bauen. Dennoch gibt es eine Möglichkeit einen view zu bauen, der in den meisten Fällen gut genug ist.

Es beginnt mit etwas ziemlich Lächerlichem:

CREATE OR REPLACE VIEW generator_16
AS SELECT 0 n UNION ALL SELECT 1  UNION ALL SELECT 2  UNION ALL 
   SELECT 3   UNION ALL SELECT 4  UNION ALL SELECT 5  UNION ALL
   SELECT 6   UNION ALL SELECT 7  UNION ALL SELECT 8  UNION ALL
   SELECT 9   UNION ALL SELECT 10 UNION ALL SELECT 11 UNION ALL
   SELECT 12  UNION ALL SELECT 13 UNION ALL SELECT 14 UNION ALL 
   SELECT 15;

Es ist ein Zeilengenerator für 16 Zeilen. Dieselbe Methode kann benutzt werden, um größere Generatoren zu bauen. Zum Beispiel um eine Million Zeilen zu generieren – wie am Ende des Artikels zu sehen ist. Naja, nicht wirklich. Es gibt natürlich einen besseren Weg:

CREATE OR REPLACE VIEW generator_256
AS SELECT ( hi.n * 16 + lo.n ) AS n
     FROM generator_16 lo
        , generator_16 hi;

Der view verwendet einen cross join um das kartesische Produkt des vorherigen views mit sich selbst zu bilden. Alle Werte der „lo“ Seite werden jedem Wert der „hi“ Seite zugeordnet („jeder mit jedem“). Das Ergebnis hat daher 256 Zeilen (16x16).

Es genügt aber nicht einfach nur Zeilen zu generieren, man braucht nummerierte Zeilen um den Zeilengerator wie oben beschrieben zu benutzen.

Daher betrachte ich die beiden Seiten des cross joins als Ziffern einer hexadezimalen Zahl. Die „lo“ Seite stellt dabei die Ziffer mit geringerer Wertigkeit dar, die „hi“ Seite die Ziffer mir höherer Wertigkeit. Die Berechnung kann man mit SQL erklären:

SELECT CONCAT(LPAD(hi.n,2,' '), ' * 16 + '
            , LPAD(lo.n,2,' '), ' = '
            , LPAD(hi.n*16+lo.n, 3,' '))
              AS "HI        LO   SEQ"
  FROM generator_16 lo, generator_16 hi;

+--------------------+
| HI        LO   SEQ |
+--------------------+
|  0 * 16 +  0 =   0 | 
|  0 * 16 +  1 =   1 | 
|  0 * 16 +  2 =   2 | 
|  0 * 16 +  3 =   3 | 
|  0 * 16 +  4 =   4 | 
|  0 * 16 +  5 =   5 | 
|  0 * 16 +  6 =   6 | 
|  0 * 16 +  7 =   7 | 
|  0 * 16 +  8 =   8 | 
|  0 * 16 +  9 =   9 | 
|  0 * 16 + 10 =  10 | 
|  0 * 16 + 11 =  11 | 
|  0 * 16 + 12 =  12 | 
|  0 * 16 + 13 =  13 | 
|  0 * 16 + 14 =  14 | 
|  0 * 16 + 15 =  15 | 
|  1 * 16 +  0 =  16 | 
|  1 * 16 +  1 =  17 | 
. . . . . . . . . . .
| 15 * 16 + 14 = 254 | 
| 15 * 16 + 15 = 255 | 
+--------------------+
256 rows in set (0.00 sec)

I glaube, du weißt jetzt auch, wie man größere Generatoren baut?

Diese Methode hat natürlich auch Einschränkungen:

• Die views sind begrenzt

  Sie können keine beliebige Zeilenzahl erzeugen. Es ist aber möglich, beliebig große Generatoren vorzubereiten (siehe unten).

• Die views bilden immer das volle kartesische Produkt

  Es ist zwar möglich den view durch eine where-Klausel einzuschränken, dennoch werden alle Zeilen erzeugt. Nur werden eben Überflüssige gefiltert. Es ist daher ineffizient einen großen Generator zu verwenden, wenn man nur weinige Zeilen benötigt.

Eine andere Eigenschaft dieser Methode ist, dass die Zeilen in undefinierter Reihenfolge erzeugt werden. Es scheint zwar oben so als würden die Zahlen in aufsteigender Reihenfolge erzeugt werden, das ist jedoch nur aufgrund des nested-loops join Algorithmus der Fall. Wenn man einen weiteren meta-view erstellt, z.b. GENERATOR_64k, sieht man, dass der Block Nested-Loops join Algorithmus zuschlägt, und die Reihenfolge nicht mehr aufsteigend ist. Das bedeutet aber nicht, dass der Generator nicht funktioniert. Es wird noch immer jede Nummer genau einmal geliefert. Wenn man eine bestimmte Reihenfolge benötigt, muss man einfach ein ORDER BY im äußersten select machen.

Zum Schluss noch ein paar nützlicher Generatoren bis zu einer „Mega-Zeile“. Die einzige Änderung ist, dass anstatt arithmetischer Operatoren Bitoperationen verwendet werden.

CREATE OR REPLACE VIEW generator_16
AS SELECT 0 n UNION ALL SELECT 1  UNION ALL SELECT 2  UNION ALL 
   SELECT 3   UNION ALL SELECT 4  UNION ALL SELECT 5  UNION ALL
   SELECT 6   UNION ALL SELECT 7  UNION ALL SELECT 8  UNION ALL
   SELECT 9   UNION ALL SELECT 10 UNION ALL SELECT 11 UNION ALL
   SELECT 12  UNION ALL SELECT 13 UNION ALL SELECT 14 UNION ALL 
   SELECT 15;

CREATE OR REPLACE VIEW generator_256
AS SELECT ( ( hi.n << 4 ) | lo.n ) AS n
     FROM generator_16 lo, generator_16 hi;

CREATE OR REPLACE VIEW generator_4k
AS SELECT ( ( hi.n << 8 ) | lo.n ) AS n
     FROM generator_256 lo, generator_16 hi;

CREATE OR REPLACE VIEW generator_64k
AS SELECT ( ( hi.n << 8 ) | lo.n ) AS n
     FROM generator_256 lo, generator_256 hi;

CREATE OR REPLACE VIEW generator_1m
AS SELECT ( ( hi.n << 16 ) | lo.n ) AS n
     FROM generator_64k lo, generator_16 hi;

Sogar der letzte view, der 2²⁰ Zeilen erzeugt, liefert sein Ergebnis in einer Sekunde. Zeilengeneratoren diese Größe benutze ich ohnehin nur, um Testdaten zu erzeugen.