Thread: SQL99 Hierarchical queries
Hi hackers! I have done initial implementation of SQL99 WITH clause (attached). It's now only for v7.3.4 and haven't a lot of checks and restrictions. It can execute only simple WITH queries like WITH tree AS (SELECT id,pnt,name,1::int AS level FROM t WHERE id=0 UNION SELECT t.id,t.pnt,t.name,tree.level+1 FROM t JOIN tree ON tree.id=t.pnt ) SELECT * FROM tree; It would be great if someone with knowledge of Pg internals can make a kind of code review and make some advices how to better implement all this. Regards, Evgen.
Attachment
> I have done initial implementation of SQL99 WITH clause (attached). > It's now only for v7.3.4 and haven't a lot of checks and restrictions. What kind of restrictions are on it? Chris
> > I have done initial implementation of SQL99 WITH clause (attached). > > It's now only for v7.3.4 and haven't a lot of checks and restrictions. > > What kind of restrictions are on it? Main restriction is that the query inside WITH alias can refer only to back and to itself. For example WITH a as (...),b as (...)select ...; a can refer only to itself, b - to a and b. Its needed to restrict WITH aliased query not to use WITH aliasing itself, i.e. avoid situation of WITH inside WITH. And make also some other checks. But this isn't done yet. Regards, Evgen.
hello, I tested you patch, and it's good work. I would all methods in PostgreSQL. I found query which kill backand WITH t AS ( SELECT 0::int AS i UNION ALL SELECT i + 1 FROM t WHERE i < 100) SELECT * FROM t; Regards Pavel Stehule
Ok, I'm started porting it to 8.0.1 and will fix this also. By the way, did you know any test suit for such queries? To make some regression test. Regards, Evgen > I tested you patch, and it's good work. I would all methods in PostgreSQL. > I found query which kill backand > > WITH t AS ( > SELECT 0::int AS i > UNION ALL SELECT i + 1 FROM t WHERE i < 100) > SELECT * FROM t; > > Regards > Pavel Stehule > >
On Mon, Feb 28, 2005 at 11:07:51AM +0300, Evgen Potemkin wrote: > Ok, I'm started porting it to 8.0.1 and will fix this also. By the > way, did you know any test suit for such queries? To make some > regression test. Evgen, Thanks very much for doing this work. Is there some way you can summarize what you did so others can join you in working on it? If it is easier for you to write this in some language other than English, please do, and we'll find translators :) I noticed that the patch touches the parser, the optimizer and the executor. What does it to with each? What did I miss? Cheers, D -- David Fetter david@fetter.org http://fetter.org/ phone: +1 510 893 6100 mobile: +1 415 235 3778 Remember to vote!
I'm curious what kind of performance differences there would be over using something like the nested-set model? Would this be faster, or slower? On Thu, 2005-02-24 at 13:02 +0300, Evgen Potemkin wrote: > Hi hackers! > > I have done initial implementation of SQL99 WITH clause (attached). > It's now only for v7.3.4 and haven't a lot of checks and restrictions. > It can execute only simple WITH queries like > WITH tree AS (SELECT id,pnt,name,1::int AS level FROM t WHERE id=0 > UNION SELECT t.id,t.pnt,t.name,tree.level+1 FROM t JOIN tree ON > tree.id=t.pnt ) SELECT * FROM tree; > It would be great if someone with knowledge of Pg internals can make a > kind of code review and make some advices how to better implement all > this. > > Regards, Evgen. > ---------------------------(end of broadcast)--------------------------- > TIP 3: if posting/reading through Usenet, please send an appropriate > subscribe-nomail command to majordomo@postgresql.org so that your > message can get through to the mailing list cleanly -- Mike Benoit <ipso@snappymail.ca>
On Mon, 28 Feb 2005, Evgen Potemkin wrote: > Ok, I'm started porting it to 8.0.1 and will fix this also. > By the way, did you know any test suit for such queries? To make some > regression test. > Hello, I can find some examples on internet and prepare regression tests. I think PostgreSQL can support all syntax H.Q. Is more easy created question via Oracle syntax, and processing is faster (maybe better optimalisation now), than ANSI WITH syntax. Can You add support for clausule VALUE? Pavel Stehule
Mike, > I'm curious what kind of performance differences there would be over > using something like the nested-set model? > > Would this be faster, or slower? The answer is "yes". ;-) Which tree structures you use depends on what you're trying to accomplish and what your use case is. There are some structures (for example, heirarchical org charts) for which nested sets can't be beat. There are plenty of reasons to implement other tree structures, such as graphs, cycles, and delimited lists depending on what you're trying to depict. What WITH is going to "replace", if anything, is the simple adjacency list structure. -- Josh Berkus Aglio Database Solutions San Francisco
> Thanks very much for doing this work. Is there some way you can > summarize what you did so others can join you in working on it? If it > is easier for you to write this in some language other than English, > please do, and we'll find translators :) > > I noticed that the patch touches the parser, the optimizer and the > executor. What does it to with each? What did I miss? > > Cheers, > D Ok, i'll make some doc on this topic. Regards, Evgen
> > Ok, I'm started porting it to 8.0.1 and will fix this also. > > By the way, did you know any test suit for such queries? To make some > > regression test. > > > Hello, I can find some examples on internet and prepare regression tests. > I think PostgreSQL can support all syntax H.Q. Is more easy created > question via Oracle syntax, and processing is faster (maybe better > optimalisation now), than ANSI WITH syntax. Can You add support for > clausule VALUE? > > Pavel Stehule On this weekend I'll see to DB2 reference and if there some description on what is it, I'll try to implement it. Regards, Evgen.
Hello hackers, > Thanks very much for doing this work. Is there some way you can > summarize what you did so others can join you in working on it? If it > is easier for you to write this in some language other than English, > please do, and we'll find translators :) > > I noticed that the patch touches the parser, the optimizer and the > executor. What does it to with each? What did I miss? > This is some info about implementations. Parser. WITH aliased queries stored as list of SUBQUERY nodes. Each of them is parsed as usually. In pstate->withClause already analyzed part of WITH queries list is stored. When next WITH subquery is analyzed, it's been added to subqueries list inside withClause node, so any WITH subquery can see al prevoius WITH subqueries. In FROM clause all WITH aliases represented by special type of RangTblEntry - RTE_WITH_SUBQUERY. It stores a reference to WithClause node and index of itself in QITH subqueries list. For analyzing var added step to search in WITH aliases if they are present. Recursiveness support. Before WITH subquery analyzing in pstate->withClause->calias stored it's alias. So when transforming FROM clause item and relation name found only in pstate->withClause->calias query marked as recursive. SQL99 recursive queries are made using UNION and first UNION subquery should be non recursive (this isn't currently checked). Thus when transforming set operation statement, after analyzing of first statement it's is RTE stored in pstate->withClause->cRTE, and all checks for vars in this WITH subquery in made against this RTE. Optimizer. WithClause node transformed to With node, scan of RTEs of type RTE_WITH_SUBQUERY to WithScan nodes. Each WITH subquery is enveloped into WithSubPlan node. It stores result and working tuplestores, and some flags (used for prevent double initialization and execution) for each subquery. Nothing extraordinary is done here. Executor. When executor tries to fetch first tuple from any WithScan node, this node check whether With node have been executed, if no then it executes it and then fetches all it's tuples from it's result tuplestore. "With" node being executed is simply call ExecNode on each subplan in it's list and storing tuples in result tuplestore. Recursiveness support. It's all done in Append node. If it marked as recusrive, it changes a little it's behaviour. Tuples fetched from subplan are stored in workin table. When Append reaches the end of list of its subqueries it call nodeWithSwitchTables. This function for query being executed will append result table to final table, move working table to result table, and clean working table. After this Append begins next loop of subqueries execution, starting from 2nd subquery. Thus first Append subquery is executed only once. Execution ends when no one tuple fetched from all subqueries. This approach allows WithScan nodes to fetch data fetched by Append in previous loop. Regards, Evgen.
Hi Evgen, How's the syncing with HEAD going? Cheers, Chris Evgen Potemkin wrote: > Ok, I'm started porting it to 8.0.1 and will fix this also. > By the way, did you know any test suit for such queries? To make some > regression test. > > Regards, Evgen > >>I tested you patch, and it's good work. I would all methods in PostgreSQL. >>I found query which kill backand >> >>WITH t AS ( >> SELECT 0::int AS i >> UNION ALL SELECT i + 1 FROM t WHERE i < 100) >>SELECT * FROM t; >> >>Regards >>Pavel Stehule >> >> > > > ---------------------------(end of broadcast)--------------------------- > TIP 5: Have you checked our extensive FAQ? > > http://www.postgresql.org/docs/faq
> Hi Evgen, > > How's the syncing with HEAD going? > > Cheers, > > Chris I'm working on it. Regards, Evgen.
Hi Evgen, I just keep pinging this patch thread every once in a while to make sure it doesn't get forgotten :) How is the syncing with 8.1 CVS coming along? Chris Evgen Potemkin wrote: > Hi hackers! > > I have done initial implementation of SQL99 WITH clause (attached). > It's now only for v7.3.4 and haven't a lot of checks and restrictions. > It can execute only simple WITH queries like > WITH tree AS (SELECT id,pnt,name,1::int AS level FROM t WHERE id=0 > UNION SELECT t.id,t.pnt,t.name,tree.level+1 FROM t JOIN tree ON > tree.id=t.pnt ) SELECT * FROM tree; > It would be great if someone with knowledge of Pg internals can make a > kind of code review and make some advices how to better implement all > this. > > Regards, Evgen. > > > ------------------------------------------------------------------------ > > > ---------------------------(end of broadcast)--------------------------- > TIP 3: if posting/reading through Usenet, please send an appropriate > subscribe-nomail command to majordomo@postgresql.org so that your > message can get through to the mailing list cleanly