Diagnosing DERBY-47 and DERBY-713 (queries with IN (?,?) filters)

[James Synge <ja...@gmail.com>]

I'd like to fix DERBY-47 and DERBY-713 (essentially the same bug), and
so have been working to understand what is going wrong.

I've created a wiki page with my analysis so far,

 http://wiki.apache.org/db-derby/DerbyBug47.

In summary, for the queries I tested of the form:

SELECT ... FROM t WHERE indexedColumn IN (?, ..., ?)

It would appear that the IN list is treated as a single predicate to be applied
to each row in the selected index (i.e. for each value of the column found in
the index, each value in the IN list is compared with that column value), but
I'm new to working on Derby, and so could use some help figuring out how
to debug the execution of queries.  I've been able to debug through
the optimizer,
but I don't understand the generated code, especially given that it's expressed
as bytecode.  Can someone suggest a means of debugging the execution
phase (or getting a human readable form of the code)?

FWIW, my tests clearly show that for the type of query shown above, it
would be better to treat the IN list rather like the outer table of a
nested loop join (as the results below demonstrate), where each
parameter in the IN list is used to "probe" the index.
This matches a suggestion Daniel Neades made in DERBY-713.

Thanks,
James Synge

Re: Diagnosing DERBY-47 and DERBY-713 (queries with IN (?,?) filters)

[Mike Matrigali <mi...@sbcglobal.net>]

James Synge wrote:

> In summary, two problems are:
> 
> 1)
>    The IN list is used to create a scan of the index, starting with the 
> lowest
>    value in the IN list, and continuing through the greatest value in
> the IN list
>    (as opposed to creating N probes into the BTree).
> 
> 2)
>    After finding an index row in the range, rather than testing the 
> predicate
>    against the index row, the base table row is fetched before the 
> predicate
>    (restriction) is applied.
> 
> James
> 
> 
I believe there was a previous discussion about approaches to this 
problem on the derby list.  I seem to remember rick suggesting some
query plan graphs of the solutions.

The two approaches I remember are:

1) create some sort of index result set which would understand "in list"
    key'ing rather than single key.  It would be nice if it could also 
be used for "or's" expressed not as in lists.  It would use existing 
technology
    to basically do probes/scans for each key in the in list.  Doing this
    would then require new costing and probably new optimizer work to
    teach it when to choose this kind of query.  I believe writing the
    the result node to do this is relatively easy, just extend some code
    and then code up reopenScan() with each new key.  If I were doing
    this, this is probably the first thing I would try and see if I could
    get the optimizer hints to work to force this plan so I could quickly
    see if this path works.

2) somehow rewrite the query as a bunch of unions with each having one
    key from the in list.  Doing this might mean no changes necessary
    to the optimizer as it would just do whatever it does today with
    the unions.  I don't know anything about query rewrite, so don't know
    how hard or easy this approach might be.

Re: Diagnosing DERBY-47 and DERBY-713 (queries with IN (?,?) filters)

[James Synge <ja...@gmail.com>]

On 10/2/06, Yip Ng <yi...@gmail.com> wrote:
> One way is to dump the actual generated code into the file system.  You can do this
> using Java property -Dderby.debug.true=DumpClassFile.  e.g.:
>
> java -Dderby.debug.true=DumpClassFile  org.apache.derby.tools.ij

Thanks for that tip.

Thanks also to Army for his detailed reply.

I've done some further debugging, this time through the execution of the query,
and have a much better understand of how bad the generated plan is for this kind
of query.  I've updated the wiki with my findings:

http://wiki.apache.org/db-derby/DerbyBug47

In summary, two problems are:

1)
    The IN list is used to create a scan of the index, starting with the lowest
    value in the IN list, and continuing through the greatest value in
the IN list
    (as opposed to creating N probes into the BTree).

2)
    After finding an index row in the range, rather than testing the predicate
    against the index row, the base table row is fetched before the predicate
    (restriction) is applied.

James

Re: Diagnosing DERBY-47 and DERBY-713 (queries with IN (?,?) filters)

[Yip Ng <yi...@gmail.com>]

On 10/1/06, James Synge <ja...@gmail.com> wrote:
>
> <snip>
> but I don't understand the generated code, especially given that it's
> expressed
> as bytecode.  Can someone suggest a means of debugging the execution
> phase (or getting a human readable form of the code)?
> </snip>


One way is to dump the actual generated code into the file system.  You can
do this
using Java property -Dderby.debug.true=DumpClassFile.  e.g.:

java -Dderby.debug.true=DumpClassFile org.apache.derby.tools.ij

When you issued the query of interest, you should be able to see the
generated activation .class file.  With this, you can either read it using
javap or use a Java decompiler.  I personally like to read bytecode.  =)

Yip

Re: Diagnosing DERBY-47 and DERBY-713 (queries with IN (?,?) filters)

[Bryan Pendleton <bp...@amberpoint.com>]

> I'd like to fix DERBY-47 and DERBY-713 (essentially the same bug), and
> so have been working to understand what is going wrong.

Great! Welcome to the community!

> as bytecode.  Can someone suggest a means of debugging the execution
> phase (or getting a human readable form of the code)?

I don't know the answer to this, but I think it's a great place to start.
Right now, I think that you can basically work with query plan dumps,
as described at http://wiki.apache.org/db-derby/PerformanceDiagnosisTips
and at http://db.apache.org/derby/docs/10.2/tuning/ttundepth33391.html

It seems like working at the query plan level is appropriate for DERBY-47
and DERBY-713; that is, it seems to me that if we can concisely express
the current query plan that Derby uses, and can concisely express the
desired query plan, we will be well on the way to describing the changes
that are needed.

Is this the direction you were heading?

thanks,

bryan