| 1 |
src/backend/optimizer/plan/README |
| 2 |
|
| 3 |
Subselects |
| 4 |
========== |
| 5 |
|
| 6 |
Vadim B. Mikheev |
| 7 |
|
| 8 |
|
| 9 |
From [email protected] Fri Feb 13 09:01:19 1998 |
| 10 |
Received: from renoir.op.net ([email protected] [209.152.193.4]) |
| 11 |
by candle.pha.pa.us (8.8.5/8.8.5) with ESMTP id JAA11576 |
| 12 |
for <[email protected]>; Fri, 13 Feb 1998 09:01:17 -0500 (EST) |
| 13 |
Received: from hub.org (hub.org [209.47.148.200]) by renoir.op.net (o1/$Revision: 1.14 $) with ESMTP id IAA09761 for <[email protected]>; Fri, 13 Feb 1998 08:41:22 -0500 (EST) |
| 14 |
Received: from localhost (majordom@localhost) by hub.org (8.8.8/8.7.5) with SMTP id IAA08135; Fri, 13 Feb 1998 08:40:17 -0500 (EST) |
| 15 |
Received: by hub.org (TLB v0.10a (1.23 tibbs 1997/01/09 00:29:32)); Fri, 13 Feb 1998 08:38:42 -0500 (EST) |
| 16 |
Received: (from majordom@localhost) by hub.org (8.8.8/8.7.5) id IAA06646 for pgsql-hackers-outgoing; Fri, 13 Feb 1998 08:38:35 -0500 (EST) |
| 17 |
Received: from dune.krasnet.ru (dune.krasnet.ru [193.125.44.86]) by hub.org (8.8.8/8.7.5) with ESMTP id IAA04568 for <[email protected]>; Fri, 13 Feb 1998 08:37:16 -0500 (EST) |
| 18 |
Received: from sable.krasnoyarsk.su (dune.krasnet.ru [193.125.44.86]) |
| 19 |
by dune.krasnet.ru (8.8.7/8.8.7) with ESMTP id UAA13717 |
| 20 |
for <[email protected]>; Fri, 13 Feb 1998 20:51:03 +0700 (KRS) |
| 21 |
(envelope-from [email protected]) |
| 22 |
Message-ID: <[email protected]> |
| 23 |
Date: Fri, 13 Feb 1998 20:50:50 +0700 |
| 24 |
From: "Vadim B. Mikheev" <[email protected]> |
| 25 |
Organization: ITTS (Krasnoyarsk) |
| 26 |
X-Mailer: Mozilla 4.04 [en] (X11; I; FreeBSD 2.2.5-RELEASE i386) |
| 27 |
MIME-Version: 1.0 |
| 28 |
To: PostgreSQL Developers List <[email protected]> |
| 29 |
Subject: [HACKERS] Subselects are in CVS... |
| 30 |
Content-Type: text/plain; charset=us-ascii |
| 31 |
Content-Transfer-Encoding: 7bit |
| 32 |
Sender: [email protected] |
| 33 |
Precedence: bulk |
| 34 |
Status: OR |
| 35 |
|
| 36 |
This is some implementation notes and opened issues... |
| 37 |
|
| 38 |
First, implementation uses new type of parameters - PARAM_EXEC - to deal |
| 39 |
with correlation Vars. When query_planner() is called, it first tries to |
| 40 |
replace all upper queries Var referenced in current query with Param of |
| 41 |
this type. Some global variables are used to keep mapping of Vars to |
| 42 |
Params and Params to Vars. |
| 43 |
|
| 44 |
After this, all current query' SubLinks are processed: for each SubLink |
| 45 |
found in query' qual union_planner() (old planner() function) will be |
| 46 |
called to plan corresponding subselect (union_planner() calls |
| 47 |
query_planner() for "simple" query and supports UNIONs). After subselect |
| 48 |
are planned, optimizer knows about is this correlated, un-correlated or |
| 49 |
_undirect_ correlated (references some grand-parent Vars but no parent |
| 50 |
ones: uncorrelated from the parent' point of view) query. |
| 51 |
|
| 52 |
For uncorrelated and undirect correlated subqueries of EXPRession or |
| 53 |
EXISTS type SubLinks will be replaced with "normal" clauses from |
| 54 |
SubLink->Oper list (I changed this list to be list of EXPR nodes, |
| 55 |
not just Oper ones). Right sides of these nodes are replaced with |
| 56 |
PARAM_EXEC parameters. This is second use of new parameter type. |
| 57 |
At run-time these parameters get value from result of subquery |
| 58 |
evaluation (i.e. - from target list of subquery). Execution plan of |
| 59 |
subquery itself becomes init plan of parent query. InitPlan knows |
| 60 |
what parameters are to get values from subquery' results and will be |
| 61 |
executed "on-demand" (for query select * from table where x > 0 and |
| 62 |
y > (select max(a) from table_a) subquery will not be executed at all |
| 63 |
if there are no tuples with x > 0 _and_ y is not used in index scan). |
| 64 |
|
| 65 |
SubLinks for subqueries of all other types are transformed into |
| 66 |
new type of Expr node - SUBPLAN_EXPR. Expr->args are just correlation |
| 67 |
variables from _parent_ query. Expr->oper is new SubPlan node. |
| 68 |
|
| 69 |
This node is used for InitPlan too. It keeps subquery range table, |
| 70 |
indices of Params which are to get value from _parent_ query Vars |
| 71 |
(i.e. - from Expr->args), indices of Params into which subquery' |
| 72 |
results are to be substituted (this is for InitPlans), SubLink |
| 73 |
and subquery' execution plan. |
| 74 |
|
| 75 |
Plan node was changed to know about dependencies on Params from |
| 76 |
parent queries and InitPlans, to keep list of changed Params |
| 77 |
(from the above) and so be re-scanned if this list is not NULL. |
| 78 |
Also, added list of InitPlans (actually, all of them for current |
| 79 |
query are in topmost plan node now) and other SubPlans (from |
| 80 |
plan->qual) - to initialize them and let them know about changed |
| 81 |
Params (from the list of their "interests"). |
| 82 |
|
| 83 |
After all SubLinks are processed, query_planner() calls qual' |
| 84 |
canonificator and does "normal" work. By using Params optimizer |
| 85 |
is mostly unchanged. |
| 86 |
|
| 87 |
Well, Executor. To get subplans re-evaluated without ExecutorStart() |
| 88 |
and ExecutorEnd() (without opening and closing relations and indices |
| 89 |
and without many palloc() and pfree() - this is what SQL-funcs does |
| 90 |
on each call) ExecReScan() now supports most of Plan types... |
| 91 |
|
| 92 |
Explanation of EXPLAIN. |
| 93 |
|
| 94 |
vac=> explain select * from tmp where x >= (select max(x2) from test2 |
| 95 |
where y2 = y and exists (select * from tempx where tx = x)); |
| 96 |
NOTICE: QUERY PLAN: |
| 97 |
|
| 98 |
Seq Scan on tmp (cost=40.03 size=101 width=8) |
| 99 |
SubPlan |
| 100 |
^^^^^^^ subquery is in Seq Scan' qual, its plan is below |
| 101 |
-> Aggregate (cost=2.05 size=0 width=0) |
| 102 |
InitPlan |
| 103 |
^^^^^^^^ EXISTS subsubquery is InitPlan of subquery |
| 104 |
-> Seq Scan on tempx (cost=4.33 size=1 width=4) |
| 105 |
-> Result (cost=2.05 size=0 width=0) |
| 106 |
^^^^^^ EXISTS subsubquery was transformed into Param |
| 107 |
and so we have Result node here |
| 108 |
-> Index Scan on test2 (cost=2.05 size=1 width=4) |
| 109 |
|
| 110 |
|
| 111 |
Opened issues. |
| 112 |
|
| 113 |
1. No read permissions checking (easy, just not done yet). |
| 114 |
2. readfuncs.c can't read subplan-s (easy, not critical, because of |
| 115 |
we currently nowhere use ascii representation of execution plans). |
| 116 |
3. ExecReScan() doesn't support all plan types. At least support for |
| 117 |
MergeJoin has to be implemented. |
| 118 |
4. Memory leaks in ExecReScan(). |
| 119 |
5. I need in advice: if subquery introduced with NOT IN doesn't return |
| 120 |
any tuples then qualification is failed, yes ? |
| 121 |
6. Regression tests !!!!!!!!!!!!!!!!!!!! |
| 122 |
(Could we use data/queries from MySQL' crash.me ? |
| 123 |
Copyright-ed ? Could they give us rights ?) |
| 124 |
7. Performance. |
| 125 |
- Should be good when subquery is transformed into InitPlan. |
| 126 |
- Something should be done for uncorrelated subqueries introduced |
| 127 |
with ANY/ALL - keep thinking. Currently, subplan will be re-scanned |
| 128 |
for each parent tuple - very slow... |
| 129 |
|
| 130 |
Results of some test. TMP is table with x,y (int4-s), x in 0-9, |
| 131 |
y = 100 - x, 1000 tuples (10 duplicates of each tuple). TEST2 is table |
| 132 |
with x2, y2 (int4-s), x2 in 1-99, y2 = 100 -x2, 10000 tuples (100 dups). |
| 133 |
|
| 134 |
Trying |
| 135 |
|
| 136 |
select * from tmp where x >= (select max(x2) from test2 where y2 = y); |
| 137 |
|
| 138 |
and |
| 139 |
|
| 140 |
begin; |
| 141 |
select y as ty, max(x2) as mx into table tsub from test2, tmp |
| 142 |
where y2 = y group by ty; |
| 143 |
vacuum tsub; |
| 144 |
select x, y from tmp, tsub where x >= mx and y = ty; |
| 145 |
drop table tsub; |
| 146 |
end; |
| 147 |
|
| 148 |
Without index on test2(y2): |
| 149 |
|
| 150 |
SubSelect -> 320 sec |
| 151 |
Using temp table -> 32 sec |
| 152 |
|
| 153 |
Having index |
| 154 |
|
| 155 |
SubSelect -> 17 sec (2M of memory) |
| 156 |
Using temp table -> 32 sec (12M of memory: -S 8192) |
| 157 |
|
| 158 |
Vadim |