db-derby-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Joel Turkel" <joel.tur...@gmail.com>
Subject Subquery Materialization in Nested Loops Outer Join
Date Thu, 17 Jan 2008 23:24:41 GMT
Hi,

I'm seeing performance problems when running a query that left outer
joins to subqueries together. Each subquery returns 1000 rows and
takes under 1 sec to execute. The whole query returns 0 rows (as
expected) but takes 60 secs. The join is evaluated using nested loops,
so I assume the problem is one of the subqueries is repeatedly
executed.  If I manually materialize the second subquery into a temp
table the query takes under 1 second. Searching around the mailing
lists it sounds like subqueries in the from clause should be
materialized (http://issues.apache.org/jira/browse/DERBY-781)?

I played around with SQL and the problem persists if I change the left
outer join to an inner join. However, the problem goes away if I
switch inner join to use old style join syntax i.e. putting the join
condition in the where clause.

I've pasted additional details below. Any help would be appreciated.

Thanks,
Joel

Here's the problem query:

 -- Returns 0 rows
 SELECT V2.RECORD_ID, V2.GENERATION_ID, V2.IS_DELETE, V2.CONTENT_HASH
 FROM (
         -- Returns 1000 rows
         SELECT R.RECORD_ID, R.GENERATION_ID, R.CONTENT_HASH, R.IS_DELETE
         FROM RECORDS R
         WHERE R.GENERATION_ID > 1 AND R.GENERATION_ID <= 2 AND
R.GENERATION_ID =
                 (SELECT MAX(R2.GENERATION_ID)
                 FROM RECORDS R2
                 WHERE R.RECORD_ID = R2.RECORD_ID AND R.GENERATION_ID
> 1 AND R.GENERATION_ID <= 2)
 ) V2
 LEFT OUTER JOIN (
         -- Returns 1000 rows
         SELECT R.RECORD_ID, R.CONTENT_HASH
         FROM RECORDS R
         WHERE R.GENERATION_ID =
                 (SELECT MAX(R2.GENERATION_ID)
                 FROM RECORDS R2
                 WHERE R.RECORD_ID = R2.RECORD_ID AND R2.GENERATION_ID <= 1)
 ) V1
 ON (V2.RECORD_ID = V1.RECORD_ID)
 WHERE (V1.CONTENT_HASH IS NULL AND V2.IS_DELETE = 0) OR
V1.CONTENT_HASH != V2.CONTENT_HASH

The RECORDS table is defined as:

 CREATE TABLE RECORDS (
     RECORD_ID VARCHAR(32672),
     GENERATION_ID BIGINT,
     IS_DELETE SMALLINT DEFAULT 0,
     CONTENT_HASH VARCHAR(20) FOR BIT DATA,
     PRIMARY KEY (RECORD_ID, GENERATION_ID)
 )

Here's the query plan:

 ******* Project-Restrict ResultSet (18):
 Number of opens = 1
 Rows seen = 0
 Rows filtered = 0
 restriction = false
 projection = true
     constructor time (milliseconds) = 0
     open time (milliseconds) = 0
     next time (milliseconds) = 0
     close time (milliseconds) = 0
     restriction time (milliseconds) = 0
     projection time (milliseconds) = 0
     optimizer estimated row count:       438217.52
     optimizer estimated cost:       227211.52

 Source result set:
     Nested Loop Join ResultSet:
     Number of opens = 1
     Rows seen from the left = 1000
     Rows seen from the right = 0
     Rows filtered = 0
     Rows returned = 0
         constructor time (milliseconds) = 0
         open time (milliseconds) = 0
         next time (milliseconds) = 0
         close time (milliseconds) = 0
         optimizer estimated row count:       438217.52
         optimizer estimated cost:       227211.52

     Left result set:
         Attached subqueries:
             Begin Subquery Number 0
             Once ResultSetAttached to 3):
             Number of opens = 1000
             Rows seen = 1000
             Source result set:
                 constructor time (milliseconds) = 0
                 open time (milliseconds) = 0
                 next time (milliseconds) = 0
                 close time (milliseconds) = 0
                 optimizer estimated row count:       438217.00
                 optimizer estimated cost:     32134578.41

                 Project-Restrict ResultSet (8):
                 Number of opens = 1000
                 Rows seen = 1000
                 Rows filtered = 0
                 restriction = false
                 projection = true
                     constructor time (milliseconds) = 0
                     open time (milliseconds) = 0
                     next time (milliseconds) = 0
                     close time (milliseconds) = 0
                     restriction time (milliseconds) = 0
                     projection time (milliseconds) = 0
                     optimizer estimated row count:       438217.00
                     optimizer estimated cost:     32134578.41

                 Source result set:
                     Scalar Aggregate ResultSet:
                     Number of opens = 1000
                     Rows input = 2000
                         constructor time (milliseconds) = 0
                         open time (milliseconds) = 0
                         next time (milliseconds) = 0
                         close time (milliseconds) = 0
                         optimizer estimated row count:      9573010.73
                         optimizer estimated cost:     32134578.41

                     Index Key Optimization = false
                     Source result set:
                         Project-Restrict ResultSet (7):
                         Number of opens = 1000
                         Rows seen = 2000
                         Rows filtered = 0
                         restriction = false
                         projection = true
                             constructor time (milliseconds) = 0
                             open time (milliseconds) = 0
                             next time (milliseconds) = 0
                             close time (milliseconds) = 0
                             restriction time (milliseconds) = 0
                             projection time (milliseconds) = 0
                             optimizer estimated row count:      9573010.73
                             optimizer estimated cost:     32134578.41

                         Source result set:
                             Project-Restrict ResultSet (6):
                             Number of opens = 1000
                             Rows seen = 2000
                             Rows filtered = 0
                             restriction = true
                             projection = false
                                 constructor time (milliseconds) = 0
                                 open time (milliseconds) = 0
                                 next time (milliseconds) = 0
                                 close time (milliseconds) = 0
                                 restriction time (milliseconds) = 0
                                 projection time (milliseconds) = 0
                                 optimizer estimated row count:      9573010.73
                                 optimizer estimated cost:     32134578.41

                             Source result set:
                                 Index Scan ResultSet for RECORDS
using constraint SQL080117095423590 at read uncommitted isolation
level using share row locking chosen by the optimizer
                                 Number of opens = 1000
                                 Rows seen = 2000
                                 Rows filtered = 0
                                 Fetch Size = 1
                                     constructor time (milliseconds) = 0
                                     open time (milliseconds) = 0
                                     next time (milliseconds) = 0
                                     close time (milliseconds) = 0
                                     next time in milliseconds/row = 0

                                 scan information:
                                     Bit set of columns fetched={0, 1}
                                     Number of columns fetched=2
                                     Number of deleted rows visited=0
                                     Number of pages visited=2046
                                     Number of rows qualified=2000
                                     Number of rows visited=2999
                                     Scan type=btree
                                     Tree height=2
                                     start position:
     >= on first 1 column(s).
     Ordered null semantics on the following columns:
 0
                                     stop position:
     > on first 1 column(s).
     Ordered null semantics on the following columns:
 0
                                     qualifiers:
 None
                                     optimizer estimated row count:
  9573010.73
                                     optimizer estimated cost:     32134578.41


             End Subquery Number 0
         Project-Restrict ResultSet (3):
         Number of opens = 1
         Rows seen = 1000
         Rows filtered = 0
         restriction = true
         projection = true
             constructor time (milliseconds) = 0
             open time (milliseconds) = 0
             next time (milliseconds) = 0
             close time (milliseconds) = 0
             restriction time (milliseconds) = 0
             projection time (milliseconds) = 0
             optimizer estimated row count:          218.45
             optimizer estimated cost:         1035.35

         Source result set:
             Table Scan ResultSet for RECORDS at read uncommitted
isolation level using share row locking chosen by the optimizer
             Number of opens = 1
             Rows seen = 1000
             Rows filtered = 0
             Fetch Size = 1
                 constructor time (milliseconds) = 0
                 open time (milliseconds) = 0
                 next time (milliseconds) = 0
                 close time (milliseconds) = 0
                 next time in milliseconds/row = 0

             scan information:
                 Bit set of columns fetched=All
                 Number of columns fetched=4
                 Number of pages visited=6
                 Number of rows qualified=1000
                 Number of rows visited=2000
                 Scan type=heap
                 start position:
 null                stop position:
 null                qualifiers:
 Column[0][0] Id: 1
 Operator: <=
 Ordered nulls: false
 Unknown return value: false
 Negate comparison result: false
 Column[0][1] Id: 1
 Operator: <=
 Ordered nulls: false
 Unknown return value: true
 Negate comparison result: true

                 optimizer estimated row count:          218.45
                 optimizer estimated cost:         1035.35

     Right result set:
         Project-Restrict ResultSet (17):
         Number of opens = 1000
         Rows seen = 1000000
         Rows filtered = 1000000
         restriction = true
         projection = true
             constructor time (milliseconds) = 0
             open time (milliseconds) = 0
             next time (milliseconds) = 0
             close time (milliseconds) = 0
             restriction time (milliseconds) = 0
             projection time (milliseconds) = 0
             optimizer estimated row count:       438217.52
             optimizer estimated cost:       226176.16

         Source result set:
             Attached subqueries:
                 Begin Subquery Number 1
                 Once ResultSetAttached to 11):
                 Number of opens = 2000000
                 Rows seen = 2000000
                 Source result set:
                     constructor time (milliseconds) = 0
                     open time (milliseconds) = 0
                     next time (milliseconds) = 0
                     close time (milliseconds) = 0
                     optimizer estimated row count:         2006.00
                     optimizer estimated cost:       147100.38

                     Project-Restrict ResultSet (15):
                     Number of opens = 2000000
                     Rows seen = 2000000
                     Rows filtered = 0
                     restriction = false
                     projection = true
                         constructor time (milliseconds) = 0
                         open time (milliseconds) = 0
                         next time (milliseconds) = 0
                         close time (milliseconds) = 0
                         restriction time (milliseconds) = 0
                         projection time (milliseconds) = 0
                         optimizer estimated row count:         2006.00
                         optimizer estimated cost:       147100.38

                     Source result set:
                         Scalar Aggregate ResultSet:
                         Number of opens = 2000000
                         Rows input = 2000000
                             constructor time (milliseconds) = 0
                             open time (milliseconds) = 0
                             next time (milliseconds) = 0
                             close time (milliseconds) = 0
                             optimizer estimated row count:       132793.19
                             optimizer estimated cost:       147100.38

                         Index Key Optimization = false
                         Source result set:
                             Project-Restrict ResultSet (14):
                             Number of opens = 2000000
                             Rows seen = 2000000
                             Rows filtered = 0
                             restriction = false
                             projection = true
                                 constructor time (milliseconds) = 0
                                 open time (milliseconds) = 0
                                 next time (milliseconds) = 0
                                 close time (milliseconds) = 0
                                 restriction time (milliseconds) = 0
                                 projection time (milliseconds) = 0
                                 optimizer estimated row count:       132793.19
                                 optimizer estimated cost:       147100.38

                             Source result set:
                                 Index Scan ResultSet for RECORDS
using constraint SQL080117095423590 at read uncommitted isolation
level using share row locking chosen by the optimizer
                                 Number of opens = 2000000
                                 Rows seen = 2000000
                                 Rows filtered = 0
                                 Fetch Size = 1
                                     constructor time (milliseconds) = 0
                                     open time (milliseconds) = 0
                                     next time (milliseconds) = 0
                                     close time (milliseconds) = 0
                                     next time in milliseconds/row = 0

                                 scan information:
                                     Bit set of columns fetched={0, 1}
                                     Number of columns fetched=2
                                     Number of deleted rows visited=0
                                     Number of pages visited=4048000
                                     Number of rows qualified=2000000
                                     Number of rows visited=4000000
                                     Scan type=btree
                                     Tree height=2
                                     start position:
     >= on first 1 column(s).
     Ordered null semantics on the following columns:
 0
                                     stop position:
     > on first 2 column(s).
     Ordered null semantics on the following columns:
 0 1
                                     qualifiers:
 None
                                     optimizer estimated row count:
   132793.19
                                     optimizer estimated cost:       147100.38


                 End Subquery Number 1
             Project-Restrict ResultSet (11):
             Number of opens = 1000
             Rows seen = 2000000
             Rows filtered = 1000000
             restriction = true
             projection = true
                 constructor time (milliseconds) = 0
                 open time (milliseconds) = 0
                 next time (milliseconds) = 0
                 close time (milliseconds) = 0
                 restriction time (milliseconds) = 0
                 projection time (milliseconds) = 0
                 optimizer estimated row count:       438217.52
                 optimizer estimated cost:       226176.16

             Source result set:
                 Table Scan ResultSet for RECORDS at read uncommitted
isolation level using share row locking chosen by the optimizer
                 Number of opens = 1000
                 Rows seen = 2000000
                 Rows filtered = 0
                 Fetch Size = 1
                     constructor time (milliseconds) = 0
                     open time (milliseconds) = 0
                     next time (milliseconds) = 0
                     close time (milliseconds) = 0
                     next time in milliseconds/row = 0

                 scan information:
                     Bit set of columns fetched={0, 1, 3}
                     Number of columns fetched=3
                     Number of pages visited=6
                     Number of rows qualified=2000000
                     Number of rows visited=2000000
                     Scan type=heap
                     start position:
 null                    stop position:
 null                    qualifiers:
 None
                     optimizer estimated row count:       438217.52
                     optimizer estimated cost:       226176.16

Mime
View raw message