[linux-l] SQL

[Volker Grabsch]

On Wed, Oct 18, 2006 at 09:40:16PM +0200, Robert C. Helling wrote:
> >Nun, wir haben bisher zwei Lösungen jeweils zweimal gehabt.
> >Einmal mit LEFT JOIN, und einmal ein SELECT auf zwei Tabellen
> >gleichzeitig.
[...]
> Asymptotisch kann man das aber besser machen: Vorher sortiere ich naemlich 
> beide Tabellen nach der gemeinsamen Spalte, das dauert mit Quicksort
> M log(M) + N log(N),

Da eines davon normalerweise ein Primärschlüssel ist, hat es auch einen
entsprechenden Index. Zweiteres könnte ebenfalls einen (Sekundär-)Index
erhalten. Das heißt, die Sortierzeit fällt weg bzw. geschieht schon
beim Einfügen. (wesentlich schneller, da bereits sortiert => Binärsuche
oder Hash-Verfahren oder Kombination aus beiden).

> dann kann ich die Tabellen "nebeneinander legen" und 
> das durchsuchen nach Paaren dauert nur noch M+N. Daher ist dieses 
> Verfahren wesentlich schneller fuer grosse M und N.

Auch ein LEFT JOIN sollte ebenfalls so arbeiten, nicht nur ein
Mehrtabellen-SELECT.


Viele Grüße,

    Volker

-- 
Volker Grabsch
---<<(())>>---
Administrator
NotJustHosting GbR