You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jena.apache.org by an...@apache.org on 2015/09/13 18:45:44 UTC
jena git commit: JENA-1023: Letf join support.
Repository: jena
Updated Branches:
refs/heads/master 18d85b3d4 -> 05c9eae48
JENA-1023: Letf join support.
Refactor for common hasgh-join engine in AbstractIterHashJoin.
Different implements.
2 version for LeftJoin, depending on which side is used to build the
hash table.
Project: http://git-wip-us.apache.org/repos/asf/jena/repo
Commit: http://git-wip-us.apache.org/repos/asf/jena/commit/05c9eae4
Tree: http://git-wip-us.apache.org/repos/asf/jena/tree/05c9eae4
Diff: http://git-wip-us.apache.org/repos/asf/jena/diff/05c9eae4
Branch: refs/heads/master
Commit: 05c9eae484650bfaa585f41ac77284bb0c38b17f
Parents: 18d85b3
Author: Andy Seaborne <an...@apache.org>
Authored: Sun Sep 13 17:45:38 2015 +0100
Committer: Andy Seaborne <an...@apache.org>
Committed: Sun Sep 13 17:45:38 2015 +0100
----------------------------------------------------------------------
.../engine/join/AbstractIterHashJoin.java | 239 +++++++++++++++++++
.../jena/sparql/engine/join/HashProbeTable.java | 19 +-
.../sparql/engine/join/QueryIterHashJoin.java | 144 ++---------
.../engine/join/QueryIterHashLeftJoin_Left.java | 112 +++++++++
.../join/QueryIterHashLeftJoin_Right.java | 108 +++++++++
.../apache/jena/sparql/engine/join/TS_Join.java | 3 +-
.../engine/join/TestHashLeftJoin_Left.java | 32 +++
.../engine/join/TestHashLeftJoin_Right.java | 31 +++
8 files changed, 555 insertions(+), 133 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/jena/blob/05c9eae4/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/AbstractIterHashJoin.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/AbstractIterHashJoin.java b/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/AbstractIterHashJoin.java
new file mode 100644
index 0000000..7d31354
--- /dev/null
+++ b/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/AbstractIterHashJoin.java
@@ -0,0 +1,239 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.jena.sparql.engine.join;
+
+import java.util.Iterator ;
+import java.util.List ;
+
+import org.apache.jena.atlas.iterator.Iter ;
+import org.apache.jena.sparql.algebra.Algebra ;
+import org.apache.jena.sparql.core.Var ;
+import org.apache.jena.sparql.engine.ExecutionContext ;
+import org.apache.jena.sparql.engine.QueryIterator ;
+import org.apache.jena.sparql.engine.binding.Binding ;
+import org.apache.jena.sparql.engine.iterator.QueryIter2 ;
+import org.apache.jena.sparql.engine.iterator.QueryIterPeek ;
+import org.apache.jena.sparql.engine.join.JoinKey ;
+
+/** Hash join algorithm
+ *
+ * This code materializes one input into the probe table
+ * then hash joins the other input from the stream side.
+ */
+
+public abstract class AbstractIterHashJoin extends QueryIter2 {
+ protected long s_countProbe = 0 ; // Count of the probe data size
+ protected long s_countScan = 0 ; // Count of the scan data size
+ protected long s_countResults = 0 ; // Overall result size.
+ protected long s_trailerResults = 0 ; // Results from the trailer iterator.
+ // See also stats in the probe table.
+
+ protected final JoinKey joinKey ;
+ protected final HashProbeTable hashTable ;
+
+ private Iterator<Binding> iterStream ;
+ private Binding rowStream = null ;
+ private Iterator<Binding> iterCurrent ;
+ private boolean yielded ; // Flag to note when current probe causes a result.
+ // Hanlde any "post join" additions.
+ private Iterator<Binding> iterTail = null ;
+
+ enum Phase { INIT, HASH , STREAM, TRAILER, DONE }
+ Phase state = Phase.INIT ;
+
+ private Binding slot = null ;
+
+ protected AbstractIterHashJoin(JoinKey joinKey, QueryIterator probeIter, QueryIterator streamIter, ExecutionContext execCxt) {
+ super(probeIter, streamIter, execCxt) ;
+
+ if ( joinKey == null ) {
+ QueryIterPeek pProbe = QueryIterPeek.create(probeIter, execCxt) ;
+ QueryIterPeek pStream = QueryIterPeek.create(streamIter, execCxt) ;
+
+ Binding bLeft = pProbe.peek() ;
+ Binding bRight = pStream.peek() ;
+
+ List<Var> varsLeft = Iter.toList(bLeft.vars()) ;
+ List<Var> varsRight = Iter.toList(bRight.vars()) ;
+ joinKey = JoinKey.createVarKey(varsLeft, varsRight) ;
+ probeIter = pProbe ;
+ streamIter = pStream ;
+ }
+
+ this.joinKey = joinKey ;
+ this.iterStream = streamIter ;
+ this.hashTable = new HashProbeTable(joinKey) ;
+ this.iterCurrent = null ;
+ buildHashTable(probeIter) ;
+
+ }
+
+ private void buildHashTable(QueryIterator iter1) {
+ state = Phase.HASH ;
+ for (; iter1.hasNext();) {
+ Binding row1 = iter1.next() ;
+ s_countProbe ++ ;
+ hashTable.put(row1) ;
+ }
+ iter1.close() ;
+ state = Phase.STREAM ;
+ }
+
+ @Override
+ protected boolean hasNextBinding() {
+ if ( isFinished() )
+ return false ;
+ if ( slot == null ) {
+ slot = moveToNextBindingOrNull() ;
+ if ( slot == null ) {
+ close() ;
+ return false;
+ }
+ }
+ return true ;
+ }
+
+ @Override
+ protected Binding moveToNextBinding() {
+ Binding r = slot ;
+ slot = null ;
+ return r ;
+ }
+
+ protected Binding moveToNextBindingOrNull() {
+ // iterCurrent is the iterator of entries in the
+ // probe hashed table for the current stream row.
+ // iterStream is the stream of incoming rows.
+
+ switch ( state ) {
+ case DONE : return null ;
+ case HASH :
+ case INIT :
+ throw new IllegalStateException() ;
+ case TRAILER :
+ return doOneTail() ;
+ case STREAM :
+ }
+
+ for(;;) {
+ // Ensure we are processing a row.
+ while ( iterCurrent == null ) {
+ // Move on to the next row from the right.
+ if ( ! iterStream.hasNext() ) {
+ state = Phase.TRAILER ;
+ iterTail = joinFinished() ;
+ if ( iterTail != null )
+ return doOneTail() ;
+ return null ;
+ }
+ rowStream = iterStream.next() ;
+ s_countScan ++ ;
+ iterCurrent = hashTable.getCandidates(rowStream) ;
+ yielded = false ;
+ }
+
+ // Emit one row using the rightRow and the current matched left rows.
+ if ( ! iterCurrent.hasNext() ) {
+ iterCurrent = null ;
+ if ( ! yielded ) {
+ Binding b = noYieldedRows(rowStream) ;
+ if ( b != null ) {
+ s_countScan ++ ;
+ return b ;
+ }
+ }
+ continue ;
+ }
+
+ // Nested loop join, only on less.
+ //Iterator<Binding> iter = nestedLoop(iterCurrent, rowStream) ;
+
+ Binding rowCurrentProbe = iterCurrent.next() ;
+ Binding r = Algebra.merge(rowCurrentProbe, rowStream) ;
+ Binding r2 = null ;
+
+ if (r != null)
+ r2 = yieldOneResult(rowCurrentProbe, rowStream, r) ;
+ if ( r2 == null ) {
+ // Reject
+ } else {
+ yielded = true ;
+ s_countResults ++ ;
+ return r2 ;
+ }
+ }
+ }
+
+
+ private Binding doOneTail() {
+ // Only in TRAILING
+ if ( iterTail.hasNext() ) {
+ s_countResults ++ ;
+ s_trailerResults ++ ;
+ return iterTail.next() ;
+ }
+ state = Phase.DONE ;
+ // Completely finished now.
+ iterTail = null ;
+ return null ;
+ }
+
+ /**
+ * Signal about to return a result.
+ * @param rowCurrentProbe
+ * @param rowStream
+ * @param rowResult
+ * @return
+ */
+ protected abstract Binding yieldOneResult(Binding rowCurrentProbe, Binding rowStream, Binding rowResult) ;
+
+ /** Signal a row that yields no matches.
+ * This method can return a binding (the outer join case)
+ * which will then be yielded. {@code yieldOneResult} will <em>not</em> be called.
+ * @param rowStream
+ * @return
+ */
+ protected abstract Binding noYieldedRows(Binding rowStream) ;
+
+ /**
+ * Signal the end of the hash join.
+ * Outer joins can now add any "no matche" results.
+ * @return QueryIterator or null
+ */
+ protected abstract QueryIterator joinFinished() ;
+
+ @Override
+ protected void closeSubIterator() {
+ if ( JoinLib.JOIN_EXPLAIN ) {
+ String x = String.format(
+ "HashJoin: LHS=%d RHS=%d Results=%d RightMisses=%d MaxBucket=%d NoKeyBucket=%d",
+ s_countProbe, s_countScan, s_countResults,
+ hashTable.s_countScanMiss, hashTable.s_maxBucketSize, hashTable.s_noKeyBucketSize) ;
+ System.out.println(x) ;
+ }
+ hashTable.clear();
+ }
+
+ @Override
+ protected void requestSubCancel() {
+ hashTable.clear();
+ }
+}
+
+
http://git-wip-us.apache.org/repos/asf/jena/blob/05c9eae4/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/HashProbeTable.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/HashProbeTable.java b/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/HashProbeTable.java
index 3238113..111131c 100644
--- a/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/HashProbeTable.java
+++ b/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/HashProbeTable.java
@@ -27,14 +27,16 @@ import org.apache.jena.atlas.iterator.Iter;
import org.apache.jena.ext.com.google.common.collect.ArrayListMultimap;
import org.apache.jena.ext.com.google.common.collect.Multimap;
import org.apache.jena.sparql.engine.binding.Binding;
+import org.apache.jena.sparql.engine.join.JoinKey ;
/** The probe table for a hash join */
class HashProbeTable {
- private long s_count = 0;
- private long s_bucketCount = 0;
- private long s_maxBucketSize = 0;
- private long s_noKeyBucketSize = 0;
- private long s_maxMatchGroup = 0;
+ /*package*/ long s_count = 0;
+ /*package*/ long s_bucketCount = 0;
+ /*package*/ long s_maxBucketSize = 0;
+ /*package*/ long s_noKeyBucketSize = 0;
+ /*package*/ long s_maxMatchGroup = 0;
+ /*package*/ long s_countScanMiss = 0;
private final List<Binding> noKeyBucket = new ArrayList<>();
private final Multimap<Object, Binding> buckets;
@@ -65,6 +67,8 @@ class HashProbeTable {
if ( x != null ) {
s_maxMatchGroup = Math.max(s_maxMatchGroup, x.size());
iter = x.iterator();
+ } else {
+ s_countScanMiss ++ ;
}
}
// And the rows with no common hash key
@@ -102,6 +106,11 @@ class HashProbeTable {
return list;
}
+ public Iterator<Binding> values() {
+ return Iter.concat(buckets.values().iterator(),
+ noKeyBucket.iterator()) ;
+ }
+
public void clear() {
buckets.clear();
}
http://git-wip-us.apache.org/repos/asf/jena/blob/05c9eae4/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/QueryIterHashJoin.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/QueryIterHashJoin.java b/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/QueryIterHashJoin.java
index 98e779d..d208c54 100644
--- a/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/QueryIterHashJoin.java
+++ b/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/QueryIterHashJoin.java
@@ -18,43 +18,23 @@
package org.apache.jena.sparql.engine.join;
-import java.util.Iterator ;
-import java.util.List ;
-
-import org.apache.jena.atlas.iterator.Iter ;
import org.apache.jena.atlas.logging.Log ;
-import org.apache.jena.sparql.algebra.Algebra ;
-import org.apache.jena.sparql.core.Var ;
import org.apache.jena.sparql.engine.ExecutionContext ;
import org.apache.jena.sparql.engine.QueryIterator ;
import org.apache.jena.sparql.engine.binding.Binding ;
-import org.apache.jena.sparql.engine.iterator.QueryIter2 ;
import org.apache.jena.sparql.engine.iterator.QueryIterNullIterator ;
-import org.apache.jena.sparql.engine.iterator.QueryIterPeek ;
+import org.apache.jena.sparql.engine.join.JoinKey ;
-/** Hash join. This code materializes the left into a probe table
- * then hash joins from the right.
- */
-public class QueryIterHashJoin extends QueryIter2 {
- private long s_countLHS = 0 ; // Left input side size
- private long s_countRHS = 0 ; // Right input side size
- private long s_countResults = 0 ; // Result size.
- private long s_bucketCount = 0 ;
- private long s_maxBucketSize = 0 ;
- private long s_noKeyBucketSize = 0 ;
- private long s_maxMatchGroup = 0 ;
- private long s_countRightMiss = 0 ;
-
- private final JoinKey joinKey ;
- private final HashProbeTable hashTable ;
+/** Hash left join.
+ * This code materializes the right into a probe table
+ * then hash joins from the left.
+ */
- private Iterator<Binding> iterRight ;
- private Binding rowRight = null ;
- private Iterator<Binding> iterCurrent ;
-
- private Binding slot = null ;
- private boolean finished = false ;
+//* This code materializes the left into a probe table
+//* then hash joins from the right.
+public class QueryIterHashJoin extends AbstractIterHashJoin {
+
/**
* Create a hashjoin QueryIterator.
* @param joinKey Join key - if null, one is guessed by snooping the input QueryIterators
@@ -72,7 +52,6 @@ public class QueryIterHashJoin extends QueryIter2 {
}
if ( joinKey != null && joinKey.length() > 1 )
Log.warn(QueryIterHashJoin.class, "Multivariable join key") ;
-
return new QueryIterHashJoin(joinKey, left, right, execCxt) ;
}
@@ -89,111 +68,22 @@ public class QueryIterHashJoin extends QueryIter2 {
}
private QueryIterHashJoin(JoinKey joinKey, QueryIterator left, QueryIterator right, ExecutionContext execCxt) {
- super(left, right, execCxt) ;
-
- if ( joinKey == null ) {
- QueryIterPeek pLeft = QueryIterPeek.create(left, execCxt) ;
- QueryIterPeek pRight = QueryIterPeek.create(right, execCxt) ;
-
- Binding bLeft = pLeft.peek() ;
- Binding bRight = pRight.peek() ;
-
- List<Var> varsLeft = Iter.toList(bLeft.vars()) ;
- List<Var> varsRight = Iter.toList(bRight.vars()) ;
- joinKey = JoinKey.createVarKey(varsLeft, varsRight) ;
- left = pLeft ;
- right = pRight ;
- }
-
- this.joinKey = joinKey ;
- this.iterRight = right ;
- this.hashTable = new HashProbeTable(joinKey) ;
- this.iterCurrent = null ;
- phase1(left) ;
- }
-
- private void phase1(Iterator<Binding> iter1) {
- // Phase 1 : Build hash table.
- for (; iter1.hasNext();) {
- Binding row1 = iter1.next() ;
- s_countLHS ++ ;
- hashTable.put(row1) ;
- }
+ super(joinKey, left, right, execCxt) ;
}
@Override
- protected boolean hasNextBinding() {
- if ( finished )
- return false ;
- if ( slot == null ) {
- slot = moveToNextBindingOrNull() ;
- if ( slot == null ) {
- close() ;
- return false;
- }
- }
- return true ;
+ protected Binding yieldOneResult(Binding rowCurrentProbe, Binding rowStream, Binding rowResult) {
+ return rowResult ;
}
@Override
- protected Binding moveToNextBinding() {
- Binding r = slot ;
- slot = null ;
- return r ;
+ protected Binding noYieldedRows(Binding rowCurrentProbe) {
+ return null;
}
-
- protected Binding moveToNextBindingOrNull() {
- // Gather stats
- // Internal IteratorSlotted.ended call?
- // iterCurrent is the iterator of entries in the left hashed table
- // for the right row.
- // iterRight is the stream of incoming rows.
- for(;;) {
- // Ensure we are processing a row.
- while ( iterCurrent == null ) {
- // Move on to the next row from the right.
- if ( ! iterRight.hasNext() ) {
- joinFinished() ;
- return null ;
- }
-
- rowRight = iterRight.next() ;
- s_countRHS ++ ;
- iterCurrent = hashTable.getCandidates(rowRight) ;
- }
-
- // Emit one row using the rightRow and the current matched left rows.
- if ( ! iterCurrent.hasNext() ) {
- iterCurrent = null ;
- continue ;
- }
-
- Binding rowLeft = iterCurrent.next() ;
- Binding r = Algebra.merge(rowLeft, rowRight) ;
- if (r != null) {
- s_countResults ++ ;
- return r ;
- }
- }
- }
-
- private void joinFinished() {
- }
-
+
@Override
- protected void closeSubIterator() {
- finished = true ;
- if ( JoinLib.JOIN_EXPLAIN ) {
- String x = String.format(
- "HashJoin: LHS=%d RHS=%d Results=%d RightMisses=%d MaxBucket=%d NoKeyBucket=%d",
- s_countLHS, s_countRHS, s_countResults,
- s_countRightMiss, s_maxBucketSize, s_noKeyBucketSize) ;
- System.out.println(x) ;
- }
+ protected QueryIterator joinFinished() {
+ return null;
}
- @Override
- protected void requestSubCancel() {
- finished = true ;
- }
}
http://git-wip-us.apache.org/repos/asf/jena/blob/05c9eae4/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/QueryIterHashLeftJoin_Left.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/QueryIterHashLeftJoin_Left.java b/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/QueryIterHashLeftJoin_Left.java
new file mode 100644
index 0000000..5406311
--- /dev/null
+++ b/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/QueryIterHashLeftJoin_Left.java
@@ -0,0 +1,112 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.jena.sparql.engine.join;
+
+import java.util.* ;
+
+import org.apache.jena.atlas.iterator.Iter ;
+import org.apache.jena.atlas.logging.Log ;
+import org.apache.jena.sparql.engine.ExecutionContext ;
+import org.apache.jena.sparql.engine.QueryIterator ;
+import org.apache.jena.sparql.engine.binding.Binding ;
+import org.apache.jena.sparql.engine.iterator.QueryIterNullIterator ;
+import org.apache.jena.sparql.engine.iterator.QueryIterPlainWrapper ;
+import org.apache.jena.sparql.engine.join.JoinKey ;
+import org.apache.jena.sparql.expr.ExprList ;
+
+/**
+ * Hash left join.
+ *
+ * This code materializes the left hand side into a probe table then hash joins
+ * from the right.
+ *
+ * See {@link QueryIterHashLeftJoin_Right} for one that uses the right hand side
+ * to make the probe table.
+ */
+
+public class QueryIterHashLeftJoin_Left extends AbstractIterHashJoin {
+ // Left join conditions
+ private final ExprList conditions;
+ /**
+ * Create a hashjoin QueryIterator.
+ * @param joinKey Join key - if null, one is guessed by snooping the input QueryIterators
+ * @param left
+ * @param right
+ * @param conditions
+ * @param execCxt
+ * @return QueryIterator
+ */
+ public static QueryIterator create(JoinKey joinKey, QueryIterator left, QueryIterator right, ExprList conditions, ExecutionContext execCxt) {
+ // Easy cases.
+ if ( ! left.hasNext() ) {
+ left.close() ;
+ right.close() ;
+ return QueryIterNullIterator.create(execCxt) ;
+ }
+ if ( ! right.hasNext() ) {
+ right.close() ;
+ return left ;
+ }
+
+ if ( joinKey != null && joinKey.length() > 1 )
+ Log.warn(QueryIterHashLeftJoin_Left.class, "Multivariable join key") ;
+
+ return new QueryIterHashLeftJoin_Left(joinKey, left, right, conditions, execCxt) ;
+ }
+
+ /**
+ * Create a hashjoin QueryIterator.
+ * @param left
+ * @param right
+ * @param execCxt
+ * @return QueryIterator
+ */
+ public static QueryIterator create(QueryIterator left, QueryIterator right, ExprList conditions, ExecutionContext execCxt) {
+ return create(null, left, right, conditions, execCxt) ;
+ }
+
+ private QueryIterHashLeftJoin_Left(JoinKey joinKey, QueryIterator left, QueryIterator right, ExprList conditions, ExecutionContext execCxt) {
+ super(joinKey, left, right, execCxt) ;
+ this.conditions = conditions ;
+ }
+
+ private Set<Binding> leftHits = new HashSet<>() ;
+
+ @Override
+ protected Binding yieldOneResult(Binding rowCurrentProbe, Binding rowStream, Binding rowResult) {
+ if ( conditions != null && ! conditions.isSatisfied(rowResult, getExecContext()) )
+ return null ;
+ leftHits.add(rowCurrentProbe) ;
+ return rowResult ;
+ }
+
+ // Right is stream, left is the probe table.
+ @Override
+ protected Binding noYieldedRows(Binding rowCurrentProbe) {
+ return null;
+ }
+
+ @Override
+ protected QueryIterator joinFinished() {
+ Iterator<Binding> iter = Iter.filter(hashTable.values(), b-> ! leftHits.contains(b) ) ;
+ return new QueryIterPlainWrapper(iter, getExecContext()) ;
+ }
+}
+
+
http://git-wip-us.apache.org/repos/asf/jena/blob/05c9eae4/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/QueryIterHashLeftJoin_Right.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/QueryIterHashLeftJoin_Right.java b/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/QueryIterHashLeftJoin_Right.java
new file mode 100644
index 0000000..00a0c41
--- /dev/null
+++ b/jena-arq/src/main/java/org/apache/jena/sparql/engine/join/QueryIterHashLeftJoin_Right.java
@@ -0,0 +1,108 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.jena.sparql.engine.join;
+
+import org.apache.jena.atlas.logging.Log ;
+import org.apache.jena.sparql.engine.ExecutionContext ;
+import org.apache.jena.sparql.engine.QueryIterator ;
+import org.apache.jena.sparql.engine.binding.Binding ;
+import org.apache.jena.sparql.engine.iterator.QueryIterNullIterator ;
+import org.apache.jena.sparql.engine.join.JoinKey ;
+import org.apache.jena.sparql.expr.ExprList ;
+
+/**
+ * Hash left join.
+ *
+ * This code materializes the right hand side into a probe table then hash joins
+ * from the left.
+ *
+ * See {@link QueryIterHashLeftJoin_Left} for one that uses the right hand side
+ * to make the probe table.
+ */
+
+//* This code materializes the left into a probe table
+//* then hash joins from the right.
+
+public class QueryIterHashLeftJoin_Right extends AbstractIterHashJoin {
+ // Left join conditions
+ private final ExprList conditions;
+
+ /**
+ * Create a hashjoin QueryIterator.
+ * @param joinKey Join key - if null, one is guessed by snooping the input QueryIterators
+ * @param left
+ * @param right
+ * @param conditions
+ * @param execCxt
+ * @return QueryIterator
+ */
+ public static QueryIterator create(JoinKey joinKey, QueryIterator left, QueryIterator right, ExprList conditions, ExecutionContext execCxt) {
+ // Easy cases.
+ if ( ! left.hasNext() ) {
+ left.close() ;
+ right.close() ;
+ return QueryIterNullIterator.create(execCxt) ;
+ }
+ if ( ! right.hasNext() ) {
+ right.close() ;
+ return left ;
+ }
+
+ if ( joinKey != null && joinKey.length() > 1 )
+ Log.warn(QueryIterHashLeftJoin_Right.class, "Multivariable join key") ;
+
+ return new QueryIterHashLeftJoin_Right(joinKey, left, right, conditions, execCxt) ;
+ }
+
+ /**
+ * Create a hashjoin QueryIterator.
+ * @param left
+ * @param right
+ * @param execCxt
+ * @return QueryIterator
+ */
+ public static QueryIterator create(QueryIterator left, QueryIterator right, ExprList conditions, ExecutionContext execCxt) {
+ return create(null, left, right, conditions, execCxt) ;
+ }
+
+ private QueryIterHashLeftJoin_Right(JoinKey joinKey, QueryIterator left, QueryIterator right, ExprList conditions, ExecutionContext execCxt) {
+ // NB Right. Left
+ super(joinKey, right, left, execCxt) ;
+ this.conditions = conditions ;
+ }
+
+ @Override
+ protected Binding yieldOneResult(Binding rowCurrentProbe, Binding rowStream, Binding rowResult) {
+ if ( conditions != null && ! conditions.isSatisfied(rowResult, getExecContext()) )
+ return null ;
+ return rowResult ;
+ }
+
+ @Override
+ protected Binding noYieldedRows(Binding rowCurrentProbe) {
+ return rowCurrentProbe;
+ }
+
+ @Override
+ protected QueryIterator joinFinished() {
+ return null ;
+ }
+}
+
+
http://git-wip-us.apache.org/repos/asf/jena/blob/05c9eae4/jena-arq/src/test/java/org/apache/jena/sparql/engine/join/TS_Join.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/test/java/org/apache/jena/sparql/engine/join/TS_Join.java b/jena-arq/src/test/java/org/apache/jena/sparql/engine/join/TS_Join.java
index bd00872..4e76a8b 100644
--- a/jena-arq/src/test/java/org/apache/jena/sparql/engine/join/TS_Join.java
+++ b/jena-arq/src/test/java/org/apache/jena/sparql/engine/join/TS_Join.java
@@ -32,7 +32,8 @@ import org.junit.runners.Suite.SuiteClasses ;
, TestLeftJoinSimple.class
, TestLeftJoinNestedLoopSimple.class // Real simple materializing version.
, TestLeftJoinNestedLoop.class
- //, TestLeftHashJoin.class
+ , TestHashLeftJoin_Left.class // Left hash, stream right
+ , TestHashLeftJoin_Right.class // Normal implementation.
})
public class TS_Join { }
http://git-wip-us.apache.org/repos/asf/jena/blob/05c9eae4/jena-arq/src/test/java/org/apache/jena/sparql/engine/join/TestHashLeftJoin_Left.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/test/java/org/apache/jena/sparql/engine/join/TestHashLeftJoin_Left.java b/jena-arq/src/test/java/org/apache/jena/sparql/engine/join/TestHashLeftJoin_Left.java
new file mode 100644
index 0000000..ec28c92
--- /dev/null
+++ b/jena-arq/src/test/java/org/apache/jena/sparql/engine/join/TestHashLeftJoin_Left.java
@@ -0,0 +1,32 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.jena.sparql.engine.join;
+
+import org.apache.jena.sparql.algebra.Table ;
+import org.apache.jena.sparql.engine.QueryIterator ;
+import org.apache.jena.sparql.expr.ExprList ;
+
+/** Left outer join where the left hand side used to create the hash probe table */
+public class TestHashLeftJoin_Left extends AbstractTestLeftJoin {
+ @Override
+ public QueryIterator join(JoinKey joinKey, Table left, Table right, ExprList conditions) {
+ return QueryIterHashLeftJoin_Left.create(joinKey, left.iterator(null), right.iterator(null), conditions, null) ;
+ }
+}
+
http://git-wip-us.apache.org/repos/asf/jena/blob/05c9eae4/jena-arq/src/test/java/org/apache/jena/sparql/engine/join/TestHashLeftJoin_Right.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/test/java/org/apache/jena/sparql/engine/join/TestHashLeftJoin_Right.java b/jena-arq/src/test/java/org/apache/jena/sparql/engine/join/TestHashLeftJoin_Right.java
new file mode 100644
index 0000000..3497112
--- /dev/null
+++ b/jena-arq/src/test/java/org/apache/jena/sparql/engine/join/TestHashLeftJoin_Right.java
@@ -0,0 +1,31 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.jena.sparql.engine.join;
+
+import org.apache.jena.sparql.algebra.Table ;
+import org.apache.jena.sparql.engine.QueryIterator ;
+import org.apache.jena.sparql.expr.ExprList ;
+
+/** Left outer join where the right hand side used to create the hash probe table */
+public class TestHashLeftJoin_Right extends AbstractTestLeftJoin {
+ @Override
+ public QueryIterator join(JoinKey joinKey, Table left, Table right, ExprList conditions) {
+ return QueryIterHashLeftJoin_Right.create(joinKey, left.iterator(null), right.iterator(null), conditions, null) ;
+ }
+}