Wie kann ich Abfragen beschleunigen, die nach dem Wurzelknoten einer transitiven Schließung suchen?

Question

Ich habe eine historische Tabelle mit transitivem Abschluss, die einen Baum darstellt.

create table TRANSITIVE_CLOSURE
  (
    CHILD_NODE_ID number not null enable,
    ANCESTOR_NODE_ID number not null enable,
    DISTANCE number not null enable,
    FROM_DATE date not null enable,
    TO_DATE date not null enable,
    constraint TRANSITIVE_CLOSURE_PK unique (CHILD_NODE_ID, ANCESTOR_NODE_ID, DISTANCE, FROM_DATE, TO_DATE)
  );

Hier sind einige Beispieldaten:

CHILD_NODE_ID | ANCESTOR_NODE_ID | DISTANCE 
--------------------------------------------
1             | 1                | 0
2             | 1                | 1
2             | 2                | 0
3             | 1                | 2
3             | 2                | 1
3             | 3                | 0

Leider verursacht meine aktuelle Abfrage zum Auffinden des Stammknotens eine vollständige Tabellendurchsuchung:

select *
from transitive_closure tc
where 
  distance = 0
  and not exists (
  select null
  from transitive_closure tci
  where tc.child_node_id = tci.child_node_id
    and tci.distance <> 0
);

Oberflächlich betrachtet sieht es nicht allzu teuer aus, aber wenn ich mich 1 Million Zeilen nähere, fängt diese spezielle Abfrage an, unangenehm zu werden... vor allem, wenn sie Teil einer Ansicht ist, die den Adjazenzbaum für Legacy-Unterstützung abruft.

Gibt es eine bessere Möglichkeit, den Wurzelknoten eines transitiven Abschlusses zu finden? Ich würde gerne unseren gesamten alten Code neu schreiben, aber das kann ich nicht... also muss ich die Adjazenzliste irgendwie erstellen. Alles außer dem Wurzelknoten zu erhalten ist einfach, gibt es also einen besseren Weg? Denke ich über dieses Problem auf die falsche Weise?

Abfrageplan für eine Tabelle mit 800k Zeilen.

OPERATION                                  OBJECT_NAME        OPTIONS         COST 
SELECT STATEMENT                                                              2301 
  HASH JOIN                                                   RIGHT ANTI      2301 
    Access Predicates
      TC.CHILD_NODE_ID=TCI.CHILD_NODE_ID 
    TABLE ACCESS                           TRANSITIVE_CLOSURE FULL            961 
      Filter Predicates 
        TCI.DISTANCE = 1 
    TABLE ACCESS                           TRANSITIVE_CLOSURE FULL            962 
      Filter Predicates 
        DISTANCE=0

Answer 1

Wie lange dauert die Ausführung der Abfrage, und wie lange soll sie dauern? (Normalerweise wollen Sie die Kosten nicht für die Abstimmung verwenden. Nur sehr wenige Leute wissen, was "explain plan cost" wirklich bedeutet).

Auf meinem langsamen Desktop dauerte die Abfrage nur 1,5 Sekunden für 800K Zeilen. Und dann 0,5 Sekunden, nachdem die Daten im Speicher waren. Bekommen Sie etwas wesentlich Schlimmeres, oder wird diese Abfrage sehr häufig ausgeführt?

Ich weiß nicht, wie Ihre Daten aussehen, aber ich würde vermuten, dass ein vollständiger Tabellenscan für diese Abfrage immer am besten ist. Unter der Annahme, dass Ihre hierarchischen Daten relativ flach sind, d. h. es gibt viele Abstände von 0 und 1, aber sehr wenige Abstände von 100, wird die wichtigste Spalte nicht sehr ausgeprägt sein. Das bedeutet dass jeder der Indexeinträge für den Abstand auf eine große Anzahl von Blöcken verweisen wird. Es ist viel billiger, die gesamte Tabelle auf einmal zu lesen, indem mehrere Blöcke gelesen werden zu lesen, als einen großen Teil der Tabelle blockweise zu lesen.

Was meinen Sie außerdem mit historisch? Können Sie die Ergebnisse dieser Abfrage in einer materialisierten Ansicht speichern?

Eine andere Möglichkeit ist die Verwendung analytischer Funktionen. Dadurch wird der zweite Tabellenscan durch eine Sortierung ersetzt. Dieser Ansatz ist normalerweise schneller, aber bei mir dauert diese Abfrage tatsächlich länger, nämlich 5,5 Sekunden statt 1,5 Sekunden. Aber vielleicht klappt es in Ihrer Umgebung besser.

select * from
(
    select
        max(case when distance <> 0 then 1 else 0 end)
            over (partition by child_node_id) has_non_zero_distance
        ,transitive_closure.*
    from transitive_closure
)
where distance = 0
    and has_non_zero_distance = 0;

Answer 2

Können Sie versuchen, einen Index auf distance und child_node_id hinzuzufügen, oder ändern Sie die Reihenfolge dieser Spalten im bestehenden eindeutigen Index ? Ich denke, dass es dann für die äußere Abfrage möglich sein sollte, auf die Tabelle über den Index über die Entfernung zuzugreifen, während die innere Abfrage nur Zugriff auf den Index benötigt.

Answer 3

Fügen Sie EINEN Wurzelknoten hinzu, von dem alle Ihre aktuellen Wurzelknoten abgeleitet sind. Dann würden Sie einfach die Kinder Ihres einen Wurzelknotens abfragen. Problem gelöst.