In one of my previous comments I mentioned that d47_engine_doNOTCommit_v1.patch has a problem where the addition of an InListResultSet to the FromList causes all of the SUR (Scrollable Updatable Result set) tests that use an IN-clause to fail. More specifically, the presence of the InListResultSet causes Derby to downgrade the cursor scrollability to "CONCUR_READ_ONLY".
I was eventually able to track down the cause of this behavior: whether or not Derby downgrades a result set to CONCUR_READ_ONLY depends on the value returned by the execution time result set in the "isForUpdate()" method. The default (as defined in NoPutResultSetImpl) is to return false.
In the case of the SUR tests (prior to my changes) we were getting a ScrollInsensitiveResultSet on top of a TableScanResultSet. The former gets its "isForUpdate()" value from the latter, and the latter correctly returns "true" to indicate that the result set is for update and thus no downgrade is needed. With d47_engine_doNotCommit_v1.patch applied, though, we add an InListResultSet to the FromList, which ultimately gives us a JoinResultSet at execution time. The JoinResultSet class does not define an "isForUpdate()" method, so we just return the default--which is "false". That causes the cursor concurrency to be downgraded to CONCUR_READ_ONLY.
To see what would happen I forced JoinResultSet to return "true" and then there was an ASSERT failure because JoinResultSets are not expected to be used for update/delete. The relevant code is in execute/JoinResultSet.java; in the "getRowLocation()" method we see the following comment:
- A join is combining rows from two sources, so it has no
- single row location to return; just return a null.
My guess is that, since the decision to disallow update/delete on a JoinResultSet was intentional, trying to code around that restriction is a bad idea. Or at the very least, it would require a lot more investigation and/or work.
Instead of pursuing that potentially treacherous path, I was able to come up with some logic that checks to see if a result set is updatable at compile time and, if so, to skip the IN-list rewrite. Early testing suggests that this is viable solution.
HOWEVER, as the list of "exceptions" to the IN-list (_v1.patch) rewrite grew, I started to wonder if there wasn't some other solution to
DERBY-47 that would accomplish the same thing, minus all of the exception cases.
A few days later I came across some queries involving multiple IN-list predicates for a single SELECT statement. It turns out that many of those queries return incorrect results (duplicate rows) and/or run much more slowly with the _v1 patch than without.
The fact that there are so many "exceptions to the rule" combined with the undesirable behavior in the face of multiple IN-lists prompted me to abandon my initial idea of internally adding an InListResultSetNode to the user's FROM list (d47_engine_doNOTCommit_v1.patch).
Instead I have been working on an alternate approach to the problem. This second approach, like the first, is based on a comment made by someone else on this issue. This time, though, the comment in question is from James Synge and is as follows:
> The goal of the re-write is to avoid the source of
> which is that we don't have a multi-probe index scan, only
> range index scans, and worse still, when there are parameters
> involved, the range is the entire index.
In short, I decided to work with the execution-time result sets to see if it is possible to enforce some kind of "multi-probing" for indexes. That is to say, instead of scanning a range of values on the index, we want to make it so that Derby probes the index N times, where N is the size of the IN-list. For each probe, then, we'll get all rows for which the target column's value equals the N-th value in the IN-list.
Effectively, this comes down to the "Marker" strategy in Derby47Performance.java, where we evaluate an equality predicate, "column = ?", N times. Except of course that, unlike with the Marker strategy, we do the N evaluations internally instead of making the user do it.
A high-level description of how this approach will work is as follows:
- If any value in the IN-list is not a constant AND is not a parameter,
then do processing as usual (no optimizations, no rewrite). Notice
that with this approach we do still perform the optimization if
IN-list values are parameters. That is not the case for the current
Derby rewrite (i.e. without any changes for
- During preprocessing, replace the IN-list with an equality predicate of
the form "column = ?". I.e. the right operand will be a parameter node,
the left operand will be whatever column reference belongs to the IN-list
(hereafter referred to as the "target column"). We call this new, internal
predicate an IN-list "probe predicate" because it will be the basis of
the multi-probing logic at execution time.
- During costing, the equality predicate "column = ?" will be treated as
a start/stop key by normal optimizer processing (no changes necessary).
If the predicate is deemed a start/stop key for the first column in
an index, then we'll multiply the estimated cost of "column = ?" by
the size of the IN-list, to account for the fact that we're actually
evaluating the predicate N times (not just once).
If the predicate is not a start/stop key for the first column in
the index, then we do not adjust the cost. See below for why.
- After we have found the best plan (including a best conglomerate choice),
check to see if the IN-list probe predicate is a start/stop key on the
first column in the chosen conglomerate. In order for that to be the
case the conglomerate must be an index (because we don't have start/stop
keys on table conglomerates). If the probe predicate is not a
start/stop key for the first column in the index, then we "revert" the probe
predicate back to its original IN-list form and evaluate it as a "normal"
InListOperatorNode. In this way we are effectively "giving up" on the multi-
probing approach. This is why we don't change the cost for such probe
predicates (mentioned above).
If the probe predicate is a start/stop key on the first column in
the index conglomerate, then leave it as it is.
- When it comes time to generate the byte code, look to see if we have
a probe predicate that is a start/stop key on the first column in the
chosen conglomerate. If so, generate an array of DataValueDescriptors
to hold the values from the corresponding IN-list and pass that array
to the underlying execution-time result set (i.e. to TableScanResultSet).
Then generate the probe predicate as a "normal" start/stop key for the
scan. This will serve as a "place-holder" for the IN-list values
at execution time.
- Finally, at execution time, instead of using a single start key and a
single stop key to define a scan range, we iterate through the IN-list
values and for each non-duplicate value V[i] (0 <= i < N) we treat V[i]
as both a start key and a stop key. Or put another way, we plug
V[i] into the "column = ?" predicate and retrieve all matching rows.
In this way we are "probing" the index for all rows having value V[i]
in the target column. Once all rows matching V[i] have been returned,
we then grab the next IN-list value, V[i+1], and we reposition the
scan (by calling "reopenCore()"), this time using V[i+1] as the start
and stop key (i.e. plugging V[i+1] into "column = ?"). This will
return all rows having value V[1+1] in the target column.
Continue this process until all values in the IN-list have been
exhausted. When we reach that point, we are done.
As a simple example, assume our query is of the form:
select ... from admin.changes where id in (1, 20000)
During preprocessing we will effectively change this to be:
select ... from admin.changes where id = ?
where "id = ?" is our IN-list "probe predicate". Note that we must make sure the optimizer recognizes "id = ?" as a disguised IN-list operator, as opposed to a true relational operator. The reason is that, while we do treat the probe predicate as a "fake" relational operator so that it can be seen as a start/stop key for the relevant indexes, there are many operations (ex. transitive closure) that should not be done on a probe predicate. So we have to be able to distinguish a probe predicate from other relational predicates.
With the probe predicate in place the optimizer will determine that it is a start/stop key for any index having column "ID" as the first column, and thus the optimizer is more likely to choose one of those indexes over a table scan. If we assume the optimizer decides to use an index on ID for the query, then we'll generate the IN-list values (1, 20000) and we will pass them to the underlying index scan. We'll then generate the probe predicate "column = ?" as a start and stop key for the scan.
At execution, then, the scan will first open up the index by using "1" as the start and stop key for the scan (or put another way, by plugging "1" into the probe predicate, "column = ?"). That will return all rows having ID equal to "1". Then when that scan ends, we'll reopen the scan a second time, this time using "20000" as the start and stop key, therefore returning all the 20000's. Meanwhile, all result sets higher up in the result set tree will just see a stream of rows from the index where ID only equals 1 or 20000.
This works for IN-lists with parameters, as well, because by the time execution starts we know what values the parameters hold.
The first draft of code for implementing all of this is pretty much done, but I plan to post it in increments for ease of review. If all goes well, nothing should change functionally until the final patch, which will be the preprocessing patch that does the actual creation of the "probe predicate". At that point all of the machinery should be in place to recognize the probe predicate and function accordingly.
I ran Derby47PerformanceTest with this "multi-probing" approach and the numbers were similar to what I saw with the _v1 approach (more details coming later). Unlike the _v1 approach, though, the multi-probing approach works with subqueries, left outer joins, and scrollable updatable result sets. In addition, all of the test queries that I came up with involving multiple IN-lists run correctly with the multi-probing approach, and in many cases run quite a bit more quickly--neither of which was true for the _v1 approach. And yes, I do hope to add those test cases to the nightlies as part of my work on this issue.
Incremental patches are forthcoming. In the meantime, if anyone has any comments/suggestions on the approach outlined above, I would appreciated the feedback...