WITH RECURSIVE patch V0.1
WITH RECURSIVE patch V0.1
Here are patches to implement WITH RECURSIVE clause. There are some
limitiations and TODO items(see the "Current limitations" section
below). Comments are welcome.
1. Credit
These patches were developed by Yoshiyuki Asaba (y-asab@sraoss.co.jp)
with some discussions with Tatsuo Ishii (ishii@sraoss.co.jp).
- prior patches:
http://archives.postgresql.org/pgsql-patches/2008-03/msg00327.php
The patches include some extentions to the patches above.
2. Design proposales
See: http://archives.postgresql.org/pgsql-hackers/2008-02/msg00642.php
3. Implementation details
- Parsing recursive queries
We convert WITH clause to following structure in analyzer.
/*
* WithClause -
* reprensentation of WITH clause
*/
typedef struct WithClause
{
NodeTag type;
List *subquery; /* query list */
bool recursive; /* true = WITH RECURSIVE */
} WithClause;
If recursive is false, WITH clause is converted to a subquery.
Next we call transformWithClause() to check if the query defined in
WITH RECURSIVE clause is a liner recursive query.
transformWithClause() does followings:
1) Detect query which is not allowed in SQL standard
2) Create a name dependency graphs
transoform* functions checks if target tables actually exist and throw
an error if tables do not exist.
For example in following query:
WITH RECURSIVE x AS (SELECT * from y),
y AS (SELECT * FROM pg_class)
SELECT * FROM x;
x's definition referes to y and y is defined after x's definition. If
we evaluate x and y in the order of above, an error will occur while
evaluating x since y is not defined yet.
To avoid the problem we create new function:
void checkWellFormedCte(ParseState *pstate, WithClause *withClause);
which performs topological sort on graphs.
Non recursive term will be the start of the graph, checks type
checking one by one.
names appear in WITH RECURSIVE clause form a name dependency
graph. The nodes in the graph is represented by CteNode type:
typedef struct CteNode;
struct CteNode
{
Alias *alias;
CteList *dependency; /* if NULL the node does not call other node */
bool self_reference;
bool non_recursive;
} CteNode;
If there is loop in the dependency graph, a matual recursion exists
and an error occurs (error code 0A00).
* Note that this part is not implemented in the V1.0 patches yet.
Tables defined in WITH RECURSIVE clause is identified as RTE_RECURSIVE.
A name space is added to p_recursive_namespace in ParseState
structure. The added item's structure is following:
typedef struct RangeRecursive
{
NodeTag type;
Node *subquery; /* whole subquery */
Alias *alias; /* table alias & optional column aliases */
List *coldeflist; /* list of ColumnDef nodes to describe result
* of function returning RECORD */
Node *non_recursive_term; /* anaylze result of non recursive term */
bool recursive; /* reserved */
} RangeRecursive;
non_recursive_term keeps the result of analyze on non recursive term.
Using this, the type of recursive query is inferenced.
- Generating a plan
New plan node "Recursion" and "Recursive scan" is added.
Recursion scan is a plan which returns WT. Recursion is a plan which
execute recursive query. The subplan of Recursion is always "Append".
Below is an example EXPLAIN output.
EXPLAIN WITH RECURSIVE subdepartment AS
(
-- non recursive term
SELECT * FROM department WHERE name = 'A'
UNION ALL
-- recursive term
SELECT d.* FROM department AS d, subdepartment
WHERE d.parent_department = subdepartment.id
)
SELECT * FROM subdepartment;
QUERY PLAN
-------------------------------------------------------------------------------------------
Recursion on subdepartment (cost=0.00..50.76 rows=12 width=40)
-> Append (cost=0.00..50.64 rows=12 width=40)
-> Seq Scan on department (cost=0.00..24.50 rows=6 width=40) <-- non recusrive term
Filter: (name = 'A'::text)
-> Hash Join (cost=0.01..26.02 rows=6 width=40) <-- recursive term
Hash Cond: (d.parent_department = subdepartment.id)
-> Seq Scan on department d (cost=0.00..21.60 rows=1160 width=40)
-> Hash (cost=0.00..0.00 rows=1 width=4)
-> Recursive Scan on subdepartment (cost=0.00..0.00 rows=1 width=4)
- Executor
new files nodeRecursion.c and nodeRecursivescan.c are added.
The structure which represents the Recursion plan is as follows:
typedef struct Recursion
{
Scan scan;
Plan *subplan;
List *subrtable; /* temporary workspace for planner */
} Recursion;
typedef struct RecursionState
{
ScanState ss; /* its first field is NodeTag */
PlanState *subplan;
bool recursive_empty; /* if recursive term does exist, true */
Tuplestorestate *intermediate_tuplestorestate; /* intermediate table */
bool init_done; /* initialization flag */
} RecursiveState;
Following function are defined.
TupleTableSlot *
ExecRecursion(RecursionState *)
{
...
if (non recursive term)
{
slot = ExecProcNode(non recurisve term)
tuplestore_puttuple(WT, slot);
return slot;
}
/* calculate recursive term */
slot = ExecProcNode(recursive term)
if (!TupIsNull(slot)
{
slot = ExecProcNode(Nested Loop);
if (slot is empty)
swap(intermediate_tuplestorestate, WT)
else
tuplestore_puttuple(intermediate_tuplestorestate, slot)
}
...
}
- Executing RecursiveScan
Returns tuples store in a work table. Work table is stored in Estate structure.
typedef struct EState
{
...
Tuplestorestate *es_tuplestorestate; /* Stuff used for recursive query */
...
} EState;
RecursiveScan and RecursiveScanState structures.
typedef struct RecursiveScan
{
Plan *plan;
Plan *subplan;
} RecursiveScan;
typedef struct RecursiveScanState
{
ScanState ss;
TupleDesc tupdesc;
bool done_init;
} RecursiveScanState;
RecursiveScanState initialized RecursionState the initialize the type
information. Since Recursive plan is an upper plan of RecursiveScan,
initialization should be delayed. For this purpose we use done_init
flag.
Scan functions:
static TupleTableSlot *
RecursivescanNext(RecursiveScanState *node)
{
...
if (tuplestore_gettupleslot(node->ss.ps->state->es_tuplestorestate, true, slot))
return slot;
...
}
TupleTableSlot *
ExecRecursiveScan(RecursiveScanState *)
{
/*
* Delay initializing type info because type inference did not do
* in ExecInitRecursiveScan.
*/
if (!node->init_done)
{
ExecAssignScanType(&node->ss,
node->ss.ps.state->es_rscan_tupledesc);
/*
* Initialize result tuple type and projection info.
*/
ExecAssignResultTypeFromTL(&node->ss.ps);
ExecAssignScanProjectionInfo(&node->ss);
node->init_done = true;
}
return ExecScan(&node->ss, (ExecScanAccessMtd) RecursivescanNext);
}
4. New source codes:
- src/backend/parser/parse_cte.c
parse CTE (not completed)
- src/backend/executor/nodeRecursion.c
- src/include/nodeRecursion.h
Execute Recursion plan
- src/backend/executor/nodeRecursivescan.c
- src/include/nodeRecursivescan.h
Execute Recursive scan plan
5. Limitations and TODO
1) Only the last SELECT of UNION ALL can include self recursion name.
2) Cost of Recursion and Recursivescan plan are always 0.
3) Some recursion type checking is not complete.
4) Outer join for recursive name and tables does not work.
5) Need regression test cases.
6) Documentation needed.
6. Executing WITH RECURSIVE cluase examples
DROP TABLE IF EXISTS department;
DROP TABLE
CREATE TABLE department (
id INT PRIMARY KEY, -- department ID
parent_department INT REFERENCES department, -- upper department ID
name TEXT -- department name
);
psql:recursive-e.sql:6: NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "department_pkey" for table "department"
CREATE TABLE
INSERT INTO department VALUES (0, NULL, 'ROOT');
INSERT 0 1
INSERT INTO department VALUES (1, 0, 'A');
INSERT 0 1
INSERT INTO department VALUES (2, 1, 'B');
INSERT 0 1
INSERT INTO department VALUES (3, 2, 'C');
INSERT 0 1
INSERT INTO department VALUES (4, 2, 'D');
INSERT 0 1
INSERT INTO department VALUES (5, 0, 'E');
INSERT 0 1
INSERT INTO department VALUES (6, 4, 'F');
INSERT 0 1
INSERT INTO department VALUES (7, 5, 'G');
INSERT 0 1
-- department structure represented here is as follows:
--
-- ROOT-+->A-+->B-+->C
-- | |
-- | +->D-+->F
-- +->E-+->G
EXPLAIN WITH RECURSIVE subdepartment AS
(
-- non recursive term
SELECT * FROM department WHERE name = 'A'
UNION ALL
-- recursive term
SELECT d.* FROM department AS d, subdepartment
WHERE d.parent_department = subdepartment.id
)
SELECT * FROM subdepartment;
QUERY PLAN
-------------------------------------------------------------------------------------------
Recursion on subdepartment (cost=0.00..50.76 rows=12 width=40)
-> Append (cost=0.00..50.64 rows=12 width=40)
-> Seq Scan on department (cost=0.00..24.50 rows=6 width=40)
Filter: (name = 'A'::text)
-> Hash Join (cost=0.01..26.02 rows=6 width=40)
Hash Cond: (d.parent_department = subdepartment.id)
-> Seq Scan on department d (cost=0.00..21.60 rows=1160 width=40)
-> Hash (cost=0.00..0.00 rows=1 width=4)
-> Recursive Scan on subdepartment (cost=0.00..0.00 rows=1 width=4)
(9 rows)
-- extract all departments under 'A'. Result should be A, B, C, D and F
WITH RECURSIVE subdepartment AS
(
-- non recursive term
SELECT * FROM department WHERE name = 'A'
UNION ALL
-- recursive term
SELECT d.* FROM department AS d, subdepartment
WHERE d.parent_department = subdepartment.id
)
SELECT * FROM subdepartment ORDER BY name;
id | parent_department | name
----+-------------------+------
1 | 0 | A
2 | 1 | B
3 | 2 | C
4 | 2 | D
6 | 4 | F
(5 rows)
-- extract all departments under 'E'. Result should be E and G.
WITH RECURSIVE subdepartment AS
(
-- non recursive term
SELECT * FROM department WHERE name = 'E'
UNION ALL
-- recursive term
SELECT d.* FROM department AS d, subdepartment
WHERE d.parent_department = subdepartment.id
)
SELECT * FROM subdepartment ORDER BY name;
id | parent_department | name
----+-------------------+------
5 | 0 | E
7 | 5 | G
(2 rows)
--
Tatsuo Ishii
SRA OSS, Inc. Japan
Attachments:
On Sun, May 18, 2008 at 08:51:29PM +0900, Tatsuo Ishii wrote:
WITH RECURSIVE patch V0.1
Here are patches to implement WITH RECURSIVE clause. There are some
limitiations and TODO items(see the "Current limitations" section
below). Comments are welcome.1. Credit
These patches were developed by Yoshiyuki Asaba (y-asab@sraoss.co.jp)
with some discussions with Tatsuo Ishii (ishii@sraoss.co.jp).
This is really great! Kudos to all who made this happen :)
I tried a bunch of different queries, and so far, only these two
haven't worked. Any ideas what I'm doing wrong here?
WITH RECURSIVE t(n) AS (
SELECT 1
UNION ALL
SELECT n+1
FROM t
WHERE n < 100
)
SELECT * FROM t;
ERROR: cannot extract attribute from empty tuple slot
WITH RECURSIVE t(n) AS (
VALUES (1)
UNION ALL
SELECT n+1
FROM t
WHERE n < 100
)
SELECT * FROM t;
ERROR: cannot extract attribute from empty tuple slot
Cheers,
David.
--
David Fetter <david@fetter.org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter@gmail.com
Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate
David Fetter írta:
On Sun, May 18, 2008 at 08:51:29PM +0900, Tatsuo Ishii wrote:
WITH RECURSIVE patch V0.1
Here are patches to implement WITH RECURSIVE clause. There are some
limitiations and TODO items(see the "Current limitations" section
below). Comments are welcome.1. Credit
These patches were developed by Yoshiyuki Asaba (y-asab@sraoss.co.jp)
with some discussions with Tatsuo Ishii (ishii@sraoss.co.jp).This is really great! Kudos to all who made this happen :)
I tried a bunch of different queries, and so far, only these two
haven't worked. Any ideas what I'm doing wrong here?WITH RECURSIVE t(n) AS (
SELECT 1
UNION ALL
SELECT n+1
FROM t
WHERE n < 100
)
SELECT * FROM t;
ERROR: cannot extract attribute from empty tuple slotWITH RECURSIVE t(n) AS (
VALUES (1)
UNION ALL
SELECT n+1
FROM t
WHERE n < 100
)
SELECT * FROM t;
ERROR: cannot extract attribute from empty tuple slotCheers,
David.
Here's a test case attached shamelessly stolen from
http://www.adp-gmbh.ch/ora/sql/connect_by.html
This query (without naming toplevel columns) works:
# with recursive x as (select * from test_connect_by where parent is
null union all select base.* from test_connect_by as base, x where
base.parent = x.child) select * from x;
parent | child
--------+-------
| 38
| 26
| 18
18 | 11
18 | 7
26 | 13
26 | 1
26 | 12
38 | 15
38 | 17
38 | 6
17 | 9
17 | 8
15 | 10
15 | 5
5 | 2
5 | 3
(17 rows)
It even works when I add my "level" column:
# with recursive x(level, parent, child) as (select 1::bigint, * from
test_connect_by where parent is null union all select x.level + 1,
base.* from test_connect_by as base, x where base.parent = x.child)
select * from x;
level | parent | child
-------+--------+-------
1 | | 38
1 | | 26
1 | | 18
2 | 18 | 11
2 | 18 | 7
2 | 26 | 13
2 | 26 | 1
2 | 26 | 12
2 | 38 | 15
2 | 38 | 17
2 | 38 | 6
3 | 17 | 9
3 | 17 | 8
3 | 15 | 10
3 | 15 | 5
4 | 5 | 2
4 | 5 | 3
(17 rows)
But I have a little problem with the output.
If it's not obvious, here is the query tweaked a little below.
# with recursive x(level, parent, child) as (select 1::integer, * from
test_connect_by where parent is null union all select x.level + 1,
base.* from test_connect_by as base, x where base.parent = x.child)
select lpad(' ', 4*level - 1) || child from x;
?column?
------------------
38
26
18
11
7
13
1
12
15
17
6
9
8
10
5
2
3
(17 rows)
Can we get the rows in tree order, please? I.e. something like this:
?column?
------------------
38
15
10
5
2
3
17
9
8
6
26
13
1
12
18
11
7
(17 rows)
After all, I didn't specify any ORDER BY clauses in the base, recursive
or the final queries.
Also, it seems there are no infinite recursion detection:
# with recursive x(level, parent, child) as (
select 1::integer, * from test_connect_by where parent is null
union all
select x.level + 1, base.* from test_connect_by as base, x where
base.child = x.child
) select * from x;
... it waits and waits and waits ...
Also, there's another rough edge:
# with recursive x as (select * from test_connect_by where parent is
null) select * from x;
server closed the connection unexpectedly
This probably means the server terminated abnormally
before or while processing the request.
The connection to the server was lost. Attempting reset: Succeeded.
Best regards,
Zoltán Böszörményi
--
----------------------------------
Zoltán Böszörményi
Cybertec Schönig & Schönig GmbH
http://www.postgresql.at/
Attachments:
On Sun, May 18, 2008 at 5:22 PM, Zoltan Boszormenyi <zb@cybertec.at> wrote:
Can we get the rows in tree order, please? I.e. something like this:
Is ordering by tree order defined in the standard when no explicit
order is given? If not, it probably returns them in the order they
are pulled up, which might be the fastest way.
merlin
Merlin Moncure wrote:
On Sun, May 18, 2008 at 5:22 PM, Zoltan Boszormenyi <zb@cybertec.at> wrote:
Can we get the rows in tree order, please? I.e. something like this:
Is ordering by tree order defined in the standard when no explicit
order is given? If not, it probably returns them in the order they
are pulled up, which might be the fastest way
+1 for the fastest way, which I expect to often be "find all level 1
matches", "find all level 2 matches", ... If ORDER BY is important, it
should be specified (although it may be difficult or impossible to
properly represent ORDER BY for a tree? not sure?) I think most uses of
recursive require extra client side code to deal with anyways, so only
relative order is important (order within a particular branch).
There are things I'd like to use this for right now. Currently I use
plpgsql procedures to implement my own recursion. :-)
Cheers,
mark
--
Mark Mielke <mark@mielke.cc>
This is indeed really cool. I'm sorry I haven't gotten to doing what I
promised in this area but I'm glad it's happening anyways.
"Zoltan Boszormenyi" <zb@cybertec.at> writes:
Can we get the rows in tree order, please?
...
After all, I didn't specify any ORDER BY clauses in the base, recursive or the
final queries.
The standard has a clause to specify depth-first order. However doing a
depth-first traversal would necessitate quite a different looking plan and
it's far less obvious (to me anyways) how to do it.
Also, it seems there are no infinite recursion detection:
# with recursive x(level, parent, child) as (
select 1::integer, * from test_connect_by where parent is null
union all
select x.level + 1, base.* from test_connect_by as base, x where base.child
= x.child
) select * from x;
... it waits and waits and waits ...
Well, psql might wait and wait but it's actually receiving rows. A cleverer
client should be able to deal with infinite streams of records.
I think DB2 does produce a warning if there is no clause it can determine will
bound the results. But that's not actually reliable. It's quite possible to
have clauses which will limit the output but not in a way the database can
determine. Consider for example a tree-traversal for a binary tree stored in a
recursive table reference. The DBA might know that the data contains no loops
but the database doesn't.
--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's PostGIS support!
On Mon, May 19, 2008 at 12:21:20AM -0400, Gregory Stark wrote:
"Zoltan Boszormenyi" <zb@cybertec.at> writes:
Also, it seems there are no infinite recursion detection:
# with recursive x(level, parent, child) as (
select 1::integer, * from test_connect_by where parent is null
union all
select x.level + 1, base.* from test_connect_by as base, x where base.child
= x.child
) select * from x;
... it waits and waits and waits ...Well, psql might wait and wait but it's actually receiving rows. A
cleverer client should be able to deal with infinite streams of
records.
That would be a very good thing for libpq (and its descendants) to
have :)
I think DB2 does produce a warning if there is no clause it can
determine will bound the results. But that's not actually reliable.
I'd think not, as it's (in some sense) a Halting Problem.
It's quite possible to have clauses which will limit the output but
not in a way the database can determine. Consider for example a
tree-traversal for a binary tree stored in a recursive table
reference. The DBA might know that the data contains no loops but
the database doesn't.
I seem to recall Oracle's implementation can do this traversal on
write operations, but maybe that's just their marketing.
Cheers,
David.
--
David Fetter <david@fetter.org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter@gmail.com
Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate
"David Fetter" <david@fetter.org> writes:
On Mon, May 19, 2008 at 12:21:20AM -0400, Gregory Stark wrote:
"Zoltan Boszormenyi" <zb@cybertec.at> writes:
Also, it seems there are no infinite recursion detection:
# with recursive x(level, parent, child) as (
select 1::integer, * from test_connect_by where parent is null
union all
select x.level + 1, base.* from test_connect_by as base, x where base.child
= x.child
) select * from x;
... it waits and waits and waits ...Well, psql might wait and wait but it's actually receiving rows. A
cleverer client should be able to deal with infinite streams of
records.That would be a very good thing for libpq (and its descendants) to
have :)
I think you can do it in libpq.
In psql you can use \set FETCH_COUNT or somrthing like this (I can't look it
up just now) to use a cursor to do this too.
--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's 24x7 Postgres support!
Gregory Stark írta:
This is indeed really cool. I'm sorry I haven't gotten to doing what I
promised in this area but I'm glad it's happening anyways."Zoltan Boszormenyi" <zb@cybertec.at> writes:
Can we get the rows in tree order, please?
...
After all, I didn't specify any ORDER BY clauses in the base, recursive or the
final queries.The standard has a clause to specify depth-first order. However doing a
depth-first traversal would necessitate quite a different looking plan and
it's far less obvious (to me anyways) how to do it.
That would be even cooler to have it implemented as well.
Also, it seems there are no infinite recursion detection:
# with recursive x(level, parent, child) as (
select 1::integer, * from test_connect_by where parent is null
union all
select x.level + 1, base.* from test_connect_by as base, x where base.child
= x.child
) select * from x;
... it waits and waits and waits ...Well, psql might wait and wait but it's actually receiving rows. A cleverer
client should be able to deal with infinite streams of records.
I think it's the other way around. The server should not emit infinite
number of records.
I think DB2 does produce a warning if there is no clause it can determine will
bound the results. But that's not actually reliable. It's quite possible to
have clauses which will limit the output but not in a way the database can
determine. Consider for example a tree-traversal for a binary tree stored in a
recursive table reference. The DBA might know that the data contains no loops
but the database doesn't.
Well, a maintenance resjunk could be used like the branch column in
tablefunc::connectby().
--
----------------------------------
Zoltán Böszörményi
Cybertec Schönig & Schönig GmbH
http://www.postgresql.at/
On Mon, May 19, 2008 at 08:19:17AM +0200, Zoltan Boszormenyi wrote:
The standard has a clause to specify depth-first order. However doing a
depth-first traversal would necessitate quite a different looking plan and
it's far less obvious (to me anyways) how to do it.That would be even cooler to have it implemented as well.
From an implementation point of view, the only difference between
breadth-first and depth-first is that your tuplestore needs to be LIFO
instead of FIFO. However, just looking at the plan I don't know whether
it could support that kind of usage. At the very least I don't think
the standard tuplestore code can handle it.
Well, psql might wait and wait but it's actually receiving rows. A cleverer
client should be able to deal with infinite streams of records.I think it's the other way around. The server should not emit infinite
number of records.
The server won't, the universe will end first. This is a nice example
of the halting problem:
http://en.wikipedia.org/wiki/Halting_problem
Which was proved unsolvable a long time ago.
Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/
Show quoted text
Please line up in a tree and maintain the heap invariant while
boarding. Thank you for flying nlogn airlines.
Hi,
From: Zoltan Boszormenyi <zb@cybertec.at>
Subject: Re: [PATCHES] WITH RECURSIVE patch V0.1
Date: Mon, 19 May 2008 08:19:17 +0200
Also, it seems there are no infinite recursion detection:
# with recursive x(level, parent, child) as (
select 1::integer, * from test_connect_by where parent is null
union all
select x.level + 1, base.* from test_connect_by as base, x where base.child
= x.child
) select * from x;
... it waits and waits and waits ...Well, psql might wait and wait but it's actually receiving rows. A cleverer
client should be able to deal with infinite streams of records.I think it's the other way around. The server should not emit infinite
number of records.
How about adding new GUC parameter "max_recursive_call"?
Regards,
--
Yoshiyuki Asaba
y-asaba@sraoss.co.jp
Yoshiyuki Asaba írta:
Hi,
From: Zoltan Boszormenyi <zb@cybertec.at>
Subject: Re: [PATCHES] WITH RECURSIVE patch V0.1
Date: Mon, 19 May 2008 08:19:17 +0200Also, it seems there are no infinite recursion detection:
# with recursive x(level, parent, child) as (
select 1::integer, * from test_connect_by where parent is null
union all
select x.level + 1, base.* from test_connect_by as base, x where base.child
= x.child
) select * from x;
... it waits and waits and waits ...Well, psql might wait and wait but it's actually receiving rows. A cleverer
client should be able to deal with infinite streams of records.I think it's the other way around. The server should not emit infinite
number of records.How about adding new GUC parameter "max_recursive_call"?
Yes, why not?
MSSQL has a similar MAXRECURSION hint for WITH RECURSIVE queries
according to their docs.
http://msdn.microsoft.com/en-us/library/ms186243.aspx
Regards,
--
Yoshiyuki Asaba
y-asaba@sraoss.co.jp
--
----------------------------------
Zoltán Böszörményi
Cybertec Schönig & Schönig GmbH
http://www.postgresql.at/
Martijn van Oosterhout írta:
On Mon, May 19, 2008 at 08:19:17AM +0200, Zoltan Boszormenyi wrote:
The standard has a clause to specify depth-first order. However doing a
depth-first traversal would necessitate quite a different looking plan and
it's far less obvious (to me anyways) how to do it.That would be even cooler to have it implemented as well.
From an implementation point of view, the only difference between
breadth-first and depth-first is that your tuplestore needs to be LIFO
instead of FIFO. However, just looking at the plan I don't know whether
it could support that kind of usage. At the very least I don't think
the standard tuplestore code can handle it.Well, psql might wait and wait but it's actually receiving rows. A cleverer
client should be able to deal with infinite streams of records.I think it's the other way around. The server should not emit infinite
number of records.The server won't, the universe will end first.
The universe is alive and well, thank you. :-)
But the server won't emit infinite number of records, you are right.
Given the implementation uses a tuplestore and not producing the
tupleslots on the fly, it will go OOM first not the psql client,
I watched them in 'top'. It just takes a bit of time.
This is a nice example
of the halting problem:http://en.wikipedia.org/wiki/Halting_problem
Which was proved unsolvable a long time ago.
Hmpf, yes, I forgot too much about Turing-machines since university. :-(
Have a nice day,
--
----------------------------------
Zoltán Böszörményi
Cybertec Schönig & Schönig GmbH
http://www.postgresql.at/
Martijn van Oosterhout írta:
On Mon, May 19, 2008 at 08:19:17AM +0200, Zoltan Boszormenyi wrote:
The standard has a clause to specify depth-first order. However doing a
depth-first traversal would necessitate quite a different looking plan and
it's far less obvious (to me anyways) how to do it.That would be even cooler to have it implemented as well.
From an implementation point of view, the only difference between
breadth-first and depth-first is that your tuplestore needs to be LIFO
instead of FIFO.
Are you sure? I think a LIFO tuplestore would simply return reversed
breadth-first order. Depth-first means for every new record descend into
another recursion first then continue with the next record on the right.
However, just looking at the plan I don't know whether
it could support that kind of usage. At the very least I don't think
the standard tuplestore code can handle it.
--
----------------------------------
Zoltán Böszörményi
Cybertec Schönig & Schönig GmbH
http://www.postgresql.at/
On Mon, May 19, 2008 at 11:56:17AM +0200, Zoltan Boszormenyi wrote:
From an implementation point of view, the only difference between
breadth-first and depth-first is that your tuplestore needs to be LIFO
instead of FIFO.Are you sure? I think a LIFO tuplestore would simply return reversed
breadth-first order. Depth-first means for every new record descend into
another recursion first then continue with the next record on the right.
Say your tree looks like:
Root->A, D
A->B,C
D->E,F
LIFO pushes A and D. It then pops A and pushes B and C. B and C have no
children and are returned. Then D is popped and E and F pushed. So the
returned order is: A,B,C,D,E,F. You could also do B,C,A,E,F,D if you
wanted.
FIFO pushes A and D. It then pops A and puts B and C at *the end*. It
then pops D and pushes E and F at the end. So you get the order
A,D,B,C,E,F
Hope this helps,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/
Show quoted text
Please line up in a tree and maintain the heap invariant while
boarding. Thank you for flying nlogn airlines.
Martijn van Oosterhout írta:
On Mon, May 19, 2008 at 11:56:17AM +0200, Zoltan Boszormenyi wrote:
From an implementation point of view, the only difference between
breadth-first and depth-first is that your tuplestore needs to be LIFO
instead of FIFO.Are you sure? I think a LIFO tuplestore would simply return reversed
breadth-first order. Depth-first means for every new record descend into
another recursion first then continue with the next record on the right.Say your tree looks like:
Root->A, D
A->B,C
D->E,FLIFO pushes A and D. It then pops A and pushes B and C. B and C have no
children and are returned. Then D is popped and E and F pushed. So the
returned order is: A,B,C,D,E,F. You could also do B,C,A,E,F,D if you
wanted.FIFO pushes A and D. It then pops A and puts B and C at *the end*. It
then pops D and pushes E and F at the end. So you get the order
A,D,B,C,E,FHope this helps,
Thanks, I didn't consider popping elements off while processing.
However, if the toplevel query returns tuples in A, D order, you need
a positioned insert into the tuplestore, because the LIFO would pop D first.
Say, a "treestore" would work this way:
1. setup: treestore is empty, storage_position := 0
2. treestore_puttupleslot() adds slot at current position,
storage_position++
3. treestore_gettupleslot() removes slot from the beginning,
storage_position := 0
This works easily in memory lists but it's not obvious for me how it may
work
with disk backed temporary storage inside PG.
--
----------------------------------
Zoltán Böszörményi
Cybertec Schönig & Schönig GmbH
http://www.postgresql.at/
On Mon, May 19, 2008 at 05:57:17PM +0900, Yoshiyuki Asaba wrote:
Hi,
I think it's the other way around. The server should not emit
infinite number of records.How about adding new GUC parameter "max_recursive_call"?
Couldn't we just have it pay attention to the existing
max_stack_depth?
Cheers,
David.
--
David Fetter <david@fetter.org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter@gmail.com
Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate
On Sun, 2008-05-18 at 22:17 -0700, David Fetter wrote:
On Mon, May 19, 2008 at 12:21:20AM -0400, Gregory Stark wrote:
"Zoltan Boszormenyi" <zb@cybertec.at> writes:
Also, it seems there are no infinite recursion detection:
# with recursive x(level, parent, child) as (
select 1::integer, * from test_connect_by where parent is null
union all
select x.level + 1, base.* from test_connect_by as base, x where base.child
= x.child
) select * from x;
... it waits and waits and waits ...Well, psql might wait and wait but it's actually receiving rows. A
cleverer client should be able to deal with infinite streams of
records.That would be a very good thing for libpq (and its descendants) to
have :)I think DB2 does produce a warning if there is no clause it can
determine will bound the results. But that's not actually reliable.I'd think not, as it's (in some sense) a Halting Problem.
It's quite possible to have clauses which will limit the output but
not in a way the database can determine. Consider for example a
tree-traversal for a binary tree stored in a recursive table
reference. The DBA might know that the data contains no loops but
the database doesn't.I seem to recall Oracle's implementation can do this traversal on
write operations, but maybe that's just their marketing.
It may be possible to solve at least some of it by doing something
similar to hash version of DISTINCT by having an hashtable of tuples
already returned and not descending branches where you have already
been.
Show quoted text
Cheers,
David.
--
David Fetter <david@fetter.org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter@gmail.comRemember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate
On Sun, 2008-05-18 at 22:17 -0700, David Fetter wrote:
On Mon, May 19, 2008 at 12:21:20AM -0400, Gregory Stark wrote:
"Zoltan Boszormenyi" <zb@cybertec.at> writes:
Also, it seems there are no infinite recursion detection:
# with recursive x(level, parent, child) as (
select 1::integer, * from test_connect_by where parent is null
union all
select x.level + 1, base.* from test_connect_by as base, x where base.child
= x.child
) select * from x;
... it waits and waits and waits ...Well, psql might wait and wait but it's actually receiving rows. A
cleverer client should be able to deal with infinite streams of
records.That would be a very good thing for libpq (and its descendants) to
have :)I think DB2 does produce a warning if there is no clause it can
determine will bound the results. But that's not actually reliable.I'd think not, as it's (in some sense) a Halting Problem.
It's quite possible to have clauses which will limit the output but
not in a way the database can determine. Consider for example a
tree-traversal for a binary tree stored in a recursive table
reference. The DBA might know that the data contains no loops but
the database doesn't.I seem to recall Oracle's implementation can do this traversal on
write operations, but maybe that's just their marketing.
It may be possible to solve at least some of it by doing something
similar to hash version of DISTINCT by having an hashtable of tuples
already returned and not descending branches where you have already
been.
Show quoted text
Cheers,
David.
--
David Fetter <david@fetter.org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter@gmail.comRemember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate
"Martijn van Oosterhout" <kleptog@svana.org> writes:
From an implementation point of view, the only difference between
breadth-first and depth-first is that your tuplestore needs to be LIFO
instead of FIFO.
I think it's not so simple. How do you reconcile that concept with the join
plans like merge join or hash join which expect you to be able to be able to
process the records in a specific order?
It sounds like you might have to keep around a stack of started executor nodes
or something but hopefully we can avoid anything like that because, well, ick.
--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's PostGIS support!
Gregory Stark írta:
"Martijn van Oosterhout" <kleptog@svana.org> writes:
From an implementation point of view, the only difference between
breadth-first and depth-first is that your tuplestore needs to be LIFO
instead of FIFO.I think it's not so simple. How do you reconcile that concept with the join
plans like merge join or hash join which expect you to be able to be able to
process the records in a specific order?It sounds like you might have to keep around a stack of started executor nodes
or something but hopefully we can avoid anything like that because, well, ick.
If I understand the code right, the recursion from level N to level N+1
goes like this:
collect all records from level N and JOIN it with the recursive query.
This way
we get all level 1 records from the base query, then all records at the
second level, etc.
This is how it gets breadth-first ordering.
Depth-first ordering could go like this: get only 1 from the current
level then go
into recursion. Repeat until there are no records in the current level.
The only difference would be more recursion steps. Instead of one per level,
there would be N per level if there are N tuples in the current level.
Definitely
slower then the current implementation but comparable with the tablefunc.c
connectby() code.
--
----------------------------------
Zoltán Böszörményi
Cybertec Schönig & Schönig GmbH
http://www.postgresql.at/
On May 19, 1:17 am, da...@fetter.org (David Fetter) wrote:
On Mon, May 19, 2008 at 12:21:20AM -0400, Gregory Stark wrote:
It's quite possible to have clauses which will limit the output but
not in a way the database can determine. Consider for example a
tree-traversal for a binary tree stored in a recursive table
reference. The DBA might know that the data contains no loops but
the database doesn't.I seem to recall Oracle's implementation can do this traversal on
write operations, but maybe that's just their marketing.
That's how I implement (id, name, parent)-trees as a DBA, having an
insert/update trigger function check_no_loops(), but I'm not sure that
it would be faster than the hash method suggested by Hannu Krosing. I
guess it depends on whether you're inserting/updating or selecting
more. Does it make sense to leave the option to the user, whether to
check for infinite recursion just in time or not?
Kev
On Sun, May 18, 2008 at 08:51:29PM +0900, Tatsuo Ishii wrote:
WITH RECURSIVE patch V0.1
Here are patches to implement WITH RECURSIVE clause. There are some
limitiations and TODO items(see the "Current limitations" section
below). Comments are welcome.1. Credit
These patches were developed by Yoshiyuki Asaba (y-asab@sraoss.co.jp)
with some discussions with Tatsuo Ishii (ishii@sraoss.co.jp).This is really great! Kudos to all who made this happen :)
Thanks. In addition to above, Sumitomo Electric Information Systems
Co., and SRA OSS, Inc. Japan made this happen.
I and Yoshiyuki Asaba are now in Ottawa to join PGCon. I hope to have
some discussions on this here with anyone who are interested in this.
--
Tatsuo Ishii
SRA OSS, Inc. Japan
Show quoted text
I tried a bunch of different queries, and so far, only these two
haven't worked. Any ideas what I'm doing wrong here?WITH RECURSIVE t(n) AS (
SELECT 1
UNION ALL
SELECT n+1
FROM t
WHERE n < 100
)
SELECT * FROM t;
ERROR: cannot extract attribute from empty tuple slotWITH RECURSIVE t(n) AS (
VALUES (1)
UNION ALL
SELECT n+1
FROM t
WHERE n < 100
)
SELECT * FROM t;
ERROR: cannot extract attribute from empty tuple slotCheers,
David.
--
David Fetter <david@fetter.org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter@gmail.comRemember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate
Hi,
From: David Fetter <david@fetter.org>
Subject: Re: [HACKERS] [PATCHES] WITH RECURSIVE patch V0.1
Date: Mon, 19 May 2008 04:36:30 -0700
I think it's the other way around. The server should not emit
infinite number of records.How about adding new GUC parameter "max_recursive_call"?
Couldn't we just have it pay attention to the existing
max_stack_depth?
Recursive query does not consume stack. The server enters an infinite
loop without consuming stack. Stack-depth error does not happen.
Regards,
--
Yoshiyuki Asaba
y-asaba@sraoss.co.jp
"Yoshiyuki Asaba" <y-asaba@sraoss.co.jp> writes:
Hi,
From: David Fetter <david@fetter.org>
Subject: Re: [HACKERS] [PATCHES] WITH RECURSIVE patch V0.1
Date: Mon, 19 May 2008 04:36:30 -0700I think it's the other way around. The server should not emit
infinite number of records.How about adding new GUC parameter "max_recursive_call"?
Couldn't we just have it pay attention to the existing
max_stack_depth?Recursive query does not consume stack. The server enters an infinite
loop without consuming stack. Stack-depth error does not happen.
We could have a separate guc variable which limits the maximum number of
levels of recursive iterations. That might be a useful feature for DBAs that
want to limit their users from issuing an infinite query.
Note that users can always construct their query to limit the number of
recursive iterations. So this would only be useful for DBAs that don't trust
their users and want to impose a limit. It doesn't add any actual expressive
power that SQL doesn't have already.
The recursive query syntax in the spec actually does include the ability to
assign an output column to show what level of recursive iteration you're on.
So alternately we could have a GUC variable which just allows the DBA to
prohibit any recursive query without such a column and a fiter imposing a
maximum value on it. That's probably the most appropriate option.
--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's Slony Replication support!
Couldn't we just have it pay attention to the existing
max_stack_depth?Recursive query does not consume stack. The server enters an infinite
loop without consuming stack. Stack-depth error does not happen.We could have a separate guc variable which limits the maximum number of
levels of recursive iterations. That might be a useful feature for DBAs that
want to limit their users from issuing an infinite query.
statement_timeout :)
Joshua D. Drake
"Joshua D. Drake" <jd@commandprompt.com> writes:
Couldn't we just have it pay attention to the existing
max_stack_depth?Recursive query does not consume stack. The server enters an infinite
loop without consuming stack. Stack-depth error does not happen.We could have a separate guc variable which limits the maximum number of
levels of recursive iterations. That might be a useful feature for DBAs that
want to limit their users from issuing an infinite query.statement_timeout :)
Good point.
Though it occurs to me that if you set FETCH_COUNT in psql (or do the
equivalent in your code ) statement_timeout becomes much less useful.
--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's On-Demand Production Tuning
Hi,
From: David Fetter <david@fetter.org>
Subject: Re: [PATCHES] WITH RECURSIVE patch V0.1
Date: Sun, 18 May 2008 11:47:37 -0700
I tried a bunch of different queries, and so far, only these two
haven't worked. Any ideas what I'm doing wrong here?WITH RECURSIVE t(n) AS (
SELECT 1
UNION ALL
SELECT n+1
FROM t
WHERE n < 100
)
SELECT * FROM t;
ERROR: cannot extract attribute from empty tuple slot
Thank you for the report. I've fixed.
postgres=# WITH RECURSIVE t(n) AS (
SELECT 1
UNION ALL
SELECT n+1
FROM t
WHERE n < 100
)
SELECT count(*) FROM t;
count
-------
100
(1 row)
Regards,
--
Yoshiyuki Asaba
y-asaba@sraoss.co.jp
On Sat, May 24, 2008 at 03:21:01AM +0900, Yoshiyuki Asaba wrote:
Hi,
From: David Fetter <david@fetter.org>
Subject: Re: [PATCHES] WITH RECURSIVE patch V0.1
Date: Sun, 18 May 2008 11:47:37 -0700I tried a bunch of different queries, and so far, only these two
haven't worked. Any ideas what I'm doing wrong here?WITH RECURSIVE t(n) AS (
SELECT 1
UNION ALL
SELECT n+1
FROM t
WHERE n < 100
)
SELECT * FROM t;
ERROR: cannot extract attribute from empty tuple slotThank you for the report. I've fixed.
postgres=# WITH RECURSIVE t(n) AS (
SELECT 1
UNION ALL
SELECT n+1
FROM t
WHERE n < 100
)
SELECT count(*) FROM t;
count
-------
100
(1 row)Regards,
--
Yoshiyuki Asaba
y-asaba@sraoss.co.jp
Great!
Where is the new patch?
Cheers,
David.
--
David Fetter <david@fetter.org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter@gmail.com
Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate
Hi,
From: David Fetter <david@fetter.org>
Subject: Re: [PATCHES] WITH RECURSIVE patch V0.1
Date: Fri, 23 May 2008 11:26:30 -0700
Where is the new patch?
I will create the revised patch on June.
This is a patch for this problem.
*** ../../pgsql/src/backend/executor/nodeRecursivescan.c 2008-05-24 04:45:23.000000000 +0900
--- src/backend/executor/nodeRecursivescan.c 2008-05-24 04:47:54.000000000 +0900
***************
*** 37,43 ****
node->ss.ps.state->es_tuplestorestate = tuplestore_begin_heap(true, false, work_mem);
}
! slot = node->ss.ps.ps_ResultTupleSlot;
if (tuplestore_gettupleslot(node->ss.ps.state->es_tuplestorestate, true, slot))
return slot;
--- 37,43 ----
node->ss.ps.state->es_tuplestorestate = tuplestore_begin_heap(true, false, work_mem);
}
! slot = node->ss.ss_ScanTupleSlot;
if (tuplestore_gettupleslot(node->ss.ps.state->es_tuplestorestate, true, slot))
return slot;
Regards,
--
Yoshiyuki Asaba
y-asaba@sraoss.co.jp
On Sat, May 24, 2008 at 05:01:11AM +0900, Yoshiyuki Asaba wrote:
Hi,
From: David Fetter <david@fetter.org>
Subject: Re: [PATCHES] WITH RECURSIVE patch V0.1
Date: Fri, 23 May 2008 11:26:30 -0700Where is the new patch?
I will create the revised patch on June. This is a patch for this
problem.
Thanks very much :)
Cheers,
David.
--
David Fetter <david@fetter.org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter@gmail.com
Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate
Hi,
From: Zoltan Boszormenyi <zb@cybertec.at>
Subject: Re: [PATCHES] WITH RECURSIVE patch V0.1
Date: Sun, 18 May 2008 23:22:02 +0200
But I have a little problem with the output.
If it's not obvious, here is the query tweaked a little below.
...
Can we get the rows in tree order, please? I.e. something like this:
?column?
------------------
38
15
10
5
2
3
17
9
8
6
26
13
1
12
18
11
7
(17 rows)
No, you can't. However, you can obtain recursive path by using ARRAY
type, as another way. Here is a sample SQL.
WITH RECURSIVE x(level, parent, child, path) AS
(SELECT 1::integer, * , array[child] FROM test_connect_by
WHERE parent IS NULL
UNION ALL
SELECT x.level + 1, base.*, array_append(path, base.child)
FROM test_connect_by AS base, x WHERE base.parent = x.child
)
SELECT path, array_to_string(path, '->') FROM x
WHERE NOT EXISTS (SELECT 1 FROM test_connect_by WHERE parent =
x.child);
path | array_to_string
-------------+-----------------
{18,11} | 18->11
{18,7} | 18->7
{26,13} | 26->13
{26,1} | 26->1
{26,12} | 26->12
{38,6} | 38->6
{38,17,9} | 38->17->9
{38,17,8} | 38->17->8
{38,15,10} | 38->15->10
{38,15,5,2} | 38->15->5->2
{38,15,5,3} | 38->15->5->3
(11 rows)
Regards,
--
Yoshiyuki Asaba
y-asaba@sraoss.co.jp
On Sun, May 18, 2008 at 08:51:29PM +0900, Tatsuo Ishii wrote:
WITH RECURSIVE patch V0.1
Please find updated patch with bug fixes from Yoshiyuki Asaba and
Michael Meskes. Any mistakes in it are mine. :)
Cheers,
David.
--
David Fetter <david@fetter.org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter@gmail.com
Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate
Attachments:
recursive_query-2.patch.gzapplication/x-gzipDownload
��8H recursive_query-2.patch �\{s����[����V�)�=�kw\�i���9�����
EAk�TH��OO�����I������{=���b����e8��H{�S����������p��������s��v��o���9\����K�C�!��(=\-���a���NL���~� 1���QH��5������t<���3�E����0���#��'b���X�#�<���c�O�s�t:�x�*���=�%P�D={l��a�� ���!���������j=���*t�)9!��t��Oc���������Q=G�4o�U�rz�V��;?�wWg�N��R�������w�||}���qe|��`M��
����U�@9�`�dR3�WnJc�
��r�_t�!F=c0�C�Mch����y��R:�g4L��O���$�������-��A ����m, �{�4���&�����Sb�q����k7\��ip����STA�N�4��
��^����s��4�{B�-o��PC��H�B����$�qJ������vaq��C1�)�kC�@��pFNN��������������=����
����;�0�nY����.��2�G�$�
����w���y�����lF��:H�
�
��5���2��AnH�i��t�ES�����8(}Op$lL8���Yg� ����I�S���d=}���N*(��T� ?.��I]���{T� ��Uso��4
�6R��ZOe��<�I�2����3�}p ��n�����Z���$bt��O�u�D�dB��
c����_�}�2�L�a��S��Q#�m��Y�4��c�V��sY���(<���W����uE��8ma��L�r��0mYc��NE|5���f18�Ct��3#�52�>_�D��)dQ�)�W1<�SG�#uWh�r6�J��n��2��_#_���$i�����;_��^�$
�h%(_�C/�9Qx]��x���EU��
M�$��(��oC�DU~��^^���l�C�W�67|A�N� �n��xJ�_���)P����F� ��d�'������p�S���t�o��&w����_d�R��!�{�8��\�Z����,��k�k���z��X�z���3]�cN?�%��mX���`
}7��`���������E DuD��oA%VAS�b]5����L��
(���76������a
L�] 3����o��}S��P��o|�~H��Kh�v���mvT���U[h�<(�[�MN�K�>��{C����.�m�N���7������Y��|��wo��V��H�Y7�zl��\Ge������fZ��m���m�e�!��?Aky?�Imy�7�59��z��v%�1-�r�2�+jV�~�_������! ��������c��x�$�����z�8���,J���7�7q���}���KRvlRB#��� t�6�D��1V2^cLSX� >$$�H�0���K�7tZ#���H���Yb8f���
f2��>�2����]� s"R������d� GF�ng�r�Mrh�i���Y��5����t\H�n������v
o����>��x%��Pl��TNO ��p�8��>��g"���
�u�E���Zf(�~�Z��������U@E����*��B������h8`��SY?1���OkW�������e������@�]\�U\��(�y��� JI#��U\PN�g��k�g{�a���6�vz�|+v�=��r��To�_r9�
ht4zEl;��4�� ��~i#q�>��<?�_��Ry� �u!������1��zD�C���������>�ch��H����"tU�Z|>t
�|�����u�\�j���A-6/0y&2�p4��
�?ft�^4�T�;#�)�2|�L�(`�� ?[�� a�9�$�����4��1u�m;����xnW+_c� �}t�Z�0S��f~3!)��O�4��O�Kv��.�iD��<�$]����p�+U�P�QZ�v��Z�`u����CX���1�OF���?�P7� vf��=���n�5(�m�D���p�F���;M�G�x��)��5T3�� � `>�o���B�8��)���R{ ��9��M��>#l��eh�EY���*���$�d"o=�v��9�4�9*��a;�>�hFEBJg�|
a%8�~8���z�:�[�,���%��KR�U��c�����z9]�A�����y����1�eW ���������'�� �;��" =a�4�����K��kp| ���| 3��i�/�iSh�-o����fY?�#�Ew040����'h����:f&~�B-3v?i��G_�e
��d+��1��[jV� ��AB?��4����C/Z=����|�Z��vm:��gx&����Y���@��&�9r`5��U�h���,�{g�=[�,�����w�,����N��l���"��W��
��jn`G�x��������#� B��{GY(�/��keL47���-I�+{��$0�4�%���r<*���`��K� ���������x�,&��u�vp����W�_L^\^���-.�� ��Tnr"�H*����w^��:�N�h^�J�;��nd]�4p�?y*�4�p3�� "����]����4��� sL\6�M|�In���\��������I��q��������o���U�3����!����5���em��0gj�f���L�[d��������<�����~&~�/:y��\>���X�1�p+w������f�����-9�d���Xu@�v���,(L����t�m�Id�v���J1� B�� �E1Nb����R���u��}�dx/��dI�� ]��b4�C�Q�G�}�2��z��?p�h���(�����8�����f54,�5 �$M�&0��B�� ��;�0
�(?��@t����z���]p��Yu���5v@ocGI�Y��� ���2��qW�yBS}����jk�#����P*$��B��%Z���������E8&�0 LP�c������,�:�*� �U'r��gl�VK�E��-�o)r���Y��a�C���c����X[%������V�(������Y#P��`��z��^�z�P�X#����0���j���7�!�Z%(��Y���fBb����������*D��.������� T�
[ ��3��xnf ��Qm�����J����0jRP����F�L3s~�����E&���.��$���B�/�Jt�0�-cd+@b����(���,M���"`�D+T�8���<j*�hX��> Z�!���PY��FM����"jU�thK3B=��pk�\�e�Ua�E^�&�e���a�[��3C����lC�aK 5���j��D0zF�a0�hd�
6 ��t��Eh4�R�Er}�� Z�������w�A���L�����b�Mi��m�z
�e�Ai�,B�C��0�@9 �_6$�-B%��r�����V���?�\�w�k�W����3b����v��F��&���UR;bc\;&#k��eb������F<��c �,��a��`E���.�: j�L��F��������L��G��~�������������U�������t�jNYP(���wg�u����>��b�G��_����h*�@O���*ATh���\�~�*�a�ri��<�K4���AU�&\`�fF���Q���_������^���q��O)�k#V��x�*C�A Mz��o�-.�����%>���6C
�^�HA�,o�����7�h���R��n�e�������J�T��e!ZE���8����}oU�m+uH����y��a�58�Q]J��m�2�����
�b�* j
V�T��=�x�Z�����AP�*��/��tyK��2P�V��/���/��DBS�v��rle�G����(�1+����3AVB��^�5���{B�$a���1c"|!������4fm5�0%�Z�����*=�rm?��9�����o�U�%?���nE��JT�Y�L0�5A�[��K('��B��.Jl2�aV��r=��������8�l�ADA�x������G#�����}�6��F��F#L�+���}"�&�c9Y��<%.(|��?.��?w�Z:�Z@e�O���g��P������,��}����$6BE�����[Fu�|�)��k�]� ����� 9C�����1P����1�
k�����V��5^�3�v.6'����!ABq���Z>�h�S,��U+�;3av �(a���S�t\���/�G$�<�*�<��Ek���Z�b,P������pS��
\�B�tyG��������1�����Q��;JWj0�x�����N�bW������N�����x���Yn�+�
�g����I@�E���-���2MQ�=r@�=��+��1����_���.����{_�3��g�.f/�4����MS�[��w�Xp�fAZ�C�K��b
X�{���N��S�����������?n���N�3�~�+�K;�u� ���/$~`?_YB�O�{���G���/5�i�JU���
��p*�NZ�S��GL��"P�2������p��<��D_ yd��``}Q����%��K����*�>D���)�
��4��K
�cOW�M�������(�0�"Se�tl ��G�|t���x��V ]�"4�������@f}8�� ~���F��d�Ee���vHgU����y����`\� y�RMO�P���WD
=���/�,�r%�**M�7���U���Q�#O��4�����e���(����73"^H�C�ng���o�d!s
�d�=^7�d� ���[F)��J�A ��������{6������2��^�h,�d���y�Q�S�1 ���Q�E�����H������-�����Z�G��CP�. ��0���`,BR��s�+������u%�*o��k&W3���^��'S�� �b��>��M,v2��B/�����G��o��0:\�l��6Y��Y���J��UX����[� ��������1��
�-E����%��� @P���������pUD�w�����<�C�ow���B�C/I3�gQ�\��x�������^���zN� �Dlc��K���0,���xxD ��)8�'� ���>��PB��/�z�nw��3�bW������y��~{J�\�5��ad��]���$���j[�B�x��\����
H��_��bv�c4O�=H�}�x23�4�x�
���AB�=:�=0;��w'+� ���EM/�n'9o���[��(d��k�M�
���#.����D�a��;���)���"��90e������z��l�p��� �1�?���8�t����K�����.C����D6L���^a�~�4� �q�������l���B��`�B�|�D�����Y$��Y
8�8Z�>���&�w��f�]�1� x�����Us��
��"�r����qF��O���w� �q��V4*[���J7�����q����]�2��H���me�
�?c��}Z�_�&�O�2�������]I��6Rk�y�&���L������o3�K�f���,�1
�5R��+�=>!��������YW'�]���|���%��/u�'�5���o���v7�(�q�(I���
��\�������$x&�6d�sJ���o�:�;G���W����������7��'���������_����B���C�w��|�wIY���
:_Ys�x��� _W����9e���p�_��f��S7�h;A&�yq��E�j=X<a�Y�!��Zr~*�y�{�R5"��<�T������� !��k�7}@<��B��i��y�E�-���U����LS��m�q���Uu_o�M8�������G��r����+4����x�YW��8F�J�|�c�t�a����vi��f��U^-u\������� d}l1Qq�
l
���������Yp)������l�F�dT�F ��K�G��[�x��dv�q���
+��������T�u
�m9��5F�F�����\���+x�����f�A� �L#������U��i�X���gO�H�g�W�u��#��CJ��q��"!������`$q���6������Q=���F�������guu�K�mWKt�-@�%��*��O�����9��e��sR M�ph�����.=MK%`�s�����,=���������$�Q�]�9AJ��g
��H\��_�d�P_�)���������VJ����-jY�
��W��l��}[�G�pAD"0�|0�7���[�����B�
ZC&����r��0(S����PS�1,�=o�h�� c�����E�b���Z�h=�f�LS�[1��%MQ��I�b���@6�f��wey%!�%�P����q�C�s
� ����E����Dr4��(*�
��v����Hv�+���d#J��b�������I5�!#Q+�����cG�S�J�M?�l(���o�HsJ
����GA���p%���C�������B���� s���lQj�g����������
o��3����g(E�b�*�P=en:���d9�z������;����n)����5��rJN�
w� Re����((����w�g�,=)M�����d�*��g��$S�v^�'�
��:yQ�y�`fO�~�g�F�9�"`������]���$��� ��������(^��=��>y~����T �j#(z�q�����/�i�����0��Y�F�����a7��3�ILp����J
p�.�����)l�{HHI-���� �v2D�fr �f~Y8h�$�������������V�t�@3��n�i1n8�n�����y ��������(2�`�o��{��h������V��� �\je�sR0�M}>���I���s
6 B+�u��/�l��������#����:�����@�X�����'y��k%':��1�U5�����y�W�Z�_�^��J3��l���#�<�[k���>�zp����J>�k,��B���sl(�u� ��5��}�U��}�dF�+On����1X")����>B�]�.��Q����� ����(P�CL�# %�����-\��(�G�7��7����kF���RE�IM
4����f �wO�]�2MSB�}�s����;@������e#�'%'t������5�pT$�#��gfD�Ts������uxFV�V��?��g��wt?�s���B�nw�ul��:r�U����������f- �t���u�iu�1qd#}\9����z�N���Q-����<3��W��-�����ec������}������JeHKR��r��*,���t�a��AO�W�Z�Um������h��k�%�>.�����OK��;&(o��a4�Nv���qT�F�5�jb��1L�V>�1��� ��� 6�����
��� �D :/�~ �������>^��b����q���m1m:�9�,c�{hz�oP4o���
5�q8[N!u�`_���A���G�^`�1 �F�� �vZ�.����"�v�
dT;
�@#~�J�������t�.'����q�/$��E����O���YW�����7��N���w��p��(Kl�P�����\G�\���*�`��b�y_?���3�ls�J�5w�����jE����
���u�]�QR��6�P�K�u/YT8(�:�����# ���R� �ri,�D,ND�<!O;$YM-Je�1P-���9�)� y�����"�v��t��y�^t���
!��: ��d��"�L�ZbY�H,i��SI�O�5x�V����d��TY��X
���pA��8���,���w����X�5B��q4��H�$�%��H�SD����\��L�� ��E��j��+� ������X�NN�m? �/�������v0�����P.>�u��V��X��R��Z9(�����:t����K�B ��_�(~����Yi!��S�i��T&�8=��p$���G��/m�����
: �
�R��*�It��H�T[����S�7�z�&������`����������)�[''�FEe0a2��*;��WHi�@�D��`4��}�� ���$�B�&��f�7�}94��N��+����?�:1���+��r1�����{���d� U���P�)����|N�f{F��:O`}d��DK��2,�AL-��E,��o,����Dy��}t�:QT�/�����T���{T�R��q�`��fW��fP���>[�*@Q��:�
e�.>�����%���Pt~���'����y{���cYq/��RY�)�9%�����'���
I4q�E��Y������� �~G�s�!�D�|M��X@�!�&�`S�=�Q���-�CHY��)�p�J��K9%���xmj�4c��$E~g\`�+XsY�Ql��J �''��#����Q��F�����J���B����6J��i�K7��Tn`��{�����O��r�1=�������r�Z/I����{��lSn���i���V�������8������U�����]��1~f�_I|#�n�l���f����:$�+��%�X��| ��hic������
�U�+��k�X��`\��J��b�xX�R0K+��
��NY"p�Ai���h����������r2M���t��k`�1�}[��eV����@^2�1 �cQ���b���EZ���,TS��FL1�n�K��D1(�!�I�D���P���8��k��%���4�0d���<&J���9$��������
��% ������T�aG�!�~��l�.SB�@�:^�{Ooag�<