Mailing-List: contact derby-dev-help@db.apache.org; run by ezmlm
Precedence: bulk
Reply-To: <derby-dev@db.apache.org>
Message-ID: <19703473.1149693810592.JavaMail.jira@brutus>
Date: Wed, 7 Jun 2006 15:23:30 +0000 (GMT+00:00)
From: "A B (JIRA)" <derby-dev@db.apache.org>
To: derby-dev@db.apache.org
Subject: [jira] Resolved: (DERBY-1365) Address potential problems with
 optimizer logic in some rarely-exercised code.
In-Reply-To: <29766048.1149178229937.JavaMail.jira@brutus>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable

     [ http://issues.apache.org/jira/browse/DERBY-1365?page=3Dall ]
    =20
A B resolved DERBY-1365:
------------------------

    Resolution: Fixed
    Derby Info:   (was: [Patch Available])

Patch checked into 10.1 with svn # 412218 and into trunk with svn # 412222.=
  I have verified by inspection that the change is in both codelines and th=
at there were no new failures in the nightly tests.  So I'm resolving and c=
losing this issue.

Thanks for committing, Satheesh.

> Address potential problems with optimizer logic in some rarely-exercised =
code.
> -------------------------------------------------------------------------=
-----
>
>          Key: DERBY-1365
>          URL: http://issues.apache.org/jira/browse/DERBY-1365
>      Project: Derby
>         Type: Bug

>   Components: Performance
>     Versions: 10.1.2.4, 10.2.0.0, 10.1.3.0
>     Reporter: A B
>     Assignee: A B
>     Priority: Minor
>      Fix For: 10.2.0.0, 10.1.3.0, 10.1.2.5
>  Attachments: d1365_v1.patch, d1365_v1.stat
>
> While looking at the optimization code in Derby for some other work I'm d=
oing, I've noticed a couple of small pieces of code that could potentially =
lead to failures for some queries.  Thus far I have been unable to come up =
with any examples to demonstrate these problems with the current codeline (=
hence the term "potential" problems) because the relevant lines of code are=
 hard to exercise--they require large, complex databases and/or some tricky=
 timing scenarios that I have thus far been unable to produce in the contex=
t of the test harness.  And in fact, a look at the code coverage results fo=
r the pieces of code shows that neither is actually exercised by the curren=
t derbyall suite--which I believe is more indicative of how hard it is to e=
xercise the code in question than it is of incomplete/lacking tests.
> All of that said, analysis of the relevant code does indeed seem to indic=
ate that some (minor) changes are in order.  In particular, consider the fo=
llowing two potential problems.
> 1) Potential logic error when determining the best join order for a subqu=
ery that has more than one FROM table.
> This particular issue is very timing-sensitive.  It will only occur if th=
ere is an outer query which has a subquery and the optimization phase of th=
e subquery "times out" in the middle of costing a join order.  The relevant=
 point in the code can be found in OptimizerImpl.java, around line 420:
>     if (permuteState !=3D JUMPING)
>     {
>         // By setting firstLookOrder to our target join order
>         // and then setting our permuteState to JUMPING, we'll
>         // jump to the target join order and get the cost.  That
>         // cost will then be saved as bestCost, allowing us to
>         // proceed with normal timeout logic.
>         for (int i =3D 0; i < numOptimizables; i++)
>             firstLookOrder[i] =3D bestJoinOrder[i];
>         permuteState =3D JUMPING;
>         // If we were in the middle of a join order when this
>         // happened, then reset the join order before jumping.
>         if (joinPosition > 0)
>             rewindJoinOrder();
>     }
> The problem occurs at the last part of this "if" block, with the call to =
rewind the join order.  The rewindJoinOrder() method will "pull" each optim=
izable that has an assigned position in the current join order and, for eac=
h one, decrement joinPosition--until all optimizables have been pulled and =
joinPosition has a value of "0".  So far so good.
> The trick is that, unlike the other calls to rewindJoinOrder() in Optimiz=
erImpl, this particular call occurs *before* the joinPosition variable is i=
ncremented (it's incremented every time a call to find the "next permutatio=
n" is made, until all optimizables (FROM tables) have been assigned a posit=
ion in the join order).  What this means is that, with the code as it curre=
ntly stands, the call to rewindJoinOrder() will put joinPosition at 0, but =
shortly thereafter joinPosition will be incremented to "1".  The subsequent=
 search for a "next permutation" will then try to place an optimizable at p=
osition 1 in the join order--but since there would be no optimizable at pos=
ition 0 (we would have inadvertently skipped over it because of the increme=
nt after rewinding), the logic for finding/setting the next optimizable in =
the join order would break down.  So I think this needs to be addressed--an=
d it should be as simple as setting joinPosition to -1 after the aforementi=
oned call to rewindJoinOrder().  This -1 value is what joinPosition is set =
to before each round of optimization, so there is a precedent and, I believ=
e, that is the right thing to do.  Once that's done all of the existing log=
ic will work as normal.
> 2) Potential NullPointerException if optimizer comes up with unreasonably=
 high cost estimates (esp. Double.POSITIVE_INFINITY) and then, at execution=
 time, Derby tries to do a hash join based on such an estimate with a Resul=
tSet that has no rows.
> In this case, the code in question is in the constructor logic for Backin=
gStoreHashtable.java.  In cases where the backing hash table receives an un=
reasonably high cost estimate (a "red flag" estimate as noted in the commen=
ts), it's possible that, for cases where the row_source field of the object=
 is null or has no rows (which indicates an empty result set), the hash_tab=
le field will end up being null when we reach the end of the constructor.  =
But if we create a BackingStoreHashtable with a null hash_table, then any c=
alls to the BackingStoreHashtable's methods that expect a valid (non-null) =
hash_table could fail with an NPE.  Thus there should be some additional lo=
gic to ensure that, upon completion of the constructor code, hash_table has=
 been initialized to some appropriate non-null value--namely, an empy hash =
table if there are no rows to process.

--=20
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
   http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
   http://www.atlassian.com/software/jira