This is a high level answer, with no specific knowledge about what the
optimizer does actually.
I would say that it makes sense to cost a hash join with any set of
columns in an index as long at the cost appropriately accounts for how
many rows in the index it will have to look at to get those rows. So
I would guess that the cost for using non leading columns would mostly
be the cost of reading ALL rows in the index. This may be an
appropriate plan just as it may be appropriate to scan an entire index
if all you are looking for is where 3rd key column = ? -- as the index
may be way smaller than the base table.
other comments below.
Army wrote:
In a thread on derby-user a long while back there was a brief discussion
of multi-column indexes and when Derby can use them. One quote that
came from that thread was the following:
http://article.gmane.org/gmane.comp.apache.db.derby.user/3175
<begin quote>
Derby can only use the index if all the leading columns in a
multi-column index are part of the where clause. Note that it can use
it if only 2 leading of 3 columns are available. Often such an index is
created so that it is a "covering" index so that the results of a select
can be returned just from the index without going to the base table.
<end quote>
So given that Derby can only use an index if all the _leading_ columns
in the index are part of the where clause, I'm wondering if that same
restriction should be true when it comes to finding hash key columns for
a hash join?
More specifically, there is code in Derby to look at a list of
predicates to determine which columns of an index are referenced by
those predicates, and every such column is then treated as a "hash key
column". The presence of at least one hash key column tells Derby that
it is possible to do a hash join using the index--i.e. that the hash
join is "feasible"--and thus the optimizer will figure out the cost of
the hash join and factor that into its choice of "best access path".
The code to find the key columns is in
HashJoinStrategy.findHashKeyColumns():
...
// Build a Vector of all the hash key columns
int colCtr;
Vector hashKeyVector = new Vector();
for (colCtr = 0; colCtr < columns.length; colCtr++)
{
// Is there an equijoin condition on this column?
if (predList.hasOptimizableEquijoin(innerTable, columns[colCtr]))
{
hashKeyVector.addElement(new Integer(colCtr));
}
}
...
Just before this block of code the "columns" array is initialized
according to the conglomerate descriptor for innerTable--so if the
descriptor is an index, "columns" will hold all the columns that make up
the index.
Notice that this code does _not_ take into consideration the notion of
"leading" columns for an index. If, for example, the index columns are
[2, 1, 3] and the predicate list has a single predicate that references
column 3, the "if" statement above will return false for "2" and "1",
and then it will return true for "3". Then, since we found at least one
hash key column, Derby determines that a hash join is feasible and so
will go on to cost the hash join using the index.
However, since column "3" is _not_ a leading column for the index, this
doesn't seem correct to me--or at the very least, it seems sub-optimal.
Since we haven't matched the leading column of the index, is it really
useful to use the index? When costing the hash join the optimizer will
take into account whether or not the index is a covering index, but it
does not, so far as I can see, account for the fact that the hash key
columns might *not* be leading columns. On the contrary, it looks like
the costing code assumes that if the index is going to be used, we have
matched a leading set of columns. (see FromBaseTable.estimateCost()).
The reason I bring this up is because I have a rather large query that
has several levels of nested subqueries and a whole slew of predicates
on the tables and subqueries in question. When run against Derby as it
is, the query takes hours (yes, HOURS) to execute--I killed it after 2
hours and it had only returned a fraction of the total rows in the
result set. But if I add logic to the "findHashkeyColumns" method above
so that it only counts _leading_ columns as "hash key columns", the same
query executes in under 3 minutes. That's still a tad long, but it's
far better than hours...
The change I made was to add the following "else" block to the code
snippet above:
// Is there an equijoin condition on this column?
if (predList.hasOptimizableEquijoin(innerTable, columns[colCtr]))
{
hashKeyVector.addElement(new Integer(colCtr));
}
+ else if ((cd != null) && cd.isIndex() &&
+ !innerTable.isCoveringIndex(cd)) {
+ // if we're trying to do a hash join with an index conglomerate,
+ // then we either need to match a _leading_ set of columns from
+ // the conglomerate, or else the index has to be covering; otherwise
+ // we can't use the index to evaluate all of the predicates,
+ // which means we end up going back to the table, which is
+ // not optimal. So here, if the index is not covering, we
+ // only consider the leading columns as hash keys.
+ break;
+ }
All of that said, can anyone out there provided feedback/comments on the
following two questions:
1) Does it really make sense to use an index for a hash join when the
hash key columns are _not_ leading columns for the index?
I think yes, just not as useful. If you have leading columns then
one can set specific start and stop ranges for a scan on the btree.
Without a leading column you have to scan all rows and apply qualifiers,
which still may be better than scanning all rows in base table. Depends
on number of rows you expect to qualify and relatively how many trips
to base table per scanned row you will have to take.
2) Does the change included above make sense? I've run derbyall with
this change applied and didn't see any unexpected failures, and I've
convinced myself that this is the correct thing to do. But of course,
convincing myself is the easy part--if anyone else out there can offer
input one way or the other, I'd appreciate it...
again i am not sure about the whole process, but it does not seem like
you need to a covering index as one may be able to eliminate multiple
index rows without going to the base table so it may be useful to scan
an index, even if it is not covering. Also I am not sure what
isCoveringIndex() does - the comments you included above was using
the definition of a covering index as one which has all the columns
in the select list, where for choosing the usefulness of an index it may
only need the columns in the where clause.
In the event that I hear no protests, I'll create a Jira entry and post
this small change as an "enhancement" for 10.2...
Thanks much,
Army
