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 Wed, 07 Mar 2007 22:17:24 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_exec_v1.stat
                d47_mp_exec_v1.patch

Committed d47_mp_codeGen_v1.patch with svn # 515795:

    URL: http://svn.apache.org/viewvc?view=rev&rev=515795

And now attaching d47_mp_exec_v1.patch, which is a patch to implement execution-time "probing"
given a probe predicate "place-holder" and a list of IN values.  This patch creates a new
execution-time result, MuliProbeTableScanResultSet, to perform the probing. Generally speaking
the process is as follows, where "probe list" (aka "probeValues") corresponds to the IN list
in question.

  0 - Open a scan using the first value in the (sorted) probe list as a start AND stop key.

Then for each call to "getNextRowCore()":

  1 - See if we have a row to read from the current scan position. If so, return that row
(done).

  2 - If there are no more rows to read from the current scan position AND if there are more
    probe values to look at, then a) reopen the scan using the next probe value as the start/
    stop key and b) go back to step 1.  Otherwise proceed to step 3.
    
  3 - Return null (no more rows).

At a higher-level the changes in exec_v1.patch make it so that repeated calls to MultiProbeTableScanResultSet.getNextRowCore()
will first return all rows matching probeValues[0], then all rows matching probeValues[1],
and so on (duplicate probe values are ignored).  Once all matching rows for all values in
probeValues have been returned, the call to getNextRowCore() will return null, thereby ending
the scan.

In order to accommodate the above behavior, the following changes were made to existing files:

 1 - Add correct instantiation logic to the "getMultiProbeTableScanResultSet()"
   method of GenericResultSetFactory, which was just a stub method before this
   patch.

 2 - Overloaded methods in TableScanResultSet to allow the passing of a "probe value"
   into the openScanController() and reopenScanController() methods.  The methods
   then use the probe value (if one exists) as the start/stop key for positioning
   a scan, instead of using the start/stop key passed into the result set constructor.

 3 - Made the iapi.types.DataType class implement the java.lang.Comparable interface
   for the sake of easy sorting (just let the JVM do the sort).  Since DataType (the
   superclass of all datatypes and base implementation of the DataValueDescriptor
   interface) already has a "compare()" method that returns an integer to indicate
   less than, greater than, or equal, all we have to do is wrap that method inside
   a "compareTo()" method and we're done.

   There are two issues worth mentioning regarding this sort.  First, the compareTo()
   method does not throw any exceptions, so if an error occurs while trying to compare
   two DataValueDescriptors, we will simply treat the values as "equal" when running
   in insane mode (in sane mode we will throw an assertion failure).  Is this
   acceptable?  If not, is there a better way to handle this, aside from writing my
   own sorting code? (which is doable but seems like overkill).

   Second, for some strange reason sorting the probeValues array directly (i.e.
   in-place sort) leads to incorrect parameter value assignment when executing a
   prepared statement multiple times.  I was unable to figure out why that might
   be (maybe related to DERBY-827?).  To get around the problem I create clones
   of the IN values and then sort the clones.  That solves the problem but has
   the obvious drawback of extra memory requirements.  I'm hoping that for now
   this is an okay workaround (progress, not perfection), but if anyone has any
   ideas as to what could be going on here, I'd appreciate the input.

   And of course, if there are any other reasons why it's bad to make DataType
   implement the Comparable interface, I hope that reviewers can speak up.  If
   it comes down to it I can always add a simple sort method to MultiProbeTSCRS
   and just use that.

As with all preceding patches, this patch should not have any functional effect on Derby processing
because the new behavior depends on probe predicates, which do not yet exist.  I have not
yet had a chance to run derbyall as a sanity check, but plan to do so before committing. 
In the meantime, questions/comments/feedback on exec_v1.patch as attached would be much appreciated.

> 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_exec_v1.patch, d47_mp_exec_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