MySQL: Gefangen im Nested Loop

In den letzten Wochen habe ich mich endlich mal ein wenig mit der Arbeitsweise von MySQL beschäftigt und dabei ein paar ganz interessante Dinge herausbekommen - und auch ein paar Überraschungen erlebt. Die größte Überraschung dabei war, dass MySQL Join-Operationen mit erstaunlicher Einfallslosigkeit durchführt: jeder Join ist ein Nested Loop. Ich konnte mir das zunächst nicht so recht vorstellen: was passiert denn dann beim Join großer Datenmengen, wenn man nur den NL-Join zur Verfügung hat und weder MERGE JOIN noch HASH JOIN, also nur ein Verfahren, das sehr gut für Zugriffe mit hoher Selektivität geeignet ist und erste Ergebnisse rasch zurückliefert, aber mit Massendaten wenig Freude bereitet? Die Antwort lautet: man wartet.

Dazu ein kleiner Test, der nicht so ganz fair ist, weil er die unterschiedliche Konfiguration der Datenbanken nicht berücksichtigt und außerdem einen Fall konstruiert, bei dem MySQL dumm aussehen muss. Dabei lege ich zwei Tabellen mit identischen Inhalten an, die jeweils 32 mal die Menge der Zahlen von 1 bis 1000 und eine zusätzliche Füll-Spalte enthalten:

-- Oracle 11.1.0.7
-- Windows 7
drop table t1;
drop table t2;

create table t1
as
with 
generator1
as (
select rownum col1
     , lpad('*', 100, '*') col2
  from dual
connect by level <= 1000)
,
generator2
as (
select rownum id
  from dual 
connect by level <= 32)
select generator1.*
  from generator1
     , generator2
 order by generator2.id
        , generator1.col1;
        
create table t2
as
select * from t1;        
        
exec dbms_stats.gather_table_stats(user, 'T1')        
exec dbms_stats.gather_table_stats(user, 'T2')

explain plan for
select count(*)
  from t1, t2
 where t1.col1 = t2.col1;

select count(*)
  from t1, t2
 where t1.col1 = t2.col1;

Oracle findet diese Aufgabe ziemlich banal und liefert folgende Ergebnisse:

PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------
Plan hash value: 906334482

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |     8 |   286   (3)| 00:00:04 |
|   1 |  SORT AGGREGATE     |      |     1 |     8 |            |          |
|*  2 |   HASH JOIN         |      |  1024K|  8000K|   286   (3)| 00:00:04 |
|   3 |    TABLE ACCESS FULL| T1   | 32000 |   125K|   140   (1)| 00:00:02 |
|   4 |    TABLE ACCESS FULL| T2   | 32000 |   125K|   140   (1)| 00:00:02 |
----------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("T1"."COL1"="T2"."COL1")

SQL> select count(*)
  2    from t1, t2
  3   where t1.col1 = t2.col1;

  COUNT(*)
----------
   1024000

Abgelaufen: 00:00:00.08

Angesichts des Fehlens von Indizes wird daraus ein HASH JOIN, dessen cardinality-Schätzungen völlig akkurat sind, was angesichts der Harmlosigkeit der Query nicht weiter überrascht. Nun der gleiche Fall mit MySQL - wobei dort kein dem connect by dual Verfahren entsprechender Generator zur Verfügung steht (und auch keine CTEs), so dass der Aufbau mit traditionelleren Techniken (mit einer Tabelle, die über eine gewisse Anzahl von Datensätzen verfügt) erfolgen muss:

-- MySQL 5.6.10
-- Windows 7
-- Tabellen-Engine: InnoDB

use world;

drop table t1;
drop table t2;

set @NUM = 0;

create table t1
select @NUM:=@NUM+1 col1
     , repeat('*', 100) col2
  from city t 
 limit 1000;

insert into t1
select * from t1;

insert into t1
select * from t1;

insert into t1
select * from t1;

insert into t1
select * from t1;

insert into t1
select * from t1;

create table t2
select * from t1;

explain
select count(*)
  from t1, t2
 where t1.col1 = t2.col1;

select count(*)
  from t1, t2
 where t1.col1 = t2.col1;

Das Parsing macht MySQL dabei keine Schwierigkeiten; möglicherweise hätte ich eine explizite Statistikerfassung durchführen sollen, aber die 31808 sind ja schon recht nah am korrekten Ergebnis - für den Plan hätte es aber ohnehin keinen Unterschied gemacht, denn eine andere Lösung hat die Engine nicht:

mysql> explain select count(*)  from t1, t2 where t1.col1 = t2.col1;
+----+-------------+-------+------+---------------+------+---------+------+-------+----------------------------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows  | Extra                                              |
+----+-------------+-------+------+---------------+------+---------+------+-------+----------------------------------------------------+
|  1 | SIMPLE      | t1    | ALL  | NULL          | NULL | NULL    | NULL | 31808 | NULL                                               |
|  1 | SIMPLE      | t2    | ALL  | NULL          | NULL | NULL    | NULL | 31808 | Using where; Using join buffer (Block Nested Loop) |
+----+-------------+-------+------+---------------+------+---------+------+-------+----------------------------------------------------+
2 rows in set (0.00 sec)

mysql> select count(*)  from t1, t2 where t1.col1 = t2.col1;
+----------+
| count(*) |
+----------+
|  1024000 |
+----------+
1 row in set (41.63 sec)

Also 0,08 sec. für Oracle und 41,63 sec. für MySQL - wie gesagt: es ist kein ganz fairer Vergleich, aber man sieht doch recht deutlich, dass MySQL für Join-Operationen dieser Art nicht ausgesprochen gut geeignet ist. Die Engine liest hier jeden Datensatz aus T1 und führt dazu dann eine Lookup-Leseoperation in T2 durch. Und da T2 für diesen Lookup keinen unterstützenden Index anbieten kann, werden das dann insgesamt 32001 Full Table Scans (im Plan: type = ALL). In den Statistiken der Session (information_schema.session_status) lässt sich diese Arbeit nicht so recht ablesen - immerhin erhöhen sich die Werte für SLOW_QUERIES (laut Doku: "The number of queries that have taken more than long_query_time seconds"), SELECT_SCAN ("The number of joins that did a full scan of the first table.") und SELECT_FULL_JOIN ("The number of joins that perform table scans because they do not use indexes. If this value is not 0, you should carefully check the indexes of your tables."). Offensichtlich hält MySQL das Fehlen von Indizes in einem solchen Fall für ein ernstes Versäumnis. Hier also der Index zur Unterstützung des Joins:

-- MySQL
create index t2_idx on t2(col1);

mysql> explain select count(*)  from t1, t2 where t1.col1 = t2.col1;
+----+-------------+-------+------+---------------+--------+---------+---------------+-------+-------------+
| id | select_type | table | type | possible_keys | key    | key_len | ref           | rows  | Extra       |
+----+-------------+-------+------+---------------+--------+---------+---------------+-------+-------------+
|  1 | SIMPLE      | t1    | ALL  | NULL          | NULL   | NULL    | NULL          | 31808 | Using where |
|  1 | SIMPLE      | t2    | ref  | t2_idx        | t2_idx | 9       | world.t1.col1 |    16 | Using index |
+----+-------------+-------+------+---------------+--------+---------+---------------+-------+-------------+
2 rows in set (0.00 sec)

mysql> select count(*)  from t1, t2 where t1.col1 = t2.col1;
+----------+
| count(*) |
+----------+
|  1024000 |
+----------+
1 row in set (0.41 sec)

Mit 32000 Index-Lookups schafft MySQL den Join also in 0,41 sec. Das ist natürlich eine Verbesserung, aber ein HASH JOIN wäre hier immer noch geeigneter, was nicht nur meine, sondern auch die Meinung des CBO im Oracle-Fall ist:

-- Oracle
create index t2_idx on t2(col1);

PLAN_TABLE_OUTPUT
---------------------------------------------------------------------------------
Plan hash value: 1807176592

---------------------------------------------------------------------------------
| Id  | Operation              | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------
|   0 | SELECT STATEMENT       |        |     1 |     8 |   167   (5)| 00:00:03 |
|   1 |  SORT AGGREGATE        |        |     1 |     8 |            |          |
|*  2 |   HASH JOIN            |        |  1024K|  8000K|   167   (5)| 00:00:03 |
|   3 |    TABLE ACCESS FULL   | T1     | 32000 |   125K|   140   (1)| 00:00:02 |
|   4 |    INDEX FAST FULL SCAN| T2_IDX | 32000 |   125K|    20   (0)| 00:00:01 |
---------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("T1"."COL1"="T2"."COL1")

Im Oracle-Fall wird aus dem FULL TABLE SCAN also ein INDEX FAST FULL SCAN, weil T2_IDX deutlich kleiner ist als T2. Um Oracle vom NL-Join zu überzeugen, muss ein USE_NL-Hint verwendet werden. In diesem Fall steigen aber die logischen Lesezugriffe (consistent gets) von 569 für den HASH JOIN auf 15486 für den NESTED LOOPS.

Auf meinen Merkzettel kommt jedenfalls die Erkenntnis, dass ich im MySQL-Kontext auf große Join-Operationen lieber verzichten sollte, bis dort HASH JOIN-Operationen möglich sind - was dann möglicherweise ad calendas graecas bedeuten mag... In Maria-DB 5.5 ist der HASH JOIN übrigens impelmentiert, wie ich bei Ovais Tariq gelesen habe, der eine sehr solide wirkende Analyse aktueller MySQL- und MariaDB-Join-Verfahren liefert.

P.S.: Ursprünglich wollte ich drüber schreiben: "To HASH and HASH Not" nach der schönen Howard Hawks Verfilmung des entsprechenden Hemingway-Romans mit Humphrey Bogart und Loren Bacall, aber dann erinnerte ich mich daran, dass ich eigentlich inhaltlich halbwegs plausible Überschriften wählen wollte, um das vorgestellte Publikum (und mich) nicht zu desorientieren. Jetzt ist der Titel dafür dann klassische B-Film-Benennung.