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 Tue, 27 Feb 2007 00:06:05 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_CBO_MoAP_v1.stat
                d47_mp_CBO_MoAP_v1.patch

Committed d47_relOpPredCheck_v1.patch with svn 512079 after getting the okay from Mike to
do so (on derby-dev):

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

Attaching the second incremental patch, d47_mp_CBO_MoAP_v1.patch, which updates the logic
for cost-based optimization (CBO) and modification of access paths (MoAP) to recognize IN-list
"probe predicates" and to handle them appropriately.  More specifically this patch adds code
to do the following:

  - During costing, recognize when we're using a probe predicate as a start/stop key
    and adjust the cost accordingly.  This means multiplying the estimated cost and
    row count for "column = ?" by the number of values in the IN-list (because we are
    effectively going to evaluate "column = ?" N times, where N is the size of the
    IN-list, and we could return one or more rows for each of the N evaluations).
    As mentioned in Mike's comment above, we also want to make sure that the resultant
    row count estimate is not greater than the total number of rows in the table.

  - When determining which predicates can be used as start/stop keys for the current
    conglomerate, only consider a probe predicate to be a start/stop key if it applies
    to the _first_ column in the conglomerate.  Otherwise the probe predicate would
    end up being generated as a store qualifier, which means we would only get rows
    for which "column = ?" was true when the parameter was set to the _first_ value
    in the IN-list.  That means we would end up with incorrect results (missing
    rows).

  - If cost-based optimization is complete and we are modifying access paths in
    preparation for code generation, then take any probe predicates that are *not*
    going to be used as start/stop keys for the chosen conglomerate and "revert" them
    back to their original IN-list form (i.e. to the InListOperatorNodes from which
    they were built).  Those InListOpNodes will then be generated as normal IN-list
    restrictions on the rows returned from store.  If we did not do this reverting
    then the predicates would ultimately be ignored (since they are not valid
    qualifiers) and we would therefore end up with incorrect results (extra rows).

  - If we're modifying access paths and we have chosen to do multi-probing of an index
    then we disable bulk fetching for the target base table.  Logically this is not a
    requirement.  However, it turns out that bulk fetch can lead to poor performance
    when multi-probing an index if the number of probe values is high (several hundred
    or more) BUT that number is still just a small fraction of the total number of rows
    in the table.  An example of such a scenario is found in the Derby47PerformanceTest
    program attached to this issue.  If the total number of rows in the ADMIN.CHANGES
    table is 100,000 and there are 200 or more parameter markers in the IN-list, the
    performance of multi-probing with bulk fetch enabled is just as bad as a table
    scan--and actually gets worse as the number of parameters grows.

I cannot say with any certainty why bulk fetching performs so badly in this situation.  My
guess (and it's just a guess) is that when we bulk fetch we end up reading a unnecessary pages
from disk.  My (perhaps faulty) thinking is that for each probe we do of the index our start
and stop keys are going to be the same value.  That means that we are probably going to be
returning at most a handful of rows (more likely just a row or two).  But perhaps bulk fetching
is somehow causing us to read more pages from disk than we need and the result is a slowdown
in performance?

Does anyone know if that actually makes any sense?  I could be completely wrong here so I'd
appreciate any correction.

All of that said, I found that if I disable bulk fetch for multi-probing the performance returns
to what I would expect (matching and even beating the "Marker" strategy posted by James),
so that's what d47_mp_CBO_MoAP_v1.patch does.  At the very least I'm hoping this is an acceptable
step in the right direction.

As with my previous patch, this CBO_MoAP patch should not change any existing functionality
because all of the new behavior depends on the existence of "probe predicates", which do not
yet exist.

Review comments are much appreciated (esp. w.r.t the bulk fetching changes)...

> 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_CBO_MoAP_v1.patch, d47_mp_CBO_MoAP_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