db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "A B (JIRA)" <j...@apache.org>
Subject [jira] Updated: (DERBY-47) Some possible improvements to IN optimization
Date Mon, 05 Mar 2007 23:45:25 GMT

     [ https://issues.apache.org/jira/browse/DERBY-47?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

A B updated DERBY-47:
---------------------

    Attachment: d47_mp_codeGen_v1.stat
                d47_mp_codeGen_v1.patch

Attaching d47_mp_codeGen_v1.patch, which updates Derby code generation to account for the
potential presence of IN-list probe predicates.  This patch does the following:

  1 - Moves the code for generating a list of IN values into a new method, InListOperatorNode.generateListAsArray()".
 The new method is then called from two places:

     A. InListOperatorNode.generateExpression(): the "normal" code-path for
        generating IN-list bytecode (prior to DERBY-47 changes).

     B. PredicateList.generateInListValues(): new method for generating the IN-list
        values that will serve as the execution-time index "probe" values. This
        method also generates a boolean to indicate whether or not the values
        are already sorted (i.e. if we sorted them at compile time, which means
        they all must have been constants).

  2 - Adds code to ParameterNode that allows generation of a "place-holder" value (instead
of the ParameterNode itself) for probe-predicates.  This is required because a probe predicate
has the form "column = ?" where the right operand is an internally generated parameter node
that does not actually correspond to a user parameter.  Since that parameter node is "fake"
we can't really generate it; instead we need to be able to generate a legitimate ValueNode--either
a constant node or a "real" parameter node--to serve as the place-holder.  The codeGen patch
makes that possible.

  3 - Updates the generateExpression() method of BinaryOperatorNode to account for situations
where the optimizer chooses a plan for which a probe predicate is *not* a useful start/stop
key and thus is not being used for execution-time index probing.  In this case we simply "revert"
the probe predicate back to the InListOperatorNode from which it was created.  Or put another
way, we "give up" on index multi-probing and simply generate the original IN-list as a regular
restriction.

    In creating this patch I realized that having the "revert" code in BinaryOperatorNode.generateExpression()
is a "catch-all" for any probe predicates that are not "useful" for the final access path.
 So by doing the "revert" operation at code generation time we remove the need for the explicit
"revertToSourceInList()" calls that I added to "modification of access paths" code in the
previous patch (d47_CBO_MoAP).  Since I could not see any benefit to reverting during MoAP
vs. reverting at code gen time, I opted to go with the latter.  So this patch also removes
the now unnecessary "revertToSourceInList()" calls from PredicateList.java.

  4 - Adds logic to NestedLoopJoinStrategy to generate a new type of result set, MultiProbeTableScanResultSet,
for probing an index at execution time.  The new result set does not yet exist (incremental
development) but the code to generate such a result set is added as part of this patch.  Note
that we should never choose to do "multi-probing" for a hash join; comments explaining why
are in the patch, along with a sanity assertion to catch any cases for which that might incorrectly
happen.

  5 - Adds a new method, "getMultiProbeTableScanResultSet()", to the ResultSetFactory interface.
 Also adds a corresponding stub method to GenericResultSetFactory.  The latter is just a dummy
method and will be filled in with the appropriate code as part of a subsequent patch.

I ran derbyall and suites.All on Red Hat Linux with ibm142 and there were no new failures.
 Reviews are appreciated, as always.  If I hear no objections I will commit this patch in
a couple of days.

> Some possible improvements to IN optimization
> ---------------------------------------------
>
>                 Key: DERBY-47
>                 URL: https://issues.apache.org/jira/browse/DERBY-47
>             Project: Derby
>          Issue Type: Improvement
>          Components: SQL
>    Affects Versions: 10.0.2.0
>         Environment: all
>            Reporter: Sunitha Kambhampati
>         Assigned To: A B
>         Attachments: d47_engine_doNotCommit_v1.patch, d47_engine_doNotCommit_v1.stat,
d47_mp_addlTestCases.patch, d47_mp_CBO_MoAP_v1.patch, d47_mp_CBO_MoAP_v1.stat, d47_mp_codeGen_v1.patch,
d47_mp_codeGen_v1.stat, d47_mp_relOpPredCheck_v1.patch, d47_mp_relOpPredCheck_v1.stat, derby-47-performance-data.txt,
derby-47-performance-data.txt, Derby47PerformanceTest.java, Derby47PerformanceTest.java, InListOperatorNode.java,
QueryPlanUniqueIndexAndWordIndexOneTerm.txt, QueryPlanUniqueIndexAndWordIndexTwoTerms.txt,
QueryPlanUniqueIndexOnlyOneTerm.txt, QueryPlanUniqueIndexOnlyTwoTerms.txt, readlocks.diff,
readlocks_withContext.diff
>
>
> Consider a simple case of  - 
> A table tbl has 10000 rows, there is a primary key index on i1
> and the query in question is 
>  select * from tbl where i1 in (-1,100000)
> derby does a table scan of the entire table even though the "IN" list has only two values
and the comparison is on a field that has an index.
> Briefly looking at the code, it seems like we insert a between and use the IN list to
get the start and stop values for the scan. Thus the range of the values in the "IN" list
here plays an important role. 
> Thus if the query was changed to select * from tbl where i1 in (-1, 1), an index scan
would be chosen.
> It would be nice if we could do something clever in this case where there is clearly
an index on the field and the number of values in the IN list is known. Maybe use the rowcount
estimate and the IN list size to do some optimizations.  
> - consider the length of the "IN" list to do searches on the table.  ie use the IN list
values to do index key searches on the table,
> -or try to convert it to a join. Use the "IN" list values to create a temporary table
and do a join. It is most likely that the optimizer will choose the table with "IN" list here
as the outer table in the join and thus will do key searches on the larger table. 
> -------------------------------------------------------------------
> some query plans that I logged using derby.language.logQueryPlan=true for some similar
queries:
> Table has ascending values from 0 - 9999 for i1. primary key index on i1.
> GMT Thread[UT0,5,main] (XID = 19941), (SESSIONID = 0), select * from scanfixed where
i1 in (-1,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990) ******* Project-Restrict ResultSet
(2):
> Number of opens = 1
> Rows seen = 10000
> Rows filtered = 9990
> 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:          750.38
> 	optimizer estimated cost:         8579.46
> Source result set:
> 	Table Scan ResultSet for SCANFIXED at read committed isolation level using instantaneous
share row locking chosen by the optimizer
> 	Number of opens = 1
> 	Rows seen = 10000
> 	Rows filtered = 0
> 	Fetch Size = 16
> 		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=9
> 		Number of pages visited=417
> 		Number of rows qualified=10000
> 		Number of rows visited=10000
> 		Scan type=heap
> 		start position: 
> null		stop position: 
> null		qualifiers:
> Column[0][0] Id: 0
> Operator: <=
> Ordered nulls: false
> Unknown return value: false
> Negate comparison result: false
> Column[0][1] Id: 0
> Operator: <
> Ordered nulls: false
> Unknown return value: true
> Negate comparison result: true
> 		optimizer estimated row count:          750.38
> 		optimizer estimated cost:         8579.46
> ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> l
> 2004-10-14 18:59:47.577 GMT Thread[UT0,5,main] (XID = 19216), (SESSIONID = 0), select
* from scanfixed where i1 in (9999,9998,9997,9996,9995,9994,9993,9992,9991,9990) ******* Project-Restrict
ResultSet (3):
> Number of opens = 1
> Rows seen = 10
> 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:            4.80
> 	optimizer estimated cost:           39.53
> Source result set:
> 	Index Row to Base Row ResultSet for SCANFIXED:
> 	Number of opens = 1
> 	Rows seen = 10
> 	Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8}
> 		constructor time (milliseconds) = 0
> 		open time (milliseconds) = 0
> 		next time (milliseconds) = 0
> 		close time (milliseconds) = 0
> 		optimizer estimated row count:            4.80
> 		optimizer estimated cost:           39.53
> 		Index Scan ResultSet for SCANFIXED using index SCANFIXEDX at read committed isolation
level using instantaneous share row locking chosen by the optimizer
> 		Number of opens = 1
> 		Rows seen = 10
> 		Rows filtered = 0
> 		Fetch Size = 16
> 			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=2
> 			Number of deleted rows visited=0
> 			Number of pages visited=2
> 			Number of rows qualified=10
> 			Number of rows visited=10
> 			Scan type=btree
> 			Tree height=2
> 			start position: 
> 	>= on first 1 column(s).
> 	Ordered null semantics on the following columns: 
> 			stop position: 
> 	> on first 1 column(s).
> 	Ordered null semantics on the following columns: 
> 			qualifiers:
> None
> 			optimizer estimated row count:            4.80
> 			optimizer estimated cost:           39.53

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


Mime
View raw message