granicus.if.org Git - postgresql/blob - src/backend/optimizer/plan/README

   1 $PostgreSQL: pgsql/src/backend/optimizer/plan/README,v 1.3 2008/03/21 13:23:28 momjian Exp $
   2
   3 Subselects
   4 ==========
   5
   6 Vadim B. Mikheev
   7
   8
   9 From owner-pgsql-hackers@hub.org Fri Feb 13 09:01:19 1998
  10 Received: 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)
  13 Received: from hub.org (hub.org [209.47.148.200]) by renoir.op.net (o1/$Revision: 1.3 $) with ESMTP id IAA09761 for <maillist@candle.pha.pa.us>; 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 <hackers@postgreSQL.org>; 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 <hackers@postgreSQL.org>; Fri, 13 Feb 1998 20:51:03 +0700 (KRS)
  21         (envelope-from vadim@sable.krasnoyarsk.su)
  22 Message-ID: <34E44FBA.D64E7997@sable.krasnoyarsk.su>
  23 Date: Fri, 13 Feb 1998 20:50:50 +0700
  24 From: "Vadim B. Mikheev" <vadim@sable.krasnoyarsk.su>
  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 <hackers@postgreSQL.org>
  29 Subject: [HACKERS] Subselects are in CVS...
  30 Content-Type: text/plain; charset=us-ascii
  31 Content-Transfer-Encoding: 7bit
  32 Sender: owner-pgsql-hackers@hub.org
  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
 159
 160