Rekursion durch grossen Baum

Hallo.

Ich bin auf meinen ersten Schritten mit Postgres.
Das Thema ist bestimmt nicht ganz neu,aber ich habe noch keine Lösung gefunden.

Ich habe aus einem Import einer anderen Datenquelle eine Tabelle mit einem Tree Verzeichnis mit ca. 11936 Datasets. Dieses besitzt Foreign Keys zu weiteren Informationen (sprachspezifische Labels etc.).

Nun möchte ich diese Tabelle in eine neue Tabelle auslesen, und für die Performance und Anzeige mit zusätzliche Informationen bestücken (fertige Breadcrumbs etc.)

Entsprechend einer Baumstruktur habe ich nun eine Rekursion, welche soweit auch funktioniert. Bei der grossen Datenmenge aber wird der Stack voll und die Ausführung bricht ab.

Unten der Code, hat jemand eine Idee wie ich das Problem mit dem Stack beheben kann, so dass durch den gesamten Baum iterieren kann?


\

/* Ursprungstabelle */

CREATE TABLE tabletree
(
id integer,
hi_key character varying,
hi_parentkey character varying,
hi_sort integer,
hi_level integer
)
WITH (OIDS=FALSE);
ALTER TABLE tabletree OWNER TO postgres;




/Einige Daten in der Ursprungstabelle/

INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘0ca54e38-1110-418f-89af-2f60dc795bc9’, ‘’, 10, 1);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘ea06d488-ca3a-4d39-b6cb-71ad2c482537’, ‘0ca54e38-1110-418f-89af-2f60dc795bc9’, 10, 2);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘fe2ae92d-7134-4456-ac83-d9ea11ca99d7’, ‘ea06d488-ca3a-4d39-b6cb-71ad2c482537’, 10, 3);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘53c0989a-e64b-476e-939a-a43ab8441853’, ‘fe2ae92d-7134-4456-ac83-d9ea11ca99d7’, 10, 4);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘23856fb0-1f4e-4a00-963b-972c55cd07ee’, ‘53c0989a-e64b-476e-939a-a43ab8441853’, 10, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘0ddfb8df-6a3e-46b2-867f-ad3c421d6aa9’, ‘53c0989a-e64b-476e-939a-a43ab8441853’, 20, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘fc05ad61-40ab-45aa-8fff-fdf143cd1225’, ‘fe2ae92d-7134-4456-ac83-d9ea11ca99d7’, 20, 4);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘a1505999-b38c-4b76-82d0-447632594381’, ‘fc05ad61-40ab-45aa-8fff-fdf143cd1225’, 10, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘91ea4413-51d2-41c7-b279-18b432390a42’, ‘fc05ad61-40ab-45aa-8fff-fdf143cd1225’, 20, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘ca788458-de3d-441f-8d21-597903a4a686’, ‘fc05ad61-40ab-45aa-8fff-fdf143cd1225’, 30, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘f1735d2c-c9ba-4ced-81c2-67dd84f928e9’, ‘fe2ae92d-7134-4456-ac83-d9ea11ca99d7’, 30, 4);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘3e478b00-4219-4dea-a0dd-a3720c23425c’, ‘f1735d2c-c9ba-4ced-81c2-67dd84f928e9’, 10, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘9cf2aadc-4742-45f3-99d9-4d219c95412a’, ‘f1735d2c-c9ba-4ced-81c2-67dd84f928e9’, 20, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘6f8e1520-8970-4b8a-93f4-fe2eac804ebe’, ‘f1735d2c-c9ba-4ced-81c2-67dd84f928e9’, 30, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘cdb25efa-1a9d-43df-8a3f-d861022a1253’, ‘f1735d2c-c9ba-4ced-81c2-67dd84f928e9’, 40, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘fb9e56e3-59c9-439b-95f2-7af4ab4be824’, ‘f1735d2c-c9ba-4ced-81c2-67dd84f928e9’, 50, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘ddf65bbc-6250-4368-aab0-83c19d025ab3’, ‘fe2ae92d-7134-4456-ac83-d9ea11ca99d7’, 40, 4);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘5a3357ed-9216-4013-afc6-b66dd1a80345’, ‘ddf65bbc-6250-4368-aab0-83c19d025ab3’, 10, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘00eeca6d-a83b-444c-af6e-570f8ce2c052’, ‘ddf65bbc-6250-4368-aab0-83c19d025ab3’, 20, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘767d5732-2c1f-4a0f-bf3f-7630b64d6361’, ‘fe2ae92d-7134-4456-ac83-d9ea11ca99d7’, 50, 4);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘38f98d65-fa20-4942-ae0a-b328fbfb8bad’, ‘767d5732-2c1f-4a0f-bf3f-7630b64d6361’, 10, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘0b197e6c-123f-426e-a628-d67202f699a2’, ‘767d5732-2c1f-4a0f-bf3f-7630b64d6361’, 20, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘b7e83a61-9b95-404a-b580-87689d02a391’, ‘767d5732-2c1f-4a0f-bf3f-7630b64d6361’, 30, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘99afb5ec-db1e-4976-ad3e-0781d74fb671’, ‘767d5732-2c1f-4a0f-bf3f-7630b64d6361’, 40, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘cd23023a-9757-44fd-abe2-f0c800b98472’, ‘767d5732-2c1f-4a0f-bf3f-7630b64d6361’, 50, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘bd31e399-a12e-4226-85f1-5de95c67c315’, ‘767d5732-2c1f-4a0f-bf3f-7630b64d6361’, 60, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘ce45a0ae-b63d-4c0b-bf9d-c71905d51728’, ‘767d5732-2c1f-4a0f-bf3f-7630b64d6361’, 70, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘d8b2403a-8f93-4832-99e6-c91c8481e991’, ‘767d5732-2c1f-4a0f-bf3f-7630b64d6361’, 80, 5);
INSERT INTO tabletree (hi_key, hi_parentkey, hi_sort, hi_level) VALUES ( ‘5a1d2f26-ae63-4bcd-8e78-aebc85d295f1’, ‘767d5732-2c1f-4a0f-bf3f-7630b64d6361’, 90, 5);



/* Temporäre Tabelle zur Verarbeitung */

CREATE TABLE result
(
id serial NOT NULL,
hi_key character varying,
hi_parentkey character varying,
hi_level integer,
CONSTRAINT result_pkey PRIMARY KEY (id)
)
WITH (OIDS=FALSE);
ALTER TABLE result OWNER TO postgres;




/* Zieltabelle /
CREATE TABLE newtabletree
(
id serial NOT NULL,
hi_key character varying,
hi_parentkey character varying,
hi_level integer,
CONSTRAINT newtabletree_pkey PRIMARY KEY (id)
)
WITH (OIDS=FALSE);
ALTER TABLE newtabletree OWNER TO postgres;




/
Rekursive Funktion zur Verarbeitung des Inhalts */

CREATE OR REPLACE FUNCTION createcatalogindex(character varying)
RETURNS character varying AS
$BODY$DECLARE

myKey ALIAS FOR $1;

myParentKey VARCHAR;
myNewParentKey VARCHAR;
myReturnValue VARCHAR;

itemTableTree RECORD;
itemResult RECORD;
itemResultCount RECORD;

BEGIN
myParentKey := NULL;

IF myKey IS NOT NULL THEN
FOR itemTableTree IN
SELECT * FROM tabletree
WHERE hi_parentkey=myKey
LOOP
myParentKey := itemTableTree.hi_key;
myReturnValue := myParentKey;
IF (myParentKey IS NOT NULL) THEN
INSERT INTO result (hi_key, hi_parentkey, hi_level) VALUES (itemTableTree.hi_key, itemTableTree.hi_parentkey, itemTableTree.hi_level);
INSERT INTO newtabletree (hi_key, hi_parentkey, hi_level) VALUES (itemTableTree.hi_key, itemTableTree.hi_parentkey, itemTableTree.hi_level);
ELSE
END IF;
END LOOP;
ELSE
END IF;

SELECT COUNT(*) INTO itemResultCount FROM result;

IF itemResultCount.count > 0 THEN

SELECT s.*
INTO itemResult
FROM result s
LIMIT 1;

myNewParentKey := itemResult.hi_key;


DELETE FROM result WHERE hi_key = myNewParentKey;

perform createcatalogindex(myNewParentKey);


myReturnValue := myNewParentKey;
RETURN myReturnValue;

ELSE
myReturnValue := myParentKey;
RETURN myReturnValue;
END IF;
END;$BODY$
LANGUAGE ‘plpgsql’ VOLATILE
COST 100;
ALTER FUNCTION createcatalogindex(character varying) OWNER TO postgres;


/* Aufruf der Funktion: */
SELECT createcatalogindex(’’);





Gruss
eisenstein

So ungern ich auf zukünftige Features verweise: PostgreSQL 8.4 dürfte die notwendigen Mittel dafür haben. Dort werden sich Windowing Functions finden.

Oh, und ich habe gestern gesehen das es speziell zu diesem Thema einen Vortrag auf dem PGDay 2008 geben wird:

Schedule | European PGDay 2008

Ich gehe mal davon aus, daß das für kleine Datenmengen getest ist und funktioniert. Hast Du mal die Speicherparameter erhöht? Ich denke da an work_mem.

Andreas

die recursion sollte also maximal dessen tiefe erreichen …

bei 10 od. 20 knoten ist das ja kein ding … von dieser tiefe gehe ich im schlechtesten falle aus - bei dem beschriebenen anwendungsfall

ich vermute eher deine recursion haut nicht hin

Die Rekursion läuft einwandfrei bei kleineren Datenmengen.

Bei grösseren erhalte ich im pgadmin diese Meldung:

ERROR: stack depth limit exceeded
HINT: Increase the configuration parameter “max_stack_depth”, after ensuring the platform’s stack depth limit is adequate.


Mir stellt sich die Frage ob ich die Rekursion so verändern kann, das ich trotz dieser Menge die Limite nicht erreichen werde…

Wenn ich work_mem erhöhe ändert sich nichts. Erhöhe ich max_stack_depth - wie in der Fehlermeldung angegben, kann ich postgres nicht mehr starten.
Ich muss dazu sagen,d as es sich um Postgres 8.3 auf einem Windows Server 2003 handelt.

huhu :slight_smile: wie tief ist der baum?

Welcher Wert war vorher eingestellt?
Auf welchen Wert möchtest du das ändern?

Und warum möchte die Datenbank nicht mehr starten? Das steht normal im Logfile …


symbiont: die Tiefe ist egal, das Problem wird nur verschoben, nicht gelöst.

huhu 7 “Levels”

Ich habe mich nicht korrekt ausgedrückt: Der Service startet dann nicht mehr. Entsprechend habe ich keinen Logeintrag. Es wird auch kein Fehler angezeigt, auf der Konsole wird nur vermerkt “PostgreSQL Database Server konnte nicht gestartet werden. Der Dienst hat keinen Fehler gemeldet.”


Danke schonmal für die Antworten.

“Entsprechend” nicht, meistens taucht im Logfile oder im Systemlog etwas auf.

bei NUR 7 levels ist davon auszugehen, dass du einen fehler in deiner rekursion hast - bzw. evtl trigger rekursiv ausgefuehrt werden, sodass die 7 rekursionen (mehr braucht man nicht) ueberschritten werden

auch wenn du glaubst, dass deine funktion korrekt ist - ich wuerde sie nochaml pruefen …

dass deine “kleinen” test-daten zu funktionieren scheinen koennte auch daran liegen, dass dort keine entsprechende situation vorkommt, die dazu fuehren wuerde dass deine rekursion zu einer von-neumann-katastrophe aussarten g

Es lag am zu hohem max_stack_depth
Ich hab den nun auf 3 MB gesetzt. Der Service läuft, die Rekursion bricht wie bisher ab.

Ich habe jetzt auch die Levels miteinbezogen, das hilft aber - wie ich erwartet habe - nicht.

work_mem = 100MB # min 64kB
#maintenance_work_mem = 16MB # min 1MB
max_stack_depth = 3MB # min 100kB

also ich habe jetzt mal deine fkt genau angeschaut … und ich kann beim besten willen keine abbruch-bedingung vor dem rekursiven aufruf der funktion erkennen !

du selektierst zwar oben mit dem uebergeb. key ne menge … und selbst wenn die leer ist - nichts zu tun waere - rufst du wieder die rekursive funktion auf …

wenn da jemals was funktioniert hat, hast du das sicher danach abgeaendert …

SELECT COUNT(*) INTO itemResultCount FROM result;

IF itemResultCount.count > 0 THEN

Enthät die Tabelle result keine Einträge mehr, wird die Funktion nicht mehr aufgerufen.

itemResultCount.count ist immer 1

ja … und vorher wird die tabelle result immer gefuellt … also wie soll result dann jemals leer sein ?

ich schaetze du selectierst das count von der falschen table

Result wird temporär befüllt und wieder geleert. Meiner Meinung nach funtkioniert das korrekt. Ich werde das aber alles bei Gelegenheit nochmals durchgehen.

Gibt es denn gute Debugging Methoden oder Tools mit pl/pgSQL?

Leider muss ich mit dem Experiment abbrechen und auf mir bekannte Umgebungen wechseln.

Ich hatte gehofft einen Weg zu finden eine optimale Performance für die Abbildung
Eines grossen Datenbaumes zu finden. Mir liegen Beispiele von verschiedenen Firmen vor welche die gleiche Daten-Basis besitzen umgesetzt in MSSQL oder MySQL. In beiden ist die Performance ein erhebliches Problem.

Vielen Dank fürs mitdenken!

Gruss

Eisenstein

hmm das DELETE habe ich glatt uebersehen :slight_smile:

nichts desto trotz ist ein fehler in der rekursions-gunktion sehr wahrscheinlich - weil bei z.B. baumtiefe von 7 ueberhaupt nicht mit einem stack-problem zu rechnen ist …

ich verwende selbst an manchen stellen rekursive funktionen - sogar in triggern duck - klar beim entwickeln kanns da schonmal zum kollaps auf dem stack kommen - aber das lag bisher immer daran, dass die rekursion kein ende fand

bei mir wurde da aber auch immer sowas aehnliches wie ein stack-trace ausgegeben …

kannst du den fehler mal produzieren und mal schauen ob du sowas auch bekommst und hier posten ?

obs gescheite debugger gibt weiss ich nicht …

weisst was das problem sein wird ?

Deine Daten sind kein Baum, sondern ein Netz - und du hast irgendwo ne Schleife drin …

danach wuerde ich mal schauen … du musst in die Rekursion sowas wie ne Rekursiondetection einbauen lach

das mein ich völlig ernst

deswegen mag das mit deinen kleinen Daten funktioniert haben … und mit den “vielen” nicht …

du selektierst ja immer von der original-table mit dem parent-key … nur wenn irgendwann irgendwo der neue parent-key “zurueck” zeigt bist gearscht :slight_smile:

Also du solltest dein obiges select noch um ein AND NOT EXISTS (subquery …) erweitern wo die subquery in deinen zieldaten schaut, ob du den aktuellen parent-key nicht schon indiziert hast …