You are viewing a plain text version of this content. The canonical link for it is here.
Posted to derby-user@db.apache.org by Joel Turkel <jo...@gmail.com> on 2008/01/18 00:24:41 UTC
Subquery Materialization in Nested Loops Outer Join
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