Split iterating into subspaces for performance

9 files changed, 395 insertions, 91 deletions

diff --git a/vespajlib/src/main/java/com/yahoo/tensor/IndexedTensor.java b/vespajlib/src/main/java/com/yahoo/tensor/IndexedTensor.java
index 4091fd97a16..1719a4ecc7a 100644
--- a/vespajlib/src/main/java/com/yahoo/tensor/IndexedTensor.java
+++ b/vespajlib/src/main/java/com/yahoo/tensor/IndexedTensor.java
@@ -12,6 +12,7 @@ import java.util.List;
 import java.util.Map;
 import java.util.NoSuchElementException;
 import java.util.Optional;
+import java.util.Set;
 
 /**
  * An indexed (dense) tensor backed by a double array.
@@ -60,6 +61,20 @@ public class IndexedTensor implements Tensor {
         return new ValueIterator();
     }
 
+    /**
+     * Returns an iterator over value iterators where the outer iterator is over each unique value of the dimensions
+     * given and the inner iterator is over each unique value of the rest of the dimensions, in the same order as
+     * other iterator.
+     * 
+     * @param dimensions the names of the dimensions of the superspace
+     * @param dimensionSizes the size of each dimension in the space we are returning values for, containing
+     *                       one value per dimension of this tensor (in order). Each size may be the same or smaller
+     *                       than the corresponding size of this tensor
+     */
+    public Iterator<SubspaceIterator> subspaceIterator(Set<String> dimensions, int[] dimensionSizes) {
+        return new SuperspaceIterator(dimensions, dimensionSizes);
+    }
+
     /** 
      * Returns the value at the given indexes
      * 
@@ -82,7 +97,13 @@ public class IndexedTensor implements Tensor {
             return Double.NaN;
         }
     }
-    
+
+    /** Returns the value at these indexes */
+    private double get(Indexes indexes) {
+        return values[toValueIndex(indexes.indexesForReading(), dimensionSizes)];
+    }
+
+    // TODO: Change to get
     private static int toValueIndex(int[] indexes, int[] dimensionSizes) {
         if (indexes.length == 1) return indexes[0]; // for speed
         if (indexes.length == 0) return 0; // for speed
@@ -92,7 +113,8 @@ public class IndexedTensor implements Tensor {
             valueIndex += productOfDimensionsAfter(i, dimensionSizes) * indexes[i];
         return valueIndex;
     }
-    
+
+    // TODO: Change to get
     private static int toValueIndex(TensorAddress address, int[] dimensionSizes) {
         if (address.labels().isEmpty()) return 0;
 
@@ -113,11 +135,11 @@ public class IndexedTensor implements Tensor {
     public TensorType type() { return type; }
 
     /**
-     * Returns the lenght of this in the nth dimension
+     * Returns the length of this in the nth dimension
      *
      * @throws IndexOutOfBoundsException if the index is larger than the number of dimensions in this tensor minus one
      */
-    public int length(int dimension) {
+    public int size(int dimension) {
         return dimensionSizes[dimension];
     }
 
@@ -127,30 +149,15 @@ public class IndexedTensor implements Tensor {
             return values.length == 0 ? Collections.emptyMap() : Collections.singletonMap(TensorAddress.empty, values[0]);
         
         ImmutableMap.Builder<TensorAddress, Double> builder = new ImmutableMap.Builder<>();
-        int[] tensorIndexes = new int[dimensionSizes.length];
+        Indexes indexes = new Indexes(dimensionSizes, values.length);
         for (int i = 0; i < values.length; i++) {
-            builder.put(new TensorAddress(tensorIndexes), values[i]);
+            builder.put(indexes.toAddress(), values[i]);
             if (i < values.length -1)
-                next(tensorIndexes);
+                indexes.next();
         }
         return builder.build();
     }
     
-    private void next(int[] tensorIndexes) {
-        nextRecursively(tensorIndexes.length - 1, tensorIndexes);
-    }
-
-    // TODO: Tail recursion -> loop
-    private void nextRecursively(int dimension, int[] tensorIndexes) {
-        if (tensorIndexes[dimension] + 1 == dimensionSizes[dimension]) {
-            tensorIndexes[dimension] = 0;
-            nextRecursively(dimension - 1, tensorIndexes);
-        }
-        else {
-            tensorIndexes[dimension]++;
-        }
-    }
-
     @Override
     public int hashCode() { return Arrays.hashCode(values); }
 
@@ -190,9 +197,9 @@ public class IndexedTensor implements Tensor {
                                                    " for " + type);
             for (int i = 0; i < dimensionSizes.length; i++ ) {
                 Optional<Integer> size = type.dimensions().get(i).size();
-                if (size.isPresent() && size.get() != dimensionSizes[i])
-                    throw new IllegalArgumentException("Size of " + type.dimensions() + " must be " + size.get() + 
-                                                       ", not " + dimensionSizes[i]);
+                if (size.isPresent() && size.get() < dimensionSizes[i])
+                    throw new IllegalArgumentException("Size of " + type.dimensions() + " is " + dimensionSizes[i] +
+                                                       " but cannot be larger than " + size.get());
             }
             
             return new BoundBuilder(type, dimensionSizes);
@@ -397,71 +404,251 @@ public class IndexedTensor implements Tensor {
 
     }
     
+    // TODO: Generalize to vector cell iterator?
     private final class CellIterator implements Iterator<Map.Entry<TensorAddress, Double>> {
 
-        private int cursor = 0;
-        private final int[] tensorIndexes = new int[dimensionSizes.length];
+        private int count = 0;
+        private final Indexes indexes = new Indexes(dimensionSizes, values.length);
 
         @Override
         public boolean hasNext() {
-            return cursor < values.length;
+            return count < indexes.size();
         }
 
         @Override
         public Map.Entry<TensorAddress, Double> next() {
-            if ( ! hasNext()) throw new NoSuchElementException();
+            if ( ! hasNext()) throw new NoSuchElementException("No cell at " + indexes);
             
-            Map.Entry<TensorAddress, Double> current = new Cell(new TensorAddress(tensorIndexes), values[cursor]);
+            Map.Entry<TensorAddress, Double> current = new Cell(indexes.toAddress(), values[count]); // TODO: Correct to get(indexes)
             
-            cursor++;
+            count++;
             if (hasNext())
-                IndexedTensor.this.next(tensorIndexes);
+                indexes.next();
 
             return current;
         }
         
-        private class Cell implements Map.Entry<TensorAddress, Double> {
+    }
 
-            private final TensorAddress address;
-            private final Double value;
-            
-            private Cell(TensorAddress address, Double value) {
-                this.address = address;
-                this.value = value;
-            }
-            
-            @Override
-            public TensorAddress getKey() { return address; }
+    private class Cell implements Map.Entry<TensorAddress, Double> {
 
-            @Override
-            public Double getValue() { return value; }
+        private final TensorAddress address;
+        private final Double value;
 
-            @Override
-            public Double setValue(Double value) {
-                throw new UnsupportedOperationException("A tensor cannot be modified");
-            }
+        private Cell(TensorAddress address, Double value) {
+            this.address = address;
+            this.value = value;
+        }
+
+        @Override
+        public TensorAddress getKey() { return address; }
 
+        @Override
+        public Double getValue() { return value; }
+
+        @Override
+        public Double setValue(Double value) {
+            throw new UnsupportedOperationException("A tensor cannot be modified");
         }
 
     }
 
     private final class ValueIterator implements Iterator<Double> {
 
-        private int cursor = 0;
+        private int count = 0;
 
         @Override
         public boolean hasNext() {
-            return cursor < values.length;
+            return count < values.length;
         }
 
         @Override
         public Double next() {
             try {
-                return values[cursor++];
+                return values[count++];
             }
             catch (IndexOutOfBoundsException e) {
-                throw new NoSuchElementException("No element at position " + cursor);
+                throw new NoSuchElementException("No element at position " + count);
+            }
+        }
+
+    }
+    
+    private final class SuperspaceIterator implements Iterator<SubspaceIterator> {
+
+        private final Indexes superindexes;
+
+        /** true at indexes whose dimension subspaces iterate over */
+        private final boolean[] subdimensionIndexes;
+        
+        /** 
+         * The sizes of the space we'll return values of, one value for each dimension of this tensor,
+         * which may be equal to or smaller than the sizes of this tensor 
+         */
+        private final int[] dimensionSizes;
+
+        private int count = 0;
+        
+        private SuperspaceIterator(Set<String> superdimensionNames, int[] dimensionSizes) {
+            this.dimensionSizes = dimensionSizes;
+            
+            boolean[] superdimensionIndexes = new boolean[dimensionSizes.length]; // for outer iterator
+            subdimensionIndexes = new boolean [dimensionSizes.length]; // for inner iterator
+            for (int i = 0; i < type.dimensions().size(); i++ ) {
+                boolean superDimension = superdimensionNames.contains(type.dimensions().get(i).name());
+                superdimensionIndexes[i] = superDimension;
+                subdimensionIndexes[i] =  ! superDimension;
+            }
+            
+            superindexes = new Indexes(dimensionSizes, superdimensionIndexes);
+        }
+        
+        @Override
+        public boolean hasNext() {
+            return count < superindexes.size();
+        }
+
+        @Override
+        public SubspaceIterator next() {
+            if ( ! hasNext()) throw new NoSuchElementException("No cell at " + superindexes);
+            SubspaceIterator subspace = new SubspaceIterator(subdimensionIndexes, superindexes.indexesCopy(), dimensionSizes);
+            count++;
+            if (hasNext())
+                superindexes.next();
+            return subspace;
+        }
+
+    }
+
+    /**
+     * An iterator over a subspace of this tensor. This is exposed to allow clients to query the size.
+     */
+    public final class SubspaceIterator implements Iterator<Map.Entry<TensorAddress, Double>> {
+
+        private final Indexes indexes;
+        private int count = 0;
+        
+        /** 
+         * Creates a new subspace iterator
+         * 
+         * @param dimensionIndexes a boolean array with a true entry for dimensions we should iterate over and false
+         *                         entries for all other dimensions
+         * @param address the address of the first cell of this subspace. 
+         */
+        private SubspaceIterator(boolean[] dimensionIndexes, int[] address, int[] dimensionSizes) {
+            this.indexes = new Indexes(dimensionSizes, dimensionIndexes, address);
+        }
+        
+        /** Returns the total number of cells in this subspace */
+        public int size() { 
+            return indexes.size();
+        }
+        
+        @Override
+        public boolean hasNext() { return count < indexes.size(); }            
+
+        @Override
+        public Map.Entry<TensorAddress, Double> next() {
+            if ( ! hasNext()) throw new NoSuchElementException("No cell at " + indexes);
+
+            Map.Entry<TensorAddress, Double> current = new Cell(indexes.toAddress(), get(indexes));
+
+            count++;
+            if (hasNext())
+                indexes.next();
+
+            return current;
+        }
+
+    }
+    
+    /** An array of indexes into this tensor which are able to find the next index in the value order */
+    private static class Indexes {
+        
+        private final int size;
+        private final int[] indexes;
+        
+        private final int[] dimensionSizes;
+        
+        /** Only mutate (take next in) the dimension indexes which are true */
+        private final boolean[] iteratingDimensions;
+
+        private Indexes(int[] dimensionSizes, int size) {
+            this(dimensionSizes, trueArray(dimensionSizes.length), size);
+        }
+
+        private Indexes(int[] dimensionSizes, boolean[] iteratingDimensions) {
+            this(dimensionSizes, iteratingDimensions, computeSize(dimensionSizes, iteratingDimensions));
+        }
+        
+        private Indexes(int[] dimensionSizes, boolean[] iteratingDimensionIndexes, int size) {
+            this(dimensionSizes, iteratingDimensionIndexes, new int[dimensionSizes.length], size);
+        }
+
+        private Indexes(int[] dimensionSizes, boolean[] iteratingDimensions, int[] initialIndexes) {
+            this(dimensionSizes, iteratingDimensions, initialIndexes, computeSize(dimensionSizes, iteratingDimensions));
+        }
+
+        private Indexes(int[] dimensionSizes, boolean[] iteratingDimensions, int[] initialIndexes, int size) {
+            this.dimensionSizes = dimensionSizes;
+            this.iteratingDimensions = iteratingDimensions;
+            this.indexes = initialIndexes;
+            this.size = size;
+        }
+        
+        private static boolean[] trueArray(int size) {
+            boolean[] array = new boolean[size];
+            Arrays.fill(array, true);
+            return array;
+        }
+
+        private static int computeSize(int[] dimensionSizes, boolean[] iteratingDimensions) {
+            int size = 1;
+            for (int dimensionIndex = 0; dimensionIndex < dimensionSizes.length; dimensionIndex++)
+                if (iteratingDimensions[dimensionIndex])
+                    size *= dimensionSizes[dimensionIndex];
+            return size;
+        }
+        
+        private static boolean anyTrue(boolean[] values) {
+            for (boolean value : values)
+                if (value) return true;
+            return false;
+        }
+
+        /** Returns the number of values this will iterate over - i.e the product if the iterating dimension sizes */
+        public int size() {
+            return size;
+        }
+
+        private void next() {
+            int currentDimension = indexes.length - 1;
+            while ( ! iteratingDimensions[currentDimension] || 
+                    indexes[currentDimension] + 1 == dimensionSizes[currentDimension]) {
+                if ( iteratingDimensions[currentDimension])
+                    indexes[currentDimension--] = 0; // carry over
+                else // leave this dimension as-is
+                    currentDimension--;
             }
+            indexes[currentDimension]++;
+        }
+
+        /** Returns the address of the current position of these indexes */
+        private TensorAddress toAddress() {
+            // TODO: We may avoid the array copy by issuing a one-time-use address?
+            return new TensorAddress(indexes);
+        }
+        
+        private int[] indexesCopy() {
+            return Arrays.copyOf(indexes, indexes.length);
+        }
+
+        /** Returns a copy of the indexes of this which must not be modified */
+        private int[] indexesForReading() { return indexes; }
+
+        @Override
+        public String toString() {
+            return "indexes " + Arrays.toString(indexes);
         }
 
     }
diff --git a/vespajlib/src/main/java/com/yahoo/tensor/Tensor.java b/vespajlib/src/main/java/com/yahoo/tensor/Tensor.java
index 260c48ace7f..6f655fd5860 100644
--- a/vespajlib/src/main/java/com/yahoo/tensor/Tensor.java
+++ b/vespajlib/src/main/java/com/yahoo/tensor/Tensor.java
@@ -73,8 +73,6 @@ public interface Tensor {
         if (type().dimensions().size() > 0)
             throw new IllegalStateException("This tensor is not dimensionless. Dimensions: " + type().dimensions().size());
         if (size() == 0) return Double.NaN;
-        if (size() > 1)
-            throw new IllegalStateException("This tensor does not have a single value, it has " + size());
         return valueIterator().next();
     }
     
@@ -213,9 +211,7 @@ public interface Tensor {
 
     /** Returns true if the two given tensors are mathematically equivalent, that is whether both have the same content */
     static boolean equals(Tensor a, Tensor b) {
-        if (a == b) return true;
-        if ( ! a.cells().equals(b.cells())) return false;
-        return true;
+        return a == b || a.cells().equals(b.cells());
     }
 
     // ----------------- Factories
@@ -250,9 +246,8 @@ public interface Tensor {
     }
     
     interface Builder {
-        
+
         /** Creates a suitable builder for the given type */
-        // TODO: Create version of this which takes size info and use it when possible
         static Builder of(TensorType type) {
             boolean containsIndexed = type.dimensions().stream().anyMatch(d -> d.isIndexed());
             boolean containsMapped = type.dimensions().stream().anyMatch( d ->  ! d.isIndexed());
@@ -263,7 +258,19 @@ public interface Tensor {
             else // indexed or empty
                 return IndexedTensor.Builder.of(type);
         }
-        
+
+        /** Creates a suitable builder for the given type */
+        static Builder of(TensorType type, int[] dimensionSizes) {
+            boolean containsIndexed = type.dimensions().stream().anyMatch(d -> d.isIndexed());
+            boolean containsMapped = type.dimensions().stream().anyMatch( d ->  ! d.isIndexed());
+            if (containsIndexed && containsMapped)
+                throw new IllegalArgumentException("Combining indexed and mapped dimensions is not supported yet");
+            if (containsMapped)
+                return MappedTensor.Builder.of(type);
+            else // indexed or empty
+                return IndexedTensor.Builder.of(type, dimensionSizes);
+        }
+
         /** Returns the type this is building */
         TensorType type();
         
diff --git a/vespajlib/src/main/java/com/yahoo/tensor/TensorType.java b/vespajlib/src/main/java/com/yahoo/tensor/TensorType.java
index 0c726efc047..e829f4c909b 100644
--- a/vespajlib/src/main/java/com/yahoo/tensor/TensorType.java
+++ b/vespajlib/src/main/java/com/yahoo/tensor/TensorType.java
@@ -53,6 +53,9 @@ public class TensorType {
         return TensorTypeParser.fromSpec(specString);
     }
 
+    /** Returns true if all dimensions of this are indexed */
+    public boolean isIndexed() { return dimensions().stream().allMatch(d -> d.isIndexed()); }
+    
     private static final boolean supportsMixedTypes = false;
     
     /** 
@@ -176,7 +179,7 @@ public class TensorType {
             // both are indexed bound
             IndexedBoundDimension thisIb = (IndexedBoundDimension)this;
             IndexedBoundDimension otherIb = (IndexedBoundDimension)other.get();
-            return thisIb.size().get() > otherIb.size().get() ? thisIb : otherIb;
+            return thisIb.size().get() < otherIb.size().get() ? thisIb : otherIb;
         }
         
         @Override
diff --git a/vespajlib/src/main/java/com/yahoo/tensor/functions/Join.java b/vespajlib/src/main/java/com/yahoo/tensor/functions/Join.java
index 19b4ad39af3..df4ae4ec534 100644
--- a/vespajlib/src/main/java/com/yahoo/tensor/functions/Join.java
+++ b/vespajlib/src/main/java/com/yahoo/tensor/functions/Join.java
@@ -2,18 +2,20 @@ package com.yahoo.tensor.functions;
 
 import com.google.common.annotations.Beta;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.yahoo.tensor.IndexedTensor;
-import com.yahoo.tensor.MappedTensor;
 import com.yahoo.tensor.Tensor;
 import com.yahoo.tensor.TensorAddress;
 import com.yahoo.tensor.TensorType;
 import com.yahoo.tensor.evaluation.EvaluationContext;
 
+import java.util.Arrays;
+import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.Objects;
+import java.util.Optional;
+import java.util.Set;
 import java.util.function.DoubleBinaryOperator;
 
 /**
@@ -69,7 +71,7 @@ public class Join extends PrimitiveTensorFunction {
         TensorType joinedType = a.type().combineWith(b.type());
 
         // Choose join algorithm
-        if (a.type().equals(b.type()) && a.type().dimensions().size() == 1 && a.type().dimensions().get(0).isIndexed())
+        if (hasSingleIndexedDimension(a) && hasSingleIndexedDimension(b) && a.type().dimensions().get(0).name().equals(b.type().dimensions().get(0).name()))
             return indexedVectorJoin((IndexedTensor)a, (IndexedTensor)b, joinedType);
         else if (joinedType.dimensions().size() == a.type().dimensions().size() && joinedType.dimensions().size() == b.type().dimensions().size())
             return singleSpaceJoin(a, b, joinedType);
@@ -81,8 +83,12 @@ public class Join extends PrimitiveTensorFunction {
             return generalJoin(a, b, joinedType);
     }
     
+    private boolean hasSingleIndexedDimension(Tensor tensor) {
+        return tensor.type().dimensions().size() == 1 && tensor.type().dimensions().get(0).isIndexed();
+    }
+    
     private Tensor indexedVectorJoin(IndexedTensor a, IndexedTensor b, TensorType type) {
-        int joinedLength = Math.min(a.length(0), b.length(0));
+        int joinedLength = Math.min(a.size(0), b.size(0));
         Iterator<Double> aIterator = a.valueIterator();
         Iterator<Double> bIterator = b.valueIterator();
         IndexedTensor.Builder builder = IndexedTensor.Builder.of(type, new int[] { joinedLength});
@@ -105,6 +111,42 @@ public class Join extends PrimitiveTensorFunction {
     
     /** Join a tensor into a superspace */
     private Tensor subspaceJoin(Tensor subspace, Tensor superspace, TensorType joinedType, boolean reversedArgumentOrder) {
+        if (subspace.type().isIndexed() && superspace.type().isIndexed())
+            return indexedSubspaceJoin((IndexedTensor) subspace, (IndexedTensor) superspace, joinedType, reversedArgumentOrder);
+        else
+            return generalSubspaceJoin(subspace, superspace, joinedType, reversedArgumentOrder);
+    }
+
+    private Tensor indexedSubspaceJoin(IndexedTensor subspace, IndexedTensor superspace, TensorType joinedType, boolean reversedArgumentOrder) {
+        if (subspace.size() == 0 || superspace.size() == 0) // special case empty here to avoid doing it when finding sizes
+            return Tensor.Builder.of(joinedType, new int[joinedType.dimensions().size()]).build();
+        
+        // Find size of joined tensor
+        int[] joinedSizes = new int[joinedType.dimensions().size()];
+        for (int i = 0; i < joinedSizes.length; i++) {
+            Optional<Integer> subspaceIndex = subspace.type().indexOfDimension(joinedType.dimensions().get(i).name());
+            if (subspaceIndex.isPresent())
+                joinedSizes[i] = Math.min(superspace.size(i), subspace.size(subspaceIndex.get()));
+            else
+                joinedSizes[i] = superspace.size(i);
+        }
+
+        Tensor.Builder builder = Tensor.Builder.of(joinedType, joinedSizes);
+
+        // Find dimensions which are only in the supertype
+        Set<String> superDimensionNames = new HashSet<>(superspace.type().dimensionNames());
+        superDimensionNames.removeAll(subspace.type().dimensionNames());
+        
+        for (Iterator<IndexedTensor.SubspaceIterator> i = superspace.subspaceIterator(superDimensionNames, joinedSizes); i.hasNext(); ) {
+            IndexedTensor.SubspaceIterator subspaceInSuper = i.next();
+            joinSubspaces(subspace.valueIterator(), subspace.size(),
+                          subspaceInSuper, subspaceInSuper.size(),
+                          reversedArgumentOrder, builder);
+        }
+        return builder.build();
+    }
+
+    private Tensor generalSubspaceJoin(Tensor subspace, Tensor superspace, TensorType joinedType, boolean reversedArgumentOrder) {
         int[] subspaceIndexes = subspaceIndexes(superspace.type(), subspace.type());
         Tensor.Builder builder = Tensor.Builder.of(joinedType);
         for (Iterator<Map.Entry<TensorAddress, Double>> i = superspace.cellIterator(); i.hasNext(); ) {
@@ -112,13 +154,26 @@ public class Join extends PrimitiveTensorFunction {
             TensorAddress subaddress = mapAddressToSubspace(supercell.getKey(), subspaceIndexes);
             double subspaceValue = subspace.get(subaddress);
             if ( ! Double.isNaN(subspaceValue))
-                builder.cell(supercell.getKey(), 
+                builder.cell(supercell.getKey(),
                              reversedArgumentOrder ? combinator.applyAsDouble(supercell.getValue(), subspaceValue)
                                                    : combinator.applyAsDouble(subspaceValue, supercell.getValue()));
         }
         return builder.build();
     }
-    
+
+    private void joinSubspaces(Iterator<Double> subspace, int subspaceSize, 
+                               Iterator<Map.Entry<TensorAddress, Double>> superspace, int superspaceSize,
+                               boolean reversedArgumentOrder, Tensor.Builder builder) {
+        int joinedLength = Math.min(subspaceSize, superspaceSize);
+        for (int i = 0; i < joinedLength; i++) {
+            Double subvalue = subspace.next();
+            Map.Entry<TensorAddress, Double> supercell = superspace.next();
+            builder.cell(supercell.getKey(),
+                         reversedArgumentOrder ? combinator.applyAsDouble(supercell.getValue(), subvalue)
+                                               : combinator.applyAsDouble(subvalue, supercell.getValue()));
+        }
+    }
+
     /** Returns the indexes in the superspace type which should be retained to create the subspace type */
     private int[] subspaceIndexes(TensorType supertype, TensorType subtype) {
         int[] subspaceIndexes = new int[subtype.dimensions().size()];
diff --git a/vespajlib/src/main/java/com/yahoo/tensor/functions/Reduce.java b/vespajlib/src/main/java/com/yahoo/tensor/functions/Reduce.java
index 7595d18fb18..d18d628f12f 100644
--- a/vespajlib/src/main/java/com/yahoo/tensor/functions/Reduce.java
+++ b/vespajlib/src/main/java/com/yahoo/tensor/functions/Reduce.java
@@ -2,9 +2,7 @@ package com.yahoo.tensor.functions;
 
 import com.google.common.annotations.Beta;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.yahoo.tensor.IndexedTensor;
-import com.yahoo.tensor.MappedTensor;
 import com.yahoo.tensor.Tensor;
 import com.yahoo.tensor.TensorAddress;
 import com.yahoo.tensor.TensorType;
@@ -149,7 +147,7 @@ public class Reduce extends PrimitiveTensorFunction {
 
     private Tensor reduceIndexedVector(IndexedTensor argument) {
         ValueAggregator valueAggregator = ValueAggregator.ofType(aggregator);
-        for (int i = 0; i < argument.length(0); i++)
+        for (int i = 0; i < argument.size(0); i++)
             valueAggregator.aggregate(argument.get(i));
         return Tensor.Builder.of(TensorType.empty).cell((valueAggregator.aggregatedValue())).build();
     }
diff --git a/vespajlib/src/test/java/com/yahoo/tensor/IndexedTensorTestCase.java b/vespajlib/src/test/java/com/yahoo/tensor/IndexedTensorTestCase.java
index 5e91679c412..d1523d6fcf9 100644
--- a/vespajlib/src/test/java/com/yahoo/tensor/IndexedTensorTestCase.java
+++ b/vespajlib/src/test/java/com/yahoo/tensor/IndexedTensorTestCase.java
@@ -56,10 +56,10 @@ public class IndexedTensorTestCase {
         assertEquals(emptyWithDimensions, emptyWithDimensionsFromString);
 
         IndexedTensor emptyWithDimensionsIndexed = (IndexedTensor)emptyWithDimensions;
-        assertEquals(0, emptyWithDimensionsIndexed.length(0));
-        assertEquals(0, emptyWithDimensionsIndexed.length(1));
+        assertEquals(0, emptyWithDimensionsIndexed.size(0));
+        assertEquals(0, emptyWithDimensionsIndexed.size(1));
     }
-
+    
     @Test
     public void testBoundBuilding() {
         TensorType type = new TensorType.Builder().indexed("v", vSize)
diff --git a/vespajlib/src/test/java/com/yahoo/tensor/JoinTestCase.java b/vespajlib/src/test/java/com/yahoo/tensor/JoinTestCase.java
new file mode 100644
index 00000000000..63dd4a4a644
--- /dev/null
+++ b/vespajlib/src/test/java/com/yahoo/tensor/JoinTestCase.java
@@ -0,0 +1,36 @@
+package com.yahoo.tensor;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author bratseth
+ */
+public class JoinTestCase {
+    
+    /** Test the indexed subspace join optimization */
+    @Test
+    public void testJoinIndexedSubspace() {
+        Tensor t1, t2;
+        
+        t1 = Tensor.from("tensor(x[]):{{x:0}:1.0,{x:1}:2.0}");
+        t2 = Tensor.from("tensor(x[],y[],z[]):{{x:0,y:0,z:0}:6,{x:0,y:1,z:0}:0.0,{x:1,y:0,z:0}:10,{x:1,y:1,z:0}:0.0}");
+        assertEquals(Tensor.from("tensor(x[],y[],z[]):{{x:0,y:0,z:0}:6,{x:0,y:1,z:0}:0.0,{x:1,y:0,z:0}:20.0,{x:1,y:1,z:0}:0.0}"),
+                     t1.multiply(t2));
+        t1 = Tensor.from("tensor(x[]):{{x:0}:1.0,{x:1}:2.0}");
+        t2 = Tensor.from("tensor(x[],y[],z[]):{{x:0,y:0,z:0}:6,{x:0,y:1,z:0}:0.0,{x:1,y:0,z:0}:10,{x:1,y:1,z:0}:0.0}");
+        assertEquals(Tensor.from("tensor(x[],y[],z[]):{{x:0,y:0,z:0}:6,{x:0,y:1,z:0}:0.0,{x:1,y:0,z:0}:5.0,{x:1,y:1,z:0}:0.0}"),
+                     t2.divide(t1));
+
+        t1 = Tensor.from("tensor(y[]):{{y:0}:1.0,{y:1}:2.0}");
+        t2 = Tensor.from("tensor(x[],y[],z[]):{{x:0,y:0,z:0}:6,{x:0,y:1,z:0}:0.0,{x:1,y:0,z:0}:10,{x:1,y:1,z:0}:0.0}");
+        assertEquals(Tensor.from("tensor(x[],y[],z[]):{{x:0,y:0,z:0}:6,{x:0,y:1,z:0}:0.0,{x:1,y:0,z:0}:10.0,{x:1,y:1,z:0}:0.0}"),
+                     t1.multiply(t2));
+        t1 = Tensor.from("tensor(y[]):{{y:0}:1.0,{y:1}:2.0}");
+        t2 = Tensor.from("tensor(x[],y[],z[]):{{x:0,y:0,z:0}:6,{x:0,y:1,z:0}:0.0,{x:1,y:0,z:0}:10,{x:1,y:1,z:0}:0.0}");
+        assertEquals(Tensor.from("tensor(x[],y[],z[]):{{x:0,y:0,z:0}:6,{x:0,y:1,z:0}:0.0,{x:1,y:0,z:0}:10.0,{x:1,y:1,z:0}:0.0}"),
+                     t2.divide(t1));
+    }
+    
+}
diff --git a/vespajlib/src/test/java/com/yahoo/tensor/TensorFunctionBenchmark.java b/vespajlib/src/test/java/com/yahoo/tensor/TensorFunctionBenchmark.java
index bbab92fc16d..a450e3ec9e7 100644
--- a/vespajlib/src/test/java/com/yahoo/tensor/TensorFunctionBenchmark.java
+++ b/vespajlib/src/test/java/com/yahoo/tensor/TensorFunctionBenchmark.java
@@ -117,12 +117,12 @@ public class TensorFunctionBenchmark {
         // - After adding type: 300 ms
         // - After sorting dimensions: 100 ms
         // - After special-casing single space: 2.4 ms
-        time = new TensorFunctionBenchmark().benchmark(5000, vectors(100, 300, TensorType.Dimension.Type.mapped), TensorType.Dimension.Type.mapped, false);
-        System.out.printf("Mapped vectors,          time per join: %1$8.3f ms\n", time);
+        //time = new TensorFunctionBenchmark().benchmark(5000, vectors(100, 300, TensorType.Dimension.Type.mapped), TensorType.Dimension.Type.mapped, false);
+        //System.out.printf("Mapped vectors,          time per join: %1$8.3f ms\n", time);
         // Initial: 760 ms
         // - After special-casing subspace: 13 ms
-        time = new TensorFunctionBenchmark().benchmark(500, matrix(100, 300, TensorType.Dimension.Type.mapped), TensorType.Dimension.Type.mapped, false);
-        System.out.printf("Mapped matrix,           time per join: %1$8.3f ms\n", time);
+        //time = new TensorFunctionBenchmark().benchmark(500, matrix(100, 300, TensorType.Dimension.Type.mapped), TensorType.Dimension.Type.mapped, false);
+        //System.out.printf("Mapped matrix,           time per join: %1$8.3f ms\n", time);
 
         // ---------------- Indexed (unbound) with extra space (sidesteps current special-case optimizations):
         // Initial: 1900 ms
@@ -139,21 +139,25 @@ public class TensorFunctionBenchmark {
         // - After special casing join: 3.6 ms
         // - After special-casing reduce: 0.80 ms
         // - After create IndexedTensor without builder: 0.4 ms
-        // - After double-array backing: 0.1 ms
-        time = new TensorFunctionBenchmark().benchmark(10000, vectors(100, 300, TensorType.Dimension.Type.indexedUnbound), TensorType.Dimension.Type.indexedUnbound, false);
+        // - After double-array backing: 0.09 ms
+        time = new TensorFunctionBenchmark().benchmark(50000, vectors(100, 300, TensorType.Dimension.Type.indexedUnbound), TensorType.Dimension.Type.indexedUnbound, false);
         System.out.printf("Indexed unbound vectors, time per join: %1$8.3f ms\n", time);
         // Initial: 3500 ms
         // - After special-casing subspace: 25 ms
-        // - After moving to iterators: 10 ms
+        // - After moving to iterators: 7.7 ms
+        // - After indexed subspace join algorithm: 6
+        // - After passing sized: 3.7 ms
         time = new TensorFunctionBenchmark().benchmark(500, matrix(100, 300, TensorType.Dimension.Type.indexedUnbound), TensorType.Dimension.Type.indexedUnbound, false);
         System.out.printf("Indexed unbound matrix,  time per join: %1$8.3f ms\n", time);
 
         // ---------------- Indexed bound:
-        // Initial: 0.1 ms
-        time = new TensorFunctionBenchmark().benchmark(10000, vectors(100, 300, TensorType.Dimension.Type.indexedBound), TensorType.Dimension.Type.indexedBound, false);
+        // Initial: 0.09 ms
+        time = new TensorFunctionBenchmark().benchmark(50000, vectors(100, 300, TensorType.Dimension.Type.indexedBound), TensorType.Dimension.Type.indexedBound, false);
         System.out.printf("Indexed bound vectors,   time per join: %1$8.3f ms\n", time);
         // Initial: 25 ms
-        // - After moving to iterators: 10 ms
+        // - After moving to iterators: 7.7 ms
+        // - After indexed subspace join algorithm: 6
+        // - After passing sized: 3.7 ms
         time = new TensorFunctionBenchmark().benchmark(500, matrix(100, 300, TensorType.Dimension.Type.indexedBound), TensorType.Dimension.Type.indexedBound, false);
         System.out.printf("Indexed bound matrix,    time per join: %1$8.3f ms\n", time);
 
diff --git a/vespajlib/src/test/java/com/yahoo/tensor/TensorTestCase.java b/vespajlib/src/test/java/com/yahoo/tensor/TensorTestCase.java
index aa220e93258..eaf26fd82cd 100644
--- a/vespajlib/src/test/java/com/yahoo/tensor/TensorTestCase.java
+++ b/vespajlib/src/test/java/com/yahoo/tensor/TensorTestCase.java
@@ -79,11 +79,15 @@ public class TensorTestCase {
     @Test
     public void testOptimizedComputation() {
         assertEquals("Mapped vector",          42, (int)dotProduct(vector(Type.mapped), vectors(Type.mapped, 2)));
-        assertEquals("Indexed unbound vector", 42, (int)dotProduct(vector(Type.indexedUnbound), vectors(Type.indexedUnbound, 2)));
-        assertEquals("Indexed bound vector",   42, (int)dotProduct(vector(Type.indexedBound), vectors(Type.indexedBound, 2)));
+        assertEquals("Indexed unbound vector", 42, (int)dotProduct(vector(3, Type.indexedUnbound), vectors(5, Type.indexedUnbound, 2)));
+        assertEquals("Indexed unbound vector", 42, (int)dotProduct(vector(5, Type.indexedUnbound), vectors(3, Type.indexedUnbound, 2)));
+        assertEquals("Indexed bound vector",   42, (int)dotProduct(vector(3, Type.indexedBound), vectors(5, Type.indexedBound, 2)));
+        assertEquals("Indexed bound vector",   42, (int)dotProduct(vector(5, Type.indexedBound), vectors(3, Type.indexedBound, 2)));
         assertEquals("Mapped matrix",          42, (int)dotProduct(vector(Type.mapped), matrix(Type.mapped, 2)));
-        assertEquals("Indexed unbound matrix", 42, (int)dotProduct(vector(Type.indexedUnbound), matrix(Type.indexedUnbound, 2)));
-        assertEquals("Indexed bound matrix",   42, (int)dotProduct(vector(Type.indexedBound), matrix(Type.indexedBound, 2)));
+        assertEquals("Indexed unbound matrix", 42, (int)dotProduct(vector(3, Type.indexedUnbound), matrix(5, Type.indexedUnbound, 2)));
+        assertEquals("Indexed unbound matrix", 42, (int)dotProduct(vector(5, Type.indexedUnbound), matrix(3, Type.indexedUnbound, 2)));
+        assertEquals("Indexed bound matrix",   42, (int)dotProduct(vector(3, Type.indexedBound), matrix(5, Type.indexedBound, 2)));
+        assertEquals("Indexed bound matrix",   42, (int)dotProduct(vector(5, Type.indexedBound), matrix(3, Type.indexedBound, 2)));
         assertEquals("Mixed vector",           42, (int)dotProduct(vector(Type.mapped), vectors(Type.indexedUnbound, 2)));
         assertEquals("Mixed vector",           42, (int)dotProduct(vector(Type.mapped), vectors(Type.indexedUnbound, 2)));
         assertEquals("Mixed matrix",           42, (int)dotProduct(vector(Type.mapped), matrix(Type.indexedUnbound, 2)));
@@ -100,7 +104,7 @@ public class TensorTestCase {
         Tensor matrixInKSpace = matrix(Type.mapped, 2).get(0).multiply(unitK);
         assertEquals("Generic computation implementation", 42, (int)dotProduct(vectorInJSpace, Collections.singletonList(matrixInKSpace)));
     }
-
+    
     private double dotProduct(Tensor tensor, List<Tensor> tensors) {
         double sum = 0;
         TensorFunction dotProductFunction = new Reduce(new Join(new ConstantTensor(tensor),
@@ -119,10 +123,17 @@ public class TensorTestCase {
     private Tensor vector(TensorType.Dimension.Type dimensionType) {
         return vectors(dimensionType, 1).get(0);
     }
+
+    private Tensor vector(int vectorSize, TensorType.Dimension.Type dimensionType) {
+        return vectors(vectorSize, dimensionType, 1).get(0);
+    }
     
     /** Create a list of vectors having a single dimension x */
     private List<Tensor> vectors(TensorType.Dimension.Type dimensionType, int vectorCount) {
-        int vectorSize = 3;
+        return vectors(3, dimensionType, vectorCount);
+    }
+
+    private List<Tensor> vectors(int vectorSize, TensorType.Dimension.Type dimensionType, int vectorCount) {
         List<Tensor> tensors = new ArrayList<>();
         TensorType type = vectorType(new TensorType.Builder(), "x", dimensionType, vectorSize);
         for (int i = 0; i < vectorCount; i++) {
@@ -140,7 +151,10 @@ public class TensorTestCase {
      * This matrix contains the same vectors as returned by createVectors, in a single list element for convenience.
      */
     private List<Tensor> matrix(TensorType.Dimension.Type dimensionType, int vectorCount) {
-        int vectorSize = 3;
+        return matrix(3, dimensionType, vectorCount);
+    }
+
+    private List<Tensor> matrix(int vectorSize, TensorType.Dimension.Type dimensionType, int vectorCount) {
         TensorType.Builder typeBuilder = new TensorType.Builder();
         typeBuilder.dimension("i", dimensionType == Type.indexedBound ? Type.indexedUnbound : dimensionType);
         vectorType(typeBuilder, "x", dimensionType, vectorSize);