db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Bryan Pendleton (JIRA)" <j...@apache.org>
Subject [jira] Commented: (DERBY-47) Some possible improvements to IN optimization
Date Sun, 11 Mar 2007 18:38:09 GMT

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

Bryan Pendleton commented on DERBY-47:
--------------------------------------

Hi Army,

I finally got around to reading through the patches. Sorry it took a while.
I haven't actually *run* any of the code, just given the patches a close
reading, so some of these questions could have been answered that way, but
hopefully it's all still useful to you. Without further ado :)

By the way, all of these are *very* minor things. These patches are excellent,
and I learned a lot from reading them. This is great work!

1) In the relOpPredCheck patch, you made this change to PredicateList.java:

-			if (relop == null || ! relop.isQualifier(optTable, false))
+			if (!pred.isRelationalOpPredicate() ||
+				!pred.getRelop().isQualifier(optTable, false))

   I'm concerned that this change may have a hole for a possible NPE. Is it
   possible that there could arise a case where we have an IN-list predicate
   at this point, such that relop is null but in-list is not null, and then
   pred.isRelationalOpPredicate() would return false, but pred.getRelop()
   would return null? 

2) I spent some time studying the code in PredicateList.java which manipulates
   IN list operator predicates, and got a bit twisted around. There seems to
   be a lot of code which looks, more or less, like the following:

   RelationalOperator relop = pred.getRelop();
   InListOperatorNode inNode = pred.getSourceInList();
   boolean isIn = (inNode != null);

    if (relop == null)
    {
        /* if it's "in" operator, we generate dynamic start and stop key
         * to improve index scan performance, beetle 3858.
         */
        if (pred.getAndNode().getLeftOperand() instanceof InListOperatorNode &&
            ! ((InListOperatorNode)pred.getAndNode().getLeftOperand()).getTransformed())
        {
            isIn = true;
            inNode = (InListOperatorNode) pred.getAndNode().getLeftOperand();
        }

  My naive reaction to code like this is "shouldn't this be handled in
  pred.getSourceInList()"?

  That is, it seems like there's a lot of code in PredicateList.java which
  calls pred.getSourceInList, but then does this other complicated "if" test
  to get the InListOperatorNode a different way.

  Can you help me understand why are there these two different ways to get
  the InListOperatorNode for a predicate (via getSourceInList() and via 
  getAndNode.getLeftOperand() ), and what do you think about creating a
  "helper" function in Predicate.java, similar to getSourceInList, to clean up
  the 4 or 5 places in PredicateList.java where we have code like the above?

3) The new method PredicateList.generateInListValues() seems to go to some
   pains to handle the case where it is called, but this predicate list
   actually doesn't have any in list values to generate. My reaction was:
   "why is this routine getting called in this case?" It seems like
   NestedLoopJoinStrategy never calls generateInListValues unless there are
   actually in-list values to generate, so why does generateInListValues
   need to handle the case where there is no InListOperatorNode?

   That is, does the final "else" clause in generateInListValues ever actually
   occur?

4) The code which traverses predicate lists seems to always traverse them
   in backwards order, e.g. this code from HashJoinStrategy.java:

            for (int i = storeRestrictionList.size() - 1; i >= 0; i--)

   Why do we always traverse these backwards? Is this just an optimization
   in order to call the size() method only once? Or is there something
   deeper going on?

5) In InListOperatorNode, I at first thought that you had put this code in,
   but then after more study I saw that this was just an artifact of the
   patch program and you hadn't introduced this code, but just re-arranged it
   a bit. Still, the code showed up with "+" signs in the patch so I looked
   at it, and feel compelled to comment on it.

   This is at about line 413 in InListOperatorNode.java:

        //LocalField receiverField =
        //  acb.newFieldDeclaration(Modifier.PRIVATE, receiverType);

        leftOperand.generateExpression(acb, mb);
        mb.dup();
        //mb.putField(receiverField); // instance for method call
        /*mb.getField(receiverField);*/ mb.upCast(leftInterfaceType); // first arg

   Do you know what is going on here? What is this commented out code, and
   can we clean it up? The last line in particular is quite frustrating with
   its snippet of actual code sandwiched in between two comments on the line.

6) I seem to recall some discussions on the mailing lists from people who
   had code generation systems which tended to generate horrific IN clauses
   with, for example, upwards of 1500 elements in the IN list. I think it would
   be nice to have a test or two which verified that we can actually compile
   and run such a SQL statement. You may have already done this, and I missed
   it, but most of the test cases in the addTestCases patch seemed to have
   IN list clauses with no more than 8-10 values in them.

   A test case like this, while hideously ugly, would help to ensure that
   we didn't have some problematic N^2 or N! handling of the IN list values
   somewhere that would explode if we had too many IN list values.

7) Generally speaking, I like the new convenience methods in Predicate.java,
   but I do worry about whether we need to start being concerned about
   overall efficiency in the optimizer. For example, consider a change like:

 			RelationalOperator relop = pred.getRelop();
 
-			if (relop != null)
+			if (pred.isRelationalOpPredicate())

   since isRelationalOpPredicate may end up calling getRelop() two more times,
   and since getRelop() calls getLeftOperand() twice and does an instanceof
   check, we're incrementally adding a fair amount of code.

   It's really important that the optimizer code be clear and easy to read,
   so I'm not suggesting any drastic measures. I'm just sort of thinking
   out loud about some concerns about how to write an optimizer which is
   simultaneously both
   - clear and easy to read and understand (this is the most important)
   - yet also efficient to run


> 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