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