Return-Path: 
 <derby-dev-return-17703-apmail-db-derby-dev-archive=db.apache.org@db.apache.org>
Delivered-To: apmail-db-derby-dev-archive@www.apache.org
Received: (qmail 40852 invoked from network); 27 Mar 2006 22:01:20 -0000
Received: from hermes.apache.org (HELO mail.apache.org) (209.237.227.199)
  by minotaur.apache.org with SMTP; 27 Mar 2006 22:01:20 -0000
Received: (qmail 69628 invoked by uid 500); 27 Mar 2006 22:01:19 -0000
Delivered-To: apmail-db-derby-dev-archive@db.apache.org
Received: (qmail 69594 invoked by uid 500); 27 Mar 2006 22:01:19 -0000
Mailing-List: contact derby-dev-help@db.apache.org; run by ezmlm
Precedence: bulk
List-Help: <mailto:derby-dev-help@db.apache.org>
List-Unsubscribe: <mailto:derby-dev-unsubscribe@db.apache.org>
List-Post: <mailto:derby-dev@db.apache.org>
List-Id: <derby-dev.db.apache.org>
Reply-To: <derby-dev@db.apache.org>
Delivered-To: mailing list derby-dev@db.apache.org
Received: (qmail 69584 invoked by uid 99); 27 Mar 2006 22:01:18 -0000
Received: from asf.osuosl.org (HELO asf.osuosl.org) (140.211.166.49)
    by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 27 Mar 2006 14:01:18 -0800
X-ASF-Spam-Status: No, hits=1.9 required=10.0
	tests=DNS_FROM_RFC_ABUSE,DNS_FROM_RFC_POST
X-Spam-Check-By: apache.org
Received-SPF: neutral (asf.osuosl.org: local policy)
Received: from [32.97.110.150] (HELO e32.co.us.ibm.com) (32.97.110.150)
    by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 27 Mar 2006 14:01:18 -0800
Received: from westrelay02.boulder.ibm.com (westrelay02.boulder.ibm.com
 [9.17.195.11])
	by e32.co.us.ibm.com (8.12.11.20060308/8.12.11) with ESMTP id k2RM0tfp013769
	for <derby-dev@db.apache.org>; Mon, 27 Mar 2006 17:00:55 -0500
Received: from d03av03.boulder.ibm.com (d03av03.boulder.ibm.com
 [9.17.195.169])
	by westrelay02.boulder.ibm.com (8.12.10/NCO/VER6.8) with ESMTP id
 k2RLvkUw258058
	for <derby-dev@db.apache.org>; Mon, 27 Mar 2006 14:57:46 -0700
Received: from d03av03.boulder.ibm.com (loopback [127.0.0.1])
	by d03av03.boulder.ibm.com (8.12.11/8.13.3) with ESMTP id k2RM0suf029696
	for <derby-dev@db.apache.org>; Mon, 27 Mar 2006 15:00:54 -0700
Received: from [127.0.0.1] (svl-arbrown.svl.ibm.com [9.30.38.112])
	by d03av03.boulder.ibm.com (8.12.11/8.12.11) with ESMTP id k2RM0rIC029621
	for <derby-dev@db.apache.org>; Mon, 27 Mar 2006 15:00:54 -0700
Message-ID: <44286094.5030009@sbcglobal.net>
Date: Mon, 27 Mar 2006 14:00:52 -0800
From: Army <qozinx@sbcglobal.net>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US;
 rv:1.7.1) Gecko/20040707
X-Accept-Language: en-us, en
MIME-Version: 1.0
To: Derby Development <derby-dev@db.apache.org>
Subject: Multi-column index usage with Hash joins?
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
X-Virus-Checked: Checked by ClamAV on apache.org
X-Spam-Rating: minotaur.apache.org 1.6.2 0/1000/N

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?

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...

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