SQL/SelectFürFortgeschrittene/SchwarzfahrtErkennung

Aufgabenstellung

In einer Fahrtentabelle sollen Schwarzfahrten festgestellt werden. Schwarzfahrten sind natürlich nicht in der Tabelle, sondern die Lücken zwischen zwei Fahrten, also wenn KM-Stand Fahrtende nicht der KM-Stand der Nachfolgefahrt (des gleichen Fahrzeugs) ist.

Spalten sind Fahrt-ID, Fahrzeugnr. v, Km bei Fahrtanfang/-ende: kmStart und kmEnd, Fahrtbeginn stime:

CREATE TABLE journey(id  int, v int, kmStart int, kmEnd int, stime date);
insert into journey values(11, 4711, 100, 110, '2012-06-01');
insert into journey values(12, 4711, 110, 120, '2012-06-02');
insert into journey values(13, 4711, 121, 130, '2012-06-03');
insert into journey values(14, 4711, 130, 140, '2012-06-04');
insert into journey values(15, 4711, 140, 150, '2012-06-05');

insert into journey values(21, 4444, 100, 110, '2012-06-01');
insert into journey values(22, 4444, 111, 120, '2012-06-02');
insert into journey values(23, 4444, 121, 130, '2012-06-03');
insert into journey values(24, 4444, 130, 140, '2012-07-04');
insert into journey values(25, 4444, 140, 150, '2012-07-05');

Lösung 1 (reine Lückensuche)

Relativ einfach ist die Suche nach Lücken:

Finde alle Fahrten, für die es keine andere Fahrt gibt, deren KM-Stand am Anfang gleich dem KM-Stand am Ende dieser Fahrt ist und die nicht die letzte Fahrt dieses Fahrzeugs ist:

select id, kmEnd, stime from journey j1
  where not exists (select id from journey j2
    where j1.v = j2.v and j1.kmEnd = j2.kmStart)
    and j1.stime <> (select max(stime) from journey j3
        where j3.v = j1.v)
   ;
| id   | kmEnd | stime       |
+------+-------+------------+
|   12 |   120 | 2012-06-02 |
|   21 |   110 | 2012-06-01 |
|   22 |   120 | 2012-06-02 |

Diese Suche ist effizient.

Lösung 2 (ohne Join, Info über Nachfolger)

Wir wollen aber auch was über die Schwarzfahrt wissen: wieviel KM. Dazu erweitern wir die Spaltenliste um eine Unterabfrage (sub select):

Der Nachfolger ist die jüngste (kleinste bzgl. Zeit) Fahrt mit gleicher Fahrzeugnummer, die älter (größer) als die Ausgangsfahrt ist.

select j1.id, j1.stime, j1.kmEnd,
  (select j4.kmStart from journey j4
    where j4.v = j1.v
      and j4.stime = (select min(stime) from journey j5
        where j5.stime > j1.stime and j5.v = j1.v)
  ) as next
from journey j1
  where not exists (select id from journey j2
    where j1.v = j2.v and j1.kmEnd = j2.kmStart)
    and j1.stime <> (select max(stime) from journey j3
        where j3.v = j1.v);

| id   | stime       | kmEnd | next |
+------+------------+-------+------+
|   12 | 2012-06-02 |   120 |  121 |
|   21 | 2012-06-01 |   110 |  111 |
|   22 | 2012-06-02 |   120 |  121 |

Hier kann es aber ein Problem geben: Wenn die Zeit nicht eindeutig ist, liefert die Unterabfrage mehr als ein Element, dann wird die gesamte Abfrage ungültig. Wir nehmen aus diesen Fahrten die mit der kleinsten Id:

select j1.id, j1.stime, j1.kmEnd,
  (select j4.kmStart from journey j4
    where j4.v = j1.v
      and j4.id = (select min(Id) from journey j5
         where j5.v = j1.v and j5.stime = (select min(stime) from journey j6
            where j6.stime > j1.stime and j6.v = j1.v)
         )
  ) as next
from journey j1
  where not exists (select id from journey j2
    where j1.v = j2.v and j1.kmEnd = j2.kmStart)
    and j1.stime <> (select max(stime) from journey j3
        where j3.v = j1.v);

Lösung 3 (Join)

Jetzt wollen wir aber auch alles über den Nachfolger der Schwarzfahrt wissen. Wir wollen wieder den eindeutigen Nachfolger:

 select j1.id, j1.v, j1.stime, j1.kmEnd, succ.kmStart, succ.id, succ.stime from journey j1, journey succ
  where j1.v = succ.v and j1.id <> succ.id
     and succ.id = (select min(id) from journey j2
        where j2.v = j1.v and j2.stime = (select min(stime) from journey j3
            where j3.v = j1.v and j3.stime > j1.stime)
        )
     and j1.kmEnd <> succ.kmStart;

| id   | stime       | kmEnd | kmStart | id   | stime       |
+------+------------+-------+---------+------+------------+
|   12 | 2012-06-02 |   120 |     121 |   13 | 2012-06-03 |
|   21 | 2012-06-01 |   110 |     111 |   22 | 2012-06-02 |
|   22 | 2012-06-02 |   120 |     121 |   23 | 2012-06-03 |

Diese Lösung ist elegant, aber ineffizent: Es wird für den Join eine temporäre Tabelle gebildet mit allen Fahrten, die einen Nachfolger haben, also N - n Zeilen, wenn es N Fahrten und n letzte Fahrten gibt (n ist sehr klein gegenüber N).

Aus diesen Zeilen werden dann die der Fahrten mit nachfolgender Lücke ausgewählt.

Also erst Join, dann Reduktion.

Lösung 4 (effizenter Join)

Wir kombinieren Lösung 1 mit Lösung 3:

select j1.id, j1.stime, j1.kmEnd, succ.kmStart, succ.id, succ.stime from journey j1, journey succ
  where j1.v = succ.v and j1.id <> succ.id
     and succ.stime = (select min(stime) from journey j2 where j2.v = j1.v and j2.stime > j1.stime)
     and j1.id in (select id from journey j3
      where not exists (select id from journey j4
        where j3.v = j4.v and j3.kmEnd = j4.kmStart)
          and j3.stime <> (select max(stime) from journey j5
          where j5.v = j3.v)
      );

| id   | stime       | kmEnd | kmStart | id   | stime       |
+------+------------+-------+---------+------+------------+
|   12 | 2012-06-02 |   120 |     121 |   13 | 2012-06-03 |
|   21 | 2012-06-01 |   110 |     111 |   22 | 2012-06-02 |
|   22 | 2012-06-02 |   120 |     121 |   23 | 2012-06-03 |

Der Unterschied zu Lösung 3 ist, dass die Temporärtabelle des Join nur soviel Zeilen enthält wie es Schwarzfahrten gibt, also im allgemeinen hoffentlich sehr wenig. Das geschieht durch den Subselect aus Lösung 1 (j1.id in (select...))

Also erst Reduktion, dann Join.

Nachteil: Die Formulierung ist unübersichtlicher, aber braucht bei großen Tabellen deutlich weniger Zeit und Platz.

Massentest

Zu vielen Eingabedaten verhilft folgendes Script:

use strict;
my ($id, $v, $year, $month, $day, $km, $km2, $marker);
my $vCount = 1000;
for ($v = 1000; $v < 1000 + $vCount; $v++){
        $km = int(10000 * rand());
        for $year(2008..2011){
                for $month(1..12){
                        for $day(1..28){
                                $id++;
                                $km2 = $km + 1 + int(100 * rand);
                                print $marker, "insert into journey values($id, $v, $km, $km2, '$year-$month-$day');\n";
                                $km = $km2;
                                $marker = "";
                                if (rand() < 0.01){
                                        $km += int (20 * rand);
                                        $marker =  " ";
                                }
                        }
                }
        }
}

Daten werden so erzeugt (vorher Script unter mk_data.pl abspeichern):

perl mk_data.pl >big.sql

Wieviele Zeilen?

wc -l big.sql
1344000

Es wurden etwa 1% Schwarzfahrten erzeugt, die Lücken sind mit " " am Zeilenanfang markiert. Wieviele sind es denn?

wc -l "^ " big.sql
13477

Jetzt nach MySql importieren:

mysql demo < big.sql

Laufzeiten

Zeitangaben in MIN:SEC:

Index zur Beschleunigung erzeugen:

CREATE INDEX ix_date ON journey (stime);
CREATE INDEX ix_id ON journey (id);
CREATE INDEX ix_v ON journey (v);

Messung der Lösungen bei mysql:

time mysql <<EOS >/tmp/result.txt
select ...
EOS

Messung mit Oracle:

Um die Abfrage ein select count(*) from ( <alte Abfrage> ) herumgebaut, sonst wird nur die Zeit gemessen, die bis zur Ausgabe der 1.ten Zeile anfällt, und das ist bei den Nichtjoins kürzer.

Messung mit Firebird:

time isql-fb -u USER -p PASSW -i SQL_SCRIPT DB -o RESULT