Ich habe in einer Datenbanktabelle listen von Vektoren (Start-Ende-Wertepaare) gespeichert. Die Vektoren sind unterschiedlichen Quellen zugeordnet (A und B). Jetzt würde ich gerne über ein Select alle Wertepaare abfragen die sich zwischen A und B überschneiden.
Die Daten sehen ungefähr so aus:

start | end  | sorce
17    | 23   | A
150   | 188  | A
200   | 260  | A
19    | 30   | B
105   | 149  | B
199   | 220  | B
...

Update:
So etwas wie das folgende wird leider nicht funktionieren da die Tabelle über einige Hunderttausend bis Millionen Zeilen verfügt und ich das Ergebnis unter 10 Sekunden gerne hätte:

SELECT v1.*, v2.* FROM vectors v1, vectors v2 
WHERE v1.source != v2.source AND (
  v1.start BETWEEN v2.start AND v2.end OR
  v1.end   BETWEEN v2.start AND v2.end
)

Update 2:
Das Select lässt sich noch ein wenig eleganter und performanter ausdrücken, da es in Postgres Datentypen und Operatoren für Geometrische Objekte gibt:

SELECT v1.* FROM vectors v1 WHERE EXISTS(
    SELECT 1 FROM vectors v2 WHERE
    v1.source != v2.source AND
    box(point(v2.start,s2.start),point(s2.end,s2.end))
 && box(point(v1.start,s1.start),point(s1.end,s1.end))
 )

Der Index dazu würde so aussehen:

create index ix_range  on vectors using gist (box(point(start,start),point(end,end)))

Das Ganze kann ich bei Bedarf dann noch um eine Weitere Dimension ergänzen.

Update 3:
Mit Window-Funktionen ab Version 8.4 gehts dann richtig ab. Das ist dann auch ohne index eine Größenordnung schneller als meine letzten Vorschläge.

100.000 bis 1.000.000 Einträge sollten für nen SQL-Server problemlos in < 10 Sekunden handelbar sein wenn du auf die 3 Spalten einen Index legst.

Unsere Datenbank schafft ähnliche Anweisungen in < 3 Sekunden auf Tabellen mit 8 Millionen Datensätzen.

Lösung:

Groupierter Index (falls nicht vorhanden, einzelindexe) auf die 3 Spalten legen.