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 Fri, 16 Mar 2007 16:35:09 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_cleanup_v1.stat
                d47_mp_cleanup_v1.patch

Attaching d47_mp_cleanup_v1.patch, which is a patch to address the review comments made by
Bryan on 11/Mar/07 11:37 AM.  In particular this patch does the following:

  1 - Changes Predicate.isRelationalOpPredicate() so that it just calls
      the already existing method "isRelationalOperator()" on the left
      operand of the predicate's AND node.  I.e.:

-	return ((getRelop() != null) && (getSourceInList() == null));
+	return andNode.getLeftOperand().isRelationalOperator();

      I completely forgot that the "isRelationalOperator()" method already
      existed, even though I myself made probe-predicate-based changes to
      that method as part of d47_mp_relOpPredCheck:

	public boolean isRelationalOperator()
	{
-		return true;
+		/* If this rel op is for a probe predicate then we do not call
+		 * it a "relational operator"; it's actually a disguised IN-list
+		 * operator.
+		 */
+		return (inListProbeSource == null);
+	}
	
      As a result of those changes we can now just call that method when
      checking to see if a predicate is a relational op predicate.  This
      ultimately comes down to a simple check for a null variable in
      BinaryRelationalOperatorNode, as seen above.

      I believe this change addresses Bryan's comment #7, which pointed
      out that the old code:

		return ((getRelop() != null) && (getSourceInList() == null));

      seemed a tad expensive since it was replacing a simple call to
      "relop != null".  The new code (with this patch) is much more
      comparable to the "relop != null" check in terms of "work" that
      it does (we have an additional call to getLeftOperand(), but
      that's about it).

  2 - Inspired by the "isRelationalOperator()" method defined in ValueNode
      and used above, I added a similar method, "isInListProbeNode()",
      to ValueNode, as well.  The default case returns "false", while
      BinaryRelationalOperatorNode returns true if it has a source IN-
      list associated with it:

+	/** @see ValueNode#isInListProbeNode */
+	public boolean isInListProbeNode()
+	{
+		return (inListProbeSource != null);
+	}

      Then I added a corresponding method called "isInListProbePredicate()"
      to Predicate.java.  This method allows for simple (and relatively
      cheap) checking of a predicate to see if it is an IN-list probe
      predicate.  There are several places in the code where we would
      attempt to retrieve the underlying source IN-list (via a call to
      "getSourceInList()") just to see if it was non-null.  All of those
      occurrences have now been replaced by a call to the new method on
      Predicate.java.  I think this is a cleaner and cheaper way to
      go about it.

  3 - Modifies Predicate.getSourceInList() to return the underlying
      InListOperatorNode for probe predicates AND for "normal"
      IN-list predicates (i.e. an IN-list that could not be
      transformed into a "probe predicate" because it contains
      one or more non-parameter, non-constant values)

      This then allowed for some cleanup of the code mentioned in
      Bryan's comment #2.  Some of the logic for that code was
      specifically targeted for the old rewrite algorithm (use
      of a BETWEEN operator), so I fixed it up and added comments
      as I felt appropriate.

      I also added a second version of getSourceInList() that takes a
      boolean argument; if true, then it will only return the source
      IN list for a predicate *if* that predicate is an IN-list
      probe predicate.

  4 - Changes PredicateList.generateInListValues() to account for the
      fact that it only ever gets called when we know that there is
      a probe predicate in the list.  This addresses Bryan's review
      comment #3.

  5 - Shortens a couple of lines in FromBaseTable that were added with
      earlier patches but were longer than 80 chars.  Also rewrites
      one Sanity check in that class to avoid construction of strings
      when no error occurs (per recent discussions on derby-dev).

I ran derybyall and suites.All with ibm142 on Red Hat Linux with no new failures.  Feedback
or further review of these changes is appreciated.  I'll plan to commit on Monday if I don't
hear any objections.

Many many thanks again to Bryan for his time and suggestions!

> 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_cleanup_v1.patch,
d47_mp_cleanup_v1.stat, d47_mp_codeGen_v1.patch, d47_mp_codeGen_v1.stat, d47_mp_exec_v1.patch,
d47_mp_exec_v1.stat, d47_mp_masters_v1.patch, d47_mp_preprocess_v1.patch, d47_mp_preprocess_v1.stat,
d47_mp_preprocess_v2.patch, d47_mp_relOpPredCheck_v1.patch, d47_mp_relOpPredCheck_v1.stat,
derby-47-performance-data.txt, derby-47-performance-data.txt, Derby47PerformanceTest.java,
Derby47PerformanceTest.java, Derby47PerformanceTest.java, InListOperatorNode.java, QueryPlanUniqueIndexAndWordIndexOneTerm.txt,
QueryPlanUniqueIndexAndWordIndexTwoTerms.txt, QueryPlanUniqueIndexOnlyOneTerm.txt, QueryPlanUniqueIndexOnlyTwoTerms.txt,
readlocks.diff, readlocks_withContext.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