You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@asterixdb.apache.org by AsterixDB Code Review <do...@asterix-gerrit.ics.uci.edu> on 2021/05/06 20:38:44 UTC
Change in asterixdb[master]: [NO ISSUE] Replace Interval Merge Join with Interval Time Sweep Join
From Caleb Herbel:
Caleb Herbel has uploaded this change for review. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/11364 )
Change subject: [NO ISSUE] Replace Interval Merge Join with Interval Time Sweep Join
......................................................................
[NO ISSUE] Replace Interval Merge Join with Interval Time Sweep Join
- user model changes: no
- storage format changes: no
- interface changes: no
Details:
-Adds Time Sweep Join
-Adds DeletableTupleBufferManager to Hyracks
-Removes Interval Merge Join
-Updates Interval Relations for Time Sweep
Change-Id: Ia61c5c7d950c672e582bb1b7f32bfc389c0442d3
---
A asterixdb/asterix-algebra/src/main/java/org/apache/asterix/algebra/operators/physical/IntervalTimeSweepJoinPOperator.java
M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/AsterixJoinUtils.java
M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/IntervalJoinUtils.java
M asterixdb/asterix-app/src/main/resources/cc.conf
M asterixdb/asterix-app/src/test/resources/cc.conf
M asterixdb/asterix-app/src/test/resources/optimizerts/only.txt
M asterixdb/asterix-app/src/test/resources/runtimets/only_sqlpp.xml
M asterixdb/asterix-runtime/pom.xml
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/ActiveSweepManager.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/EndPointIndexItem.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/IntervalTimeSweepJoinOperatorDescriptor.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/IntervalTimeSweepJoiner.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/TuplePrinterUtil.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/AppendDeletableFrameTupleAccessor.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/IntegerPair.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/IntegerPairPool.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/VPartitionDeletableTupleBufferManager.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AbstractIntervalJoinUtil.java
D asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AfterIntervalJoinUtil.java
D asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/BeforeIntervalJoinUtil.java
D asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/BeforeIntervalJoinUtilFactory.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoveredByIntervalJoinUtil.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoversIntervalJoinUtil.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/IIntervalJoinUtil.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappedByIntervalJoinUtil.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappingIntervalJoinUtil.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlapsIntervalJoinUtil.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/memory/IntervalSideTuple.java
A asterixdb/asterix-runtime/src/test/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/ActiveSweepManagerTest.java
M hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/base/PhysicalOperatorTag.java
A hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTupleAccessor.java
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTuplePointerAccessor.java
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/FrameBufferManager.java
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IFrameBufferManager.java
R hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IPartitionedDeletableTupleBufferManager.java
A hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/ITupleAccessor.java
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/TupleInFrameListAccessor.java
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VPartitionTupleBufferManager.java
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableDeletableTupleMemoryManager.java
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableFrameMemoryManager.java
40 files changed, 2,894 insertions(+), 224 deletions(-)
git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb refs/changes/64/11364/1
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/algebra/operators/physical/IntervalTimeSweepJoinPOperator.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/algebra/operators/physical/IntervalTimeSweepJoinPOperator.java
new file mode 100644
index 0000000..5ac2ae1
--- /dev/null
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/algebra/operators/physical/IntervalTimeSweepJoinPOperator.java
@@ -0,0 +1,170 @@
+/*
+ * 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.asterix.algebra.operators.physical;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.logging.Logger;
+
+import org.apache.asterix.optimizer.rules.util.IntervalPartitions;
+import org.apache.asterix.runtime.operators.joins.interval.TimeSweep.IntervalTimeSweepJoinOperatorDescriptor;
+import org.apache.asterix.runtime.operators.joins.interval.utils.IIntervalJoinUtilFactory;
+import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
+import org.apache.hyracks.algebricks.core.algebra.base.IHyracksJobBuilder;
+import org.apache.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import org.apache.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import org.apache.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import org.apache.hyracks.algebricks.core.algebra.base.PhysicalOperatorTag;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.AbstractBinaryJoinOperator.JoinKind;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.IOperatorSchema;
+import org.apache.hyracks.algebricks.core.algebra.operators.physical.AbstractJoinPOperator;
+import org.apache.hyracks.algebricks.core.algebra.properties.ILocalStructuralProperty;
+import org.apache.hyracks.algebricks.core.algebra.properties.INodeDomain;
+import org.apache.hyracks.algebricks.core.algebra.properties.IPartitioningProperty;
+import org.apache.hyracks.algebricks.core.algebra.properties.IPartitioningRequirementsCoordinator;
+import org.apache.hyracks.algebricks.core.algebra.properties.IPhysicalPropertiesVector;
+import org.apache.hyracks.algebricks.core.algebra.properties.LocalOrderProperty;
+import org.apache.hyracks.algebricks.core.algebra.properties.OrderColumn;
+import org.apache.hyracks.algebricks.core.algebra.properties.OrderedPartitionedProperty;
+import org.apache.hyracks.algebricks.core.algebra.properties.PhysicalRequirements;
+import org.apache.hyracks.algebricks.core.algebra.properties.StructuralPropertiesVector;
+import org.apache.hyracks.algebricks.core.jobgen.impl.JobGenContext;
+import org.apache.hyracks.algebricks.core.jobgen.impl.JobGenHelper;
+import org.apache.hyracks.api.dataflow.IOperatorDescriptor;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
+import org.apache.hyracks.api.job.IOperatorDescriptorRegistry;
+
+public class IntervalTimeSweepJoinPOperator extends AbstractJoinPOperator {
+
+ private final List<LogicalVariable> keysLeftBranch;
+ private final List<LogicalVariable> keysRightBranch;
+ protected final IIntervalJoinUtilFactory mjcf;
+ private final IntervalPartitions intervalPartitions;
+ private final int memSizeInFrames;
+
+ private static final Logger LOGGER = Logger.getLogger(IntervalTimeSweepJoinPOperator.class.getName());
+
+ public IntervalTimeSweepJoinPOperator(JoinKind kind, JoinPartitioningType partitioningType,
+ List<LogicalVariable> sideLeftOfEqualities, List<LogicalVariable> sideRightOfEqualities,
+ int memSizeInFrames, IIntervalJoinUtilFactory mjcf, IntervalPartitions intervalPartitions) {
+ super(kind, partitioningType);
+ this.keysLeftBranch = sideLeftOfEqualities;
+ this.keysRightBranch = sideRightOfEqualities;
+ this.mjcf = mjcf;
+ this.intervalPartitions = intervalPartitions;
+ this.memSizeInFrames = memSizeInFrames;
+
+ LOGGER.fine("IntervalIndexJoinPOperator constructed with: JoinKind=" + kind + ", JoinPartitioningType="
+ + partitioningType + ", List<LogicalVariable>=" + sideLeftOfEqualities + ", List<LogicalVariable>="
+ + sideRightOfEqualities + ", int memSizeInFrames=" + memSizeInFrames
+ + ", IMergeJoinCheckerFactory mjcf=" + mjcf + ".");
+ }
+
+ public IIntervalJoinUtilFactory getIntervalMergeJoinCheckerFactory() {
+ return mjcf;
+ }
+
+ @Override
+ public PhysicalOperatorTag getOperatorTag() {
+ return PhysicalOperatorTag.INTERVAL_TIME_SWEEP_JOIN;
+ }
+
+ @Override
+ public String toString() {
+ return "INTERVAL_MERGE_JOIN" + " " + keysLeftBranch + " " + keysRightBranch;
+ }
+
+ public List<LogicalVariable> getKeysLeftBranch() {
+ return keysLeftBranch;
+ }
+
+ public List<LogicalVariable> getKeysRightBranch() {
+ return keysRightBranch;
+ }
+
+ @Override
+ public boolean isMicroOperator() {
+ return false;
+ }
+
+ @Override
+ public void computeDeliveredProperties(ILogicalOperator iop, IOptimizationContext context) {
+ List<OrderColumn> order = intervalPartitions.getLeftStartColumn();
+ IPartitioningProperty pp = new OrderedPartitionedProperty(order, null, intervalPartitions.getRangeMap());
+ List<ILocalStructuralProperty> propsLocal = new ArrayList<>();
+ propsLocal.add(new LocalOrderProperty(intervalPartitions.getLeftStartColumn()));
+ deliveredProperties = new StructuralPropertiesVector(pp, propsLocal);
+ }
+
+ @Override
+ public PhysicalRequirements getRequiredPropertiesForChildren(ILogicalOperator iop,
+ IPhysicalPropertiesVector reqdByParent, IOptimizationContext context) {
+ StructuralPropertiesVector[] pv = new StructuralPropertiesVector[2];
+ AbstractLogicalOperator op = (AbstractLogicalOperator) iop;
+
+ IPartitioningProperty ppLeft = null;
+ List<ILocalStructuralProperty> ispLeft = new ArrayList<>();
+ ispLeft.add(new LocalOrderProperty(intervalPartitions.getLeftStartColumn()));
+
+ IPartitioningProperty ppRight = null;
+ List<ILocalStructuralProperty> ispRight = new ArrayList<>();
+ ispRight.add(new LocalOrderProperty(intervalPartitions.getRightStartColumn()));
+
+ INodeDomain targetNodeDomain = context.getComputationNodeDomain();
+
+ if (op.getExecutionMode() == AbstractLogicalOperator.ExecutionMode.PARTITIONED) {
+ ppLeft = new OrderedPartitionedProperty(intervalPartitions.getLeftStartColumn(), targetNodeDomain,
+ intervalPartitions.getRangeMap());
+ ppRight = new OrderedPartitionedProperty(intervalPartitions.getRightStartColumn(), targetNodeDomain,
+ intervalPartitions.getRangeMap());
+ }
+
+ pv[0] = new StructuralPropertiesVector(ppLeft, ispLeft);
+ pv[1] = new StructuralPropertiesVector(ppRight, ispRight);
+ IPartitioningRequirementsCoordinator prc = IPartitioningRequirementsCoordinator.NO_COORDINATION;
+ return new PhysicalRequirements(pv, prc);
+ }
+
+ @Override
+ public void contributeRuntimeOperator(IHyracksJobBuilder builder, JobGenContext context, ILogicalOperator op,
+ IOperatorSchema opSchema, IOperatorSchema[] inputSchemas, IOperatorSchema outerPlanSchema)
+ throws AlgebricksException {
+ int[] keysLeft = JobGenHelper.variablesToFieldIndexes(keysLeftBranch, inputSchemas[0]);
+ int[] keysRight = JobGenHelper.variablesToFieldIndexes(keysRightBranch, inputSchemas[1]);
+
+ IOperatorDescriptorRegistry spec = builder.getJobSpec();
+ RecordDescriptor recordDescriptor =
+ JobGenHelper.mkRecordDescriptor(context.getTypeEnvironment(op), opSchema, context);
+
+ IOperatorDescriptor opDesc = getIntervalOperatorDescriptor(keysLeft, keysRight, spec, recordDescriptor, mjcf);
+ contributeOpDesc(builder, (AbstractLogicalOperator) op, opDesc);
+
+ ILogicalOperator src1 = op.getInputs().get(0).getValue();
+ builder.contributeGraphEdge(src1, 0, op, 0);
+ ILogicalOperator src2 = op.getInputs().get(1).getValue();
+ builder.contributeGraphEdge(src2, 0, op, 1);
+ }
+
+ IOperatorDescriptor getIntervalOperatorDescriptor(int[] keysLeft, int[] keysRight, IOperatorDescriptorRegistry spec,
+ RecordDescriptor recordDescriptor, IIntervalJoinUtilFactory mjcf) {
+ return new IntervalTimeSweepJoinOperatorDescriptor(spec, memSizeInFrames, keysLeft, keysRight, recordDescriptor,
+ mjcf);
+ }
+}
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/AsterixJoinUtils.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/AsterixJoinUtils.java
index 672cb25..0e196b1 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/AsterixJoinUtils.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/AsterixJoinUtils.java
@@ -80,6 +80,6 @@
}
IntervalPartitions intervalPartitions =
IntervalJoinUtils.createIntervalPartitions(op, fi, sideLeft, sideRight, rangeMap, context, LEFT, RIGHT);
- IntervalJoinUtils.setSortMergeIntervalJoinOp(op, fi, sideLeft, sideRight, context, intervalPartitions);
+ IntervalJoinUtils.setIntervalTimeSweepJoinOp(op, fi, sideLeft, sideRight, context, intervalPartitions);
}
}
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/IntervalJoinUtils.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/IntervalJoinUtils.java
index e10f9fb..ea28232 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/IntervalJoinUtils.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/IntervalJoinUtils.java
@@ -27,13 +27,12 @@
import java.util.Map;
import org.apache.asterix.algebra.operators.physical.IntervalMergeJoinPOperator;
+import org.apache.asterix.algebra.operators.physical.IntervalTimeSweepJoinPOperator;
import org.apache.asterix.common.annotations.RangeAnnotation;
import org.apache.asterix.common.exceptions.CompilationException;
import org.apache.asterix.common.exceptions.ErrorCode;
import org.apache.asterix.lang.common.util.FunctionUtil;
import org.apache.asterix.om.functions.BuiltinFunctions;
-import org.apache.asterix.runtime.operators.joins.interval.utils.AfterIntervalJoinUtilFactory;
-import org.apache.asterix.runtime.operators.joins.interval.utils.BeforeIntervalJoinUtilFactory;
import org.apache.asterix.runtime.operators.joins.interval.utils.CoveredByIntervalJoinUtilFactory;
import org.apache.asterix.runtime.operators.joins.interval.utils.CoversIntervalJoinUtilFactory;
import org.apache.asterix.runtime.operators.joins.interval.utils.IIntervalJoinUtilFactory;
@@ -55,7 +54,7 @@
import org.apache.hyracks.algebricks.core.algebra.functions.IFunctionInfo;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.AbstractBinaryJoinOperator;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
-import org.apache.hyracks.algebricks.core.algebra.operators.logical.OrderOperator;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.OrderOperator.IOrder.OrderKind;
import org.apache.hyracks.algebricks.core.algebra.operators.physical.AbstractJoinPOperator;
import org.apache.hyracks.algebricks.core.algebra.operators.physical.AssignPOperator;
import org.apache.hyracks.algebricks.core.algebra.properties.IPartitioningProperty.PartitioningType;
@@ -89,6 +88,15 @@
context.getPhysicalOptimizationConfig().getMaxFramesForJoin(), mjcf, intervalPartitions));
}
+ protected static void setIntervalTimeSweepJoinOp(AbstractBinaryJoinOperator op, FunctionIdentifier fi,
+ List<LogicalVariable> sideLeft, List<LogicalVariable> sideRight, IOptimizationContext context,
+ IntervalPartitions intervalPartitions) throws AlgebricksException {
+ IIntervalJoinUtilFactory mjcf = createIntervalJoinCheckerFactory(fi, intervalPartitions.getRangeMap());
+ op.setPhysicalOperator(new IntervalTimeSweepJoinPOperator(op.getJoinKind(),
+ AbstractJoinPOperator.JoinPartitioningType.BROADCAST, sideLeft, sideRight,
+ context.getPhysicalOptimizationConfig().getMaxFramesForJoin(), mjcf, intervalPartitions));
+ }
+
/**
* Certain Relations not yet supported as seen below. Will default to regular join.
* Inserts partition sort key.
@@ -107,12 +115,15 @@
insertPartitionSortKey(op, left, leftPartitionVar, sideLeft.get(0), context);
insertPartitionSortKey(op, right, rightPartitionVar, sideRight.get(0), context);
- List<IntervalColumn> leftIC = Collections.singletonList(new IntervalColumn(leftPartitionVar.get(0),
- leftPartitionVar.get(1), OrderOperator.IOrder.OrderKind.ASC));
- List<IntervalColumn> rightIC = Collections.singletonList(new IntervalColumn(rightPartitionVar.get(0),
- rightPartitionVar.get(1), OrderOperator.IOrder.OrderKind.ASC));
+ final int INTERVAL_START_INDEX = 0;
+ final int INTERVAL_END_INDEX = 1;
+ int rightFirstSortField = INTERVAL_START_INDEX;
+ int rightSecondSortField = INTERVAL_END_INDEX;
+ int leftFirstSortField = INTERVAL_START_INDEX;
+ int leftSecondSortField = INTERVAL_END_INDEX;
+ OrderKind orderOfJoin = OrderKind.ASC;
- //Set Partitioning Types
+ //Set Partitioning Types and reverse order of join if necessary
PartitioningType leftPartitioningType = PartitioningType.ORDERED_PARTITIONED;
PartitioningType rightPartitioningType = PartitioningType.ORDERED_PARTITIONED;
if (fi.equals(BuiltinFunctions.INTERVAL_OVERLAPPED_BY)) {
@@ -133,6 +144,14 @@
} else {
throw new CompilationException(ErrorCode.COMPILATION_ILLEGAL_STATE, fi.getName());
}
+
+ List<IntervalColumn> leftIC =
+ Collections.singletonList(new IntervalColumn(leftPartitionVar.get(leftFirstSortField),
+ leftPartitionVar.get(leftSecondSortField), orderOfJoin));
+ List<IntervalColumn> rightIC =
+ Collections.singletonList(new IntervalColumn(rightPartitionVar.get(rightFirstSortField),
+ rightPartitionVar.get(rightSecondSortField), orderOfJoin));
+
return new IntervalPartitions(rangeMap, leftIC, rightIC, leftPartitioningType, rightPartitioningType);
}
@@ -193,10 +212,6 @@
mjcf = new CoversIntervalJoinUtilFactory();
} else if (fi.equals(BuiltinFunctions.INTERVAL_COVERED_BY)) {
mjcf = new CoveredByIntervalJoinUtilFactory();
- } else if (fi.equals(BuiltinFunctions.INTERVAL_BEFORE)) {
- mjcf = new BeforeIntervalJoinUtilFactory();
- } else if (fi.equals(BuiltinFunctions.INTERVAL_AFTER)) {
- mjcf = new AfterIntervalJoinUtilFactory();
} else if (fi.equals(BuiltinFunctions.INTERVAL_OVERLAPPING)) {
mjcf = new OverlappingIntervalJoinUtilFactory(rangeMap);
} else {
diff --git a/asterixdb/asterix-app/src/main/resources/cc.conf b/asterixdb/asterix-app/src/main/resources/cc.conf
index 51c71c2..aab7364 100644
--- a/asterixdb/asterix-app/src/main/resources/cc.conf
+++ b/asterixdb/asterix-app/src/main/resources/cc.conf
@@ -19,19 +19,9 @@
txn.log.dir=target/tmp/asterix_nc1/txnlog
core.dump.dir=target/tmp/asterix_nc1/coredump
iodevices=asterix_nc1/iodevice1
-iodevices=asterix_nc1/iodevice2
nc.api.port=19004
#jvm.args=-agentlib:jdwp=transport=dt_socket,server=y,suspend=y,address=5006
-[nc/asterix_nc2]
-ncservice.port=9091
-txn.log.dir=target/tmp/asterix_nc2/txnlog
-core.dump.dir=target/tmp/asterix_nc2/coredump
-iodevices=asterix_nc2/iodevice1
-iodevices=asterix_nc1/iodevice2
-nc.api.port=19005
-#jvm.args=-agentlib:jdwp=transport=dt_socket,server=y,suspend=y,address=5007
-
[nc]
address=127.0.0.1
command=asterixnc
diff --git a/asterixdb/asterix-app/src/test/resources/cc.conf b/asterixdb/asterix-app/src/test/resources/cc.conf
index 953284964..f8d1ce9 100644
--- a/asterixdb/asterix-app/src/test/resources/cc.conf
+++ b/asterixdb/asterix-app/src/test/resources/cc.conf
@@ -18,19 +18,10 @@
[nc/asterix_nc1]
txn.log.dir=target/tmp/asterix_nc1/txnlog
core.dump.dir=target/tmp/asterix_nc1/coredump
-iodevices=target/tmp/asterix_nc1/iodevice1,
-iodevices=../asterix-server/target/tmp/asterix_nc1/iodevice2
+iodevices=target/tmp/asterix_nc1/iodevice1
nc.api.port=19004
#jvm.args=-agentlib:jdwp=transport=dt_socket,server=y,suspend=y,address=5006
-[nc/asterix_nc2]
-ncservice.port=9091
-txn.log.dir=target/tmp/asterix_nc2/txnlog
-core.dump.dir=target/tmp/asterix_nc2/coredump
-iodevices=target/tmp/asterix_nc2/iodevice1,../asterix-server/target/tmp/asterix_nc2/iodevice2
-nc.api.port=19005
-#jvm.args=-agentlib:jdwp=transport=dt_socket,server=y,suspend=y,address=5007
-
[nc]
credential.file=src/test/resources/security/passwd
python.cmd.autolocate=true
diff --git a/asterixdb/asterix-app/src/test/resources/optimizerts/only.txt b/asterixdb/asterix-app/src/test/resources/optimizerts/only.txt
index fe95886..106f5c0 100644
--- a/asterixdb/asterix-app/src/test/resources/optimizerts/only.txt
+++ b/asterixdb/asterix-app/src/test/resources/optimizerts/only.txt
@@ -16,3 +16,5 @@
# specific language governing permissions and limitations
# under the License.
#
+
+temporal/interval_joins/
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/only_sqlpp.xml b/asterixdb/asterix-app/src/test/resources/runtimets/only_sqlpp.xml
index 334dd52..ff6ef8f 100644
--- a/asterixdb/asterix-app/src/test/resources/runtimets/only_sqlpp.xml
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/only_sqlpp.xml
@@ -19,5 +19,105 @@
!-->
<test-suite xmlns="urn:xml.testframework.asterix.apache.org" ResultOffsetPath="results" QueryOffsetPath="queries_sqlpp" QueryFileExtension=".sqlpp">
<test-group name="failed">
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_after">
+ <output-dir compare="Text">interval_after</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_before">
+ <output-dir compare="Text">interval_before</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_covered_by">
+ <output-dir compare="Text">interval_covered_by</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_covers">
+ <output-dir compare="Text">interval_covers</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_ended_by">
+ <output-dir compare="Text">interval_ended_by</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_ends">
+ <output-dir compare="Text">interval_ends</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_meets">
+ <output-dir compare="Text">interval_meets</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_met_by">
+ <output-dir compare="Text">interval_met_by</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_overlapped_by">
+ <output-dir compare="Text">interval_overlapped_by</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_overlapping">
+ <output-dir compare="Text">interval_overlapping</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_overlaps">
+ <output-dir compare="Text">interval_overlaps</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_started_by">
+ <output-dir compare="Text">interval_started_by</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_starts">
+ <output-dir compare="Text">interval_starts</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins_spilling">
+ <compilation-unit name="interval_after">
+ <output-dir compare="Text">interval_after</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins_spilling">
+ <compilation-unit name="interval_before">
+ <output-dir compare="Text">interval_before</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins_spilling">
+ <compilation-unit name="interval_covered_by">
+ <output-dir compare="Text">interval_covered_by</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins_spilling">
+ <compilation-unit name="interval_covers">
+ <output-dir compare="Text">interval_covers</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins_spilling">
+ <compilation-unit name="interval_overlapped_by">
+ <output-dir compare="Text">interval_overlapped_by</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins_spilling">
+ <compilation-unit name="interval_overlapping">
+ <output-dir compare="Text">interval_overlapping</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins_spilling">
+ <compilation-unit name="interval_overlaps">
+ <output-dir compare="Text">interval_overlaps</output-dir>
+ </compilation-unit>
+ </test-case>
</test-group>
</test-suite>
diff --git a/asterixdb/asterix-runtime/pom.xml b/asterixdb/asterix-runtime/pom.xml
index 6672b38..c19b5bd 100644
--- a/asterixdb/asterix-runtime/pom.xml
+++ b/asterixdb/asterix-runtime/pom.xml
@@ -116,6 +116,10 @@
<artifactId>hyracks-control-common</artifactId>
</dependency>
<dependency>
+ <groupId>org.apache.hyracks</groupId>
+ <artifactId>hyracks-test-support</artifactId>
+ </dependency>
+ <dependency>
<groupId>org.apache.asterix</groupId>
<artifactId>asterix-transactions</artifactId>
<version>${project.version}</version>
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/ActiveSweepManager.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/ActiveSweepManager.java
new file mode 100644
index 0000000..de57295
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/ActiveSweepManager.java
@@ -0,0 +1,116 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep;
+
+import java.util.Comparator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.PriorityQueue;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.FrameTupleCursor;
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.IntervalJoinUtil;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.std.buffermanager.IPartitionedDeletableTupleBufferManager;
+import org.apache.hyracks.dataflow.std.structures.TuplePointer;
+
+public class ActiveSweepManager {
+
+ private static final Logger LOGGER = Logger.getLogger(ActiveSweepManager.class.getName());
+
+ private final int partition;
+ private final int key;
+ private final byte indexPoint;
+
+ private final IPartitionedDeletableTupleBufferManager bufferManager;
+ private final PriorityQueue<EndPointIndexItem> indexQueue;
+ private EndPointIndexItem item = null;
+ private final LinkedList<TuplePointer> active = new LinkedList<>();
+
+ public ActiveSweepManager(IPartitionedDeletableTupleBufferManager bufferManager, int key, int joinBranch,
+ Comparator<EndPointIndexItem> endPointComparator, byte point) {
+ this.bufferManager = bufferManager;
+ this.key = key;
+ this.partition = joinBranch;
+ indexQueue = new PriorityQueue<>(16, endPointComparator);
+ this.indexPoint = point;
+ }
+
+ public boolean addTuple(FrameTupleCursor cursor, TuplePointer tp) throws HyracksDataException {
+ if (bufferManager.insertTuple(partition, cursor.getAccessor(), cursor.getTupleId(), tp)) {
+ long point;
+ if (indexPoint == 1) {
+ point = IntervalJoinUtil.getIntervalEnd(cursor.getAccessor(), cursor.getTupleId(), key);
+ } else {
+ point = IntervalJoinUtil.getIntervalStart(cursor.getAccessor(), cursor.getTupleId(), key);
+ }
+ EndPointIndexItem e = new EndPointIndexItem(tp, indexPoint, point);
+ indexQueue.add(e);
+ active.add(tp);
+ item = indexQueue.peek();
+ if (LOGGER.isLoggable(Level.FINE)) {
+ LOGGER.fine("Add to memory (partition: " + partition + " index: " + e + ").");
+ }
+ // System.err.println("Add to memory (partition: " + partition + " index: " + e + ").");
+ return true;
+ }
+ return false;
+ }
+
+ public void removeTop() throws HyracksDataException {
+ // Remove from active.
+ if (LOGGER.isLoggable(Level.FINE)) {
+ LOGGER.fine("Remove top from memory (partition: " + partition + " index: " + item + ").");
+ }
+ // System.err.println("Remove top from memory (partition: " + partition + " index: " + item + ").");
+ bufferManager.deleteTuple(partition, item.getTuplePointer());
+ active.remove(item.getTuplePointer());
+ indexQueue.remove(item);
+ item = indexQueue.peek();
+ }
+
+ public long getTopPoint() {
+ // System.err.println("Get top from memory (partition: " + partition + " index: " + item + ").");
+ return item.getPoint();
+ }
+
+ public List<TuplePointer> getActiveList() {
+ return active;
+ }
+
+ public boolean isEmpty() {
+ return indexQueue.isEmpty();
+ }
+
+ public boolean hasRecords() {
+ return !indexQueue.isEmpty();
+ }
+
+ public void clear() throws HyracksDataException {
+ for (TuplePointer leftTp : active) {
+ bufferManager.deleteTuple(partition, leftTp);
+ }
+ indexQueue.clear();
+ active.clear();
+ item = null;
+ bufferManager.clearPartition(partition);
+ }
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/EndPointIndexItem.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/EndPointIndexItem.java
new file mode 100644
index 0000000..4a61b56
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/EndPointIndexItem.java
@@ -0,0 +1,95 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep;
+
+import java.io.Serializable;
+import java.util.Comparator;
+
+import org.apache.hyracks.dataflow.std.structures.TuplePointer;
+
+public class EndPointIndexItem implements Serializable {
+ private static final long serialVersionUID = 1L;
+
+ public static final byte START_POINT = 0;
+ public static final byte END_POINT = 1;
+
+ public static final Comparator<EndPointIndexItem> EndPointAscComparator = new Comparator<EndPointIndexItem>() {
+ @Override
+ public int compare(EndPointIndexItem epi1, EndPointIndexItem epi2) {
+ int c = Long.compare(epi1.getPoint(), epi2.getPoint());
+ if (c == 0) {
+ c = epi1.getStart() - epi2.getStart();
+ }
+ return c;
+ }
+
+ };
+
+ public static final Comparator<EndPointIndexItem> EndPointDescComparator = new Comparator<EndPointIndexItem>() {
+ @Override
+ public int compare(EndPointIndexItem epi1, EndPointIndexItem epi2) {
+ int c = Long.compare(epi2.getPoint(), epi1.getPoint());
+ if (c == 0) {
+ c = epi2.getStart() - epi1.getStart();
+ }
+ return c;
+ }
+
+ };
+
+ private TuplePointer tp;
+ private byte start;
+ private long point;
+
+ public EndPointIndexItem() {
+ reset(new TuplePointer(), (byte) -1, Long.MIN_VALUE);
+ }
+
+ public EndPointIndexItem(TuplePointer tp, byte start, long point) {
+ reset(tp, start, point);
+ }
+
+ public void reset(EndPointIndexItem item) {
+ reset(item.getTuplePointer(), item.getStart(), item.getPoint());
+ }
+
+ public void reset(TuplePointer tp, byte start, long point) {
+ this.tp = tp;
+ this.start = start;
+ this.point = point;
+ }
+
+ public TuplePointer getTuplePointer() {
+ return tp;
+ }
+
+ public byte getStart() {
+ return start;
+ }
+
+ public long getPoint() {
+ return point;
+ }
+
+ @Override
+ public String toString() {
+ return "EndPointIndexItem " + tp + " " + (start == START_POINT ? "start" : "end") + ": " + point;
+ }
+
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/IntervalTimeSweepJoinOperatorDescriptor.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/IntervalTimeSweepJoinOperatorDescriptor.java
new file mode 100644
index 0000000..e517a85
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/IntervalTimeSweepJoinOperatorDescriptor.java
@@ -0,0 +1,189 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep;
+
+import java.nio.ByteBuffer;
+import java.util.Comparator;
+
+import org.apache.asterix.runtime.operators.joins.interval.utils.IIntervalJoinUtil;
+import org.apache.asterix.runtime.operators.joins.interval.utils.IIntervalJoinUtilFactory;
+import org.apache.hyracks.api.context.IHyracksTaskContext;
+import org.apache.hyracks.api.dataflow.ActivityId;
+import org.apache.hyracks.api.dataflow.IActivity;
+import org.apache.hyracks.api.dataflow.IActivityGraphBuilder;
+import org.apache.hyracks.api.dataflow.IOperatorNodePushable;
+import org.apache.hyracks.api.dataflow.TaskId;
+import org.apache.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.api.job.IOperatorDescriptorRegistry;
+import org.apache.hyracks.api.job.JobId;
+import org.apache.hyracks.dataflow.common.comm.util.FrameUtils;
+import org.apache.hyracks.dataflow.std.base.AbstractActivityNode;
+import org.apache.hyracks.dataflow.std.base.AbstractOperatorDescriptor;
+import org.apache.hyracks.dataflow.std.base.AbstractStateObject;
+import org.apache.hyracks.dataflow.std.base.AbstractUnaryInputSinkOperatorNodePushable;
+import org.apache.hyracks.dataflow.std.base.AbstractUnaryInputUnaryOutputOperatorNodePushable;
+
+public class IntervalTimeSweepJoinOperatorDescriptor extends AbstractOperatorDescriptor {
+ private static final long serialVersionUID = 1L;
+
+ private static final int JOIN_BUILD_ACTIVITY_ID = 0;
+ private static final int JOIN_PROBE_ACTIVITY_ID = 1;
+ private final int buildKey;
+ private final int probeKey;
+ private final int memoryForJoin;
+ private final IIntervalJoinUtilFactory imjcf;
+
+ public IntervalTimeSweepJoinOperatorDescriptor(IOperatorDescriptorRegistry spec, int memoryForJoin, int[] buildKey,
+ int[] probeKeys, RecordDescriptor recordDescriptor, IIntervalJoinUtilFactory imjcf) {
+ super(spec, 2, 1);
+ outRecDescs[0] = recordDescriptor;
+ this.buildKey = buildKey[0];
+ this.probeKey = probeKeys[0];
+ this.memoryForJoin = memoryForJoin;
+ this.imjcf = imjcf;
+ }
+
+ @Override
+ public void contributeActivities(IActivityGraphBuilder builder) {
+ ActivityId buildAid = new ActivityId(odId, JOIN_BUILD_ACTIVITY_ID);
+ ActivityId probeAid = new ActivityId(odId, JOIN_PROBE_ACTIVITY_ID);
+
+ IActivity probeAN = new JoinProbeActivityNode(probeAid);
+ IActivity buildAN = new JoinBuildActivityNode(buildAid, probeAid);
+
+ builder.addActivity(this, buildAN);
+ builder.addSourceEdge(0, buildAN, 0);
+
+ builder.addActivity(this, probeAN);
+ builder.addSourceEdge(1, probeAN, 0);
+ builder.addTargetEdge(0, probeAN, 0);
+ builder.addBlockingEdge(buildAN, probeAN);
+ }
+
+ public static class JoinCacheTaskState extends AbstractStateObject {
+ private IntervalTimeSweepJoiner joiner;
+
+ private JoinCacheTaskState(JobId jobId, TaskId taskId) {
+ super(jobId, taskId);
+ }
+ }
+
+ private class JoinBuildActivityNode extends AbstractActivityNode {
+ private static final long serialVersionUID = 1L;
+
+ private final ActivityId nljAid;
+
+ public JoinBuildActivityNode(ActivityId id, ActivityId nljAid) {
+ super(id);
+ this.nljAid = nljAid;
+ }
+
+ @Override
+ public IOperatorNodePushable createPushRuntime(final IHyracksTaskContext ctx,
+ IRecordDescriptorProvider recordDescProvider, final int partition, int nPartitions) {
+ final RecordDescriptor rd0 = recordDescProvider.getInputRecordDescriptor(nljAid, 0);
+ final RecordDescriptor rd1 = recordDescProvider.getInputRecordDescriptor(getActivityId(), 0);
+
+ return new AbstractUnaryInputSinkOperatorNodePushable() {
+ private JoinCacheTaskState state;
+
+ @Override
+ public void open() throws HyracksDataException {
+ state = new JoinCacheTaskState(ctx.getJobletContext().getJobId(),
+ new TaskId(getActivityId(), partition));
+
+ IIntervalJoinUtil imjc = imjcf.createIntervalMergeJoinUtil(buildKey, probeKey, ctx, nPartitions);
+
+ byte point = true ? EndPointIndexItem.START_POINT : EndPointIndexItem.END_POINT;
+ Comparator<EndPointIndexItem> endPointComparator =
+ true ? EndPointIndexItem.EndPointAscComparator : EndPointIndexItem.EndPointDescComparator;
+
+ state.joiner = new IntervalTimeSweepJoiner(ctx, memoryForJoin, imjc, buildKey, probeKey, rd0, rd1,
+ endPointComparator);
+ }
+
+ @Override
+ public void nextFrame(ByteBuffer buffer) throws HyracksDataException {
+ ByteBuffer copyBuffer = ctx.allocateFrame(buffer.capacity());
+ FrameUtils.copyAndFlip(buffer, copyBuffer);
+ state.joiner.processBuildFrame(copyBuffer);
+ }
+
+ @Override
+ public void close() throws HyracksDataException {
+ state.joiner.processBuildClose();
+ ctx.setStateObject(state);
+ }
+
+ @Override
+ public void fail() {
+ // No variables to update.
+ }
+ };
+ }
+ }
+
+ private class JoinProbeActivityNode extends AbstractActivityNode {
+ private static final long serialVersionUID = 1L;
+
+ public JoinProbeActivityNode(ActivityId id) {
+ super(id);
+ }
+
+ @Override
+ public IOperatorNodePushable createPushRuntime(final IHyracksTaskContext ctx,
+ IRecordDescriptorProvider recordDescProvider, final int partition, int nPartitions) {
+ return new AbstractUnaryInputUnaryOutputOperatorNodePushable() {
+ private JoinCacheTaskState state;
+
+ @Override
+ public void open() throws HyracksDataException {
+ writer.open();
+ state = (JoinCacheTaskState) ctx.getStateObject(
+ new TaskId(new ActivityId(getOperatorId(), JOIN_BUILD_ACTIVITY_ID), partition));
+ }
+
+ @Override
+ public void nextFrame(ByteBuffer buffer) throws HyracksDataException {
+ // Maybe Come back
+ ByteBuffer copyBuffer = ctx.allocateFrame(buffer.capacity());
+ FrameUtils.copyAndFlip(buffer, copyBuffer);
+ state.joiner.processProbeFrame(copyBuffer, writer);
+ }
+
+ @Override
+ public void close() throws HyracksDataException {
+ try {
+ state.joiner.processProbeClose(writer);
+ } finally {
+ writer.close();
+ }
+ }
+
+ @Override
+ public void fail() throws HyracksDataException {
+ writer.fail();
+ }
+ };
+ }
+ }
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/IntervalTimeSweepJoiner.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/IntervalTimeSweepJoiner.java
new file mode 100644
index 0000000..40b8960
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/IntervalTimeSweepJoiner.java
@@ -0,0 +1,337 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep;
+
+import java.nio.ByteBuffer;
+import java.util.Comparator;
+import java.util.List;
+import java.util.logging.Logger;
+
+import org.apache.asterix.runtime.operators.joins.interval.TimeSweep.memory.VPartitionDeletableTupleBufferManager;
+import org.apache.asterix.runtime.operators.joins.interval.utils.IIntervalJoinUtil;
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.FrameTupleCursor;
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.RunFilePointer;
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.RunFileStream;
+import org.apache.hyracks.api.comm.IFrame;
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
+import org.apache.hyracks.api.comm.IFrameWriter;
+import org.apache.hyracks.api.comm.VSizeFrame;
+import org.apache.hyracks.api.context.IHyracksTaskContext;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.common.comm.io.FrameTupleAppender;
+import org.apache.hyracks.dataflow.common.comm.util.FrameUtils;
+import org.apache.hyracks.dataflow.std.buffermanager.ITupleAccessor;
+import org.apache.hyracks.dataflow.std.structures.TuplePointer;
+
+/**
+ * Interval Index Merge Joiner takes two sorted streams of input and joins.
+ * The two sorted streams must be in a logical order and the comparator must
+ * support keeping that order so the join will work.
+ * The left stream will spill to disk when memory is full.
+ * The both right and left use memory to maintain active intervals for the join.
+ */
+public class IntervalTimeSweepJoiner {
+
+ private static final Logger LOGGER = Logger.getLogger(IntervalTimeSweepJoiner.class.getName());
+
+ protected static final int JOIN_PARTITIONS = 2;
+ protected static final int BUILD_PARTITION = 0;
+ protected static final int PROBE_PARTITION = 1;
+
+ private final IIntervalJoinUtil iju;
+ private final int buildKey;
+ private final int probeKey;
+
+ protected final IFrame[] inputBuffer;
+ protected final FrameTupleCursor[] inputCursor;
+ protected final FrameTupleAppender resultAppender;
+ private final VPartitionDeletableTupleBufferManager bufferManager;
+ private final ITupleAccessor[] memoryAccessor;
+ private final RunFilePointer[] runFilePointer;
+
+ private final int[] streamIndex;
+
+ private final ActiveSweepManager[] activeManager;
+ private final byte point;
+
+ private final RunFileStream[] runFileStream;
+
+ public IntervalTimeSweepJoiner(IHyracksTaskContext ctx, int memorySize, IIntervalJoinUtil iju, int buildKey,
+ int probeKey, RecordDescriptor buildRd, RecordDescriptor probeRd,
+ Comparator<EndPointIndexItem> endPointComparator) throws HyracksDataException {
+ // Memory (probe buffer)
+ if (memorySize < 5) {
+ throw new RuntimeException(
+ "IntervalMergeJoiner does not have enough memory (needs > 4, got " + memorySize + ").");
+ }
+
+ this.iju = iju;
+ this.buildKey = buildKey;
+ this.probeKey = probeKey;
+
+ inputBuffer = new IFrame[JOIN_PARTITIONS];
+ inputBuffer[BUILD_PARTITION] = new VSizeFrame(ctx);
+ inputBuffer[PROBE_PARTITION] = new VSizeFrame(ctx);
+
+ inputCursor = new FrameTupleCursor[JOIN_PARTITIONS];
+ inputCursor[BUILD_PARTITION] = new FrameTupleCursor(buildRd);
+ inputCursor[PROBE_PARTITION] = new FrameTupleCursor(probeRd);
+
+ RecordDescriptor[] recordDescriptors = new RecordDescriptor[JOIN_PARTITIONS];
+ recordDescriptors[BUILD_PARTITION] = buildRd;
+ recordDescriptors[PROBE_PARTITION] = probeRd;
+
+ //Two frames are used for the runfile stream, and one frame for each input (2 outputs)
+ bufferManager =
+ new VPartitionDeletableTupleBufferManager(ctx, VPartitionDeletableTupleBufferManager.NO_CONSTRAIN,
+ JOIN_PARTITIONS, memorySize * ctx.getInitialFrameSize(), recordDescriptors);
+ memoryAccessor = new ITupleAccessor[JOIN_PARTITIONS];
+ memoryAccessor[PROBE_PARTITION] = bufferManager.getTupleAccessor(probeRd);
+ memoryAccessor[BUILD_PARTITION] = bufferManager.getTupleAccessor(buildRd);
+
+ // Run File and frame cache (build buffer)
+ runFileStream = new RunFileStream[JOIN_PARTITIONS];
+ runFileStream[BUILD_PARTITION] = new RunFileStream(ctx, "imj-build");
+ runFileStream[PROBE_PARTITION] = new RunFileStream(ctx, "itsj-probe");
+ runFileStream[BUILD_PARTITION].createRunFileWriting();
+ runFileStream[BUILD_PARTITION].startRunFileWriting();
+ runFileStream[PROBE_PARTITION].createRunFileWriting();
+ runFileStream[PROBE_PARTITION].startRunFileWriting();
+
+ this.point = true ? EndPointIndexItem.START_POINT : EndPointIndexItem.END_POINT;
+ activeManager = new ActiveSweepManager[JOIN_PARTITIONS];
+ activeManager[BUILD_PARTITION] =
+ new ActiveSweepManager(bufferManager, buildKey, BUILD_PARTITION, endPointComparator, point);
+ activeManager[PROBE_PARTITION] =
+ new ActiveSweepManager(bufferManager, probeKey, PROBE_PARTITION, endPointComparator, point);
+
+ runFilePointer = new RunFilePointer[JOIN_PARTITIONS];
+ runFilePointer[BUILD_PARTITION] = new RunFilePointer();
+ runFilePointer[PROBE_PARTITION] = new RunFilePointer();
+
+ streamIndex = new int[JOIN_PARTITIONS];
+ streamIndex[BUILD_PARTITION] = -1;
+ streamIndex[PROBE_PARTITION] = -1;
+
+ // Result
+ this.resultAppender = new FrameTupleAppender(new VSizeFrame(ctx));
+ }
+
+ public void processBuildFrame(ByteBuffer buffer) throws HyracksDataException {
+ inputCursor[BUILD_PARTITION].reset(buffer);
+ for (int x = 0; x < inputCursor[BUILD_PARTITION].getAccessor().getTupleCount(); x++) {
+ runFileStream[BUILD_PARTITION].addToRunFile(inputCursor[BUILD_PARTITION].getAccessor(), x);
+ }
+ }
+
+ public void processBuildClose() throws HyracksDataException {
+ runFileStream[BUILD_PARTITION].flushRunFile();
+ runFileStream[BUILD_PARTITION].startReadingRunFile(inputCursor[BUILD_PARTITION]);
+ }
+
+ public void processProbeFrame(ByteBuffer buffer, IFrameWriter writer) throws HyracksDataException {
+ inputCursor[PROBE_PARTITION].reset(buffer);
+ for (int x = 0; x < inputCursor[PROBE_PARTITION].getAccessor().getTupleCount(); x++) {
+ runFileStream[PROBE_PARTITION].addToRunFile(inputCursor[PROBE_PARTITION].getAccessor(), x);
+ }
+ }
+
+ public void processProbeClose(IFrameWriter writer) throws HyracksDataException {
+
+ runFileStream[PROBE_PARTITION].flushRunFile();
+ runFileStream[PROBE_PARTITION].startReadingRunFile(inputCursor[PROBE_PARTITION]);
+
+ processJoin(writer);
+
+ runFileStream[PROBE_PARTITION].close();
+ runFileStream[BUILD_PARTITION].close();
+ }
+
+ private boolean hasNext(int partition) throws HyracksDataException {
+ if (inputCursor[partition].hasNext()) {
+ // Must keep condition in a separate `if` due to actions applied in loadNextBuffer.
+ return true;
+ } else {
+ return runFileStream[partition].loadNextBuffer(inputCursor[partition]);
+ }
+ }
+
+ public void processJoin(IFrameWriter writer) throws HyracksDataException {
+
+ // Initialize Variables
+ boolean continueBuild = true;
+ boolean continueProbe = true;
+ boolean choseProbePath;
+
+ if (hasNext(PROBE_PARTITION) && hasNext(BUILD_PARTITION)) {
+ // Preload Memory
+ inputCursor[BUILD_PARTITION].next();
+ inputCursor[PROBE_PARTITION].next();
+ // Centralize Has next
+ // Run Algorithm
+ do {
+ // Choose Correct Path
+ if (!continueBuild) {
+ choseProbePath = true;
+ } else if (!continueProbe) {
+ choseProbePath = false;
+ } else {
+ choseProbePath = iju.choosePath(inputCursor[BUILD_PARTITION].getAccessor(),
+ inputCursor[BUILD_PARTITION].getTupleId(), inputCursor[PROBE_PARTITION].getAccessor(),
+ inputCursor[PROBE_PARTITION].getTupleId());
+ }
+ // Process the correct side based on chosen path.
+ if (choseProbePath) {
+ processRemoveOldTuples(PROBE_PARTITION, BUILD_PARTITION, probeKey, false);
+ addToMemoryAndProcessJoin(PROBE_PARTITION, BUILD_PARTITION, false, writer);
+ // Needs to check for another frame
+ continueProbe = hasNext(PROBE_PARTITION);
+ if (continueProbe) {
+ inputCursor[PROBE_PARTITION].next();
+ }
+ } else {
+ processRemoveOldTuples(BUILD_PARTITION, PROBE_PARTITION, buildKey, true);
+ addToMemoryAndProcessJoin(BUILD_PARTITION, PROBE_PARTITION, true, writer);
+ // Needs to check for another frame
+ continueBuild = hasNext(BUILD_PARTITION);
+ if (continueBuild) {
+ inputCursor[BUILD_PARTITION].next();
+ }
+ }
+ // Based on continue, not has next.
+ } while (continueProbe || continueBuild);
+ }
+
+ resultAppender.write(writer, true);
+
+ activeManager[BUILD_PARTITION].clear();
+ activeManager[PROBE_PARTITION].clear();
+ runFileStream[BUILD_PARTITION].close();
+ runFileStream[PROBE_PARTITION].close();
+ runFileStream[BUILD_PARTITION].removeRunFile();
+ runFileStream[PROBE_PARTITION].removeRunFile();
+ }
+
+ private void processRemoveOldTuples(int active, int passive, int key, boolean reversed)
+ throws HyracksDataException {
+ //Remove from passive that can no longer match with active.
+ //TuplePrinterUtil.printTuple("Active", inputCursor[active].getAccessor(), inputCursor[active].getTupleId());
+ if (reversed) {
+ while (activeManager[active].hasRecords() && iju.checkToRemoveInMemory(inputCursor[passive].getAccessor(),
+ inputCursor[passive].getTupleId(), key, activeManager[active].getTopPoint(), true)) {
+ activeManager[active].removeTop();
+ }
+ } else {
+ while (activeManager[passive].hasRecords() && iju.checkToRemoveInMemory(inputCursor[active].getAccessor(),
+ inputCursor[active].getTupleId(), key, activeManager[passive].getTopPoint(), false)) {
+ activeManager[passive].removeTop();
+ }
+ }
+ }
+
+ private void addToMemoryAndProcessJoin(int active, int passive, boolean reversed, IFrameWriter writer)
+ throws HyracksDataException {
+ //Add to active, end point index and buffer.
+ TuplePointer tp = new TuplePointer();
+ if (activeManager[active].addTuple(inputCursor[active], tp)) {
+ processTupleJoin(activeManager[passive].getActiveList(), memoryAccessor[passive], inputCursor[active],
+ reversed, writer);
+ } else {
+ // Spill Case
+ freezeAndSpill(writer, reversed);
+ }
+ }
+
+ private void freezeAndSpill(IFrameWriter writer, boolean reversed) throws HyracksDataException {
+
+ int freezePartition;
+ if (bufferManager.getNumTuples(BUILD_PARTITION) > bufferManager.getNumTuples(PROBE_PARTITION)) {
+ freezePartition = PROBE_PARTITION;
+ } else {
+ freezePartition = BUILD_PARTITION;
+ }
+
+ runFilePointer[freezePartition].reset(runFileStream[freezePartition].getReadPointer(),
+ inputCursor[freezePartition].getTupleId());
+
+ if (freezePartition == PROBE_PARTITION) {
+ // Probe side from disk
+ processTupleSpill(PROBE_PARTITION, BUILD_PARTITION, true, writer);
+ } else {
+ // Build side from disk
+ processTupleSpill(BUILD_PARTITION, PROBE_PARTITION, false, writer);
+
+ }
+
+ }
+
+ private void processTupleSpill(int active, int passive, boolean reversed, IFrameWriter writer)
+ throws HyracksDataException {
+ // Process left tuples one by one, check them with active memory from the right branch.
+ while (activeManager[passive].hasRecords()) {
+ // Add individual tuples.
+ processTupleJoin(activeManager[passive].getActiveList(), memoryAccessor[passive], inputCursor[active],
+ reversed, writer);
+
+ if (inputCursor[active].hasNext()) {
+ inputCursor[active].next();
+ } else {
+ break;
+ }
+ }
+ if (!activeManager[passive].hasRecords()) {
+ unfreezeAndContinue(active);
+ }
+ }
+
+ private void unfreezeAndContinue(int frozenPartition) throws HyracksDataException {
+ int flushPartition = frozenPartition == BUILD_PARTITION ? PROBE_PARTITION : BUILD_PARTITION;
+
+ // Clear memory
+ activeManager[flushPartition].clear();
+
+ // Reset Position of Run File and cursor on frozen side.
+ runFileStream[frozenPartition].startReadingRunFile(inputCursor[frozenPartition],
+ runFilePointer[frozenPartition].getFileOffset());
+ inputCursor[frozenPartition].resetPosition(runFilePointer[frozenPartition].getTupleIndex());
+ runFilePointer[frozenPartition].reset(-1, -1);
+ }
+
+ private void processTupleJoin(List<TuplePointer> outer, ITupleAccessor outerAccessor, FrameTupleCursor tupleCursor,
+ boolean reversed, IFrameWriter writer) throws HyracksDataException {
+ for (TuplePointer outerTp : outer) {
+ outerAccessor.reset(outerTp);
+ if (iju.checkToSaveInResult(outerAccessor, outerTp.getTupleIndex(), tupleCursor.getAccessor(),
+ tupleCursor.getTupleId(), reversed)) {
+ addToResult(outerAccessor, outerTp.getTupleIndex(), tupleCursor.getAccessor(), tupleCursor.getTupleId(),
+ reversed, writer);
+ }
+ }
+ }
+
+ private void addToResult(IFrameTupleAccessor accessor1, int index1, IFrameTupleAccessor accessor2, int index2,
+ boolean reversed, IFrameWriter writer) throws HyracksDataException {
+ if (reversed) {
+ FrameUtils.appendConcatToWriter(writer, resultAppender, accessor2, index2, accessor1, index1);
+ } else {
+ FrameUtils.appendConcatToWriter(writer, resultAppender, accessor1, index1, accessor2, index2);
+ }
+ }
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/TuplePrinterUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/TuplePrinterUtil.java
new file mode 100644
index 0000000..f24345d5
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/TuplePrinterUtil.java
@@ -0,0 +1,65 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep;
+
+import org.apache.asterix.dataflow.data.nontagged.printers.adm.AObjectPrinterFactory;
+import org.apache.hyracks.algebricks.data.IPrinter;
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.std.buffermanager.ITupleAccessor;
+
+public class TuplePrinterUtil {
+
+ private static final IPrinter printer = AObjectPrinterFactory.INSTANCE.createPrinter();
+
+ private TuplePrinterUtil() {
+ }
+
+ public static void printTuple(String message, ITupleAccessor accessor) throws HyracksDataException {
+ if (accessor.exists()) {
+ printTuple(message, accessor, accessor.getTupleId());
+ } else {
+ System.out.flush();
+ System.err.flush();
+ System.err.print(String.format("%1$-" + 15 + "s", message) + " --");
+ System.err.print("no tuple");
+ System.err.println();
+ System.err.flush();
+ }
+ }
+
+ public static void printTuple(String message, IFrameTupleAccessor accessor, int tupleId)
+ throws HyracksDataException {
+ System.out.flush();
+ System.err.flush();
+ System.err.print(String.format("%1$-" + 15 + "s", message) + " -- " + accessor.getTupleLength(tupleId) + " --");
+ int fields = accessor.getFieldCount();
+ for (int i = 0; i < fields; ++i) {
+ System.err.print(" " + i + ": ");
+ int fieldStartOffset = accessor.getFieldStartOffset(tupleId, i);
+ int fieldSlotsLength = accessor.getFieldSlotsLength();
+ int tupleStartOffset = accessor.getTupleStartOffset(tupleId);
+ printer.print(accessor.getBuffer().array(), fieldStartOffset + fieldSlotsLength + tupleStartOffset,
+ accessor.getFieldLength(tupleId, i), System.err);
+ }
+ System.err.println();
+ System.err.flush();
+ }
+
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/AppendDeletableFrameTupleAccessor.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/AppendDeletableFrameTupleAccessor.java
new file mode 100644
index 0000000..b164b0d
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/AppendDeletableFrameTupleAccessor.java
@@ -0,0 +1,411 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep.memory;
+
+import java.nio.ByteBuffer;
+import java.util.Comparator;
+import java.util.PriorityQueue;
+
+import org.apache.commons.lang3.tuple.Pair;
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.std.sort.util.IAppendDeletableFrameTupleAccessor;
+import org.apache.hyracks.util.IntSerDeUtils;
+
+/**
+ * This is a special frame which is used in TupleMemoryBuffer.
+ * This frame has a special structure to organize the deleted spaces.
+ * Specifically, the endOffset of the deleted tuple will be set as negative number.
+ * And we add a special <code>deleted_space</code> field at the last 4 bytes to
+ * remember how many bytes has been deleted.
+ * The offsets also store both the start and end values because tuples may be out of
+ * after several add, remove and reorganize operations.
+ * A frame is formatted with tuple data concatenated starting at offset 0,
+ * one tuple after another.
+ * Offset FS - 4 holds an int indicating the amount of <code>deleted_space</code> in the frame.
+ * Offset FS - 4 holds an int indicating the number of tuples (N) in the frame.
+ * FS - ((i + 1) * (4 + 4)) for i from 0 to N - 1 holds an two ints indicating
+ * the offset and length of the (i + 1)^th tuple.
+ * The tuple references are organized as a sequence of ints indicating the start of the field
+ * followed by the length of each tuple.
+ * The offset if the start of the frame.
+ * The tuple has been deleted if the length is 0.
+ *
+ * <pre>
+ * [ *tuple_1_bytes*,
+ * *tuple_2_bytes*,
+ * ...
+ * int length, int offset, # tuple 2
+ * int length, int offset, # tuple 1
+ * int tuple_append,
+ * int next_index,
+ * int deleted_space,
+ * int index_count,
+ * ]
+ * </pre>
+ *
+ * <pre>
+ * [ *tuple_1_bytes*,
+ * *tuple_2_bytes*,
+ * ...
+ * int end_offset,
+ * int offset, # tuple 2
+ * int offset, # tuple 1
+ * int deleted_space,
+ * int tuple_count,
+ * ]
+ * </pre>
+ */
+public class AppendDeletableFrameTupleAccessor implements IAppendDeletableFrameTupleAccessor {
+
+ public static final Comparator<Pair<Integer, Integer>> INDEX_OFFSET_ASC_COMPARATOR =
+ new Comparator<Pair<Integer, Integer>>() {
+ @Override
+ public int compare(Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) {
+ return p1.getValue() - p2.getValue();
+ }
+
+ };
+
+ private static final int SIZE_INDEX_COUNT = 4;
+ private static final int SIZE_DELETED_SPACE = 4;
+ private static final int SIZE_NEXT_INDEX = 4;
+ private static final int SIZE_TUPLE_APPEND = 4;
+
+ private static final int SIZE_START_OFFSET = 4;
+ private static final int SIZE_END_OFFSET = 4;
+ private static final int SIZE_OFFSET_GROUP = SIZE_END_OFFSET + SIZE_START_OFFSET;
+
+ private final RecordDescriptor recordDescriptor;
+ private ByteBuffer buffer;
+ private int indexSlotsOffset;
+ private int indexCount;
+ private int tupleAppend;
+ private int deletedSpace;
+ private int nextIndex;
+ private byte[] array; // to speed up the array visit a little
+ private IntegerPairPool ipp = new IntegerPairPool();
+
+ private final PriorityQueue<IntegerPair> reorganizeQueue;
+
+ public AppendDeletableFrameTupleAccessor(RecordDescriptor recordDescriptor) {
+ this.recordDescriptor = recordDescriptor;
+ reorganizeQueue = new PriorityQueue<>(16, IntegerPair.RIGHT_ASC_COMPARATOR);
+ }
+
+ private int getIndexCount() {
+ return IntSerDeUtils.getInt(array, getIndexCountOffset());
+ }
+
+ private void setIndexCount(int count) {
+ IntSerDeUtils.putInt(array, getIndexCountOffset(), count);
+ }
+
+ private int getIndexCountOffset() {
+ return buffer.capacity() - SIZE_INDEX_COUNT;
+ }
+
+ private int getDeletedSpace() {
+ return IntSerDeUtils.getInt(array, getDeletedSpaceOffset());
+ }
+
+ private void setDeletedSpace(int space) {
+ IntSerDeUtils.putInt(array, getDeletedSpaceOffset(), space);
+ }
+
+ private int getDeletedSpaceOffset() {
+ return getIndexCountOffset() - SIZE_DELETED_SPACE;
+ }
+
+ private int getNextIndex() {
+ return IntSerDeUtils.getInt(array, getNextIndexOffset());
+ }
+
+ private void setNextIndex(int index) {
+ IntSerDeUtils.putInt(array, getNextIndexOffset(), index);
+ }
+
+ private int getNextIndexOffset() {
+ return getDeletedSpaceOffset() - SIZE_NEXT_INDEX;
+ }
+
+ private int getAndUpdateNextIndex() {
+ int index = nextIndex;
+ nextIndex = index + 1;
+ while (nextIndex < indexCount) {
+ if (getTupleEndOffset(nextIndex) <= 0) {
+ break;
+ }
+ nextIndex++;
+ }
+ setNextIndex(nextIndex);
+ return index;
+ }
+
+ private int getTupleAppend() {
+ return IntSerDeUtils.getInt(array, getTupleAppendOffset());
+ }
+
+ private void setTupleAppend(int offset) {
+ IntSerDeUtils.putInt(array, getTupleAppendOffset(), offset);
+ }
+
+ private int getTupleAppendOffset() {
+ return getNextIndexOffset() - SIZE_TUPLE_APPEND;
+ }
+
+ private int getIndexSlotOffset() {
+ return getTupleAppendOffset();
+ }
+
+ @Override
+ public void clear(ByteBuffer buffer) throws HyracksDataException {
+ this.buffer = buffer;
+ this.array = buffer.array();
+ setIndexCount(0);
+ setDeletedSpace(0);
+ setNextIndex(0);
+ setTupleAppend(0);
+ resetCounts();
+ }
+
+ @Override
+ public void reset(ByteBuffer buffer) {
+ this.buffer = buffer;
+ this.array = buffer.array();
+ resetCounts();
+ }
+
+ private void resetCounts() {
+ indexSlotsOffset = getIndexSlotOffset();
+ deletedSpace = getDeletedSpace();
+ indexCount = getIndexCount();
+ tupleAppend = getTupleAppend();
+ nextIndex = getNextIndex();
+ }
+
+ /**
+ * Append the record into the frame. This method will not validate the space, please make sure space is enough
+ * by calling {@link #getContiguousFreeSpace()}
+ *
+ * @param tupleAccessor
+ * @param tIndex
+ * @return
+ * @throws HyracksDataException
+ */
+ @Override
+ public int append(IFrameTupleAccessor tupleAccessor, int tIndex) throws HyracksDataException {
+ byte[] src = tupleAccessor.getBuffer().array();
+ int tStartOffset = tupleAccessor.getTupleStartOffset(tIndex);
+ int length = tupleAccessor.getTupleLength(tIndex);
+ System.arraycopy(src, tStartOffset, array, tupleAppend, length);
+ int index = getAndUpdateNextIndex();
+ if (index < indexCount) {
+ // Don't change index count
+ } else {
+ // Increment count
+ setIndexCount(++indexCount);
+ }
+ setTupleOffsets(index, tupleAppend, length);
+ tupleAppend += length;
+ setTupleAppend(tupleAppend);
+ return index;
+ }
+
+ @Override
+ public void delete(int tupleIndex) {
+ int endOffset = getTupleEndOffset(tupleIndex);
+ if (endOffset > 0) {
+ setTupleEndOffset(tupleIndex, -endOffset);
+ deletedSpace += endOffset - getTupleStartOffset(tupleIndex);
+ setDeletedSpace(deletedSpace);
+ if (nextIndex > tupleIndex) {
+ nextIndex = tupleIndex;
+ setNextIndex(nextIndex);
+ }
+ }
+ }
+
+ @Override
+ public void reOrganizeBuffer() {
+ if (deletedSpace <= 0) {
+ return;
+ }
+ reclaimDeletedEnding();
+
+ // Build reorganize queue
+ IntegerPair ip;
+ int endOffset;
+ int startOffset;
+ for (int i = 0; i < indexCount; i++) {
+ endOffset = getTupleEndOffset(i);
+ if (endOffset > 0) {
+ ip = ipp.takeOne();
+ ip.reset(i, getTupleStartOffset(i));
+ reorganizeQueue.add(ip);
+ }
+ }
+
+ int index;
+ tupleAppend = 0;
+ while (!reorganizeQueue.isEmpty()) {
+ ip = reorganizeQueue.remove();
+ index = ip.getLeft();
+ startOffset = getTupleStartOffset(index);
+ endOffset = getTupleEndOffset(index);
+ if (endOffset >= 0) {
+ int length = endOffset - startOffset;
+ assert length >= 0;
+ if (tupleAppend != startOffset) {
+ System.arraycopy(array, startOffset, array, tupleAppend, length);
+ }
+ setTupleOffsets(index, tupleAppend, length);
+ tupleAppend += length;
+ }
+ ipp.giveBack(ip);
+ }
+ setTupleAppend(tupleAppend);
+ deletedSpace = 0;
+ setDeletedSpace(0);
+
+ // Clean up
+ reorganizeQueue.clear();
+ }
+
+ private void reclaimDeletedEnding() {
+ for (int i = indexCount - 1; i >= 0; i--) {
+ int endOffset = getTupleEndOffset(i);
+ if (endOffset <= 0) {
+ indexCount--;
+ } else {
+ break;
+ }
+ }
+ setIndexCount(indexCount);
+ if (nextIndex > indexCount) {
+ setNextIndex(indexCount);
+ }
+ }
+
+ @Override
+ public int getTotalFreeSpace() {
+ return getContiguousFreeSpace() + deletedSpace;
+ }
+
+ @Override
+ public int getContiguousFreeSpace() {
+ int slotSpace = indexCount * SIZE_OFFSET_GROUP;
+ return indexSlotsOffset - tupleAppend - slotSpace;
+ }
+
+ @Override
+ public int getFieldCount() {
+ return recordDescriptor.getFieldCount();
+ }
+
+ @Override
+ public int getFieldSlotsLength() {
+ return recordDescriptor.getFieldCount() * 4;
+ }
+
+ @Override
+ public int getFieldEndOffset(int tupleIndex, int fIdx) {
+ return IntSerDeUtils.getInt(array, getTupleStartOffset(tupleIndex) + fIdx * 4);
+ }
+
+ @Override
+ public int getFieldStartOffset(int tupleIndex, int fIdx) {
+ return fIdx == 0 ? 0 : IntSerDeUtils.getInt(array, getTupleStartOffset(tupleIndex) + (fIdx - 1) * 4);
+ }
+
+ @Override
+ public int getAbsoluteFieldStartOffset(int tupleIndex, int fIdx) {
+ return getTupleStartOffset(tupleIndex) + getFieldSlotsLength() + getFieldStartOffset(tupleIndex, fIdx);
+ }
+
+ @Override
+ public int getFieldLength(int tupleIndex, int fIdx) {
+ return getFieldEndOffset(tupleIndex, fIdx) - getFieldStartOffset(tupleIndex, fIdx);
+ }
+
+ @Override
+ public int getTupleLength(int tupleIndex) {
+ int endOffset = getTupleEndOffset(tupleIndex);
+ if (endOffset > 0) {
+ return endOffset - getTupleStartOffset(tupleIndex);
+ } else {
+ return endOffset + getTupleStartOffset(tupleIndex);
+ }
+ }
+
+ private void setTupleOffsets(int tupleIndex, int start, int length) {
+ setTupleStartOffset(tupleIndex, start);
+ setTupleEndOffset(tupleIndex, start + length);
+ }
+
+ @Override
+ public int getTupleEndOffset(int tupleIndex) {
+ return IntSerDeUtils.getInt(array, getTupleEndSlotOffset(tupleIndex));
+ }
+
+ private void setTupleEndOffset(int tupleIndex, int offset) {
+ IntSerDeUtils.putInt(array, getTupleEndSlotOffset(tupleIndex), offset);
+ }
+
+ @Override
+ public int getTupleStartOffset(int tupleIndex) {
+ return IntSerDeUtils.getInt(array, getTupleStartSlotOffset(tupleIndex));
+ }
+
+ public void setTupleStartOffset(int tupleIndex, int offset) {
+ IntSerDeUtils.putInt(array, getTupleStartSlotOffset(tupleIndex), offset);
+ }
+
+ public int getTupleStartSlotOffset(int tupleIndex) {
+ return indexSlotsOffset - SIZE_OFFSET_GROUP * tupleIndex - SIZE_START_OFFSET;
+ }
+
+ public int getTupleEndSlotOffset(int tupleIndex) {
+ return getTupleStartSlotOffset(tupleIndex) - SIZE_END_OFFSET;
+ }
+
+ @Override
+ public int getTupleCount() {
+ return getLiveTupleCount();
+ }
+
+ private int getLiveTupleCount() {
+ int live = 0;
+ for (int i = 0; i < indexCount; ++i) {
+ int endOffset = getTupleEndOffset(i);
+ if (endOffset > 0) {
+ live++;
+ }
+ }
+ return live;
+ }
+
+ @Override
+ public ByteBuffer getBuffer() {
+ return buffer;
+ }
+
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/IntegerPair.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/IntegerPair.java
new file mode 100644
index 0000000..1f98a2d
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/IntegerPair.java
@@ -0,0 +1,87 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep.memory;
+
+import java.io.Serializable;
+import java.util.Comparator;
+
+public class IntegerPair implements Serializable {
+ private static final long serialVersionUID = 1L;
+
+ public static final Comparator<IntegerPair> LEFT_ASC_COMPARATOR = new Comparator<IntegerPair>() {
+ @Override
+ public int compare(IntegerPair p1, IntegerPair p2) {
+ return p1.getLeft() - p2.getLeft();
+ }
+
+ };
+
+ public static final Comparator<IntegerPair> RIGHT_ASC_COMPARATOR = new Comparator<IntegerPair>() {
+ @Override
+ public int compare(IntegerPair p1, IntegerPair p2) {
+ return p1.getRight() - p2.getRight();
+ }
+
+ };
+
+ private int left;
+ private int right;
+
+ public IntegerPair() {
+ reset(Integer.MIN_VALUE, Integer.MIN_VALUE);
+ }
+
+ public IntegerPair(int l, int r) {
+ reset(l, r);
+ }
+
+ public int getLeft() {
+ return left;
+ }
+
+ public int getRight() {
+ return right;
+ }
+
+ public void reset(int l, int r) {
+ left = l;
+ right = r;
+ }
+
+ @Override
+ public String toString() {
+ return left + "," + right;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (!(obj instanceof IntegerPair)) {
+ return false;
+ } else {
+ IntegerPair p = (IntegerPair) obj;
+ return this.left == p.getLeft() && this.right == p.getRight();
+ }
+ }
+
+ @Override
+ public int hashCode() {
+ return left * 31 + right;
+ }
+
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/IntegerPairPool.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/IntegerPairPool.java
new file mode 100644
index 0000000..f559e07
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/IntegerPairPool.java
@@ -0,0 +1,39 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep.memory;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class IntegerPairPool {
+ private final List<IntegerPair> list;
+
+ public IntegerPairPool() {
+ list = new ArrayList<>();
+ }
+
+ public IntegerPair takeOne() {
+ if (list.isEmpty()) {
+ return new IntegerPair();
+ }
+ return list.remove(list.size() - 1);
+ }
+
+ public void giveBack(IntegerPair pair) {
+ list.add(pair);
+ }
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/VPartitionDeletableTupleBufferManager.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/VPartitionDeletableTupleBufferManager.java
new file mode 100644
index 0000000..38e6150
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/VPartitionDeletableTupleBufferManager.java
@@ -0,0 +1,448 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep.memory;
+
+import static org.apache.hyracks.dataflow.std.buffermanager.EnumFreeSlotPolicy.LAST_FIT;
+
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
+import org.apache.hyracks.api.context.IHyracksFrameMgrContext;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
+import org.apache.hyracks.dataflow.std.buffermanager.AbstractTupleAccessor;
+import org.apache.hyracks.dataflow.std.buffermanager.AbstractTuplePointerAccessor;
+import org.apache.hyracks.dataflow.std.buffermanager.BufferInfo;
+import org.apache.hyracks.dataflow.std.buffermanager.FrameFreeSlotPolicyFactory;
+import org.apache.hyracks.dataflow.std.buffermanager.IFrameBufferManager;
+import org.apache.hyracks.dataflow.std.buffermanager.IFrameFreeSlotPolicy;
+import org.apache.hyracks.dataflow.std.buffermanager.IPartitionedDeletableTupleBufferManager;
+import org.apache.hyracks.dataflow.std.buffermanager.IPartitionedMemoryConstrain;
+import org.apache.hyracks.dataflow.std.buffermanager.ITupleAccessor;
+import org.apache.hyracks.dataflow.std.buffermanager.ITuplePointerAccessor;
+import org.apache.hyracks.dataflow.std.buffermanager.VPartitionTupleBufferManager;
+import org.apache.hyracks.dataflow.std.sort.util.IAppendDeletableFrameTupleAccessor;
+import org.apache.hyracks.dataflow.std.structures.TuplePointer;
+
+/**
+ * This buffer manager will divide the buffers into given number of partitions.
+ * The cleared partition (spilled one in the caller side) can only get no more than one frame.
+ */
+public class VPartitionDeletableTupleBufferManager extends VPartitionTupleBufferManager
+ implements IPartitionedDeletableTupleBufferManager {
+
+ private final int[] minFreeSpace;
+ private final IAppendDeletableFrameTupleAccessor[] accessor;
+ private final IFrameFreeSlotPolicy[] policy;
+
+ public VPartitionDeletableTupleBufferManager(IHyracksFrameMgrContext ctx, IPartitionedMemoryConstrain constrain,
+ int partitions, int frameLimitInBytes, RecordDescriptor[] recordDescriptors) throws HyracksDataException {
+ super(ctx, constrain, partitions, frameLimitInBytes);
+ int maxFrames = framePool.getMemoryBudgetBytes() / framePool.getMinFrameSize();
+ FrameFreeSlotPolicyFactory frameFreeSlotPolicyFactory = new FrameFreeSlotPolicyFactory();
+ this.policy = new IFrameFreeSlotPolicy[partitions];
+ this.accessor = new AppendDeletableFrameTupleAccessor[partitions];
+ this.minFreeSpace = new int[partitions];
+ int i = 0;
+ for (RecordDescriptor rd : recordDescriptors) {
+ this.accessor[i] = new AppendDeletableFrameTupleAccessor(rd);
+ this.minFreeSpace[i] = calculateMinFreeSpace(rd);
+ this.policy[i] = frameFreeSlotPolicyFactory.createFreeSlotPolicy(LAST_FIT, maxFrames);
+ ++i;
+ }
+ }
+
+ @Override
+ public boolean insertTuple(int partition, IFrameTupleAccessor fta, int idx, TuplePointer tuplePointer)
+ throws HyracksDataException {
+ int requiredFreeSpace = calculatePhysicalSpace(fta, idx);
+ int frameId = findAvailableFrame(partition, requiredFreeSpace);
+ if (frameId < 0) {
+ // printStats("Failed insert for " + partition);
+ if (canBeInsertedAfterFreeingFrames(partition)
+ || canBeInsertedAfterCleanUpFragmentation(partition, requiredFreeSpace)) {
+ reOrganizeFrames();
+ frameId = findAvailableFrame(partition, requiredFreeSpace);
+ } else {
+ return false;
+ }
+ }
+ assert frameId >= 0;
+ partitionArray[partition].getFrame(frameId, tempInfo);
+ accessor[partition].reset(tempInfo.getBuffer());
+ assert accessor[partition].getContiguousFreeSpace() >= requiredFreeSpace;
+ int tid = accessor[partition].append(fta, idx);
+ assert tid >= 0;
+ if (accessor[partition].getContiguousFreeSpace() > minFreeSpace[partition]) {
+ policy[partition].pushNewFrame(frameId, accessor[partition].getContiguousFreeSpace());
+ }
+ tuplePointer.reset(makeGroupFrameId(partition, frameId), tid);
+ numTuples[partition]++;
+ return true;
+ }
+
+ @Override
+ public void clearPartition(int partitionId) throws HyracksDataException {
+ IFrameBufferManager partition = partitionArray[partitionId];
+ if (partition != null) {
+ partition.resetIterator();
+ int i = partition.next();
+ while (partition.exists()) {
+ accessor[partitionId].clear(partition.getFrame(i, tempInfo).getBuffer());
+ i = partition.next();
+ }
+ }
+ policy[partitionId].reset();
+ super.clearPartition(partitionId);
+ }
+
+ private boolean canBeInsertedAfterFreeingFrames(int skipPartition) {
+ for (int partition = 0; partition < partitionArray.length; ++partition) {
+ if (skipPartition == partition || partitionArray[partition] == null) {
+ continue;
+ }
+ partitionArray[partition].resetIterator();
+ int f = partitionArray[partition].next();
+ while (partitionArray[partition].exists()) {
+ partitionArray[partition].getFrame(f, tempInfo);
+ accessor[partition].reset(tempInfo.getBuffer());
+ if (accessor[partition].getTupleCount() == 0) {
+ return true;
+ }
+ f = partitionArray[partition].next();
+ }
+ }
+ return false;
+ }
+
+ private void reOrganizeFrames() {
+ for (int p = 0; p < partitionArray.length; ++p) {
+ reOrganizeFramesForPartition(p);
+ }
+ }
+
+ private void reOrganizeFramesForPartition(int partition) {
+ //System.err.printf("reOrganizeFrames -- %d:[", partition);
+ policy[partition].reset();
+ partitionArray[partition].resetIterator();
+ int f = partitionArray[partition].next();
+ while (partitionArray[partition].exists()) {
+ reOrganizeFrameForPartition(partition, f);
+ f = partitionArray[partition].next();
+ }
+ // System.err.println("] ");
+ }
+
+ private void reOrganizeFrameForPartition(int partition, int f) {
+ partitionArray[partition].getFrame(f, tempInfo);
+ accessor[partition].reset(tempInfo.getBuffer());
+ accessor[partition].reOrganizeBuffer();
+ if (accessor[partition].getTupleCount() == 0) {
+ partitionArray[partition].removeFrame(f);
+ framePool.deAllocateBuffer(tempInfo.getBuffer());
+ //System.err.print("REMOVED");
+ } else {
+ policy[partition].pushNewFrame(f, accessor[partition].getContiguousFreeSpace());
+ //accessor[partition].printStats(System.err);
+ }
+ }
+
+ private boolean canBeInsertedAfterCleanUpFragmentation(int partition, int requiredFreeSpace) {
+ partitionArray[partition].resetIterator();
+ int i = partitionArray[partition].next();
+ while (partitionArray[partition].exists()) {
+ partitionArray[partition].getFrame(i, tempInfo);
+ accessor[partition].reset(tempInfo.getBuffer());
+ if (accessor[partition].getTotalFreeSpace() >= requiredFreeSpace) {
+ return true;
+ }
+ i = partitionArray[partition].next();
+ }
+ return false;
+ }
+
+ private int findAvailableFrame(int partition, int requiredFreeSpace) throws HyracksDataException {
+ int frameId = policy[partition].popBestFit(requiredFreeSpace);
+ if (frameId >= 0) {
+ return frameId;
+ }
+ if (partitionArray[partition] == null || partitionArray[partition].getNumFrames() == 0) {
+ partitionArray[partition] = new PartitionFrameBufferManager();
+ }
+ return createNewBuffer(partition, requiredFreeSpace);
+ }
+
+ private static int calculatePhysicalSpace(IFrameTupleAccessor fta, int idx) {
+ // 4 bytes to store the offset
+ return 4 + fta.getTupleLength(idx);
+ }
+
+ private static int calculateMinFreeSpace(RecordDescriptor recordDescriptor) {
+ // + 4 for the tuple offset
+ return recordDescriptor.getFieldCount() * 4 + 4;
+ }
+
+ public void printStats(String message) {
+ System.err.print(String.format("%1$-" + 15 + "s", message) + " --");
+
+ for (int p = 0; p < partitionArray.length; ++p) {
+ System.err.printf("%d:[", p);
+ IFrameBufferManager partition = partitionArray[p];
+ if (partition != null) {
+ partitionArray[p].resetIterator();
+ int f = partitionArray[p].next();
+ while (partitionArray[p].exists()) {
+ partitionArray[p].getFrame(f, tempInfo);
+ accessor[p].reset(tempInfo.getBuffer());
+ f = partitionArray[p].next();
+ }
+ }
+ System.err.printf("] ");
+ }
+ System.err.println();
+ }
+
+ @Override
+ public void deleteTuple(int partition, TuplePointer tuplePointer) throws HyracksDataException {
+
+ int f = parseFrameIdInPartition(tuplePointer.getFrameIndex());
+ partitionArray[parsePartitionId(tuplePointer.getFrameIndex())].getFrame(f, tempInfo);
+ accessor[partition].reset(tempInfo.getBuffer());
+ accessor[partition].delete(tuplePointer.getTupleIndex());
+ numTuples[partition]--;
+
+ // // Return frame
+ // if (accessor[partition].getTupleCount() == 0 && partitionArray[partition].getNumFrames() > 1) {
+ // reOrganizeFrames(partition);
+ // }
+ }
+
+ @Override
+ public ITuplePointerAccessor getTuplePointerAccessor(final RecordDescriptor recordDescriptor) {
+ return new AbstractTuplePointerAccessor() {
+ private IAppendDeletableFrameTupleAccessor innerAccessor =
+ new AppendDeletableFrameTupleAccessor(recordDescriptor);
+
+ @Override
+ protected IFrameTupleAccessor getInnerAccessor() {
+ return innerAccessor;
+ }
+
+ @Override
+ protected void resetInnerAccessor(TuplePointer tuplePointer) {
+ partitionArray[parsePartitionId(tuplePointer.getFrameIndex())]
+ .getFrame(parseFrameIdInPartition(tuplePointer.getFrameIndex()), tempInfo);
+ innerAccessor.reset(tempInfo.getBuffer());
+ }
+ };
+ }
+
+ public ITupleAccessor getTupleAccessor(final RecordDescriptor recordDescriptor) {
+ return new AbstractTupleAccessor() {
+ private AppendDeletableFrameTupleAccessor innerAccessor =
+ new AppendDeletableFrameTupleAccessor(recordDescriptor);
+
+ @Override
+ protected IFrameTupleAccessor getInnerAccessor() {
+ return innerAccessor;
+ }
+
+ @Override
+ protected void resetInnerAccessor(TuplePointer tuplePointer) {
+ resetInnerAccessor(tuplePointer.getFrameIndex());
+ }
+
+ @Override
+ protected void resetInnerAccessor(int frameIndex) {
+ partitionArray[parsePartitionId(frameIndex)].getFrame(parseFrameIdInPartition(frameIndex), tempInfo);
+ innerAccessor.reset(tempInfo.getBuffer());
+ }
+
+ @Override
+ protected int getFrameCount() {
+ return partitionArray.length;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return hasNext(frameId, tupleId);
+ }
+
+ @Override
+ public void next() {
+ tupleId = nextTuple(frameId, tupleId);
+ if (tupleId > INITIALIZED) {
+ return;
+ }
+
+ if (frameId + 1 < getFrameCount()) {
+ ++frameId;
+ resetInnerAccessor(frameId);
+ tupleId = INITIALIZED;
+ next();
+ }
+ }
+
+ public boolean hasNext(int fId, int tId) {
+ int id = nextTuple(fId, tId);
+ if (id > INITIALIZED) {
+ return true;
+ }
+ if (fId + 1 < getFrameCount()) {
+ return hasNext(fId + 1, INITIALIZED);
+ }
+ return false;
+ }
+
+ public int nextTuple(int fId, int tId) {
+ if (fId != frameId) {
+ resetInnerAccessor(fId);
+ }
+ int id = nextTupleInFrame(tId);
+ if (fId != frameId) {
+ resetInnerAccessor(frameId);
+ }
+ return id;
+ }
+
+ public int nextTupleInFrame(int tId) {
+ int id = tId;
+ while (id + 1 < getTupleCount()) {
+ ++id;
+ if (getTupleEndOffset(id) > 0) {
+ return id;
+ }
+ }
+ return UNSET;
+ }
+
+ };
+ }
+
+ static class PartitionFrameBufferManager implements IFrameBufferManager {
+
+ int size = 0;
+ ArrayList<ByteBuffer> buffers = new ArrayList<>();
+
+ @Override
+ public void reset() throws HyracksDataException {
+ buffers.clear();
+ size = 0;
+ }
+
+ @Override
+ public BufferInfo getFrame(int frameIndex, BufferInfo returnedInfo) {
+ returnedInfo.reset(buffers.get(frameIndex), 0, buffers.get(frameIndex).capacity());
+ return returnedInfo;
+ }
+
+ @Override
+ public int getNumFrames() {
+ return size;
+ }
+
+ @Override
+ public int insertFrame(ByteBuffer frame) throws HyracksDataException {
+ int index = -1;
+ if (buffers.size() == size) {
+ buffers.add(frame);
+ index = buffers.size() - 1;
+ } else {
+ for (int i = 0; i < buffers.size(); ++i) {
+ if (buffers.get(i) == null) {
+ buffers.set(i, frame);
+ index = i;
+ break;
+ }
+ }
+ }
+ if (index == -1) {
+ throw new HyracksDataException("Did not insert frame.");
+ }
+ size++;
+ return index;
+ }
+
+ @Override
+ public void removeFrame(int frameIndex) {
+ buffers.set(frameIndex, null);
+ size--;
+ }
+
+ @Override
+ public void close() {
+ buffers = null;
+ }
+
+ int iterator = -1;
+
+ @Override
+ public int next() {
+ while (++iterator < buffers.size()) {
+ if (buffers.get(iterator) != null) {
+ break;
+ }
+ }
+ return iterator;
+ }
+
+ @Override
+ public boolean exists() {
+ return iterator < buffers.size() && buffers.get(iterator) != null;
+ }
+
+ @Override
+ public void resetIterator() {
+ iterator = -1;
+ }
+
+ @Override
+ public ITupleAccessor getTupleAccessor(final RecordDescriptor recordDescriptor) {
+ return new AbstractTupleAccessor() {
+ protected BufferInfo tempBI = new BufferInfo(null, -1, -1);
+ FrameTupleAccessor innerAccessor = new FrameTupleAccessor(recordDescriptor);
+
+ @Override
+ protected IFrameTupleAccessor getInnerAccessor() {
+ return innerAccessor;
+ }
+
+ @Override
+ protected void resetInnerAccessor(int frameIndex) {
+ getFrame(frameIndex, tempBI);
+ innerAccessor.reset(tempBI.getBuffer(), tempBI.getStartOffset(), tempBI.getLength());
+ }
+
+ protected void resetInnerAccessor(TuplePointer tuplePointer) {
+ getFrame(tuplePointer.getFrameIndex(), tempBI);
+ innerAccessor.reset(tempBI.getBuffer(), tempBI.getStartOffset(), tempBI.getLength());
+ }
+
+ @Override
+ protected int getFrameCount() {
+ return 0;
+ }
+ };
+ }
+
+ }
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AbstractIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AbstractIntervalJoinUtil.java
index 80d791c..49f69af 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AbstractIntervalJoinUtil.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AbstractIntervalJoinUtil.java
@@ -62,9 +62,14 @@
@Override
public boolean checkToSaveInResult(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) throws HyracksDataException {
- IntervalJoinUtil.getIntervalPointable(buildAccessor, buildTupleIndex, idBuild, ipBuild);
- IntervalJoinUtil.getIntervalPointable(probeAccessor, probeTupleIndex, idProbe, ipProbe);
+ IFrameTupleAccessor probeAccessor, int probeTupleIndex, boolean reversed) throws HyracksDataException {
+ if (reversed) {
+ IntervalJoinUtil.getIntervalPointable(buildAccessor, buildTupleIndex, idBuild, ipProbe);
+ IntervalJoinUtil.getIntervalPointable(probeAccessor, probeTupleIndex, idProbe, ipBuild);
+ } else {
+ IntervalJoinUtil.getIntervalPointable(buildAccessor, buildTupleIndex, idBuild, ipBuild);
+ IntervalJoinUtil.getIntervalPointable(probeAccessor, probeTupleIndex, idProbe, ipProbe);
+ }
return compareInterval(ipBuild, ipProbe);
}
@@ -90,4 +95,37 @@
long probeStart = IntervalJoinUtil.getIntervalStart(probeAccessor, probeTupleIndex, idProbe);
return buildEnd > probeStart;
}
+
+ //Checked
+ @Override
+ public boolean checkToRemoveBuildActive() {
+ return true;
+ }
+
+ @Override
+ public boolean checkToRemoveProbeActive() {
+ return true;
+ }
+
+ /**
+ * Left (first argument) interval starts after the Right (second argument) interval ends.
+ */
+ @Override
+ public boolean checkToRemoveInMemory(IFrameTupleAccessor accessor0, int tupleIndex0, int key0, long end1,
+ boolean reversed) {
+ long start0 = IntervalJoinUtil.getIntervalStart(accessor0, tupleIndex0, key0);
+
+ if (reversed) {
+ return start0 < end1;
+ }
+ return start0 > end1;
+ }
+
+ @Override
+ public boolean choosePath(IFrameTupleAccessor buildAccessor, int buildTupleIndex, IFrameTupleAccessor probeAccessor,
+ int probeTupleIndex) {
+ long buildStart = IntervalJoinUtil.getIntervalStart(buildAccessor, buildTupleIndex, idBuild);
+ long probeStart = IntervalJoinUtil.getIntervalEnd(probeAccessor, probeTupleIndex, idProbe);
+ return buildStart > probeStart;
+ }
}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AfterIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AfterIntervalJoinUtil.java
deleted file mode 100644
index 5dd4c44..0000000
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AfterIntervalJoinUtil.java
+++ /dev/null
@@ -1,62 +0,0 @@
-/*
- * 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.asterix.runtime.operators.joins.interval.utils;
-
-import org.apache.asterix.om.pointables.nonvisitor.AIntervalPointable;
-import org.apache.asterix.runtime.operators.joins.interval.utils.memory.IntervalJoinUtil;
-import org.apache.hyracks.api.comm.IFrameTupleAccessor;
-import org.apache.hyracks.api.exceptions.HyracksDataException;
-
-public class AfterIntervalJoinUtil extends AbstractIntervalJoinUtil {
-
- public AfterIntervalJoinUtil(int buildKey, int probeKey) {
- super(buildKey, probeKey);
- }
-
- @Override
- public boolean checkToSaveInMemory(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- return true;
- }
-
- @Override
- public boolean checkToRemoveInMemory(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- return false;
- }
-
- @Override
- public boolean checkForEarlyExit(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- return false;
- }
-
- @Override
- public boolean compareInterval(AIntervalPointable ipBuild, AIntervalPointable ipProbe) throws HyracksDataException {
- return il.after(ipBuild, ipProbe);
- }
-
- @Override
- public boolean checkToLoadNextProbeTuple(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- long buildEnd = IntervalJoinUtil.getIntervalEnd(buildAccessor, buildTupleIndex, idBuild);
- long probeStart = IntervalJoinUtil.getIntervalStart(probeAccessor, probeTupleIndex, idProbe);
- return probeStart <= buildEnd;
- }
-}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/BeforeIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/BeforeIntervalJoinUtil.java
deleted file mode 100644
index 5212a4d..0000000
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/BeforeIntervalJoinUtil.java
+++ /dev/null
@@ -1,62 +0,0 @@
-/*
- * 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.asterix.runtime.operators.joins.interval.utils;
-
-import org.apache.asterix.om.pointables.nonvisitor.AIntervalPointable;
-import org.apache.asterix.runtime.operators.joins.interval.utils.memory.IntervalJoinUtil;
-import org.apache.hyracks.api.comm.IFrameTupleAccessor;
-import org.apache.hyracks.api.exceptions.HyracksDataException;
-
-public class BeforeIntervalJoinUtil extends AbstractIntervalJoinUtil {
-
- public BeforeIntervalJoinUtil(int buildKey, int probeKey) {
- super(buildKey, probeKey);
- }
-
- @Override
- public boolean checkToSaveInMemory(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- long buildStart = IntervalJoinUtil.getIntervalStart(buildAccessor, buildTupleIndex, idBuild);
- long probeStart = IntervalJoinUtil.getIntervalStart(probeAccessor, probeTupleIndex, idProbe);
- return buildStart < probeStart;
- }
-
- @Override
- public boolean checkToRemoveInMemory(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- return !checkToSaveInMemory(buildAccessor, buildTupleIndex, probeAccessor, probeTupleIndex);
- }
-
- @Override
- public boolean checkForEarlyExit(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- return false;
- }
-
- @Override
- public boolean compareInterval(AIntervalPointable ipBuild, AIntervalPointable ipProbe) throws HyracksDataException {
- return il.before(ipBuild, ipProbe);
- }
-
- @Override
- public boolean checkToLoadNextProbeTuple(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- return true;
- }
-}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/BeforeIntervalJoinUtilFactory.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/BeforeIntervalJoinUtilFactory.java
deleted file mode 100644
index 1984caf..0000000
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/BeforeIntervalJoinUtilFactory.java
+++ /dev/null
@@ -1,31 +0,0 @@
-/*
- * 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.asterix.runtime.operators.joins.interval.utils;
-
-import org.apache.hyracks.api.context.IHyracksTaskContext;
-
-public class BeforeIntervalJoinUtilFactory implements IIntervalJoinUtilFactory {
- private static final long serialVersionUID = 1L;
-
- @Override
- public IIntervalJoinUtil createIntervalMergeJoinUtil(int buildKey, int probeKey, IHyracksTaskContext ctx,
- int nPartitions) {
- return new BeforeIntervalJoinUtil(buildKey, probeKey);
- }
-}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoveredByIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoveredByIntervalJoinUtil.java
index 91dfc66..dbad058 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoveredByIntervalJoinUtil.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoveredByIntervalJoinUtil.java
@@ -40,6 +40,13 @@
return buildStart <= probeEnd;
}
+ @Override
+ public boolean checkToRemoveInMemory(IFrameTupleAccessor accessor0, int tupleIndex0, int key0, long point1,
+ boolean reversed) {
+ long point0 = IntervalJoinUtil.getIntervalStart(accessor0, tupleIndex0, key0);
+ return point0 > point1;
+ }
+
/**
* Left (first argument) interval starts after the Right (second argument) interval ends.
*/
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoversIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoversIntervalJoinUtil.java
index 41c8c34..8943bb8 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoversIntervalJoinUtil.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoversIntervalJoinUtil.java
@@ -19,6 +19,8 @@
package org.apache.asterix.runtime.operators.joins.interval.utils;
import org.apache.asterix.om.pointables.nonvisitor.AIntervalPointable;
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.IntervalJoinUtil;
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
import org.apache.hyracks.api.exceptions.HyracksDataException;
public class CoversIntervalJoinUtil extends AbstractIntervalJoinUtil {
@@ -31,4 +33,11 @@
public boolean compareInterval(AIntervalPointable ipBuild, AIntervalPointable ipProbe) throws HyracksDataException {
return il.covers(ipBuild, ipProbe);
}
+
+ @Override
+ public boolean checkToRemoveInMemory(IFrameTupleAccessor accessor0, int tupleIndex0, int key0, long point1,
+ boolean reversed) {
+ long point0 = IntervalJoinUtil.getIntervalStart(accessor0, tupleIndex0, key0);
+ return point0 < point1;
+ }
}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/IIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/IIntervalJoinUtil.java
index 79eb2d7..410165c 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/IIntervalJoinUtil.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/IIntervalJoinUtil.java
@@ -62,7 +62,7 @@
* @throws HyracksDataException
*/
boolean checkToSaveInResult(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) throws HyracksDataException;
+ IFrameTupleAccessor probeAccessor, int probeTupleIndex, boolean reversed) throws HyracksDataException;
/**
* Check to see if the interval matches the join condition.
@@ -99,4 +99,14 @@
boolean checkToLoadNextProbeTuple(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
IFrameTupleAccessor probeAccessor, int probeTupleIndex);
+ boolean checkToRemoveBuildActive();
+
+ boolean checkToRemoveProbeActive();
+
+ boolean checkToRemoveInMemory(IFrameTupleAccessor accessor0, int tupleIndex0, int key0, long end1,
+ boolean reversed);
+
+ boolean choosePath(IFrameTupleAccessor buildAccessor, int buildTupleIndex, IFrameTupleAccessor probeAccessor,
+ int probeTupleIndex);
+
}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappedByIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappedByIntervalJoinUtil.java
index 2bd03a2..ccea0d6 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappedByIntervalJoinUtil.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappedByIntervalJoinUtil.java
@@ -19,6 +19,8 @@
package org.apache.asterix.runtime.operators.joins.interval.utils;
import org.apache.asterix.om.pointables.nonvisitor.AIntervalPointable;
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.IntervalJoinUtil;
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
import org.apache.hyracks.api.exceptions.HyracksDataException;
public class OverlappedByIntervalJoinUtil extends AbstractIntervalInverseJoinUtil {
@@ -31,4 +33,18 @@
public boolean compareInterval(AIntervalPointable ipBuild, AIntervalPointable ipProbe) throws HyracksDataException {
return il.overlappedBy(ipBuild, ipProbe);
}
+
+ /**
+ * Left (first argument) interval starts after the Right (second argument) interval ends.
+ */
+ @Override
+ public boolean checkToRemoveInMemory(IFrameTupleAccessor accessor0, int tupleIndex0, int key0, long end1,
+ boolean reversed) {
+ long start0 = IntervalJoinUtil.getIntervalStart(accessor0, tupleIndex0, key0);
+
+ if (reversed) {
+ return start0 < end1;
+ }
+ return start0 > end1;
+ }
}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappingIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappingIntervalJoinUtil.java
index 9aeb09b..7900e87 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappingIntervalJoinUtil.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappingIntervalJoinUtil.java
@@ -48,8 +48,8 @@
@Override
public boolean checkForEarlyExit(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- long probeStart = IntervalJoinUtil.getIntervalStart(probeAccessor, probeTupleIndex, idProbe);
long buildEnd = IntervalJoinUtil.getIntervalEnd(buildAccessor, buildTupleIndex, idBuild);
+ long probeStart = IntervalJoinUtil.getIntervalStart(probeAccessor, probeTupleIndex, idProbe);
return buildEnd <= probeStart;
}
@@ -66,18 +66,47 @@
@Override
public boolean checkToSaveInResult(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) throws HyracksDataException {
+ IFrameTupleAccessor probeAccessor, int probeTupleIndex, boolean reversed) throws HyracksDataException {
IntervalJoinUtil.getIntervalPointable(buildAccessor, buildTupleIndex, idBuild, ipBuild);
IntervalJoinUtil.getIntervalPointable(probeAccessor, probeTupleIndex, idProbe, ipProbe);
- if (ipBuild.getStartValue() < partitionStart && ipProbe.getStartValue() < partitionStart) {
- // These tuples match in a different partition
- return false;
+ if (reversed) {
+ if (ipProbe.getStartValue() < partitionStart && ipBuild.getStartValue() < partitionStart) {
+ // These tuples match in a different partition
+ return false;
+ }
+ return compareInterval(ipProbe, ipBuild);
+ } else {
+ if (ipBuild.getStartValue() < partitionStart && ipProbe.getStartValue() < partitionStart) {
+ // These tuples match in a different partition
+ return false;
+ }
+ return compareInterval(ipBuild, ipProbe);
}
- return compareInterval(ipBuild, ipProbe);
}
@Override
public boolean compareInterval(AIntervalPointable ipBuild, AIntervalPointable ipProbe) throws HyracksDataException {
return il.overlapping(ipBuild, ipProbe);
}
+
+ /**
+ * Left (first argument) interval starts after the Right (second argument) interval ends.
+ */
+ @Override
+ public boolean checkToRemoveInMemory(IFrameTupleAccessor accessor0, int tupleIndex0, int key0, long point1,
+ boolean reversed) {
+ long start0 = IntervalJoinUtil.getIntervalStart(accessor0, tupleIndex0, key0);
+ if (reversed) {
+ return point1 >= start0;
+ }
+ return start0 >= point1;
+ }
+
+ @Override
+ public boolean choosePath(IFrameTupleAccessor buildAccessor, int buildTupleIndex, IFrameTupleAccessor probeAccessor,
+ int probeTupleIndex) {
+ long buildStart = IntervalJoinUtil.getIntervalStart(buildAccessor, buildTupleIndex, idBuild);
+ long probeStart = IntervalJoinUtil.getIntervalEnd(probeAccessor, probeTupleIndex, idProbe);
+ return !(buildStart >= probeStart);
+ }
}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlapsIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlapsIntervalJoinUtil.java
index 933c565..c0d5dd4 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlapsIntervalJoinUtil.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlapsIntervalJoinUtil.java
@@ -19,6 +19,8 @@
package org.apache.asterix.runtime.operators.joins.interval.utils;
import org.apache.asterix.om.pointables.nonvisitor.AIntervalPointable;
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.IntervalJoinUtil;
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
import org.apache.hyracks.api.exceptions.HyracksDataException;
public class OverlapsIntervalJoinUtil extends AbstractIntervalJoinUtil {
@@ -31,4 +33,18 @@
public boolean compareInterval(AIntervalPointable ipBuild, AIntervalPointable ipProbe) throws HyracksDataException {
return il.overlaps(ipBuild, ipProbe);
}
+
+ @Override
+ public boolean checkToRemoveInMemory(IFrameTupleAccessor accessor0, int tupleIndex0, int key0, long end1,
+ boolean reversed) {
+ return false;
+ }
+
+ @Override
+ public boolean choosePath(IFrameTupleAccessor buildAccessor, int buildTupleIndex, IFrameTupleAccessor probeAccessor,
+ int probeTupleIndex) {
+ long buildStart = IntervalJoinUtil.getIntervalStart(buildAccessor, buildTupleIndex, idBuild);
+ long probeStart = IntervalJoinUtil.getIntervalEnd(probeAccessor, probeTupleIndex, idProbe);
+ return buildStart >= probeStart;
+ }
}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/memory/IntervalSideTuple.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/memory/IntervalSideTuple.java
index ac30067..7a7b06d 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/memory/IntervalSideTuple.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/memory/IntervalSideTuple.java
@@ -64,7 +64,7 @@
public boolean compareJoin(IntervalSideTuple ist) throws HyracksDataException {
return imjc.checkToSaveInResult(cursor.getAccessor(), cursor.getTupleId(), ist.cursor.getAccessor(),
- ist.cursor.getTupleId());
+ ist.cursor.getTupleId(), false);
}
public boolean removeFromMemory(IntervalSideTuple ist) {
diff --git a/asterixdb/asterix-runtime/src/test/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/ActiveSweepManagerTest.java b/asterixdb/asterix-runtime/src/test/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/ActiveSweepManagerTest.java
new file mode 100644
index 0000000..179fc32
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/test/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/ActiveSweepManagerTest.java
@@ -0,0 +1,298 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep;
+
+import static org.junit.Assert.assertEquals;
+
+import java.io.ByteArrayOutputStream;
+import java.io.DataOutput;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.nio.ByteBuffer;
+import java.util.logging.Logger;
+
+import org.apache.asterix.dataflow.data.nontagged.serde.AIntervalSerializerDeserializer;
+import org.apache.asterix.om.base.AInterval;
+import org.apache.asterix.om.types.ATypeTag;
+import org.apache.asterix.runtime.operators.joins.interval.TimeSweep.memory.VPartitionDeletableTupleBufferManager;
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.FrameTupleCursor;
+import org.apache.hyracks.api.comm.IFrame;
+import org.apache.hyracks.api.comm.VSizeFrame;
+import org.apache.hyracks.api.context.IHyracksTaskContext;
+import org.apache.hyracks.api.dataflow.value.ISerializerDeserializer;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import org.apache.hyracks.dataflow.common.comm.io.FrameTupleAppender;
+import org.apache.hyracks.dataflow.std.buffermanager.IPartitionedDeletableTupleBufferManager;
+import org.apache.hyracks.dataflow.std.structures.TuplePointer;
+import org.apache.hyracks.test.support.TestUtils;
+import org.junit.Before;
+import org.junit.Test;
+
+public class ActiveSweepManagerTest {
+
+ private static final Logger LOGGER = Logger.getLogger(IntervalTimeSweepJoiner.class.getName());
+
+ private final ISerializerDeserializer<AInterval> intervalSerde = AIntervalSerializerDeserializer.INSTANCE;
+ @SuppressWarnings("rawtypes")
+ private final ISerializerDeserializer[] SerDers =
+ new ISerializerDeserializer[] { AIntervalSerializerDeserializer.INSTANCE };
+ private final RecordDescriptor RecordDesc = new RecordDescriptor(SerDers);
+
+ private final int FRAME_SIZE = 320;
+
+ private final AInterval[] INTERVALS = new AInterval[] { new AInterval(99, 301, (byte) 16),
+ new AInterval(100, 300, (byte) 16), new AInterval(101, 299, (byte) 16) };
+ private final int INTERVAL_LENGTH = Byte.BYTES + Byte.BYTES + Long.BYTES + Long.BYTES;
+
+ /*
+ * Tests
+ *
+ * - add
+ * - top point
+ * - remove
+ * - has records
+ * - is empty
+ * - clear
+ */
+ IPartitionedDeletableTupleBufferManager bufferManager;
+ FrameTupleCursor memoryAccessor;
+ FrameTupleAppender appender;
+
+ @SuppressWarnings("unused")
+ private byte[] getIntervalBytes(AInterval[] intervals, int i) throws HyracksDataException {
+ try {
+ ByteArrayOutputStream bos = new ByteArrayOutputStream();
+ DataOutput dos = new DataOutputStream(bos);
+ dos.write(ATypeTag.SERIALIZED_INTERVAL_TYPE_TAG);
+ intervalSerde.serialize(intervals[i], dos);
+ bos.close();
+ return bos.toByteArray();
+ } catch (IOException e) {
+ throw HyracksDataException.create(e);
+ }
+ }
+
+ private ByteBuffer prepareData(IHyracksTaskContext ctx, AInterval[] intervals) throws HyracksDataException {
+
+ IFrame frame = new VSizeFrame(ctx);
+ FrameTupleAppender fffta = new FrameTupleAppender();
+ fffta.reset(frame, true);
+
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(RecordDesc.getFieldCount());
+
+ byte[] serializedInterval;
+
+ for (int i = 0; i < intervals.length; i++) {
+ tb.reset();
+ serializedInterval = getIntervalBytes(intervals, i);
+ tb.addField(serializedInterval, 0, serializedInterval.length);
+ fffta.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
+ }
+
+ return frame.getBuffer();
+ }
+
+ private void prepareMemory(ActiveSweepManager activeManager) throws HyracksDataException {
+ FrameTupleCursor cursor = new FrameTupleCursor(RecordDesc);
+ ByteBuffer buffer = prepareData(ctx, INTERVALS);
+ cursor.reset(buffer);
+ cursor.next();
+
+ TuplePointer tp = new TuplePointer();
+ activeManager.addTuple(cursor, tp);
+
+ tp = new TuplePointer();
+ cursor.next();
+ activeManager.addTuple(cursor, tp);
+
+ tp = new TuplePointer();
+ cursor.next();
+ activeManager.addTuple(cursor, tp);
+ }
+
+ IHyracksTaskContext ctx;
+
+ @Before
+ public void initial() throws HyracksDataException {
+ int memorySize = 5;
+ ctx = TestUtils.create(FRAME_SIZE);
+ RecordDescriptor intervalRD =
+ new RecordDescriptor(new ISerializerDeserializer[] { AIntervalSerializerDeserializer.INSTANCE });
+ RecordDescriptor[] records = { intervalRD, intervalRD };
+ bufferManager = new VPartitionDeletableTupleBufferManager(ctx,
+ VPartitionDeletableTupleBufferManager.NO_CONSTRAIN, 2, memorySize * ctx.getInitialFrameSize(), records);
+ memoryAccessor = new FrameTupleCursor(intervalRD);
+ appender = new FrameTupleAppender();
+ }
+
+ @Test
+ public void testBasicOperations() throws HyracksDataException {
+ ActiveSweepManager activeManager = new ActiveSweepManager(bufferManager, 0, 0,
+ EndPointIndexItem.EndPointAscComparator, EndPointIndexItem.START_POINT);
+
+ assertEquals(activeManager.hasRecords(), false);
+ assertEquals(activeManager.isEmpty(), true);
+
+ prepareMemory(activeManager);
+
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ activeManager.clear();
+ assertEquals(0, activeManager.getActiveList().size());
+ assertEquals(false, activeManager.hasRecords());
+ assertEquals(true, activeManager.isEmpty());
+
+ }
+
+ @Test
+ public void testAscendingStartpoint() throws HyracksDataException {
+ ActiveSweepManager activeManager = new ActiveSweepManager(bufferManager, 0, 0,
+ EndPointIndexItem.EndPointAscComparator, EndPointIndexItem.START_POINT);
+
+ assertEquals(activeManager.hasRecords(), false);
+ assertEquals(activeManager.isEmpty(), true);
+
+ prepareMemory(activeManager);
+
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ assertEquals(99, activeManager.getTopPoint());
+ activeManager.removeTop();
+ assertEquals(100, activeManager.getTopPoint());
+ activeManager.removeTop();
+ assertEquals(101, activeManager.getTopPoint());
+ activeManager.removeTop();
+
+ prepareMemory(activeManager);
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ activeManager.clear();
+ assertEquals(0, activeManager.getActiveList().size());
+ assertEquals(false, activeManager.hasRecords());
+ assertEquals(true, activeManager.isEmpty());
+ }
+
+ @Test
+ public void testDescendingStartpoint() throws HyracksDataException {
+ ActiveSweepManager activeManager = new ActiveSweepManager(bufferManager, 0, 0,
+ EndPointIndexItem.EndPointDescComparator, EndPointIndexItem.START_POINT);
+
+ assertEquals(activeManager.hasRecords(), false);
+ assertEquals(activeManager.isEmpty(), true);
+
+ prepareMemory(activeManager);
+
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ assertEquals(101, activeManager.getTopPoint());
+ activeManager.removeTop();
+ // Actual 0
+ assertEquals(100, activeManager.getTopPoint());
+ activeManager.removeTop();
+ // Actual 0
+ assertEquals(99, activeManager.getTopPoint());
+ activeManager.removeTop();
+
+ prepareMemory(activeManager);
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ activeManager.clear();
+ assertEquals(0, activeManager.getActiveList().size());
+ assertEquals(false, activeManager.hasRecords());
+ assertEquals(true, activeManager.isEmpty());
+ }
+
+ @Test
+ public void testAscendingEndpoint() throws HyracksDataException {
+ ActiveSweepManager activeManager = new ActiveSweepManager(bufferManager, 0, 0,
+ EndPointIndexItem.EndPointAscComparator, EndPointIndexItem.END_POINT);
+
+ assertEquals(activeManager.hasRecords(), false);
+ assertEquals(activeManager.isEmpty(), true);
+
+ prepareMemory(activeManager);
+
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ assertEquals(299, activeManager.getTopPoint());
+ activeManager.removeTop();
+ assertEquals(300, activeManager.getTopPoint());
+ activeManager.removeTop();
+ assertEquals(301, activeManager.getTopPoint());
+ activeManager.removeTop();
+
+ prepareMemory(activeManager);
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ activeManager.clear();
+ assertEquals(0, activeManager.getActiveList().size());
+ assertEquals(false, activeManager.hasRecords());
+ assertEquals(true, activeManager.isEmpty());
+ }
+
+ @Test
+ public void testDescendingEndpoint() throws HyracksDataException {
+ ActiveSweepManager activeManager = new ActiveSweepManager(bufferManager, 0, 0,
+ EndPointIndexItem.EndPointDescComparator, EndPointIndexItem.END_POINT);
+
+ assertEquals(activeManager.hasRecords(), false);
+ assertEquals(activeManager.isEmpty(), true);
+
+ prepareMemory(activeManager);
+
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ assertEquals(301, activeManager.getTopPoint());
+ activeManager.removeTop();
+ assertEquals(300, activeManager.getTopPoint());
+ activeManager.removeTop();
+ assertEquals(299, activeManager.getTopPoint());
+ activeManager.removeTop();
+
+ prepareMemory(activeManager);
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ activeManager.clear();
+ assertEquals(0, activeManager.getActiveList().size());
+ assertEquals(false, activeManager.hasRecords());
+ assertEquals(true, activeManager.isEmpty());
+ }
+
+}
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/base/PhysicalOperatorTag.java b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/base/PhysicalOperatorTag.java
index d590f71..0352046 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/base/PhysicalOperatorTag.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/base/PhysicalOperatorTag.java
@@ -41,6 +41,7 @@
INDEX_INSERT_DELETE,
INSERT_DELETE,
INTERVAL_MERGE_JOIN,
+ INTERVAL_TIME_SWEEP_JOIN,
LENGTH_PARTITIONED_INVERTED_INDEX_SEARCH,
MATERIALIZE,
MICRO_PRE_CLUSTERED_GROUP_BY,
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTupleAccessor.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTupleAccessor.java
new file mode 100644
index 0000000..6ec0e09
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTupleAccessor.java
@@ -0,0 +1,194 @@
+/*
+ * 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.hyracks.dataflow.std.buffermanager;
+
+import java.nio.ByteBuffer;
+
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
+import org.apache.hyracks.dataflow.std.structures.TuplePointer;
+
+public abstract class AbstractTupleAccessor implements ITupleAccessor {
+ public static final int UNSET = -2;
+ public static final int INITIALIZED = -1;
+
+ protected int tupleId = UNSET;
+
+ protected int frameId;
+
+ protected abstract IFrameTupleAccessor getInnerAccessor();
+
+ protected abstract void resetInnerAccessor(int frameId);
+
+ protected abstract void resetInnerAccessor(TuplePointer tp);
+
+ protected abstract int getFrameCount();
+
+ @Override
+ public int getTupleStartOffset() {
+ return getTupleStartOffset(tupleId);
+ }
+
+ @Override
+ public int getTupleLength() {
+ return getTupleLength(tupleId);
+ }
+
+ @Override
+ public int getAbsFieldStartOffset(int fieldId) {
+ return getAbsoluteFieldStartOffset(tupleId, fieldId);
+ }
+
+ @Override
+ public int getFieldLength(int fieldId) {
+ return getFieldLength(tupleId, fieldId);
+ }
+
+ @Override
+ public ByteBuffer getBuffer() {
+ return getInnerAccessor().getBuffer();
+ }
+
+ @Override
+ public int getFieldCount() {
+ return getInnerAccessor().getFieldCount();
+ }
+
+ @Override
+ public int getFieldSlotsLength() {
+ return getInnerAccessor().getFieldSlotsLength();
+ }
+
+ @Override
+ public int getFieldEndOffset(int tupleIndex, int fIdx) {
+ return getInnerAccessor().getFieldEndOffset(tupleId, fIdx);
+ }
+
+ @Override
+ public int getFieldStartOffset(int tupleIndex, int fIdx) {
+ return getInnerAccessor().getFieldStartOffset(tupleIndex, fIdx);
+ }
+
+ @Override
+ public int getFieldLength(int tupleIndex, int fIdx) {
+ return getInnerAccessor().getFieldLength(tupleIndex, fIdx);
+ }
+
+ @Override
+ public int getTupleLength(int tupleIndex) {
+ return getInnerAccessor().getTupleLength(tupleIndex);
+ }
+
+ @Override
+ public int getTupleEndOffset(int tupleIndex) {
+ return getInnerAccessor().getTupleEndOffset(tupleIndex);
+ }
+
+ @Override
+ public int getTupleStartOffset(int tupleIndex) {
+ return getInnerAccessor().getTupleStartOffset(tupleIndex);
+ }
+
+ @Override
+ public int getAbsoluteFieldStartOffset(int tupleIndex, int fIdx) {
+ return getInnerAccessor().getAbsoluteFieldStartOffset(tupleIndex, fIdx);
+ }
+
+ @Override
+ public int getTupleCount() {
+ return getInnerAccessor().getTupleCount();
+ }
+
+ @Override
+ public void reset(TuplePointer tuplePointer) {
+ resetInnerAccessor(tuplePointer.getFrameIndex());
+ }
+
+ @Override
+ public void reset(ByteBuffer buffer) {
+ throw new IllegalAccessError("Should never call this reset");
+ }
+
+ @Override
+ public int getTupleEndOffset() {
+ return getInnerAccessor().getTupleEndOffset(tupleId);
+ }
+
+ @Override
+ public int getFieldEndOffset(int fieldId) {
+ return getInnerAccessor().getFieldEndOffset(tupleId, fieldId);
+ }
+
+ @Override
+ public int getFieldStartOffset(int fieldId) {
+ return getInnerAccessor().getFieldStartOffset(tupleId, fieldId);
+ }
+
+ @Override
+ public void getTuplePointer(TuplePointer tp) {
+ tp.reset(frameId, tupleId);
+ }
+
+ @Override
+ public int getTupleId() {
+ return tupleId;
+ }
+
+ @Override
+ public void setTupleId(int tupleId) {
+ this.tupleId = tupleId;
+ }
+
+ @Override
+ public void reset() {
+ tupleId = INITIALIZED;
+ frameId = 0;
+ resetInnerAccessor(frameId);
+ }
+
+ @Override
+ public boolean hasNext() {
+ if (tupleId + 1 < getTupleCount() || frameId + 1 < getFrameCount()) {
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public boolean exists() {
+ return INITIALIZED < tupleId && getTupleEndOffset(tupleId) > 0 && tupleId < getTupleCount()
+ && frameId < getFrameCount();
+ }
+
+ @Override
+ public void next() {
+ // TODO Consider error messages
+ if (tupleId + 1 < getTupleCount()) {
+ ++tupleId;
+ } else if (frameId + 1 < getFrameCount()) {
+ ++frameId;
+ resetInnerAccessor(frameId);
+ tupleId = 0;
+ } else {
+ // Force exists to fail, by incrementing the tuple pointer.
+ ++tupleId;
+ }
+ }
+
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTuplePointerAccessor.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTuplePointerAccessor.java
index 2717d7a..d9da751 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTuplePointerAccessor.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTuplePointerAccessor.java
@@ -28,9 +28,9 @@
protected int tid = -1;
- abstract IFrameTupleAccessor getInnerAccessor();
+ protected abstract IFrameTupleAccessor getInnerAccessor();
- abstract void resetInnerAccessor(TuplePointer tuplePointer);
+ protected abstract void resetInnerAccessor(TuplePointer tuplePointer);
@Override
public void reset(TuplePointer tuplePointer) {
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/FrameBufferManager.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/FrameBufferManager.java
index 6a60813..9e932f6 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/FrameBufferManager.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/FrameBufferManager.java
@@ -22,6 +22,7 @@
import java.nio.ByteBuffer;
import java.util.ArrayList;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
import org.apache.hyracks.api.exceptions.HyracksDataException;
/**
@@ -29,6 +30,8 @@
*/
public class FrameBufferManager implements IFrameBufferManager {
+ int size = 0;
+ int iterator = -1;
ArrayList<ByteBuffer> buffers = new ArrayList<>();
@Override
@@ -54,6 +57,38 @@
}
@Override
+ public void removeFrame(int frameIndex) {
+ buffers.set(frameIndex, null);
+ size--;
+ }
+
+ @Override
+ public int next() {
+ while (++iterator < buffers.size()) {
+ if (buffers.get(iterator) != null) {
+ break;
+ }
+ }
+ return iterator;
+ }
+
+ @Override
+ public boolean exists() {
+ return iterator < buffers.size() && buffers.get(iterator) != null;
+ }
+
+ @Override
+ public void resetIterator() {
+ iterator = -1;
+ }
+
+ @Override
+ public ITupleAccessor getTupleAccessor(RecordDescriptor rd) {
+ assert (false);
+ return null;
+ }
+
+ @Override
public void close() {
buffers = null;
}
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IFrameBufferManager.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IFrameBufferManager.java
index 8b73b54..92ab96a 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IFrameBufferManager.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IFrameBufferManager.java
@@ -20,6 +20,7 @@
import java.nio.ByteBuffer;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
import org.apache.hyracks.api.exceptions.HyracksDataException;
/**
@@ -54,6 +55,21 @@
*/
int insertFrame(ByteBuffer frame) throws HyracksDataException;
+ void removeFrame(int frameIndex);
+
+ /**
+ * Create a iterator for frames.
+ *
+ * Allows the reuse of frame ids.
+ */
+ int next();
+
+ boolean exists();
+
+ void resetIterator();
+
+ ITupleAccessor getTupleAccessor(RecordDescriptor rd);
+
/**
* Releases the allocated resources.
*/
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AfterIntervalJoinUtilFactory.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IPartitionedDeletableTupleBufferManager.java
similarity index 62%
rename from asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AfterIntervalJoinUtilFactory.java
rename to hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IPartitionedDeletableTupleBufferManager.java
index 9fe4e9d..52a0918 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AfterIntervalJoinUtilFactory.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IPartitionedDeletableTupleBufferManager.java
@@ -16,16 +16,16 @@
* specific language governing permissions and limitations
* under the License.
*/
-package org.apache.asterix.runtime.operators.joins.interval.utils;
-import org.apache.hyracks.api.context.IHyracksTaskContext;
+package org.apache.hyracks.dataflow.std.buffermanager;
-public class AfterIntervalJoinUtilFactory implements IIntervalJoinUtilFactory {
- private static final long serialVersionUID = 1L;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.std.structures.TuplePointer;
- @Override
- public IIntervalJoinUtil createIntervalMergeJoinUtil(int buildKey, int probeKey, IHyracksTaskContext ctx,
- int nPartitions) {
- return new AfterIntervalJoinUtil(buildKey, probeKey);
- }
+public interface IPartitionedDeletableTupleBufferManager extends IPartitionedTupleBufferManager {
+
+ void deleteTuple(int partition, TuplePointer tuplePointer) throws HyracksDataException;
+
+ void printStats(String string);
+
}
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/ITupleAccessor.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/ITupleAccessor.java
new file mode 100644
index 0000000..dbbc9a9
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/ITupleAccessor.java
@@ -0,0 +1,70 @@
+/*
+ * 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.hyracks.dataflow.std.buffermanager;
+
+import java.nio.ByteBuffer;
+
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
+import org.apache.hyracks.dataflow.std.structures.TuplePointer;
+
+// TODO determine correct interface.
+public interface ITupleAccessor extends IFrameTupleAccessor {
+ int getTupleStartOffset();
+
+ int getTupleEndOffset();
+
+ int getTupleLength();
+
+ int getAbsFieldStartOffset(int fieldId);
+
+ int getFieldLength(int fieldId);
+
+ @Override
+ int getFieldCount();
+
+ @Override
+ int getFieldSlotsLength();
+
+ int getFieldEndOffset(int fieldId);
+
+ int getFieldStartOffset(int fieldId);
+
+ void reset(TuplePointer tuplePointer);
+
+ @Override
+ void reset(ByteBuffer buffer);
+
+ int getTupleId();
+
+ void setTupleId(int tupleId);
+
+ void getTuplePointer(TuplePointer tp);
+
+ /**
+ * Only reset the iterator.
+ */
+ void reset();
+
+ boolean hasNext();
+
+ void next();
+
+ boolean exists();
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/TupleInFrameListAccessor.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/TupleInFrameListAccessor.java
index aadcb26..d50a54c 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/TupleInFrameListAccessor.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/TupleInFrameListAccessor.java
@@ -41,12 +41,12 @@
}
@Override
- IFrameTupleAccessor getInnerAccessor() {
+ protected IFrameTupleAccessor getInnerAccessor() {
return bufferAccessor;
}
@Override
- void resetInnerAccessor(TuplePointer tuplePointer) {
+ protected void resetInnerAccessor(TuplePointer tuplePointer) {
bufferAccessor.reset(bufferFrames.get(tuplePointer.getFrameIndex()));
}
}
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VPartitionTupleBufferManager.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VPartitionTupleBufferManager.java
index d3d06cb..3a267f8 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VPartitionTupleBufferManager.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VPartitionTupleBufferManager.java
@@ -45,12 +45,12 @@
}
};
- private IDeallocatableFramePool framePool;
- private IFrameBufferManager[] partitionArray;
- private int[] numTuples;
+ protected IDeallocatableFramePool framePool;
+ protected IFrameBufferManager[] partitionArray;
+ protected int[] numTuples;
private final FixedSizeFrame appendFrame;
private final FixedSizeFrameTupleAppender appender;
- private BufferInfo tempInfo;
+ protected BufferInfo tempInfo;
private IPartitionedMemoryConstrain constrain;
// In case where a frame pool is shared by one or more buffer manager(s), it can be provided from the caller.
@@ -177,20 +177,21 @@
return FrameHelper.calcRequiredSpace(0, size);
}
- private int makeGroupFrameId(int partition, int fid) {
+ protected int makeGroupFrameId(int partition, int fid) {
return fid * getNumPartitions() + partition;
}
- private int parsePartitionId(int externalFrameId) {
+ protected int parsePartitionId(int externalFrameId) {
return externalFrameId % getNumPartitions();
}
- private int parseFrameIdInPartition(int externalFrameId) {
+ protected int parseFrameIdInPartition(int externalFrameId) {
return externalFrameId / getNumPartitions();
}
- private int createNewBuffer(int partition, int size) throws HyracksDataException {
+ protected int createNewBuffer(int partition, int size) throws HyracksDataException {
ByteBuffer newBuffer = requestNewBufferFromPool(size, partition);
+
if (newBuffer == null) {
return -1;
}
@@ -267,12 +268,12 @@
FrameTupleAccessor innerAccessor = new FrameTupleAccessor(recordDescriptor);
@Override
- IFrameTupleAccessor getInnerAccessor() {
+ protected IFrameTupleAccessor getInnerAccessor() {
return innerAccessor;
}
@Override
- void resetInnerAccessor(TuplePointer tuplePointer) {
+ protected void resetInnerAccessor(TuplePointer tuplePointer) {
partitionArray[parsePartitionId(tuplePointer.getFrameIndex())]
.getFrame(parseFrameIdInPartition(tuplePointer.getFrameIndex()), tempInfo);
innerAccessor.reset(tempInfo.getBuffer(), tempInfo.getStartOffset(), tempInfo.getLength());
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableDeletableTupleMemoryManager.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableDeletableTupleMemoryManager.java
index b053cac..a2788ad 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableDeletableTupleMemoryManager.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableDeletableTupleMemoryManager.java
@@ -174,12 +174,12 @@
new DeletableFrameTupleAppender(recordDescriptor);
@Override
- IFrameTupleAccessor getInnerAccessor() {
+ protected IFrameTupleAccessor getInnerAccessor() {
return bufferAccessor;
}
@Override
- void resetInnerAccessor(TuplePointer tuplePointer) {
+ protected void resetInnerAccessor(TuplePointer tuplePointer) {
bufferAccessor.reset(frames.get(tuplePointer.getFrameIndex()));
}
};
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableFrameMemoryManager.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableFrameMemoryManager.java
index 50db2ec..7e368b1 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableFrameMemoryManager.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableFrameMemoryManager.java
@@ -24,6 +24,7 @@
import java.util.List;
import org.apache.hyracks.api.comm.FrameHelper;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
import org.apache.hyracks.api.exceptions.HyracksDataException;
import org.apache.hyracks.util.IntSerDeUtils;
@@ -122,6 +123,31 @@
}
@Override
+ public void removeFrame(int frameIndex) {
+
+ }
+
+ @Override
+ public int next() {
+ return 0;
+ }
+
+ @Override
+ public boolean exists() {
+ return false;
+ }
+
+ @Override
+ public void resetIterator() {
+
+ }
+
+ @Override
+ public ITupleAccessor getTupleAccessor(RecordDescriptor rd) {
+ return null;
+ }
+
+ @Override
public void close() {
numPhysicalFrames = 0;
numLogicalFrames = 0;
--
To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/11364
To unsubscribe, or for help writing mail filters, visit https://asterix-gerrit.ics.uci.edu/settings
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Change-Id: Ia61c5c7d950c672e582bb1b7f32bfc389c0442d3
Gerrit-Change-Number: 11364
Gerrit-PatchSet: 1
Gerrit-Owner: Caleb Herbel
Gerrit-MessageType: newchange
Change in asterixdb[master]: [NO ISSUE] Replace Interval Merge Join with Interval Time Sweep Join
Posted by AsterixDB Code Review <do...@asterix-gerrit.ics.uci.edu>.
From Jenkins <je...@fulliautomatix.ics.uci.edu>:
Jenkins has posted comments on this change. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/11364 )
Change subject: [NO ISSUE] Replace Interval Merge Join with Interval Time Sweep Join
......................................................................
Patch Set 1: Integration-Tests-1
Integration Tests Failed
https://asterix-jenkins.ics.uci.edu/job/asterix-gerrit-integration-tests/11955/ : UNSTABLE
--
To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/11364
To unsubscribe, or for help writing mail filters, visit https://asterix-gerrit.ics.uci.edu/settings
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Change-Id: Ia61c5c7d950c672e582bb1b7f32bfc389c0442d3
Gerrit-Change-Number: 11364
Gerrit-PatchSet: 1
Gerrit-Owner: Caleb Herbel
Gerrit-Reviewer: Jenkins <je...@fulliautomatix.ics.uci.edu>
Gerrit-Comment-Date: Thu, 06 May 2021 21:19:36 +0000
Gerrit-HasComments: No
Gerrit-Has-Labels: Yes
Gerrit-MessageType: comment
Change in asterixdb[master]: [NO ISSUE] Replace Interval Merge Join with Interval Time Sweep Join
Posted by AsterixDB Code Review <do...@asterix-gerrit.ics.uci.edu>.
From Caleb Herbel:
Caleb Herbel has uploaded this change for review. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/11364 )
Change subject: [NO ISSUE] Replace Interval Merge Join with Interval Time Sweep Join
......................................................................
[NO ISSUE] Replace Interval Merge Join with Interval Time Sweep Join
- user model changes: no
- storage format changes: no
- interface changes: no
Details:
-Adds Time Sweep Join
-Adds DeletableTupleBufferManager to Hyracks
-Removes Interval Merge Join
-Updates Interval Relations for Time Sweep
Change-Id: Ia61c5c7d950c672e582bb1b7f32bfc389c0442d3
---
A asterixdb/asterix-algebra/src/main/java/org/apache/asterix/algebra/operators/physical/IntervalTimeSweepJoinPOperator.java
M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/AsterixJoinUtils.java
M asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/IntervalJoinUtils.java
M asterixdb/asterix-app/src/main/resources/cc.conf
M asterixdb/asterix-app/src/test/resources/cc.conf
M asterixdb/asterix-app/src/test/resources/optimizerts/only.txt
M asterixdb/asterix-app/src/test/resources/runtimets/only_sqlpp.xml
M asterixdb/asterix-runtime/pom.xml
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/ActiveSweepManager.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/EndPointIndexItem.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/IntervalTimeSweepJoinOperatorDescriptor.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/IntervalTimeSweepJoiner.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/TuplePrinterUtil.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/AppendDeletableFrameTupleAccessor.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/IntegerPair.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/IntegerPairPool.java
A asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/VPartitionDeletableTupleBufferManager.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AbstractIntervalJoinUtil.java
D asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AfterIntervalJoinUtil.java
D asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/BeforeIntervalJoinUtil.java
D asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/BeforeIntervalJoinUtilFactory.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoveredByIntervalJoinUtil.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoversIntervalJoinUtil.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/IIntervalJoinUtil.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappedByIntervalJoinUtil.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappingIntervalJoinUtil.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlapsIntervalJoinUtil.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/memory/IntervalSideTuple.java
A asterixdb/asterix-runtime/src/test/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/ActiveSweepManagerTest.java
M hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/base/PhysicalOperatorTag.java
A hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTupleAccessor.java
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTuplePointerAccessor.java
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/FrameBufferManager.java
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IFrameBufferManager.java
R hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IPartitionedDeletableTupleBufferManager.java
A hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/ITupleAccessor.java
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/TupleInFrameListAccessor.java
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VPartitionTupleBufferManager.java
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableDeletableTupleMemoryManager.java
M hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableFrameMemoryManager.java
40 files changed, 2,894 insertions(+), 224 deletions(-)
git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb refs/changes/64/11364/1
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/algebra/operators/physical/IntervalTimeSweepJoinPOperator.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/algebra/operators/physical/IntervalTimeSweepJoinPOperator.java
new file mode 100644
index 0000000..5ac2ae1
--- /dev/null
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/algebra/operators/physical/IntervalTimeSweepJoinPOperator.java
@@ -0,0 +1,170 @@
+/*
+ * 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.asterix.algebra.operators.physical;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.logging.Logger;
+
+import org.apache.asterix.optimizer.rules.util.IntervalPartitions;
+import org.apache.asterix.runtime.operators.joins.interval.TimeSweep.IntervalTimeSweepJoinOperatorDescriptor;
+import org.apache.asterix.runtime.operators.joins.interval.utils.IIntervalJoinUtilFactory;
+import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
+import org.apache.hyracks.algebricks.core.algebra.base.IHyracksJobBuilder;
+import org.apache.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import org.apache.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import org.apache.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import org.apache.hyracks.algebricks.core.algebra.base.PhysicalOperatorTag;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.AbstractBinaryJoinOperator.JoinKind;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.IOperatorSchema;
+import org.apache.hyracks.algebricks.core.algebra.operators.physical.AbstractJoinPOperator;
+import org.apache.hyracks.algebricks.core.algebra.properties.ILocalStructuralProperty;
+import org.apache.hyracks.algebricks.core.algebra.properties.INodeDomain;
+import org.apache.hyracks.algebricks.core.algebra.properties.IPartitioningProperty;
+import org.apache.hyracks.algebricks.core.algebra.properties.IPartitioningRequirementsCoordinator;
+import org.apache.hyracks.algebricks.core.algebra.properties.IPhysicalPropertiesVector;
+import org.apache.hyracks.algebricks.core.algebra.properties.LocalOrderProperty;
+import org.apache.hyracks.algebricks.core.algebra.properties.OrderColumn;
+import org.apache.hyracks.algebricks.core.algebra.properties.OrderedPartitionedProperty;
+import org.apache.hyracks.algebricks.core.algebra.properties.PhysicalRequirements;
+import org.apache.hyracks.algebricks.core.algebra.properties.StructuralPropertiesVector;
+import org.apache.hyracks.algebricks.core.jobgen.impl.JobGenContext;
+import org.apache.hyracks.algebricks.core.jobgen.impl.JobGenHelper;
+import org.apache.hyracks.api.dataflow.IOperatorDescriptor;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
+import org.apache.hyracks.api.job.IOperatorDescriptorRegistry;
+
+public class IntervalTimeSweepJoinPOperator extends AbstractJoinPOperator {
+
+ private final List<LogicalVariable> keysLeftBranch;
+ private final List<LogicalVariable> keysRightBranch;
+ protected final IIntervalJoinUtilFactory mjcf;
+ private final IntervalPartitions intervalPartitions;
+ private final int memSizeInFrames;
+
+ private static final Logger LOGGER = Logger.getLogger(IntervalTimeSweepJoinPOperator.class.getName());
+
+ public IntervalTimeSweepJoinPOperator(JoinKind kind, JoinPartitioningType partitioningType,
+ List<LogicalVariable> sideLeftOfEqualities, List<LogicalVariable> sideRightOfEqualities,
+ int memSizeInFrames, IIntervalJoinUtilFactory mjcf, IntervalPartitions intervalPartitions) {
+ super(kind, partitioningType);
+ this.keysLeftBranch = sideLeftOfEqualities;
+ this.keysRightBranch = sideRightOfEqualities;
+ this.mjcf = mjcf;
+ this.intervalPartitions = intervalPartitions;
+ this.memSizeInFrames = memSizeInFrames;
+
+ LOGGER.fine("IntervalIndexJoinPOperator constructed with: JoinKind=" + kind + ", JoinPartitioningType="
+ + partitioningType + ", List<LogicalVariable>=" + sideLeftOfEqualities + ", List<LogicalVariable>="
+ + sideRightOfEqualities + ", int memSizeInFrames=" + memSizeInFrames
+ + ", IMergeJoinCheckerFactory mjcf=" + mjcf + ".");
+ }
+
+ public IIntervalJoinUtilFactory getIntervalMergeJoinCheckerFactory() {
+ return mjcf;
+ }
+
+ @Override
+ public PhysicalOperatorTag getOperatorTag() {
+ return PhysicalOperatorTag.INTERVAL_TIME_SWEEP_JOIN;
+ }
+
+ @Override
+ public String toString() {
+ return "INTERVAL_MERGE_JOIN" + " " + keysLeftBranch + " " + keysRightBranch;
+ }
+
+ public List<LogicalVariable> getKeysLeftBranch() {
+ return keysLeftBranch;
+ }
+
+ public List<LogicalVariable> getKeysRightBranch() {
+ return keysRightBranch;
+ }
+
+ @Override
+ public boolean isMicroOperator() {
+ return false;
+ }
+
+ @Override
+ public void computeDeliveredProperties(ILogicalOperator iop, IOptimizationContext context) {
+ List<OrderColumn> order = intervalPartitions.getLeftStartColumn();
+ IPartitioningProperty pp = new OrderedPartitionedProperty(order, null, intervalPartitions.getRangeMap());
+ List<ILocalStructuralProperty> propsLocal = new ArrayList<>();
+ propsLocal.add(new LocalOrderProperty(intervalPartitions.getLeftStartColumn()));
+ deliveredProperties = new StructuralPropertiesVector(pp, propsLocal);
+ }
+
+ @Override
+ public PhysicalRequirements getRequiredPropertiesForChildren(ILogicalOperator iop,
+ IPhysicalPropertiesVector reqdByParent, IOptimizationContext context) {
+ StructuralPropertiesVector[] pv = new StructuralPropertiesVector[2];
+ AbstractLogicalOperator op = (AbstractLogicalOperator) iop;
+
+ IPartitioningProperty ppLeft = null;
+ List<ILocalStructuralProperty> ispLeft = new ArrayList<>();
+ ispLeft.add(new LocalOrderProperty(intervalPartitions.getLeftStartColumn()));
+
+ IPartitioningProperty ppRight = null;
+ List<ILocalStructuralProperty> ispRight = new ArrayList<>();
+ ispRight.add(new LocalOrderProperty(intervalPartitions.getRightStartColumn()));
+
+ INodeDomain targetNodeDomain = context.getComputationNodeDomain();
+
+ if (op.getExecutionMode() == AbstractLogicalOperator.ExecutionMode.PARTITIONED) {
+ ppLeft = new OrderedPartitionedProperty(intervalPartitions.getLeftStartColumn(), targetNodeDomain,
+ intervalPartitions.getRangeMap());
+ ppRight = new OrderedPartitionedProperty(intervalPartitions.getRightStartColumn(), targetNodeDomain,
+ intervalPartitions.getRangeMap());
+ }
+
+ pv[0] = new StructuralPropertiesVector(ppLeft, ispLeft);
+ pv[1] = new StructuralPropertiesVector(ppRight, ispRight);
+ IPartitioningRequirementsCoordinator prc = IPartitioningRequirementsCoordinator.NO_COORDINATION;
+ return new PhysicalRequirements(pv, prc);
+ }
+
+ @Override
+ public void contributeRuntimeOperator(IHyracksJobBuilder builder, JobGenContext context, ILogicalOperator op,
+ IOperatorSchema opSchema, IOperatorSchema[] inputSchemas, IOperatorSchema outerPlanSchema)
+ throws AlgebricksException {
+ int[] keysLeft = JobGenHelper.variablesToFieldIndexes(keysLeftBranch, inputSchemas[0]);
+ int[] keysRight = JobGenHelper.variablesToFieldIndexes(keysRightBranch, inputSchemas[1]);
+
+ IOperatorDescriptorRegistry spec = builder.getJobSpec();
+ RecordDescriptor recordDescriptor =
+ JobGenHelper.mkRecordDescriptor(context.getTypeEnvironment(op), opSchema, context);
+
+ IOperatorDescriptor opDesc = getIntervalOperatorDescriptor(keysLeft, keysRight, spec, recordDescriptor, mjcf);
+ contributeOpDesc(builder, (AbstractLogicalOperator) op, opDesc);
+
+ ILogicalOperator src1 = op.getInputs().get(0).getValue();
+ builder.contributeGraphEdge(src1, 0, op, 0);
+ ILogicalOperator src2 = op.getInputs().get(1).getValue();
+ builder.contributeGraphEdge(src2, 0, op, 1);
+ }
+
+ IOperatorDescriptor getIntervalOperatorDescriptor(int[] keysLeft, int[] keysRight, IOperatorDescriptorRegistry spec,
+ RecordDescriptor recordDescriptor, IIntervalJoinUtilFactory mjcf) {
+ return new IntervalTimeSweepJoinOperatorDescriptor(spec, memSizeInFrames, keysLeft, keysRight, recordDescriptor,
+ mjcf);
+ }
+}
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/AsterixJoinUtils.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/AsterixJoinUtils.java
index 672cb25..0e196b1 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/AsterixJoinUtils.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/AsterixJoinUtils.java
@@ -80,6 +80,6 @@
}
IntervalPartitions intervalPartitions =
IntervalJoinUtils.createIntervalPartitions(op, fi, sideLeft, sideRight, rangeMap, context, LEFT, RIGHT);
- IntervalJoinUtils.setSortMergeIntervalJoinOp(op, fi, sideLeft, sideRight, context, intervalPartitions);
+ IntervalJoinUtils.setIntervalTimeSweepJoinOp(op, fi, sideLeft, sideRight, context, intervalPartitions);
}
}
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/IntervalJoinUtils.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/IntervalJoinUtils.java
index e10f9fb..ea28232 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/IntervalJoinUtils.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/util/IntervalJoinUtils.java
@@ -27,13 +27,12 @@
import java.util.Map;
import org.apache.asterix.algebra.operators.physical.IntervalMergeJoinPOperator;
+import org.apache.asterix.algebra.operators.physical.IntervalTimeSweepJoinPOperator;
import org.apache.asterix.common.annotations.RangeAnnotation;
import org.apache.asterix.common.exceptions.CompilationException;
import org.apache.asterix.common.exceptions.ErrorCode;
import org.apache.asterix.lang.common.util.FunctionUtil;
import org.apache.asterix.om.functions.BuiltinFunctions;
-import org.apache.asterix.runtime.operators.joins.interval.utils.AfterIntervalJoinUtilFactory;
-import org.apache.asterix.runtime.operators.joins.interval.utils.BeforeIntervalJoinUtilFactory;
import org.apache.asterix.runtime.operators.joins.interval.utils.CoveredByIntervalJoinUtilFactory;
import org.apache.asterix.runtime.operators.joins.interval.utils.CoversIntervalJoinUtilFactory;
import org.apache.asterix.runtime.operators.joins.interval.utils.IIntervalJoinUtilFactory;
@@ -55,7 +54,7 @@
import org.apache.hyracks.algebricks.core.algebra.functions.IFunctionInfo;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.AbstractBinaryJoinOperator;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
-import org.apache.hyracks.algebricks.core.algebra.operators.logical.OrderOperator;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.OrderOperator.IOrder.OrderKind;
import org.apache.hyracks.algebricks.core.algebra.operators.physical.AbstractJoinPOperator;
import org.apache.hyracks.algebricks.core.algebra.operators.physical.AssignPOperator;
import org.apache.hyracks.algebricks.core.algebra.properties.IPartitioningProperty.PartitioningType;
@@ -89,6 +88,15 @@
context.getPhysicalOptimizationConfig().getMaxFramesForJoin(), mjcf, intervalPartitions));
}
+ protected static void setIntervalTimeSweepJoinOp(AbstractBinaryJoinOperator op, FunctionIdentifier fi,
+ List<LogicalVariable> sideLeft, List<LogicalVariable> sideRight, IOptimizationContext context,
+ IntervalPartitions intervalPartitions) throws AlgebricksException {
+ IIntervalJoinUtilFactory mjcf = createIntervalJoinCheckerFactory(fi, intervalPartitions.getRangeMap());
+ op.setPhysicalOperator(new IntervalTimeSweepJoinPOperator(op.getJoinKind(),
+ AbstractJoinPOperator.JoinPartitioningType.BROADCAST, sideLeft, sideRight,
+ context.getPhysicalOptimizationConfig().getMaxFramesForJoin(), mjcf, intervalPartitions));
+ }
+
/**
* Certain Relations not yet supported as seen below. Will default to regular join.
* Inserts partition sort key.
@@ -107,12 +115,15 @@
insertPartitionSortKey(op, left, leftPartitionVar, sideLeft.get(0), context);
insertPartitionSortKey(op, right, rightPartitionVar, sideRight.get(0), context);
- List<IntervalColumn> leftIC = Collections.singletonList(new IntervalColumn(leftPartitionVar.get(0),
- leftPartitionVar.get(1), OrderOperator.IOrder.OrderKind.ASC));
- List<IntervalColumn> rightIC = Collections.singletonList(new IntervalColumn(rightPartitionVar.get(0),
- rightPartitionVar.get(1), OrderOperator.IOrder.OrderKind.ASC));
+ final int INTERVAL_START_INDEX = 0;
+ final int INTERVAL_END_INDEX = 1;
+ int rightFirstSortField = INTERVAL_START_INDEX;
+ int rightSecondSortField = INTERVAL_END_INDEX;
+ int leftFirstSortField = INTERVAL_START_INDEX;
+ int leftSecondSortField = INTERVAL_END_INDEX;
+ OrderKind orderOfJoin = OrderKind.ASC;
- //Set Partitioning Types
+ //Set Partitioning Types and reverse order of join if necessary
PartitioningType leftPartitioningType = PartitioningType.ORDERED_PARTITIONED;
PartitioningType rightPartitioningType = PartitioningType.ORDERED_PARTITIONED;
if (fi.equals(BuiltinFunctions.INTERVAL_OVERLAPPED_BY)) {
@@ -133,6 +144,14 @@
} else {
throw new CompilationException(ErrorCode.COMPILATION_ILLEGAL_STATE, fi.getName());
}
+
+ List<IntervalColumn> leftIC =
+ Collections.singletonList(new IntervalColumn(leftPartitionVar.get(leftFirstSortField),
+ leftPartitionVar.get(leftSecondSortField), orderOfJoin));
+ List<IntervalColumn> rightIC =
+ Collections.singletonList(new IntervalColumn(rightPartitionVar.get(rightFirstSortField),
+ rightPartitionVar.get(rightSecondSortField), orderOfJoin));
+
return new IntervalPartitions(rangeMap, leftIC, rightIC, leftPartitioningType, rightPartitioningType);
}
@@ -193,10 +212,6 @@
mjcf = new CoversIntervalJoinUtilFactory();
} else if (fi.equals(BuiltinFunctions.INTERVAL_COVERED_BY)) {
mjcf = new CoveredByIntervalJoinUtilFactory();
- } else if (fi.equals(BuiltinFunctions.INTERVAL_BEFORE)) {
- mjcf = new BeforeIntervalJoinUtilFactory();
- } else if (fi.equals(BuiltinFunctions.INTERVAL_AFTER)) {
- mjcf = new AfterIntervalJoinUtilFactory();
} else if (fi.equals(BuiltinFunctions.INTERVAL_OVERLAPPING)) {
mjcf = new OverlappingIntervalJoinUtilFactory(rangeMap);
} else {
diff --git a/asterixdb/asterix-app/src/main/resources/cc.conf b/asterixdb/asterix-app/src/main/resources/cc.conf
index 51c71c2..aab7364 100644
--- a/asterixdb/asterix-app/src/main/resources/cc.conf
+++ b/asterixdb/asterix-app/src/main/resources/cc.conf
@@ -19,19 +19,9 @@
txn.log.dir=target/tmp/asterix_nc1/txnlog
core.dump.dir=target/tmp/asterix_nc1/coredump
iodevices=asterix_nc1/iodevice1
-iodevices=asterix_nc1/iodevice2
nc.api.port=19004
#jvm.args=-agentlib:jdwp=transport=dt_socket,server=y,suspend=y,address=5006
-[nc/asterix_nc2]
-ncservice.port=9091
-txn.log.dir=target/tmp/asterix_nc2/txnlog
-core.dump.dir=target/tmp/asterix_nc2/coredump
-iodevices=asterix_nc2/iodevice1
-iodevices=asterix_nc1/iodevice2
-nc.api.port=19005
-#jvm.args=-agentlib:jdwp=transport=dt_socket,server=y,suspend=y,address=5007
-
[nc]
address=127.0.0.1
command=asterixnc
diff --git a/asterixdb/asterix-app/src/test/resources/cc.conf b/asterixdb/asterix-app/src/test/resources/cc.conf
index 953284964..f8d1ce9 100644
--- a/asterixdb/asterix-app/src/test/resources/cc.conf
+++ b/asterixdb/asterix-app/src/test/resources/cc.conf
@@ -18,19 +18,10 @@
[nc/asterix_nc1]
txn.log.dir=target/tmp/asterix_nc1/txnlog
core.dump.dir=target/tmp/asterix_nc1/coredump
-iodevices=target/tmp/asterix_nc1/iodevice1,
-iodevices=../asterix-server/target/tmp/asterix_nc1/iodevice2
+iodevices=target/tmp/asterix_nc1/iodevice1
nc.api.port=19004
#jvm.args=-agentlib:jdwp=transport=dt_socket,server=y,suspend=y,address=5006
-[nc/asterix_nc2]
-ncservice.port=9091
-txn.log.dir=target/tmp/asterix_nc2/txnlog
-core.dump.dir=target/tmp/asterix_nc2/coredump
-iodevices=target/tmp/asterix_nc2/iodevice1,../asterix-server/target/tmp/asterix_nc2/iodevice2
-nc.api.port=19005
-#jvm.args=-agentlib:jdwp=transport=dt_socket,server=y,suspend=y,address=5007
-
[nc]
credential.file=src/test/resources/security/passwd
python.cmd.autolocate=true
diff --git a/asterixdb/asterix-app/src/test/resources/optimizerts/only.txt b/asterixdb/asterix-app/src/test/resources/optimizerts/only.txt
index fe95886..106f5c0 100644
--- a/asterixdb/asterix-app/src/test/resources/optimizerts/only.txt
+++ b/asterixdb/asterix-app/src/test/resources/optimizerts/only.txt
@@ -16,3 +16,5 @@
# specific language governing permissions and limitations
# under the License.
#
+
+temporal/interval_joins/
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/only_sqlpp.xml b/asterixdb/asterix-app/src/test/resources/runtimets/only_sqlpp.xml
index 334dd52..ff6ef8f 100644
--- a/asterixdb/asterix-app/src/test/resources/runtimets/only_sqlpp.xml
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/only_sqlpp.xml
@@ -19,5 +19,105 @@
!-->
<test-suite xmlns="urn:xml.testframework.asterix.apache.org" ResultOffsetPath="results" QueryOffsetPath="queries_sqlpp" QueryFileExtension=".sqlpp">
<test-group name="failed">
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_after">
+ <output-dir compare="Text">interval_after</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_before">
+ <output-dir compare="Text">interval_before</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_covered_by">
+ <output-dir compare="Text">interval_covered_by</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_covers">
+ <output-dir compare="Text">interval_covers</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_ended_by">
+ <output-dir compare="Text">interval_ended_by</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_ends">
+ <output-dir compare="Text">interval_ends</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_meets">
+ <output-dir compare="Text">interval_meets</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_met_by">
+ <output-dir compare="Text">interval_met_by</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_overlapped_by">
+ <output-dir compare="Text">interval_overlapped_by</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_overlapping">
+ <output-dir compare="Text">interval_overlapping</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_overlaps">
+ <output-dir compare="Text">interval_overlaps</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_started_by">
+ <output-dir compare="Text">interval_started_by</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins">
+ <compilation-unit name="interval_starts">
+ <output-dir compare="Text">interval_starts</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins_spilling">
+ <compilation-unit name="interval_after">
+ <output-dir compare="Text">interval_after</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins_spilling">
+ <compilation-unit name="interval_before">
+ <output-dir compare="Text">interval_before</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins_spilling">
+ <compilation-unit name="interval_covered_by">
+ <output-dir compare="Text">interval_covered_by</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins_spilling">
+ <compilation-unit name="interval_covers">
+ <output-dir compare="Text">interval_covers</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins_spilling">
+ <compilation-unit name="interval_overlapped_by">
+ <output-dir compare="Text">interval_overlapped_by</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins_spilling">
+ <compilation-unit name="interval_overlapping">
+ <output-dir compare="Text">interval_overlapping</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="temporal/interval_joins_spilling">
+ <compilation-unit name="interval_overlaps">
+ <output-dir compare="Text">interval_overlaps</output-dir>
+ </compilation-unit>
+ </test-case>
</test-group>
</test-suite>
diff --git a/asterixdb/asterix-runtime/pom.xml b/asterixdb/asterix-runtime/pom.xml
index 6672b38..c19b5bd 100644
--- a/asterixdb/asterix-runtime/pom.xml
+++ b/asterixdb/asterix-runtime/pom.xml
@@ -116,6 +116,10 @@
<artifactId>hyracks-control-common</artifactId>
</dependency>
<dependency>
+ <groupId>org.apache.hyracks</groupId>
+ <artifactId>hyracks-test-support</artifactId>
+ </dependency>
+ <dependency>
<groupId>org.apache.asterix</groupId>
<artifactId>asterix-transactions</artifactId>
<version>${project.version}</version>
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/ActiveSweepManager.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/ActiveSweepManager.java
new file mode 100644
index 0000000..de57295
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/ActiveSweepManager.java
@@ -0,0 +1,116 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep;
+
+import java.util.Comparator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.PriorityQueue;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.FrameTupleCursor;
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.IntervalJoinUtil;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.std.buffermanager.IPartitionedDeletableTupleBufferManager;
+import org.apache.hyracks.dataflow.std.structures.TuplePointer;
+
+public class ActiveSweepManager {
+
+ private static final Logger LOGGER = Logger.getLogger(ActiveSweepManager.class.getName());
+
+ private final int partition;
+ private final int key;
+ private final byte indexPoint;
+
+ private final IPartitionedDeletableTupleBufferManager bufferManager;
+ private final PriorityQueue<EndPointIndexItem> indexQueue;
+ private EndPointIndexItem item = null;
+ private final LinkedList<TuplePointer> active = new LinkedList<>();
+
+ public ActiveSweepManager(IPartitionedDeletableTupleBufferManager bufferManager, int key, int joinBranch,
+ Comparator<EndPointIndexItem> endPointComparator, byte point) {
+ this.bufferManager = bufferManager;
+ this.key = key;
+ this.partition = joinBranch;
+ indexQueue = new PriorityQueue<>(16, endPointComparator);
+ this.indexPoint = point;
+ }
+
+ public boolean addTuple(FrameTupleCursor cursor, TuplePointer tp) throws HyracksDataException {
+ if (bufferManager.insertTuple(partition, cursor.getAccessor(), cursor.getTupleId(), tp)) {
+ long point;
+ if (indexPoint == 1) {
+ point = IntervalJoinUtil.getIntervalEnd(cursor.getAccessor(), cursor.getTupleId(), key);
+ } else {
+ point = IntervalJoinUtil.getIntervalStart(cursor.getAccessor(), cursor.getTupleId(), key);
+ }
+ EndPointIndexItem e = new EndPointIndexItem(tp, indexPoint, point);
+ indexQueue.add(e);
+ active.add(tp);
+ item = indexQueue.peek();
+ if (LOGGER.isLoggable(Level.FINE)) {
+ LOGGER.fine("Add to memory (partition: " + partition + " index: " + e + ").");
+ }
+ // System.err.println("Add to memory (partition: " + partition + " index: " + e + ").");
+ return true;
+ }
+ return false;
+ }
+
+ public void removeTop() throws HyracksDataException {
+ // Remove from active.
+ if (LOGGER.isLoggable(Level.FINE)) {
+ LOGGER.fine("Remove top from memory (partition: " + partition + " index: " + item + ").");
+ }
+ // System.err.println("Remove top from memory (partition: " + partition + " index: " + item + ").");
+ bufferManager.deleteTuple(partition, item.getTuplePointer());
+ active.remove(item.getTuplePointer());
+ indexQueue.remove(item);
+ item = indexQueue.peek();
+ }
+
+ public long getTopPoint() {
+ // System.err.println("Get top from memory (partition: " + partition + " index: " + item + ").");
+ return item.getPoint();
+ }
+
+ public List<TuplePointer> getActiveList() {
+ return active;
+ }
+
+ public boolean isEmpty() {
+ return indexQueue.isEmpty();
+ }
+
+ public boolean hasRecords() {
+ return !indexQueue.isEmpty();
+ }
+
+ public void clear() throws HyracksDataException {
+ for (TuplePointer leftTp : active) {
+ bufferManager.deleteTuple(partition, leftTp);
+ }
+ indexQueue.clear();
+ active.clear();
+ item = null;
+ bufferManager.clearPartition(partition);
+ }
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/EndPointIndexItem.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/EndPointIndexItem.java
new file mode 100644
index 0000000..4a61b56
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/EndPointIndexItem.java
@@ -0,0 +1,95 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep;
+
+import java.io.Serializable;
+import java.util.Comparator;
+
+import org.apache.hyracks.dataflow.std.structures.TuplePointer;
+
+public class EndPointIndexItem implements Serializable {
+ private static final long serialVersionUID = 1L;
+
+ public static final byte START_POINT = 0;
+ public static final byte END_POINT = 1;
+
+ public static final Comparator<EndPointIndexItem> EndPointAscComparator = new Comparator<EndPointIndexItem>() {
+ @Override
+ public int compare(EndPointIndexItem epi1, EndPointIndexItem epi2) {
+ int c = Long.compare(epi1.getPoint(), epi2.getPoint());
+ if (c == 0) {
+ c = epi1.getStart() - epi2.getStart();
+ }
+ return c;
+ }
+
+ };
+
+ public static final Comparator<EndPointIndexItem> EndPointDescComparator = new Comparator<EndPointIndexItem>() {
+ @Override
+ public int compare(EndPointIndexItem epi1, EndPointIndexItem epi2) {
+ int c = Long.compare(epi2.getPoint(), epi1.getPoint());
+ if (c == 0) {
+ c = epi2.getStart() - epi1.getStart();
+ }
+ return c;
+ }
+
+ };
+
+ private TuplePointer tp;
+ private byte start;
+ private long point;
+
+ public EndPointIndexItem() {
+ reset(new TuplePointer(), (byte) -1, Long.MIN_VALUE);
+ }
+
+ public EndPointIndexItem(TuplePointer tp, byte start, long point) {
+ reset(tp, start, point);
+ }
+
+ public void reset(EndPointIndexItem item) {
+ reset(item.getTuplePointer(), item.getStart(), item.getPoint());
+ }
+
+ public void reset(TuplePointer tp, byte start, long point) {
+ this.tp = tp;
+ this.start = start;
+ this.point = point;
+ }
+
+ public TuplePointer getTuplePointer() {
+ return tp;
+ }
+
+ public byte getStart() {
+ return start;
+ }
+
+ public long getPoint() {
+ return point;
+ }
+
+ @Override
+ public String toString() {
+ return "EndPointIndexItem " + tp + " " + (start == START_POINT ? "start" : "end") + ": " + point;
+ }
+
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/IntervalTimeSweepJoinOperatorDescriptor.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/IntervalTimeSweepJoinOperatorDescriptor.java
new file mode 100644
index 0000000..e517a85
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/IntervalTimeSweepJoinOperatorDescriptor.java
@@ -0,0 +1,189 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep;
+
+import java.nio.ByteBuffer;
+import java.util.Comparator;
+
+import org.apache.asterix.runtime.operators.joins.interval.utils.IIntervalJoinUtil;
+import org.apache.asterix.runtime.operators.joins.interval.utils.IIntervalJoinUtilFactory;
+import org.apache.hyracks.api.context.IHyracksTaskContext;
+import org.apache.hyracks.api.dataflow.ActivityId;
+import org.apache.hyracks.api.dataflow.IActivity;
+import org.apache.hyracks.api.dataflow.IActivityGraphBuilder;
+import org.apache.hyracks.api.dataflow.IOperatorNodePushable;
+import org.apache.hyracks.api.dataflow.TaskId;
+import org.apache.hyracks.api.dataflow.value.IRecordDescriptorProvider;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.api.job.IOperatorDescriptorRegistry;
+import org.apache.hyracks.api.job.JobId;
+import org.apache.hyracks.dataflow.common.comm.util.FrameUtils;
+import org.apache.hyracks.dataflow.std.base.AbstractActivityNode;
+import org.apache.hyracks.dataflow.std.base.AbstractOperatorDescriptor;
+import org.apache.hyracks.dataflow.std.base.AbstractStateObject;
+import org.apache.hyracks.dataflow.std.base.AbstractUnaryInputSinkOperatorNodePushable;
+import org.apache.hyracks.dataflow.std.base.AbstractUnaryInputUnaryOutputOperatorNodePushable;
+
+public class IntervalTimeSweepJoinOperatorDescriptor extends AbstractOperatorDescriptor {
+ private static final long serialVersionUID = 1L;
+
+ private static final int JOIN_BUILD_ACTIVITY_ID = 0;
+ private static final int JOIN_PROBE_ACTIVITY_ID = 1;
+ private final int buildKey;
+ private final int probeKey;
+ private final int memoryForJoin;
+ private final IIntervalJoinUtilFactory imjcf;
+
+ public IntervalTimeSweepJoinOperatorDescriptor(IOperatorDescriptorRegistry spec, int memoryForJoin, int[] buildKey,
+ int[] probeKeys, RecordDescriptor recordDescriptor, IIntervalJoinUtilFactory imjcf) {
+ super(spec, 2, 1);
+ outRecDescs[0] = recordDescriptor;
+ this.buildKey = buildKey[0];
+ this.probeKey = probeKeys[0];
+ this.memoryForJoin = memoryForJoin;
+ this.imjcf = imjcf;
+ }
+
+ @Override
+ public void contributeActivities(IActivityGraphBuilder builder) {
+ ActivityId buildAid = new ActivityId(odId, JOIN_BUILD_ACTIVITY_ID);
+ ActivityId probeAid = new ActivityId(odId, JOIN_PROBE_ACTIVITY_ID);
+
+ IActivity probeAN = new JoinProbeActivityNode(probeAid);
+ IActivity buildAN = new JoinBuildActivityNode(buildAid, probeAid);
+
+ builder.addActivity(this, buildAN);
+ builder.addSourceEdge(0, buildAN, 0);
+
+ builder.addActivity(this, probeAN);
+ builder.addSourceEdge(1, probeAN, 0);
+ builder.addTargetEdge(0, probeAN, 0);
+ builder.addBlockingEdge(buildAN, probeAN);
+ }
+
+ public static class JoinCacheTaskState extends AbstractStateObject {
+ private IntervalTimeSweepJoiner joiner;
+
+ private JoinCacheTaskState(JobId jobId, TaskId taskId) {
+ super(jobId, taskId);
+ }
+ }
+
+ private class JoinBuildActivityNode extends AbstractActivityNode {
+ private static final long serialVersionUID = 1L;
+
+ private final ActivityId nljAid;
+
+ public JoinBuildActivityNode(ActivityId id, ActivityId nljAid) {
+ super(id);
+ this.nljAid = nljAid;
+ }
+
+ @Override
+ public IOperatorNodePushable createPushRuntime(final IHyracksTaskContext ctx,
+ IRecordDescriptorProvider recordDescProvider, final int partition, int nPartitions) {
+ final RecordDescriptor rd0 = recordDescProvider.getInputRecordDescriptor(nljAid, 0);
+ final RecordDescriptor rd1 = recordDescProvider.getInputRecordDescriptor(getActivityId(), 0);
+
+ return new AbstractUnaryInputSinkOperatorNodePushable() {
+ private JoinCacheTaskState state;
+
+ @Override
+ public void open() throws HyracksDataException {
+ state = new JoinCacheTaskState(ctx.getJobletContext().getJobId(),
+ new TaskId(getActivityId(), partition));
+
+ IIntervalJoinUtil imjc = imjcf.createIntervalMergeJoinUtil(buildKey, probeKey, ctx, nPartitions);
+
+ byte point = true ? EndPointIndexItem.START_POINT : EndPointIndexItem.END_POINT;
+ Comparator<EndPointIndexItem> endPointComparator =
+ true ? EndPointIndexItem.EndPointAscComparator : EndPointIndexItem.EndPointDescComparator;
+
+ state.joiner = new IntervalTimeSweepJoiner(ctx, memoryForJoin, imjc, buildKey, probeKey, rd0, rd1,
+ endPointComparator);
+ }
+
+ @Override
+ public void nextFrame(ByteBuffer buffer) throws HyracksDataException {
+ ByteBuffer copyBuffer = ctx.allocateFrame(buffer.capacity());
+ FrameUtils.copyAndFlip(buffer, copyBuffer);
+ state.joiner.processBuildFrame(copyBuffer);
+ }
+
+ @Override
+ public void close() throws HyracksDataException {
+ state.joiner.processBuildClose();
+ ctx.setStateObject(state);
+ }
+
+ @Override
+ public void fail() {
+ // No variables to update.
+ }
+ };
+ }
+ }
+
+ private class JoinProbeActivityNode extends AbstractActivityNode {
+ private static final long serialVersionUID = 1L;
+
+ public JoinProbeActivityNode(ActivityId id) {
+ super(id);
+ }
+
+ @Override
+ public IOperatorNodePushable createPushRuntime(final IHyracksTaskContext ctx,
+ IRecordDescriptorProvider recordDescProvider, final int partition, int nPartitions) {
+ return new AbstractUnaryInputUnaryOutputOperatorNodePushable() {
+ private JoinCacheTaskState state;
+
+ @Override
+ public void open() throws HyracksDataException {
+ writer.open();
+ state = (JoinCacheTaskState) ctx.getStateObject(
+ new TaskId(new ActivityId(getOperatorId(), JOIN_BUILD_ACTIVITY_ID), partition));
+ }
+
+ @Override
+ public void nextFrame(ByteBuffer buffer) throws HyracksDataException {
+ // Maybe Come back
+ ByteBuffer copyBuffer = ctx.allocateFrame(buffer.capacity());
+ FrameUtils.copyAndFlip(buffer, copyBuffer);
+ state.joiner.processProbeFrame(copyBuffer, writer);
+ }
+
+ @Override
+ public void close() throws HyracksDataException {
+ try {
+ state.joiner.processProbeClose(writer);
+ } finally {
+ writer.close();
+ }
+ }
+
+ @Override
+ public void fail() throws HyracksDataException {
+ writer.fail();
+ }
+ };
+ }
+ }
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/IntervalTimeSweepJoiner.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/IntervalTimeSweepJoiner.java
new file mode 100644
index 0000000..40b8960
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/IntervalTimeSweepJoiner.java
@@ -0,0 +1,337 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep;
+
+import java.nio.ByteBuffer;
+import java.util.Comparator;
+import java.util.List;
+import java.util.logging.Logger;
+
+import org.apache.asterix.runtime.operators.joins.interval.TimeSweep.memory.VPartitionDeletableTupleBufferManager;
+import org.apache.asterix.runtime.operators.joins.interval.utils.IIntervalJoinUtil;
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.FrameTupleCursor;
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.RunFilePointer;
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.RunFileStream;
+import org.apache.hyracks.api.comm.IFrame;
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
+import org.apache.hyracks.api.comm.IFrameWriter;
+import org.apache.hyracks.api.comm.VSizeFrame;
+import org.apache.hyracks.api.context.IHyracksTaskContext;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.common.comm.io.FrameTupleAppender;
+import org.apache.hyracks.dataflow.common.comm.util.FrameUtils;
+import org.apache.hyracks.dataflow.std.buffermanager.ITupleAccessor;
+import org.apache.hyracks.dataflow.std.structures.TuplePointer;
+
+/**
+ * Interval Index Merge Joiner takes two sorted streams of input and joins.
+ * The two sorted streams must be in a logical order and the comparator must
+ * support keeping that order so the join will work.
+ * The left stream will spill to disk when memory is full.
+ * The both right and left use memory to maintain active intervals for the join.
+ */
+public class IntervalTimeSweepJoiner {
+
+ private static final Logger LOGGER = Logger.getLogger(IntervalTimeSweepJoiner.class.getName());
+
+ protected static final int JOIN_PARTITIONS = 2;
+ protected static final int BUILD_PARTITION = 0;
+ protected static final int PROBE_PARTITION = 1;
+
+ private final IIntervalJoinUtil iju;
+ private final int buildKey;
+ private final int probeKey;
+
+ protected final IFrame[] inputBuffer;
+ protected final FrameTupleCursor[] inputCursor;
+ protected final FrameTupleAppender resultAppender;
+ private final VPartitionDeletableTupleBufferManager bufferManager;
+ private final ITupleAccessor[] memoryAccessor;
+ private final RunFilePointer[] runFilePointer;
+
+ private final int[] streamIndex;
+
+ private final ActiveSweepManager[] activeManager;
+ private final byte point;
+
+ private final RunFileStream[] runFileStream;
+
+ public IntervalTimeSweepJoiner(IHyracksTaskContext ctx, int memorySize, IIntervalJoinUtil iju, int buildKey,
+ int probeKey, RecordDescriptor buildRd, RecordDescriptor probeRd,
+ Comparator<EndPointIndexItem> endPointComparator) throws HyracksDataException {
+ // Memory (probe buffer)
+ if (memorySize < 5) {
+ throw new RuntimeException(
+ "IntervalMergeJoiner does not have enough memory (needs > 4, got " + memorySize + ").");
+ }
+
+ this.iju = iju;
+ this.buildKey = buildKey;
+ this.probeKey = probeKey;
+
+ inputBuffer = new IFrame[JOIN_PARTITIONS];
+ inputBuffer[BUILD_PARTITION] = new VSizeFrame(ctx);
+ inputBuffer[PROBE_PARTITION] = new VSizeFrame(ctx);
+
+ inputCursor = new FrameTupleCursor[JOIN_PARTITIONS];
+ inputCursor[BUILD_PARTITION] = new FrameTupleCursor(buildRd);
+ inputCursor[PROBE_PARTITION] = new FrameTupleCursor(probeRd);
+
+ RecordDescriptor[] recordDescriptors = new RecordDescriptor[JOIN_PARTITIONS];
+ recordDescriptors[BUILD_PARTITION] = buildRd;
+ recordDescriptors[PROBE_PARTITION] = probeRd;
+
+ //Two frames are used for the runfile stream, and one frame for each input (2 outputs)
+ bufferManager =
+ new VPartitionDeletableTupleBufferManager(ctx, VPartitionDeletableTupleBufferManager.NO_CONSTRAIN,
+ JOIN_PARTITIONS, memorySize * ctx.getInitialFrameSize(), recordDescriptors);
+ memoryAccessor = new ITupleAccessor[JOIN_PARTITIONS];
+ memoryAccessor[PROBE_PARTITION] = bufferManager.getTupleAccessor(probeRd);
+ memoryAccessor[BUILD_PARTITION] = bufferManager.getTupleAccessor(buildRd);
+
+ // Run File and frame cache (build buffer)
+ runFileStream = new RunFileStream[JOIN_PARTITIONS];
+ runFileStream[BUILD_PARTITION] = new RunFileStream(ctx, "imj-build");
+ runFileStream[PROBE_PARTITION] = new RunFileStream(ctx, "itsj-probe");
+ runFileStream[BUILD_PARTITION].createRunFileWriting();
+ runFileStream[BUILD_PARTITION].startRunFileWriting();
+ runFileStream[PROBE_PARTITION].createRunFileWriting();
+ runFileStream[PROBE_PARTITION].startRunFileWriting();
+
+ this.point = true ? EndPointIndexItem.START_POINT : EndPointIndexItem.END_POINT;
+ activeManager = new ActiveSweepManager[JOIN_PARTITIONS];
+ activeManager[BUILD_PARTITION] =
+ new ActiveSweepManager(bufferManager, buildKey, BUILD_PARTITION, endPointComparator, point);
+ activeManager[PROBE_PARTITION] =
+ new ActiveSweepManager(bufferManager, probeKey, PROBE_PARTITION, endPointComparator, point);
+
+ runFilePointer = new RunFilePointer[JOIN_PARTITIONS];
+ runFilePointer[BUILD_PARTITION] = new RunFilePointer();
+ runFilePointer[PROBE_PARTITION] = new RunFilePointer();
+
+ streamIndex = new int[JOIN_PARTITIONS];
+ streamIndex[BUILD_PARTITION] = -1;
+ streamIndex[PROBE_PARTITION] = -1;
+
+ // Result
+ this.resultAppender = new FrameTupleAppender(new VSizeFrame(ctx));
+ }
+
+ public void processBuildFrame(ByteBuffer buffer) throws HyracksDataException {
+ inputCursor[BUILD_PARTITION].reset(buffer);
+ for (int x = 0; x < inputCursor[BUILD_PARTITION].getAccessor().getTupleCount(); x++) {
+ runFileStream[BUILD_PARTITION].addToRunFile(inputCursor[BUILD_PARTITION].getAccessor(), x);
+ }
+ }
+
+ public void processBuildClose() throws HyracksDataException {
+ runFileStream[BUILD_PARTITION].flushRunFile();
+ runFileStream[BUILD_PARTITION].startReadingRunFile(inputCursor[BUILD_PARTITION]);
+ }
+
+ public void processProbeFrame(ByteBuffer buffer, IFrameWriter writer) throws HyracksDataException {
+ inputCursor[PROBE_PARTITION].reset(buffer);
+ for (int x = 0; x < inputCursor[PROBE_PARTITION].getAccessor().getTupleCount(); x++) {
+ runFileStream[PROBE_PARTITION].addToRunFile(inputCursor[PROBE_PARTITION].getAccessor(), x);
+ }
+ }
+
+ public void processProbeClose(IFrameWriter writer) throws HyracksDataException {
+
+ runFileStream[PROBE_PARTITION].flushRunFile();
+ runFileStream[PROBE_PARTITION].startReadingRunFile(inputCursor[PROBE_PARTITION]);
+
+ processJoin(writer);
+
+ runFileStream[PROBE_PARTITION].close();
+ runFileStream[BUILD_PARTITION].close();
+ }
+
+ private boolean hasNext(int partition) throws HyracksDataException {
+ if (inputCursor[partition].hasNext()) {
+ // Must keep condition in a separate `if` due to actions applied in loadNextBuffer.
+ return true;
+ } else {
+ return runFileStream[partition].loadNextBuffer(inputCursor[partition]);
+ }
+ }
+
+ public void processJoin(IFrameWriter writer) throws HyracksDataException {
+
+ // Initialize Variables
+ boolean continueBuild = true;
+ boolean continueProbe = true;
+ boolean choseProbePath;
+
+ if (hasNext(PROBE_PARTITION) && hasNext(BUILD_PARTITION)) {
+ // Preload Memory
+ inputCursor[BUILD_PARTITION].next();
+ inputCursor[PROBE_PARTITION].next();
+ // Centralize Has next
+ // Run Algorithm
+ do {
+ // Choose Correct Path
+ if (!continueBuild) {
+ choseProbePath = true;
+ } else if (!continueProbe) {
+ choseProbePath = false;
+ } else {
+ choseProbePath = iju.choosePath(inputCursor[BUILD_PARTITION].getAccessor(),
+ inputCursor[BUILD_PARTITION].getTupleId(), inputCursor[PROBE_PARTITION].getAccessor(),
+ inputCursor[PROBE_PARTITION].getTupleId());
+ }
+ // Process the correct side based on chosen path.
+ if (choseProbePath) {
+ processRemoveOldTuples(PROBE_PARTITION, BUILD_PARTITION, probeKey, false);
+ addToMemoryAndProcessJoin(PROBE_PARTITION, BUILD_PARTITION, false, writer);
+ // Needs to check for another frame
+ continueProbe = hasNext(PROBE_PARTITION);
+ if (continueProbe) {
+ inputCursor[PROBE_PARTITION].next();
+ }
+ } else {
+ processRemoveOldTuples(BUILD_PARTITION, PROBE_PARTITION, buildKey, true);
+ addToMemoryAndProcessJoin(BUILD_PARTITION, PROBE_PARTITION, true, writer);
+ // Needs to check for another frame
+ continueBuild = hasNext(BUILD_PARTITION);
+ if (continueBuild) {
+ inputCursor[BUILD_PARTITION].next();
+ }
+ }
+ // Based on continue, not has next.
+ } while (continueProbe || continueBuild);
+ }
+
+ resultAppender.write(writer, true);
+
+ activeManager[BUILD_PARTITION].clear();
+ activeManager[PROBE_PARTITION].clear();
+ runFileStream[BUILD_PARTITION].close();
+ runFileStream[PROBE_PARTITION].close();
+ runFileStream[BUILD_PARTITION].removeRunFile();
+ runFileStream[PROBE_PARTITION].removeRunFile();
+ }
+
+ private void processRemoveOldTuples(int active, int passive, int key, boolean reversed)
+ throws HyracksDataException {
+ //Remove from passive that can no longer match with active.
+ //TuplePrinterUtil.printTuple("Active", inputCursor[active].getAccessor(), inputCursor[active].getTupleId());
+ if (reversed) {
+ while (activeManager[active].hasRecords() && iju.checkToRemoveInMemory(inputCursor[passive].getAccessor(),
+ inputCursor[passive].getTupleId(), key, activeManager[active].getTopPoint(), true)) {
+ activeManager[active].removeTop();
+ }
+ } else {
+ while (activeManager[passive].hasRecords() && iju.checkToRemoveInMemory(inputCursor[active].getAccessor(),
+ inputCursor[active].getTupleId(), key, activeManager[passive].getTopPoint(), false)) {
+ activeManager[passive].removeTop();
+ }
+ }
+ }
+
+ private void addToMemoryAndProcessJoin(int active, int passive, boolean reversed, IFrameWriter writer)
+ throws HyracksDataException {
+ //Add to active, end point index and buffer.
+ TuplePointer tp = new TuplePointer();
+ if (activeManager[active].addTuple(inputCursor[active], tp)) {
+ processTupleJoin(activeManager[passive].getActiveList(), memoryAccessor[passive], inputCursor[active],
+ reversed, writer);
+ } else {
+ // Spill Case
+ freezeAndSpill(writer, reversed);
+ }
+ }
+
+ private void freezeAndSpill(IFrameWriter writer, boolean reversed) throws HyracksDataException {
+
+ int freezePartition;
+ if (bufferManager.getNumTuples(BUILD_PARTITION) > bufferManager.getNumTuples(PROBE_PARTITION)) {
+ freezePartition = PROBE_PARTITION;
+ } else {
+ freezePartition = BUILD_PARTITION;
+ }
+
+ runFilePointer[freezePartition].reset(runFileStream[freezePartition].getReadPointer(),
+ inputCursor[freezePartition].getTupleId());
+
+ if (freezePartition == PROBE_PARTITION) {
+ // Probe side from disk
+ processTupleSpill(PROBE_PARTITION, BUILD_PARTITION, true, writer);
+ } else {
+ // Build side from disk
+ processTupleSpill(BUILD_PARTITION, PROBE_PARTITION, false, writer);
+
+ }
+
+ }
+
+ private void processTupleSpill(int active, int passive, boolean reversed, IFrameWriter writer)
+ throws HyracksDataException {
+ // Process left tuples one by one, check them with active memory from the right branch.
+ while (activeManager[passive].hasRecords()) {
+ // Add individual tuples.
+ processTupleJoin(activeManager[passive].getActiveList(), memoryAccessor[passive], inputCursor[active],
+ reversed, writer);
+
+ if (inputCursor[active].hasNext()) {
+ inputCursor[active].next();
+ } else {
+ break;
+ }
+ }
+ if (!activeManager[passive].hasRecords()) {
+ unfreezeAndContinue(active);
+ }
+ }
+
+ private void unfreezeAndContinue(int frozenPartition) throws HyracksDataException {
+ int flushPartition = frozenPartition == BUILD_PARTITION ? PROBE_PARTITION : BUILD_PARTITION;
+
+ // Clear memory
+ activeManager[flushPartition].clear();
+
+ // Reset Position of Run File and cursor on frozen side.
+ runFileStream[frozenPartition].startReadingRunFile(inputCursor[frozenPartition],
+ runFilePointer[frozenPartition].getFileOffset());
+ inputCursor[frozenPartition].resetPosition(runFilePointer[frozenPartition].getTupleIndex());
+ runFilePointer[frozenPartition].reset(-1, -1);
+ }
+
+ private void processTupleJoin(List<TuplePointer> outer, ITupleAccessor outerAccessor, FrameTupleCursor tupleCursor,
+ boolean reversed, IFrameWriter writer) throws HyracksDataException {
+ for (TuplePointer outerTp : outer) {
+ outerAccessor.reset(outerTp);
+ if (iju.checkToSaveInResult(outerAccessor, outerTp.getTupleIndex(), tupleCursor.getAccessor(),
+ tupleCursor.getTupleId(), reversed)) {
+ addToResult(outerAccessor, outerTp.getTupleIndex(), tupleCursor.getAccessor(), tupleCursor.getTupleId(),
+ reversed, writer);
+ }
+ }
+ }
+
+ private void addToResult(IFrameTupleAccessor accessor1, int index1, IFrameTupleAccessor accessor2, int index2,
+ boolean reversed, IFrameWriter writer) throws HyracksDataException {
+ if (reversed) {
+ FrameUtils.appendConcatToWriter(writer, resultAppender, accessor2, index2, accessor1, index1);
+ } else {
+ FrameUtils.appendConcatToWriter(writer, resultAppender, accessor1, index1, accessor2, index2);
+ }
+ }
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/TuplePrinterUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/TuplePrinterUtil.java
new file mode 100644
index 0000000..f24345d5
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/TuplePrinterUtil.java
@@ -0,0 +1,65 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep;
+
+import org.apache.asterix.dataflow.data.nontagged.printers.adm.AObjectPrinterFactory;
+import org.apache.hyracks.algebricks.data.IPrinter;
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.std.buffermanager.ITupleAccessor;
+
+public class TuplePrinterUtil {
+
+ private static final IPrinter printer = AObjectPrinterFactory.INSTANCE.createPrinter();
+
+ private TuplePrinterUtil() {
+ }
+
+ public static void printTuple(String message, ITupleAccessor accessor) throws HyracksDataException {
+ if (accessor.exists()) {
+ printTuple(message, accessor, accessor.getTupleId());
+ } else {
+ System.out.flush();
+ System.err.flush();
+ System.err.print(String.format("%1$-" + 15 + "s", message) + " --");
+ System.err.print("no tuple");
+ System.err.println();
+ System.err.flush();
+ }
+ }
+
+ public static void printTuple(String message, IFrameTupleAccessor accessor, int tupleId)
+ throws HyracksDataException {
+ System.out.flush();
+ System.err.flush();
+ System.err.print(String.format("%1$-" + 15 + "s", message) + " -- " + accessor.getTupleLength(tupleId) + " --");
+ int fields = accessor.getFieldCount();
+ for (int i = 0; i < fields; ++i) {
+ System.err.print(" " + i + ": ");
+ int fieldStartOffset = accessor.getFieldStartOffset(tupleId, i);
+ int fieldSlotsLength = accessor.getFieldSlotsLength();
+ int tupleStartOffset = accessor.getTupleStartOffset(tupleId);
+ printer.print(accessor.getBuffer().array(), fieldStartOffset + fieldSlotsLength + tupleStartOffset,
+ accessor.getFieldLength(tupleId, i), System.err);
+ }
+ System.err.println();
+ System.err.flush();
+ }
+
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/AppendDeletableFrameTupleAccessor.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/AppendDeletableFrameTupleAccessor.java
new file mode 100644
index 0000000..b164b0d
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/AppendDeletableFrameTupleAccessor.java
@@ -0,0 +1,411 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep.memory;
+
+import java.nio.ByteBuffer;
+import java.util.Comparator;
+import java.util.PriorityQueue;
+
+import org.apache.commons.lang3.tuple.Pair;
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.std.sort.util.IAppendDeletableFrameTupleAccessor;
+import org.apache.hyracks.util.IntSerDeUtils;
+
+/**
+ * This is a special frame which is used in TupleMemoryBuffer.
+ * This frame has a special structure to organize the deleted spaces.
+ * Specifically, the endOffset of the deleted tuple will be set as negative number.
+ * And we add a special <code>deleted_space</code> field at the last 4 bytes to
+ * remember how many bytes has been deleted.
+ * The offsets also store both the start and end values because tuples may be out of
+ * after several add, remove and reorganize operations.
+ * A frame is formatted with tuple data concatenated starting at offset 0,
+ * one tuple after another.
+ * Offset FS - 4 holds an int indicating the amount of <code>deleted_space</code> in the frame.
+ * Offset FS - 4 holds an int indicating the number of tuples (N) in the frame.
+ * FS - ((i + 1) * (4 + 4)) for i from 0 to N - 1 holds an two ints indicating
+ * the offset and length of the (i + 1)^th tuple.
+ * The tuple references are organized as a sequence of ints indicating the start of the field
+ * followed by the length of each tuple.
+ * The offset if the start of the frame.
+ * The tuple has been deleted if the length is 0.
+ *
+ * <pre>
+ * [ *tuple_1_bytes*,
+ * *tuple_2_bytes*,
+ * ...
+ * int length, int offset, # tuple 2
+ * int length, int offset, # tuple 1
+ * int tuple_append,
+ * int next_index,
+ * int deleted_space,
+ * int index_count,
+ * ]
+ * </pre>
+ *
+ * <pre>
+ * [ *tuple_1_bytes*,
+ * *tuple_2_bytes*,
+ * ...
+ * int end_offset,
+ * int offset, # tuple 2
+ * int offset, # tuple 1
+ * int deleted_space,
+ * int tuple_count,
+ * ]
+ * </pre>
+ */
+public class AppendDeletableFrameTupleAccessor implements IAppendDeletableFrameTupleAccessor {
+
+ public static final Comparator<Pair<Integer, Integer>> INDEX_OFFSET_ASC_COMPARATOR =
+ new Comparator<Pair<Integer, Integer>>() {
+ @Override
+ public int compare(Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) {
+ return p1.getValue() - p2.getValue();
+ }
+
+ };
+
+ private static final int SIZE_INDEX_COUNT = 4;
+ private static final int SIZE_DELETED_SPACE = 4;
+ private static final int SIZE_NEXT_INDEX = 4;
+ private static final int SIZE_TUPLE_APPEND = 4;
+
+ private static final int SIZE_START_OFFSET = 4;
+ private static final int SIZE_END_OFFSET = 4;
+ private static final int SIZE_OFFSET_GROUP = SIZE_END_OFFSET + SIZE_START_OFFSET;
+
+ private final RecordDescriptor recordDescriptor;
+ private ByteBuffer buffer;
+ private int indexSlotsOffset;
+ private int indexCount;
+ private int tupleAppend;
+ private int deletedSpace;
+ private int nextIndex;
+ private byte[] array; // to speed up the array visit a little
+ private IntegerPairPool ipp = new IntegerPairPool();
+
+ private final PriorityQueue<IntegerPair> reorganizeQueue;
+
+ public AppendDeletableFrameTupleAccessor(RecordDescriptor recordDescriptor) {
+ this.recordDescriptor = recordDescriptor;
+ reorganizeQueue = new PriorityQueue<>(16, IntegerPair.RIGHT_ASC_COMPARATOR);
+ }
+
+ private int getIndexCount() {
+ return IntSerDeUtils.getInt(array, getIndexCountOffset());
+ }
+
+ private void setIndexCount(int count) {
+ IntSerDeUtils.putInt(array, getIndexCountOffset(), count);
+ }
+
+ private int getIndexCountOffset() {
+ return buffer.capacity() - SIZE_INDEX_COUNT;
+ }
+
+ private int getDeletedSpace() {
+ return IntSerDeUtils.getInt(array, getDeletedSpaceOffset());
+ }
+
+ private void setDeletedSpace(int space) {
+ IntSerDeUtils.putInt(array, getDeletedSpaceOffset(), space);
+ }
+
+ private int getDeletedSpaceOffset() {
+ return getIndexCountOffset() - SIZE_DELETED_SPACE;
+ }
+
+ private int getNextIndex() {
+ return IntSerDeUtils.getInt(array, getNextIndexOffset());
+ }
+
+ private void setNextIndex(int index) {
+ IntSerDeUtils.putInt(array, getNextIndexOffset(), index);
+ }
+
+ private int getNextIndexOffset() {
+ return getDeletedSpaceOffset() - SIZE_NEXT_INDEX;
+ }
+
+ private int getAndUpdateNextIndex() {
+ int index = nextIndex;
+ nextIndex = index + 1;
+ while (nextIndex < indexCount) {
+ if (getTupleEndOffset(nextIndex) <= 0) {
+ break;
+ }
+ nextIndex++;
+ }
+ setNextIndex(nextIndex);
+ return index;
+ }
+
+ private int getTupleAppend() {
+ return IntSerDeUtils.getInt(array, getTupleAppendOffset());
+ }
+
+ private void setTupleAppend(int offset) {
+ IntSerDeUtils.putInt(array, getTupleAppendOffset(), offset);
+ }
+
+ private int getTupleAppendOffset() {
+ return getNextIndexOffset() - SIZE_TUPLE_APPEND;
+ }
+
+ private int getIndexSlotOffset() {
+ return getTupleAppendOffset();
+ }
+
+ @Override
+ public void clear(ByteBuffer buffer) throws HyracksDataException {
+ this.buffer = buffer;
+ this.array = buffer.array();
+ setIndexCount(0);
+ setDeletedSpace(0);
+ setNextIndex(0);
+ setTupleAppend(0);
+ resetCounts();
+ }
+
+ @Override
+ public void reset(ByteBuffer buffer) {
+ this.buffer = buffer;
+ this.array = buffer.array();
+ resetCounts();
+ }
+
+ private void resetCounts() {
+ indexSlotsOffset = getIndexSlotOffset();
+ deletedSpace = getDeletedSpace();
+ indexCount = getIndexCount();
+ tupleAppend = getTupleAppend();
+ nextIndex = getNextIndex();
+ }
+
+ /**
+ * Append the record into the frame. This method will not validate the space, please make sure space is enough
+ * by calling {@link #getContiguousFreeSpace()}
+ *
+ * @param tupleAccessor
+ * @param tIndex
+ * @return
+ * @throws HyracksDataException
+ */
+ @Override
+ public int append(IFrameTupleAccessor tupleAccessor, int tIndex) throws HyracksDataException {
+ byte[] src = tupleAccessor.getBuffer().array();
+ int tStartOffset = tupleAccessor.getTupleStartOffset(tIndex);
+ int length = tupleAccessor.getTupleLength(tIndex);
+ System.arraycopy(src, tStartOffset, array, tupleAppend, length);
+ int index = getAndUpdateNextIndex();
+ if (index < indexCount) {
+ // Don't change index count
+ } else {
+ // Increment count
+ setIndexCount(++indexCount);
+ }
+ setTupleOffsets(index, tupleAppend, length);
+ tupleAppend += length;
+ setTupleAppend(tupleAppend);
+ return index;
+ }
+
+ @Override
+ public void delete(int tupleIndex) {
+ int endOffset = getTupleEndOffset(tupleIndex);
+ if (endOffset > 0) {
+ setTupleEndOffset(tupleIndex, -endOffset);
+ deletedSpace += endOffset - getTupleStartOffset(tupleIndex);
+ setDeletedSpace(deletedSpace);
+ if (nextIndex > tupleIndex) {
+ nextIndex = tupleIndex;
+ setNextIndex(nextIndex);
+ }
+ }
+ }
+
+ @Override
+ public void reOrganizeBuffer() {
+ if (deletedSpace <= 0) {
+ return;
+ }
+ reclaimDeletedEnding();
+
+ // Build reorganize queue
+ IntegerPair ip;
+ int endOffset;
+ int startOffset;
+ for (int i = 0; i < indexCount; i++) {
+ endOffset = getTupleEndOffset(i);
+ if (endOffset > 0) {
+ ip = ipp.takeOne();
+ ip.reset(i, getTupleStartOffset(i));
+ reorganizeQueue.add(ip);
+ }
+ }
+
+ int index;
+ tupleAppend = 0;
+ while (!reorganizeQueue.isEmpty()) {
+ ip = reorganizeQueue.remove();
+ index = ip.getLeft();
+ startOffset = getTupleStartOffset(index);
+ endOffset = getTupleEndOffset(index);
+ if (endOffset >= 0) {
+ int length = endOffset - startOffset;
+ assert length >= 0;
+ if (tupleAppend != startOffset) {
+ System.arraycopy(array, startOffset, array, tupleAppend, length);
+ }
+ setTupleOffsets(index, tupleAppend, length);
+ tupleAppend += length;
+ }
+ ipp.giveBack(ip);
+ }
+ setTupleAppend(tupleAppend);
+ deletedSpace = 0;
+ setDeletedSpace(0);
+
+ // Clean up
+ reorganizeQueue.clear();
+ }
+
+ private void reclaimDeletedEnding() {
+ for (int i = indexCount - 1; i >= 0; i--) {
+ int endOffset = getTupleEndOffset(i);
+ if (endOffset <= 0) {
+ indexCount--;
+ } else {
+ break;
+ }
+ }
+ setIndexCount(indexCount);
+ if (nextIndex > indexCount) {
+ setNextIndex(indexCount);
+ }
+ }
+
+ @Override
+ public int getTotalFreeSpace() {
+ return getContiguousFreeSpace() + deletedSpace;
+ }
+
+ @Override
+ public int getContiguousFreeSpace() {
+ int slotSpace = indexCount * SIZE_OFFSET_GROUP;
+ return indexSlotsOffset - tupleAppend - slotSpace;
+ }
+
+ @Override
+ public int getFieldCount() {
+ return recordDescriptor.getFieldCount();
+ }
+
+ @Override
+ public int getFieldSlotsLength() {
+ return recordDescriptor.getFieldCount() * 4;
+ }
+
+ @Override
+ public int getFieldEndOffset(int tupleIndex, int fIdx) {
+ return IntSerDeUtils.getInt(array, getTupleStartOffset(tupleIndex) + fIdx * 4);
+ }
+
+ @Override
+ public int getFieldStartOffset(int tupleIndex, int fIdx) {
+ return fIdx == 0 ? 0 : IntSerDeUtils.getInt(array, getTupleStartOffset(tupleIndex) + (fIdx - 1) * 4);
+ }
+
+ @Override
+ public int getAbsoluteFieldStartOffset(int tupleIndex, int fIdx) {
+ return getTupleStartOffset(tupleIndex) + getFieldSlotsLength() + getFieldStartOffset(tupleIndex, fIdx);
+ }
+
+ @Override
+ public int getFieldLength(int tupleIndex, int fIdx) {
+ return getFieldEndOffset(tupleIndex, fIdx) - getFieldStartOffset(tupleIndex, fIdx);
+ }
+
+ @Override
+ public int getTupleLength(int tupleIndex) {
+ int endOffset = getTupleEndOffset(tupleIndex);
+ if (endOffset > 0) {
+ return endOffset - getTupleStartOffset(tupleIndex);
+ } else {
+ return endOffset + getTupleStartOffset(tupleIndex);
+ }
+ }
+
+ private void setTupleOffsets(int tupleIndex, int start, int length) {
+ setTupleStartOffset(tupleIndex, start);
+ setTupleEndOffset(tupleIndex, start + length);
+ }
+
+ @Override
+ public int getTupleEndOffset(int tupleIndex) {
+ return IntSerDeUtils.getInt(array, getTupleEndSlotOffset(tupleIndex));
+ }
+
+ private void setTupleEndOffset(int tupleIndex, int offset) {
+ IntSerDeUtils.putInt(array, getTupleEndSlotOffset(tupleIndex), offset);
+ }
+
+ @Override
+ public int getTupleStartOffset(int tupleIndex) {
+ return IntSerDeUtils.getInt(array, getTupleStartSlotOffset(tupleIndex));
+ }
+
+ public void setTupleStartOffset(int tupleIndex, int offset) {
+ IntSerDeUtils.putInt(array, getTupleStartSlotOffset(tupleIndex), offset);
+ }
+
+ public int getTupleStartSlotOffset(int tupleIndex) {
+ return indexSlotsOffset - SIZE_OFFSET_GROUP * tupleIndex - SIZE_START_OFFSET;
+ }
+
+ public int getTupleEndSlotOffset(int tupleIndex) {
+ return getTupleStartSlotOffset(tupleIndex) - SIZE_END_OFFSET;
+ }
+
+ @Override
+ public int getTupleCount() {
+ return getLiveTupleCount();
+ }
+
+ private int getLiveTupleCount() {
+ int live = 0;
+ for (int i = 0; i < indexCount; ++i) {
+ int endOffset = getTupleEndOffset(i);
+ if (endOffset > 0) {
+ live++;
+ }
+ }
+ return live;
+ }
+
+ @Override
+ public ByteBuffer getBuffer() {
+ return buffer;
+ }
+
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/IntegerPair.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/IntegerPair.java
new file mode 100644
index 0000000..1f98a2d
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/IntegerPair.java
@@ -0,0 +1,87 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep.memory;
+
+import java.io.Serializable;
+import java.util.Comparator;
+
+public class IntegerPair implements Serializable {
+ private static final long serialVersionUID = 1L;
+
+ public static final Comparator<IntegerPair> LEFT_ASC_COMPARATOR = new Comparator<IntegerPair>() {
+ @Override
+ public int compare(IntegerPair p1, IntegerPair p2) {
+ return p1.getLeft() - p2.getLeft();
+ }
+
+ };
+
+ public static final Comparator<IntegerPair> RIGHT_ASC_COMPARATOR = new Comparator<IntegerPair>() {
+ @Override
+ public int compare(IntegerPair p1, IntegerPair p2) {
+ return p1.getRight() - p2.getRight();
+ }
+
+ };
+
+ private int left;
+ private int right;
+
+ public IntegerPair() {
+ reset(Integer.MIN_VALUE, Integer.MIN_VALUE);
+ }
+
+ public IntegerPair(int l, int r) {
+ reset(l, r);
+ }
+
+ public int getLeft() {
+ return left;
+ }
+
+ public int getRight() {
+ return right;
+ }
+
+ public void reset(int l, int r) {
+ left = l;
+ right = r;
+ }
+
+ @Override
+ public String toString() {
+ return left + "," + right;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (!(obj instanceof IntegerPair)) {
+ return false;
+ } else {
+ IntegerPair p = (IntegerPair) obj;
+ return this.left == p.getLeft() && this.right == p.getRight();
+ }
+ }
+
+ @Override
+ public int hashCode() {
+ return left * 31 + right;
+ }
+
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/IntegerPairPool.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/IntegerPairPool.java
new file mode 100644
index 0000000..f559e07
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/IntegerPairPool.java
@@ -0,0 +1,39 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep.memory;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class IntegerPairPool {
+ private final List<IntegerPair> list;
+
+ public IntegerPairPool() {
+ list = new ArrayList<>();
+ }
+
+ public IntegerPair takeOne() {
+ if (list.isEmpty()) {
+ return new IntegerPair();
+ }
+ return list.remove(list.size() - 1);
+ }
+
+ public void giveBack(IntegerPair pair) {
+ list.add(pair);
+ }
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/VPartitionDeletableTupleBufferManager.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/VPartitionDeletableTupleBufferManager.java
new file mode 100644
index 0000000..38e6150
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/memory/VPartitionDeletableTupleBufferManager.java
@@ -0,0 +1,448 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep.memory;
+
+import static org.apache.hyracks.dataflow.std.buffermanager.EnumFreeSlotPolicy.LAST_FIT;
+
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
+import org.apache.hyracks.api.context.IHyracksFrameMgrContext;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
+import org.apache.hyracks.dataflow.std.buffermanager.AbstractTupleAccessor;
+import org.apache.hyracks.dataflow.std.buffermanager.AbstractTuplePointerAccessor;
+import org.apache.hyracks.dataflow.std.buffermanager.BufferInfo;
+import org.apache.hyracks.dataflow.std.buffermanager.FrameFreeSlotPolicyFactory;
+import org.apache.hyracks.dataflow.std.buffermanager.IFrameBufferManager;
+import org.apache.hyracks.dataflow.std.buffermanager.IFrameFreeSlotPolicy;
+import org.apache.hyracks.dataflow.std.buffermanager.IPartitionedDeletableTupleBufferManager;
+import org.apache.hyracks.dataflow.std.buffermanager.IPartitionedMemoryConstrain;
+import org.apache.hyracks.dataflow.std.buffermanager.ITupleAccessor;
+import org.apache.hyracks.dataflow.std.buffermanager.ITuplePointerAccessor;
+import org.apache.hyracks.dataflow.std.buffermanager.VPartitionTupleBufferManager;
+import org.apache.hyracks.dataflow.std.sort.util.IAppendDeletableFrameTupleAccessor;
+import org.apache.hyracks.dataflow.std.structures.TuplePointer;
+
+/**
+ * This buffer manager will divide the buffers into given number of partitions.
+ * The cleared partition (spilled one in the caller side) can only get no more than one frame.
+ */
+public class VPartitionDeletableTupleBufferManager extends VPartitionTupleBufferManager
+ implements IPartitionedDeletableTupleBufferManager {
+
+ private final int[] minFreeSpace;
+ private final IAppendDeletableFrameTupleAccessor[] accessor;
+ private final IFrameFreeSlotPolicy[] policy;
+
+ public VPartitionDeletableTupleBufferManager(IHyracksFrameMgrContext ctx, IPartitionedMemoryConstrain constrain,
+ int partitions, int frameLimitInBytes, RecordDescriptor[] recordDescriptors) throws HyracksDataException {
+ super(ctx, constrain, partitions, frameLimitInBytes);
+ int maxFrames = framePool.getMemoryBudgetBytes() / framePool.getMinFrameSize();
+ FrameFreeSlotPolicyFactory frameFreeSlotPolicyFactory = new FrameFreeSlotPolicyFactory();
+ this.policy = new IFrameFreeSlotPolicy[partitions];
+ this.accessor = new AppendDeletableFrameTupleAccessor[partitions];
+ this.minFreeSpace = new int[partitions];
+ int i = 0;
+ for (RecordDescriptor rd : recordDescriptors) {
+ this.accessor[i] = new AppendDeletableFrameTupleAccessor(rd);
+ this.minFreeSpace[i] = calculateMinFreeSpace(rd);
+ this.policy[i] = frameFreeSlotPolicyFactory.createFreeSlotPolicy(LAST_FIT, maxFrames);
+ ++i;
+ }
+ }
+
+ @Override
+ public boolean insertTuple(int partition, IFrameTupleAccessor fta, int idx, TuplePointer tuplePointer)
+ throws HyracksDataException {
+ int requiredFreeSpace = calculatePhysicalSpace(fta, idx);
+ int frameId = findAvailableFrame(partition, requiredFreeSpace);
+ if (frameId < 0) {
+ // printStats("Failed insert for " + partition);
+ if (canBeInsertedAfterFreeingFrames(partition)
+ || canBeInsertedAfterCleanUpFragmentation(partition, requiredFreeSpace)) {
+ reOrganizeFrames();
+ frameId = findAvailableFrame(partition, requiredFreeSpace);
+ } else {
+ return false;
+ }
+ }
+ assert frameId >= 0;
+ partitionArray[partition].getFrame(frameId, tempInfo);
+ accessor[partition].reset(tempInfo.getBuffer());
+ assert accessor[partition].getContiguousFreeSpace() >= requiredFreeSpace;
+ int tid = accessor[partition].append(fta, idx);
+ assert tid >= 0;
+ if (accessor[partition].getContiguousFreeSpace() > minFreeSpace[partition]) {
+ policy[partition].pushNewFrame(frameId, accessor[partition].getContiguousFreeSpace());
+ }
+ tuplePointer.reset(makeGroupFrameId(partition, frameId), tid);
+ numTuples[partition]++;
+ return true;
+ }
+
+ @Override
+ public void clearPartition(int partitionId) throws HyracksDataException {
+ IFrameBufferManager partition = partitionArray[partitionId];
+ if (partition != null) {
+ partition.resetIterator();
+ int i = partition.next();
+ while (partition.exists()) {
+ accessor[partitionId].clear(partition.getFrame(i, tempInfo).getBuffer());
+ i = partition.next();
+ }
+ }
+ policy[partitionId].reset();
+ super.clearPartition(partitionId);
+ }
+
+ private boolean canBeInsertedAfterFreeingFrames(int skipPartition) {
+ for (int partition = 0; partition < partitionArray.length; ++partition) {
+ if (skipPartition == partition || partitionArray[partition] == null) {
+ continue;
+ }
+ partitionArray[partition].resetIterator();
+ int f = partitionArray[partition].next();
+ while (partitionArray[partition].exists()) {
+ partitionArray[partition].getFrame(f, tempInfo);
+ accessor[partition].reset(tempInfo.getBuffer());
+ if (accessor[partition].getTupleCount() == 0) {
+ return true;
+ }
+ f = partitionArray[partition].next();
+ }
+ }
+ return false;
+ }
+
+ private void reOrganizeFrames() {
+ for (int p = 0; p < partitionArray.length; ++p) {
+ reOrganizeFramesForPartition(p);
+ }
+ }
+
+ private void reOrganizeFramesForPartition(int partition) {
+ //System.err.printf("reOrganizeFrames -- %d:[", partition);
+ policy[partition].reset();
+ partitionArray[partition].resetIterator();
+ int f = partitionArray[partition].next();
+ while (partitionArray[partition].exists()) {
+ reOrganizeFrameForPartition(partition, f);
+ f = partitionArray[partition].next();
+ }
+ // System.err.println("] ");
+ }
+
+ private void reOrganizeFrameForPartition(int partition, int f) {
+ partitionArray[partition].getFrame(f, tempInfo);
+ accessor[partition].reset(tempInfo.getBuffer());
+ accessor[partition].reOrganizeBuffer();
+ if (accessor[partition].getTupleCount() == 0) {
+ partitionArray[partition].removeFrame(f);
+ framePool.deAllocateBuffer(tempInfo.getBuffer());
+ //System.err.print("REMOVED");
+ } else {
+ policy[partition].pushNewFrame(f, accessor[partition].getContiguousFreeSpace());
+ //accessor[partition].printStats(System.err);
+ }
+ }
+
+ private boolean canBeInsertedAfterCleanUpFragmentation(int partition, int requiredFreeSpace) {
+ partitionArray[partition].resetIterator();
+ int i = partitionArray[partition].next();
+ while (partitionArray[partition].exists()) {
+ partitionArray[partition].getFrame(i, tempInfo);
+ accessor[partition].reset(tempInfo.getBuffer());
+ if (accessor[partition].getTotalFreeSpace() >= requiredFreeSpace) {
+ return true;
+ }
+ i = partitionArray[partition].next();
+ }
+ return false;
+ }
+
+ private int findAvailableFrame(int partition, int requiredFreeSpace) throws HyracksDataException {
+ int frameId = policy[partition].popBestFit(requiredFreeSpace);
+ if (frameId >= 0) {
+ return frameId;
+ }
+ if (partitionArray[partition] == null || partitionArray[partition].getNumFrames() == 0) {
+ partitionArray[partition] = new PartitionFrameBufferManager();
+ }
+ return createNewBuffer(partition, requiredFreeSpace);
+ }
+
+ private static int calculatePhysicalSpace(IFrameTupleAccessor fta, int idx) {
+ // 4 bytes to store the offset
+ return 4 + fta.getTupleLength(idx);
+ }
+
+ private static int calculateMinFreeSpace(RecordDescriptor recordDescriptor) {
+ // + 4 for the tuple offset
+ return recordDescriptor.getFieldCount() * 4 + 4;
+ }
+
+ public void printStats(String message) {
+ System.err.print(String.format("%1$-" + 15 + "s", message) + " --");
+
+ for (int p = 0; p < partitionArray.length; ++p) {
+ System.err.printf("%d:[", p);
+ IFrameBufferManager partition = partitionArray[p];
+ if (partition != null) {
+ partitionArray[p].resetIterator();
+ int f = partitionArray[p].next();
+ while (partitionArray[p].exists()) {
+ partitionArray[p].getFrame(f, tempInfo);
+ accessor[p].reset(tempInfo.getBuffer());
+ f = partitionArray[p].next();
+ }
+ }
+ System.err.printf("] ");
+ }
+ System.err.println();
+ }
+
+ @Override
+ public void deleteTuple(int partition, TuplePointer tuplePointer) throws HyracksDataException {
+
+ int f = parseFrameIdInPartition(tuplePointer.getFrameIndex());
+ partitionArray[parsePartitionId(tuplePointer.getFrameIndex())].getFrame(f, tempInfo);
+ accessor[partition].reset(tempInfo.getBuffer());
+ accessor[partition].delete(tuplePointer.getTupleIndex());
+ numTuples[partition]--;
+
+ // // Return frame
+ // if (accessor[partition].getTupleCount() == 0 && partitionArray[partition].getNumFrames() > 1) {
+ // reOrganizeFrames(partition);
+ // }
+ }
+
+ @Override
+ public ITuplePointerAccessor getTuplePointerAccessor(final RecordDescriptor recordDescriptor) {
+ return new AbstractTuplePointerAccessor() {
+ private IAppendDeletableFrameTupleAccessor innerAccessor =
+ new AppendDeletableFrameTupleAccessor(recordDescriptor);
+
+ @Override
+ protected IFrameTupleAccessor getInnerAccessor() {
+ return innerAccessor;
+ }
+
+ @Override
+ protected void resetInnerAccessor(TuplePointer tuplePointer) {
+ partitionArray[parsePartitionId(tuplePointer.getFrameIndex())]
+ .getFrame(parseFrameIdInPartition(tuplePointer.getFrameIndex()), tempInfo);
+ innerAccessor.reset(tempInfo.getBuffer());
+ }
+ };
+ }
+
+ public ITupleAccessor getTupleAccessor(final RecordDescriptor recordDescriptor) {
+ return new AbstractTupleAccessor() {
+ private AppendDeletableFrameTupleAccessor innerAccessor =
+ new AppendDeletableFrameTupleAccessor(recordDescriptor);
+
+ @Override
+ protected IFrameTupleAccessor getInnerAccessor() {
+ return innerAccessor;
+ }
+
+ @Override
+ protected void resetInnerAccessor(TuplePointer tuplePointer) {
+ resetInnerAccessor(tuplePointer.getFrameIndex());
+ }
+
+ @Override
+ protected void resetInnerAccessor(int frameIndex) {
+ partitionArray[parsePartitionId(frameIndex)].getFrame(parseFrameIdInPartition(frameIndex), tempInfo);
+ innerAccessor.reset(tempInfo.getBuffer());
+ }
+
+ @Override
+ protected int getFrameCount() {
+ return partitionArray.length;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return hasNext(frameId, tupleId);
+ }
+
+ @Override
+ public void next() {
+ tupleId = nextTuple(frameId, tupleId);
+ if (tupleId > INITIALIZED) {
+ return;
+ }
+
+ if (frameId + 1 < getFrameCount()) {
+ ++frameId;
+ resetInnerAccessor(frameId);
+ tupleId = INITIALIZED;
+ next();
+ }
+ }
+
+ public boolean hasNext(int fId, int tId) {
+ int id = nextTuple(fId, tId);
+ if (id > INITIALIZED) {
+ return true;
+ }
+ if (fId + 1 < getFrameCount()) {
+ return hasNext(fId + 1, INITIALIZED);
+ }
+ return false;
+ }
+
+ public int nextTuple(int fId, int tId) {
+ if (fId != frameId) {
+ resetInnerAccessor(fId);
+ }
+ int id = nextTupleInFrame(tId);
+ if (fId != frameId) {
+ resetInnerAccessor(frameId);
+ }
+ return id;
+ }
+
+ public int nextTupleInFrame(int tId) {
+ int id = tId;
+ while (id + 1 < getTupleCount()) {
+ ++id;
+ if (getTupleEndOffset(id) > 0) {
+ return id;
+ }
+ }
+ return UNSET;
+ }
+
+ };
+ }
+
+ static class PartitionFrameBufferManager implements IFrameBufferManager {
+
+ int size = 0;
+ ArrayList<ByteBuffer> buffers = new ArrayList<>();
+
+ @Override
+ public void reset() throws HyracksDataException {
+ buffers.clear();
+ size = 0;
+ }
+
+ @Override
+ public BufferInfo getFrame(int frameIndex, BufferInfo returnedInfo) {
+ returnedInfo.reset(buffers.get(frameIndex), 0, buffers.get(frameIndex).capacity());
+ return returnedInfo;
+ }
+
+ @Override
+ public int getNumFrames() {
+ return size;
+ }
+
+ @Override
+ public int insertFrame(ByteBuffer frame) throws HyracksDataException {
+ int index = -1;
+ if (buffers.size() == size) {
+ buffers.add(frame);
+ index = buffers.size() - 1;
+ } else {
+ for (int i = 0; i < buffers.size(); ++i) {
+ if (buffers.get(i) == null) {
+ buffers.set(i, frame);
+ index = i;
+ break;
+ }
+ }
+ }
+ if (index == -1) {
+ throw new HyracksDataException("Did not insert frame.");
+ }
+ size++;
+ return index;
+ }
+
+ @Override
+ public void removeFrame(int frameIndex) {
+ buffers.set(frameIndex, null);
+ size--;
+ }
+
+ @Override
+ public void close() {
+ buffers = null;
+ }
+
+ int iterator = -1;
+
+ @Override
+ public int next() {
+ while (++iterator < buffers.size()) {
+ if (buffers.get(iterator) != null) {
+ break;
+ }
+ }
+ return iterator;
+ }
+
+ @Override
+ public boolean exists() {
+ return iterator < buffers.size() && buffers.get(iterator) != null;
+ }
+
+ @Override
+ public void resetIterator() {
+ iterator = -1;
+ }
+
+ @Override
+ public ITupleAccessor getTupleAccessor(final RecordDescriptor recordDescriptor) {
+ return new AbstractTupleAccessor() {
+ protected BufferInfo tempBI = new BufferInfo(null, -1, -1);
+ FrameTupleAccessor innerAccessor = new FrameTupleAccessor(recordDescriptor);
+
+ @Override
+ protected IFrameTupleAccessor getInnerAccessor() {
+ return innerAccessor;
+ }
+
+ @Override
+ protected void resetInnerAccessor(int frameIndex) {
+ getFrame(frameIndex, tempBI);
+ innerAccessor.reset(tempBI.getBuffer(), tempBI.getStartOffset(), tempBI.getLength());
+ }
+
+ protected void resetInnerAccessor(TuplePointer tuplePointer) {
+ getFrame(tuplePointer.getFrameIndex(), tempBI);
+ innerAccessor.reset(tempBI.getBuffer(), tempBI.getStartOffset(), tempBI.getLength());
+ }
+
+ @Override
+ protected int getFrameCount() {
+ return 0;
+ }
+ };
+ }
+
+ }
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AbstractIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AbstractIntervalJoinUtil.java
index 80d791c..49f69af 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AbstractIntervalJoinUtil.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AbstractIntervalJoinUtil.java
@@ -62,9 +62,14 @@
@Override
public boolean checkToSaveInResult(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) throws HyracksDataException {
- IntervalJoinUtil.getIntervalPointable(buildAccessor, buildTupleIndex, idBuild, ipBuild);
- IntervalJoinUtil.getIntervalPointable(probeAccessor, probeTupleIndex, idProbe, ipProbe);
+ IFrameTupleAccessor probeAccessor, int probeTupleIndex, boolean reversed) throws HyracksDataException {
+ if (reversed) {
+ IntervalJoinUtil.getIntervalPointable(buildAccessor, buildTupleIndex, idBuild, ipProbe);
+ IntervalJoinUtil.getIntervalPointable(probeAccessor, probeTupleIndex, idProbe, ipBuild);
+ } else {
+ IntervalJoinUtil.getIntervalPointable(buildAccessor, buildTupleIndex, idBuild, ipBuild);
+ IntervalJoinUtil.getIntervalPointable(probeAccessor, probeTupleIndex, idProbe, ipProbe);
+ }
return compareInterval(ipBuild, ipProbe);
}
@@ -90,4 +95,37 @@
long probeStart = IntervalJoinUtil.getIntervalStart(probeAccessor, probeTupleIndex, idProbe);
return buildEnd > probeStart;
}
+
+ //Checked
+ @Override
+ public boolean checkToRemoveBuildActive() {
+ return true;
+ }
+
+ @Override
+ public boolean checkToRemoveProbeActive() {
+ return true;
+ }
+
+ /**
+ * Left (first argument) interval starts after the Right (second argument) interval ends.
+ */
+ @Override
+ public boolean checkToRemoveInMemory(IFrameTupleAccessor accessor0, int tupleIndex0, int key0, long end1,
+ boolean reversed) {
+ long start0 = IntervalJoinUtil.getIntervalStart(accessor0, tupleIndex0, key0);
+
+ if (reversed) {
+ return start0 < end1;
+ }
+ return start0 > end1;
+ }
+
+ @Override
+ public boolean choosePath(IFrameTupleAccessor buildAccessor, int buildTupleIndex, IFrameTupleAccessor probeAccessor,
+ int probeTupleIndex) {
+ long buildStart = IntervalJoinUtil.getIntervalStart(buildAccessor, buildTupleIndex, idBuild);
+ long probeStart = IntervalJoinUtil.getIntervalEnd(probeAccessor, probeTupleIndex, idProbe);
+ return buildStart > probeStart;
+ }
}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AfterIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AfterIntervalJoinUtil.java
deleted file mode 100644
index 5dd4c44..0000000
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AfterIntervalJoinUtil.java
+++ /dev/null
@@ -1,62 +0,0 @@
-/*
- * 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.asterix.runtime.operators.joins.interval.utils;
-
-import org.apache.asterix.om.pointables.nonvisitor.AIntervalPointable;
-import org.apache.asterix.runtime.operators.joins.interval.utils.memory.IntervalJoinUtil;
-import org.apache.hyracks.api.comm.IFrameTupleAccessor;
-import org.apache.hyracks.api.exceptions.HyracksDataException;
-
-public class AfterIntervalJoinUtil extends AbstractIntervalJoinUtil {
-
- public AfterIntervalJoinUtil(int buildKey, int probeKey) {
- super(buildKey, probeKey);
- }
-
- @Override
- public boolean checkToSaveInMemory(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- return true;
- }
-
- @Override
- public boolean checkToRemoveInMemory(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- return false;
- }
-
- @Override
- public boolean checkForEarlyExit(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- return false;
- }
-
- @Override
- public boolean compareInterval(AIntervalPointable ipBuild, AIntervalPointable ipProbe) throws HyracksDataException {
- return il.after(ipBuild, ipProbe);
- }
-
- @Override
- public boolean checkToLoadNextProbeTuple(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- long buildEnd = IntervalJoinUtil.getIntervalEnd(buildAccessor, buildTupleIndex, idBuild);
- long probeStart = IntervalJoinUtil.getIntervalStart(probeAccessor, probeTupleIndex, idProbe);
- return probeStart <= buildEnd;
- }
-}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/BeforeIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/BeforeIntervalJoinUtil.java
deleted file mode 100644
index 5212a4d..0000000
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/BeforeIntervalJoinUtil.java
+++ /dev/null
@@ -1,62 +0,0 @@
-/*
- * 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.asterix.runtime.operators.joins.interval.utils;
-
-import org.apache.asterix.om.pointables.nonvisitor.AIntervalPointable;
-import org.apache.asterix.runtime.operators.joins.interval.utils.memory.IntervalJoinUtil;
-import org.apache.hyracks.api.comm.IFrameTupleAccessor;
-import org.apache.hyracks.api.exceptions.HyracksDataException;
-
-public class BeforeIntervalJoinUtil extends AbstractIntervalJoinUtil {
-
- public BeforeIntervalJoinUtil(int buildKey, int probeKey) {
- super(buildKey, probeKey);
- }
-
- @Override
- public boolean checkToSaveInMemory(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- long buildStart = IntervalJoinUtil.getIntervalStart(buildAccessor, buildTupleIndex, idBuild);
- long probeStart = IntervalJoinUtil.getIntervalStart(probeAccessor, probeTupleIndex, idProbe);
- return buildStart < probeStart;
- }
-
- @Override
- public boolean checkToRemoveInMemory(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- return !checkToSaveInMemory(buildAccessor, buildTupleIndex, probeAccessor, probeTupleIndex);
- }
-
- @Override
- public boolean checkForEarlyExit(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- return false;
- }
-
- @Override
- public boolean compareInterval(AIntervalPointable ipBuild, AIntervalPointable ipProbe) throws HyracksDataException {
- return il.before(ipBuild, ipProbe);
- }
-
- @Override
- public boolean checkToLoadNextProbeTuple(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- return true;
- }
-}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/BeforeIntervalJoinUtilFactory.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/BeforeIntervalJoinUtilFactory.java
deleted file mode 100644
index 1984caf..0000000
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/BeforeIntervalJoinUtilFactory.java
+++ /dev/null
@@ -1,31 +0,0 @@
-/*
- * 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.asterix.runtime.operators.joins.interval.utils;
-
-import org.apache.hyracks.api.context.IHyracksTaskContext;
-
-public class BeforeIntervalJoinUtilFactory implements IIntervalJoinUtilFactory {
- private static final long serialVersionUID = 1L;
-
- @Override
- public IIntervalJoinUtil createIntervalMergeJoinUtil(int buildKey, int probeKey, IHyracksTaskContext ctx,
- int nPartitions) {
- return new BeforeIntervalJoinUtil(buildKey, probeKey);
- }
-}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoveredByIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoveredByIntervalJoinUtil.java
index 91dfc66..dbad058 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoveredByIntervalJoinUtil.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoveredByIntervalJoinUtil.java
@@ -40,6 +40,13 @@
return buildStart <= probeEnd;
}
+ @Override
+ public boolean checkToRemoveInMemory(IFrameTupleAccessor accessor0, int tupleIndex0, int key0, long point1,
+ boolean reversed) {
+ long point0 = IntervalJoinUtil.getIntervalStart(accessor0, tupleIndex0, key0);
+ return point0 > point1;
+ }
+
/**
* Left (first argument) interval starts after the Right (second argument) interval ends.
*/
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoversIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoversIntervalJoinUtil.java
index 41c8c34..8943bb8 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoversIntervalJoinUtil.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/CoversIntervalJoinUtil.java
@@ -19,6 +19,8 @@
package org.apache.asterix.runtime.operators.joins.interval.utils;
import org.apache.asterix.om.pointables.nonvisitor.AIntervalPointable;
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.IntervalJoinUtil;
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
import org.apache.hyracks.api.exceptions.HyracksDataException;
public class CoversIntervalJoinUtil extends AbstractIntervalJoinUtil {
@@ -31,4 +33,11 @@
public boolean compareInterval(AIntervalPointable ipBuild, AIntervalPointable ipProbe) throws HyracksDataException {
return il.covers(ipBuild, ipProbe);
}
+
+ @Override
+ public boolean checkToRemoveInMemory(IFrameTupleAccessor accessor0, int tupleIndex0, int key0, long point1,
+ boolean reversed) {
+ long point0 = IntervalJoinUtil.getIntervalStart(accessor0, tupleIndex0, key0);
+ return point0 < point1;
+ }
}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/IIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/IIntervalJoinUtil.java
index 79eb2d7..410165c 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/IIntervalJoinUtil.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/IIntervalJoinUtil.java
@@ -62,7 +62,7 @@
* @throws HyracksDataException
*/
boolean checkToSaveInResult(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) throws HyracksDataException;
+ IFrameTupleAccessor probeAccessor, int probeTupleIndex, boolean reversed) throws HyracksDataException;
/**
* Check to see if the interval matches the join condition.
@@ -99,4 +99,14 @@
boolean checkToLoadNextProbeTuple(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
IFrameTupleAccessor probeAccessor, int probeTupleIndex);
+ boolean checkToRemoveBuildActive();
+
+ boolean checkToRemoveProbeActive();
+
+ boolean checkToRemoveInMemory(IFrameTupleAccessor accessor0, int tupleIndex0, int key0, long end1,
+ boolean reversed);
+
+ boolean choosePath(IFrameTupleAccessor buildAccessor, int buildTupleIndex, IFrameTupleAccessor probeAccessor,
+ int probeTupleIndex);
+
}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappedByIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappedByIntervalJoinUtil.java
index 2bd03a2..ccea0d6 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappedByIntervalJoinUtil.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappedByIntervalJoinUtil.java
@@ -19,6 +19,8 @@
package org.apache.asterix.runtime.operators.joins.interval.utils;
import org.apache.asterix.om.pointables.nonvisitor.AIntervalPointable;
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.IntervalJoinUtil;
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
import org.apache.hyracks.api.exceptions.HyracksDataException;
public class OverlappedByIntervalJoinUtil extends AbstractIntervalInverseJoinUtil {
@@ -31,4 +33,18 @@
public boolean compareInterval(AIntervalPointable ipBuild, AIntervalPointable ipProbe) throws HyracksDataException {
return il.overlappedBy(ipBuild, ipProbe);
}
+
+ /**
+ * Left (first argument) interval starts after the Right (second argument) interval ends.
+ */
+ @Override
+ public boolean checkToRemoveInMemory(IFrameTupleAccessor accessor0, int tupleIndex0, int key0, long end1,
+ boolean reversed) {
+ long start0 = IntervalJoinUtil.getIntervalStart(accessor0, tupleIndex0, key0);
+
+ if (reversed) {
+ return start0 < end1;
+ }
+ return start0 > end1;
+ }
}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappingIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappingIntervalJoinUtil.java
index 9aeb09b..7900e87 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappingIntervalJoinUtil.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlappingIntervalJoinUtil.java
@@ -48,8 +48,8 @@
@Override
public boolean checkForEarlyExit(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
IFrameTupleAccessor probeAccessor, int probeTupleIndex) {
- long probeStart = IntervalJoinUtil.getIntervalStart(probeAccessor, probeTupleIndex, idProbe);
long buildEnd = IntervalJoinUtil.getIntervalEnd(buildAccessor, buildTupleIndex, idBuild);
+ long probeStart = IntervalJoinUtil.getIntervalStart(probeAccessor, probeTupleIndex, idProbe);
return buildEnd <= probeStart;
}
@@ -66,18 +66,47 @@
@Override
public boolean checkToSaveInResult(IFrameTupleAccessor buildAccessor, int buildTupleIndex,
- IFrameTupleAccessor probeAccessor, int probeTupleIndex) throws HyracksDataException {
+ IFrameTupleAccessor probeAccessor, int probeTupleIndex, boolean reversed) throws HyracksDataException {
IntervalJoinUtil.getIntervalPointable(buildAccessor, buildTupleIndex, idBuild, ipBuild);
IntervalJoinUtil.getIntervalPointable(probeAccessor, probeTupleIndex, idProbe, ipProbe);
- if (ipBuild.getStartValue() < partitionStart && ipProbe.getStartValue() < partitionStart) {
- // These tuples match in a different partition
- return false;
+ if (reversed) {
+ if (ipProbe.getStartValue() < partitionStart && ipBuild.getStartValue() < partitionStart) {
+ // These tuples match in a different partition
+ return false;
+ }
+ return compareInterval(ipProbe, ipBuild);
+ } else {
+ if (ipBuild.getStartValue() < partitionStart && ipProbe.getStartValue() < partitionStart) {
+ // These tuples match in a different partition
+ return false;
+ }
+ return compareInterval(ipBuild, ipProbe);
}
- return compareInterval(ipBuild, ipProbe);
}
@Override
public boolean compareInterval(AIntervalPointable ipBuild, AIntervalPointable ipProbe) throws HyracksDataException {
return il.overlapping(ipBuild, ipProbe);
}
+
+ /**
+ * Left (first argument) interval starts after the Right (second argument) interval ends.
+ */
+ @Override
+ public boolean checkToRemoveInMemory(IFrameTupleAccessor accessor0, int tupleIndex0, int key0, long point1,
+ boolean reversed) {
+ long start0 = IntervalJoinUtil.getIntervalStart(accessor0, tupleIndex0, key0);
+ if (reversed) {
+ return point1 >= start0;
+ }
+ return start0 >= point1;
+ }
+
+ @Override
+ public boolean choosePath(IFrameTupleAccessor buildAccessor, int buildTupleIndex, IFrameTupleAccessor probeAccessor,
+ int probeTupleIndex) {
+ long buildStart = IntervalJoinUtil.getIntervalStart(buildAccessor, buildTupleIndex, idBuild);
+ long probeStart = IntervalJoinUtil.getIntervalEnd(probeAccessor, probeTupleIndex, idProbe);
+ return !(buildStart >= probeStart);
+ }
}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlapsIntervalJoinUtil.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlapsIntervalJoinUtil.java
index 933c565..c0d5dd4 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlapsIntervalJoinUtil.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/OverlapsIntervalJoinUtil.java
@@ -19,6 +19,8 @@
package org.apache.asterix.runtime.operators.joins.interval.utils;
import org.apache.asterix.om.pointables.nonvisitor.AIntervalPointable;
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.IntervalJoinUtil;
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
import org.apache.hyracks.api.exceptions.HyracksDataException;
public class OverlapsIntervalJoinUtil extends AbstractIntervalJoinUtil {
@@ -31,4 +33,18 @@
public boolean compareInterval(AIntervalPointable ipBuild, AIntervalPointable ipProbe) throws HyracksDataException {
return il.overlaps(ipBuild, ipProbe);
}
+
+ @Override
+ public boolean checkToRemoveInMemory(IFrameTupleAccessor accessor0, int tupleIndex0, int key0, long end1,
+ boolean reversed) {
+ return false;
+ }
+
+ @Override
+ public boolean choosePath(IFrameTupleAccessor buildAccessor, int buildTupleIndex, IFrameTupleAccessor probeAccessor,
+ int probeTupleIndex) {
+ long buildStart = IntervalJoinUtil.getIntervalStart(buildAccessor, buildTupleIndex, idBuild);
+ long probeStart = IntervalJoinUtil.getIntervalEnd(probeAccessor, probeTupleIndex, idProbe);
+ return buildStart >= probeStart;
+ }
}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/memory/IntervalSideTuple.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/memory/IntervalSideTuple.java
index ac30067..7a7b06d 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/memory/IntervalSideTuple.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/memory/IntervalSideTuple.java
@@ -64,7 +64,7 @@
public boolean compareJoin(IntervalSideTuple ist) throws HyracksDataException {
return imjc.checkToSaveInResult(cursor.getAccessor(), cursor.getTupleId(), ist.cursor.getAccessor(),
- ist.cursor.getTupleId());
+ ist.cursor.getTupleId(), false);
}
public boolean removeFromMemory(IntervalSideTuple ist) {
diff --git a/asterixdb/asterix-runtime/src/test/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/ActiveSweepManagerTest.java b/asterixdb/asterix-runtime/src/test/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/ActiveSweepManagerTest.java
new file mode 100644
index 0000000..179fc32
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/test/java/org/apache/asterix/runtime/operators/joins/interval/TimeSweep/ActiveSweepManagerTest.java
@@ -0,0 +1,298 @@
+/*
+ * 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.asterix.runtime.operators.joins.interval.TimeSweep;
+
+import static org.junit.Assert.assertEquals;
+
+import java.io.ByteArrayOutputStream;
+import java.io.DataOutput;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.nio.ByteBuffer;
+import java.util.logging.Logger;
+
+import org.apache.asterix.dataflow.data.nontagged.serde.AIntervalSerializerDeserializer;
+import org.apache.asterix.om.base.AInterval;
+import org.apache.asterix.om.types.ATypeTag;
+import org.apache.asterix.runtime.operators.joins.interval.TimeSweep.memory.VPartitionDeletableTupleBufferManager;
+import org.apache.asterix.runtime.operators.joins.interval.utils.memory.FrameTupleCursor;
+import org.apache.hyracks.api.comm.IFrame;
+import org.apache.hyracks.api.comm.VSizeFrame;
+import org.apache.hyracks.api.context.IHyracksTaskContext;
+import org.apache.hyracks.api.dataflow.value.ISerializerDeserializer;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import org.apache.hyracks.dataflow.common.comm.io.FrameTupleAppender;
+import org.apache.hyracks.dataflow.std.buffermanager.IPartitionedDeletableTupleBufferManager;
+import org.apache.hyracks.dataflow.std.structures.TuplePointer;
+import org.apache.hyracks.test.support.TestUtils;
+import org.junit.Before;
+import org.junit.Test;
+
+public class ActiveSweepManagerTest {
+
+ private static final Logger LOGGER = Logger.getLogger(IntervalTimeSweepJoiner.class.getName());
+
+ private final ISerializerDeserializer<AInterval> intervalSerde = AIntervalSerializerDeserializer.INSTANCE;
+ @SuppressWarnings("rawtypes")
+ private final ISerializerDeserializer[] SerDers =
+ new ISerializerDeserializer[] { AIntervalSerializerDeserializer.INSTANCE };
+ private final RecordDescriptor RecordDesc = new RecordDescriptor(SerDers);
+
+ private final int FRAME_SIZE = 320;
+
+ private final AInterval[] INTERVALS = new AInterval[] { new AInterval(99, 301, (byte) 16),
+ new AInterval(100, 300, (byte) 16), new AInterval(101, 299, (byte) 16) };
+ private final int INTERVAL_LENGTH = Byte.BYTES + Byte.BYTES + Long.BYTES + Long.BYTES;
+
+ /*
+ * Tests
+ *
+ * - add
+ * - top point
+ * - remove
+ * - has records
+ * - is empty
+ * - clear
+ */
+ IPartitionedDeletableTupleBufferManager bufferManager;
+ FrameTupleCursor memoryAccessor;
+ FrameTupleAppender appender;
+
+ @SuppressWarnings("unused")
+ private byte[] getIntervalBytes(AInterval[] intervals, int i) throws HyracksDataException {
+ try {
+ ByteArrayOutputStream bos = new ByteArrayOutputStream();
+ DataOutput dos = new DataOutputStream(bos);
+ dos.write(ATypeTag.SERIALIZED_INTERVAL_TYPE_TAG);
+ intervalSerde.serialize(intervals[i], dos);
+ bos.close();
+ return bos.toByteArray();
+ } catch (IOException e) {
+ throw HyracksDataException.create(e);
+ }
+ }
+
+ private ByteBuffer prepareData(IHyracksTaskContext ctx, AInterval[] intervals) throws HyracksDataException {
+
+ IFrame frame = new VSizeFrame(ctx);
+ FrameTupleAppender fffta = new FrameTupleAppender();
+ fffta.reset(frame, true);
+
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(RecordDesc.getFieldCount());
+
+ byte[] serializedInterval;
+
+ for (int i = 0; i < intervals.length; i++) {
+ tb.reset();
+ serializedInterval = getIntervalBytes(intervals, i);
+ tb.addField(serializedInterval, 0, serializedInterval.length);
+ fffta.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
+ }
+
+ return frame.getBuffer();
+ }
+
+ private void prepareMemory(ActiveSweepManager activeManager) throws HyracksDataException {
+ FrameTupleCursor cursor = new FrameTupleCursor(RecordDesc);
+ ByteBuffer buffer = prepareData(ctx, INTERVALS);
+ cursor.reset(buffer);
+ cursor.next();
+
+ TuplePointer tp = new TuplePointer();
+ activeManager.addTuple(cursor, tp);
+
+ tp = new TuplePointer();
+ cursor.next();
+ activeManager.addTuple(cursor, tp);
+
+ tp = new TuplePointer();
+ cursor.next();
+ activeManager.addTuple(cursor, tp);
+ }
+
+ IHyracksTaskContext ctx;
+
+ @Before
+ public void initial() throws HyracksDataException {
+ int memorySize = 5;
+ ctx = TestUtils.create(FRAME_SIZE);
+ RecordDescriptor intervalRD =
+ new RecordDescriptor(new ISerializerDeserializer[] { AIntervalSerializerDeserializer.INSTANCE });
+ RecordDescriptor[] records = { intervalRD, intervalRD };
+ bufferManager = new VPartitionDeletableTupleBufferManager(ctx,
+ VPartitionDeletableTupleBufferManager.NO_CONSTRAIN, 2, memorySize * ctx.getInitialFrameSize(), records);
+ memoryAccessor = new FrameTupleCursor(intervalRD);
+ appender = new FrameTupleAppender();
+ }
+
+ @Test
+ public void testBasicOperations() throws HyracksDataException {
+ ActiveSweepManager activeManager = new ActiveSweepManager(bufferManager, 0, 0,
+ EndPointIndexItem.EndPointAscComparator, EndPointIndexItem.START_POINT);
+
+ assertEquals(activeManager.hasRecords(), false);
+ assertEquals(activeManager.isEmpty(), true);
+
+ prepareMemory(activeManager);
+
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ activeManager.clear();
+ assertEquals(0, activeManager.getActiveList().size());
+ assertEquals(false, activeManager.hasRecords());
+ assertEquals(true, activeManager.isEmpty());
+
+ }
+
+ @Test
+ public void testAscendingStartpoint() throws HyracksDataException {
+ ActiveSweepManager activeManager = new ActiveSweepManager(bufferManager, 0, 0,
+ EndPointIndexItem.EndPointAscComparator, EndPointIndexItem.START_POINT);
+
+ assertEquals(activeManager.hasRecords(), false);
+ assertEquals(activeManager.isEmpty(), true);
+
+ prepareMemory(activeManager);
+
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ assertEquals(99, activeManager.getTopPoint());
+ activeManager.removeTop();
+ assertEquals(100, activeManager.getTopPoint());
+ activeManager.removeTop();
+ assertEquals(101, activeManager.getTopPoint());
+ activeManager.removeTop();
+
+ prepareMemory(activeManager);
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ activeManager.clear();
+ assertEquals(0, activeManager.getActiveList().size());
+ assertEquals(false, activeManager.hasRecords());
+ assertEquals(true, activeManager.isEmpty());
+ }
+
+ @Test
+ public void testDescendingStartpoint() throws HyracksDataException {
+ ActiveSweepManager activeManager = new ActiveSweepManager(bufferManager, 0, 0,
+ EndPointIndexItem.EndPointDescComparator, EndPointIndexItem.START_POINT);
+
+ assertEquals(activeManager.hasRecords(), false);
+ assertEquals(activeManager.isEmpty(), true);
+
+ prepareMemory(activeManager);
+
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ assertEquals(101, activeManager.getTopPoint());
+ activeManager.removeTop();
+ // Actual 0
+ assertEquals(100, activeManager.getTopPoint());
+ activeManager.removeTop();
+ // Actual 0
+ assertEquals(99, activeManager.getTopPoint());
+ activeManager.removeTop();
+
+ prepareMemory(activeManager);
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ activeManager.clear();
+ assertEquals(0, activeManager.getActiveList().size());
+ assertEquals(false, activeManager.hasRecords());
+ assertEquals(true, activeManager.isEmpty());
+ }
+
+ @Test
+ public void testAscendingEndpoint() throws HyracksDataException {
+ ActiveSweepManager activeManager = new ActiveSweepManager(bufferManager, 0, 0,
+ EndPointIndexItem.EndPointAscComparator, EndPointIndexItem.END_POINT);
+
+ assertEquals(activeManager.hasRecords(), false);
+ assertEquals(activeManager.isEmpty(), true);
+
+ prepareMemory(activeManager);
+
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ assertEquals(299, activeManager.getTopPoint());
+ activeManager.removeTop();
+ assertEquals(300, activeManager.getTopPoint());
+ activeManager.removeTop();
+ assertEquals(301, activeManager.getTopPoint());
+ activeManager.removeTop();
+
+ prepareMemory(activeManager);
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ activeManager.clear();
+ assertEquals(0, activeManager.getActiveList().size());
+ assertEquals(false, activeManager.hasRecords());
+ assertEquals(true, activeManager.isEmpty());
+ }
+
+ @Test
+ public void testDescendingEndpoint() throws HyracksDataException {
+ ActiveSweepManager activeManager = new ActiveSweepManager(bufferManager, 0, 0,
+ EndPointIndexItem.EndPointDescComparator, EndPointIndexItem.END_POINT);
+
+ assertEquals(activeManager.hasRecords(), false);
+ assertEquals(activeManager.isEmpty(), true);
+
+ prepareMemory(activeManager);
+
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ assertEquals(301, activeManager.getTopPoint());
+ activeManager.removeTop();
+ assertEquals(300, activeManager.getTopPoint());
+ activeManager.removeTop();
+ assertEquals(299, activeManager.getTopPoint());
+ activeManager.removeTop();
+
+ prepareMemory(activeManager);
+ assertEquals(3, activeManager.getActiveList().size());
+ assertEquals(true, activeManager.hasRecords());
+ assertEquals(false, activeManager.isEmpty());
+
+ activeManager.clear();
+ assertEquals(0, activeManager.getActiveList().size());
+ assertEquals(false, activeManager.hasRecords());
+ assertEquals(true, activeManager.isEmpty());
+ }
+
+}
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/base/PhysicalOperatorTag.java b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/base/PhysicalOperatorTag.java
index d590f71..0352046 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/base/PhysicalOperatorTag.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/base/PhysicalOperatorTag.java
@@ -41,6 +41,7 @@
INDEX_INSERT_DELETE,
INSERT_DELETE,
INTERVAL_MERGE_JOIN,
+ INTERVAL_TIME_SWEEP_JOIN,
LENGTH_PARTITIONED_INVERTED_INDEX_SEARCH,
MATERIALIZE,
MICRO_PRE_CLUSTERED_GROUP_BY,
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTupleAccessor.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTupleAccessor.java
new file mode 100644
index 0000000..6ec0e09
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTupleAccessor.java
@@ -0,0 +1,194 @@
+/*
+ * 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.hyracks.dataflow.std.buffermanager;
+
+import java.nio.ByteBuffer;
+
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
+import org.apache.hyracks.dataflow.std.structures.TuplePointer;
+
+public abstract class AbstractTupleAccessor implements ITupleAccessor {
+ public static final int UNSET = -2;
+ public static final int INITIALIZED = -1;
+
+ protected int tupleId = UNSET;
+
+ protected int frameId;
+
+ protected abstract IFrameTupleAccessor getInnerAccessor();
+
+ protected abstract void resetInnerAccessor(int frameId);
+
+ protected abstract void resetInnerAccessor(TuplePointer tp);
+
+ protected abstract int getFrameCount();
+
+ @Override
+ public int getTupleStartOffset() {
+ return getTupleStartOffset(tupleId);
+ }
+
+ @Override
+ public int getTupleLength() {
+ return getTupleLength(tupleId);
+ }
+
+ @Override
+ public int getAbsFieldStartOffset(int fieldId) {
+ return getAbsoluteFieldStartOffset(tupleId, fieldId);
+ }
+
+ @Override
+ public int getFieldLength(int fieldId) {
+ return getFieldLength(tupleId, fieldId);
+ }
+
+ @Override
+ public ByteBuffer getBuffer() {
+ return getInnerAccessor().getBuffer();
+ }
+
+ @Override
+ public int getFieldCount() {
+ return getInnerAccessor().getFieldCount();
+ }
+
+ @Override
+ public int getFieldSlotsLength() {
+ return getInnerAccessor().getFieldSlotsLength();
+ }
+
+ @Override
+ public int getFieldEndOffset(int tupleIndex, int fIdx) {
+ return getInnerAccessor().getFieldEndOffset(tupleId, fIdx);
+ }
+
+ @Override
+ public int getFieldStartOffset(int tupleIndex, int fIdx) {
+ return getInnerAccessor().getFieldStartOffset(tupleIndex, fIdx);
+ }
+
+ @Override
+ public int getFieldLength(int tupleIndex, int fIdx) {
+ return getInnerAccessor().getFieldLength(tupleIndex, fIdx);
+ }
+
+ @Override
+ public int getTupleLength(int tupleIndex) {
+ return getInnerAccessor().getTupleLength(tupleIndex);
+ }
+
+ @Override
+ public int getTupleEndOffset(int tupleIndex) {
+ return getInnerAccessor().getTupleEndOffset(tupleIndex);
+ }
+
+ @Override
+ public int getTupleStartOffset(int tupleIndex) {
+ return getInnerAccessor().getTupleStartOffset(tupleIndex);
+ }
+
+ @Override
+ public int getAbsoluteFieldStartOffset(int tupleIndex, int fIdx) {
+ return getInnerAccessor().getAbsoluteFieldStartOffset(tupleIndex, fIdx);
+ }
+
+ @Override
+ public int getTupleCount() {
+ return getInnerAccessor().getTupleCount();
+ }
+
+ @Override
+ public void reset(TuplePointer tuplePointer) {
+ resetInnerAccessor(tuplePointer.getFrameIndex());
+ }
+
+ @Override
+ public void reset(ByteBuffer buffer) {
+ throw new IllegalAccessError("Should never call this reset");
+ }
+
+ @Override
+ public int getTupleEndOffset() {
+ return getInnerAccessor().getTupleEndOffset(tupleId);
+ }
+
+ @Override
+ public int getFieldEndOffset(int fieldId) {
+ return getInnerAccessor().getFieldEndOffset(tupleId, fieldId);
+ }
+
+ @Override
+ public int getFieldStartOffset(int fieldId) {
+ return getInnerAccessor().getFieldStartOffset(tupleId, fieldId);
+ }
+
+ @Override
+ public void getTuplePointer(TuplePointer tp) {
+ tp.reset(frameId, tupleId);
+ }
+
+ @Override
+ public int getTupleId() {
+ return tupleId;
+ }
+
+ @Override
+ public void setTupleId(int tupleId) {
+ this.tupleId = tupleId;
+ }
+
+ @Override
+ public void reset() {
+ tupleId = INITIALIZED;
+ frameId = 0;
+ resetInnerAccessor(frameId);
+ }
+
+ @Override
+ public boolean hasNext() {
+ if (tupleId + 1 < getTupleCount() || frameId + 1 < getFrameCount()) {
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public boolean exists() {
+ return INITIALIZED < tupleId && getTupleEndOffset(tupleId) > 0 && tupleId < getTupleCount()
+ && frameId < getFrameCount();
+ }
+
+ @Override
+ public void next() {
+ // TODO Consider error messages
+ if (tupleId + 1 < getTupleCount()) {
+ ++tupleId;
+ } else if (frameId + 1 < getFrameCount()) {
+ ++frameId;
+ resetInnerAccessor(frameId);
+ tupleId = 0;
+ } else {
+ // Force exists to fail, by incrementing the tuple pointer.
+ ++tupleId;
+ }
+ }
+
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTuplePointerAccessor.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTuplePointerAccessor.java
index 2717d7a..d9da751 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTuplePointerAccessor.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/AbstractTuplePointerAccessor.java
@@ -28,9 +28,9 @@
protected int tid = -1;
- abstract IFrameTupleAccessor getInnerAccessor();
+ protected abstract IFrameTupleAccessor getInnerAccessor();
- abstract void resetInnerAccessor(TuplePointer tuplePointer);
+ protected abstract void resetInnerAccessor(TuplePointer tuplePointer);
@Override
public void reset(TuplePointer tuplePointer) {
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/FrameBufferManager.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/FrameBufferManager.java
index 6a60813..9e932f6 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/FrameBufferManager.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/FrameBufferManager.java
@@ -22,6 +22,7 @@
import java.nio.ByteBuffer;
import java.util.ArrayList;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
import org.apache.hyracks.api.exceptions.HyracksDataException;
/**
@@ -29,6 +30,8 @@
*/
public class FrameBufferManager implements IFrameBufferManager {
+ int size = 0;
+ int iterator = -1;
ArrayList<ByteBuffer> buffers = new ArrayList<>();
@Override
@@ -54,6 +57,38 @@
}
@Override
+ public void removeFrame(int frameIndex) {
+ buffers.set(frameIndex, null);
+ size--;
+ }
+
+ @Override
+ public int next() {
+ while (++iterator < buffers.size()) {
+ if (buffers.get(iterator) != null) {
+ break;
+ }
+ }
+ return iterator;
+ }
+
+ @Override
+ public boolean exists() {
+ return iterator < buffers.size() && buffers.get(iterator) != null;
+ }
+
+ @Override
+ public void resetIterator() {
+ iterator = -1;
+ }
+
+ @Override
+ public ITupleAccessor getTupleAccessor(RecordDescriptor rd) {
+ assert (false);
+ return null;
+ }
+
+ @Override
public void close() {
buffers = null;
}
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IFrameBufferManager.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IFrameBufferManager.java
index 8b73b54..92ab96a 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IFrameBufferManager.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IFrameBufferManager.java
@@ -20,6 +20,7 @@
import java.nio.ByteBuffer;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
import org.apache.hyracks.api.exceptions.HyracksDataException;
/**
@@ -54,6 +55,21 @@
*/
int insertFrame(ByteBuffer frame) throws HyracksDataException;
+ void removeFrame(int frameIndex);
+
+ /**
+ * Create a iterator for frames.
+ *
+ * Allows the reuse of frame ids.
+ */
+ int next();
+
+ boolean exists();
+
+ void resetIterator();
+
+ ITupleAccessor getTupleAccessor(RecordDescriptor rd);
+
/**
* Releases the allocated resources.
*/
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AfterIntervalJoinUtilFactory.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IPartitionedDeletableTupleBufferManager.java
similarity index 62%
rename from asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AfterIntervalJoinUtilFactory.java
rename to hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IPartitionedDeletableTupleBufferManager.java
index 9fe4e9d..52a0918 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/joins/interval/utils/AfterIntervalJoinUtilFactory.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/IPartitionedDeletableTupleBufferManager.java
@@ -16,16 +16,16 @@
* specific language governing permissions and limitations
* under the License.
*/
-package org.apache.asterix.runtime.operators.joins.interval.utils;
-import org.apache.hyracks.api.context.IHyracksTaskContext;
+package org.apache.hyracks.dataflow.std.buffermanager;
-public class AfterIntervalJoinUtilFactory implements IIntervalJoinUtilFactory {
- private static final long serialVersionUID = 1L;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.std.structures.TuplePointer;
- @Override
- public IIntervalJoinUtil createIntervalMergeJoinUtil(int buildKey, int probeKey, IHyracksTaskContext ctx,
- int nPartitions) {
- return new AfterIntervalJoinUtil(buildKey, probeKey);
- }
+public interface IPartitionedDeletableTupleBufferManager extends IPartitionedTupleBufferManager {
+
+ void deleteTuple(int partition, TuplePointer tuplePointer) throws HyracksDataException;
+
+ void printStats(String string);
+
}
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/ITupleAccessor.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/ITupleAccessor.java
new file mode 100644
index 0000000..dbbc9a9
--- /dev/null
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/ITupleAccessor.java
@@ -0,0 +1,70 @@
+/*
+ * 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.hyracks.dataflow.std.buffermanager;
+
+import java.nio.ByteBuffer;
+
+import org.apache.hyracks.api.comm.IFrameTupleAccessor;
+import org.apache.hyracks.dataflow.std.structures.TuplePointer;
+
+// TODO determine correct interface.
+public interface ITupleAccessor extends IFrameTupleAccessor {
+ int getTupleStartOffset();
+
+ int getTupleEndOffset();
+
+ int getTupleLength();
+
+ int getAbsFieldStartOffset(int fieldId);
+
+ int getFieldLength(int fieldId);
+
+ @Override
+ int getFieldCount();
+
+ @Override
+ int getFieldSlotsLength();
+
+ int getFieldEndOffset(int fieldId);
+
+ int getFieldStartOffset(int fieldId);
+
+ void reset(TuplePointer tuplePointer);
+
+ @Override
+ void reset(ByteBuffer buffer);
+
+ int getTupleId();
+
+ void setTupleId(int tupleId);
+
+ void getTuplePointer(TuplePointer tp);
+
+ /**
+ * Only reset the iterator.
+ */
+ void reset();
+
+ boolean hasNext();
+
+ void next();
+
+ boolean exists();
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/TupleInFrameListAccessor.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/TupleInFrameListAccessor.java
index aadcb26..d50a54c 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/TupleInFrameListAccessor.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/TupleInFrameListAccessor.java
@@ -41,12 +41,12 @@
}
@Override
- IFrameTupleAccessor getInnerAccessor() {
+ protected IFrameTupleAccessor getInnerAccessor() {
return bufferAccessor;
}
@Override
- void resetInnerAccessor(TuplePointer tuplePointer) {
+ protected void resetInnerAccessor(TuplePointer tuplePointer) {
bufferAccessor.reset(bufferFrames.get(tuplePointer.getFrameIndex()));
}
}
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VPartitionTupleBufferManager.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VPartitionTupleBufferManager.java
index d3d06cb..3a267f8 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VPartitionTupleBufferManager.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VPartitionTupleBufferManager.java
@@ -45,12 +45,12 @@
}
};
- private IDeallocatableFramePool framePool;
- private IFrameBufferManager[] partitionArray;
- private int[] numTuples;
+ protected IDeallocatableFramePool framePool;
+ protected IFrameBufferManager[] partitionArray;
+ protected int[] numTuples;
private final FixedSizeFrame appendFrame;
private final FixedSizeFrameTupleAppender appender;
- private BufferInfo tempInfo;
+ protected BufferInfo tempInfo;
private IPartitionedMemoryConstrain constrain;
// In case where a frame pool is shared by one or more buffer manager(s), it can be provided from the caller.
@@ -177,20 +177,21 @@
return FrameHelper.calcRequiredSpace(0, size);
}
- private int makeGroupFrameId(int partition, int fid) {
+ protected int makeGroupFrameId(int partition, int fid) {
return fid * getNumPartitions() + partition;
}
- private int parsePartitionId(int externalFrameId) {
+ protected int parsePartitionId(int externalFrameId) {
return externalFrameId % getNumPartitions();
}
- private int parseFrameIdInPartition(int externalFrameId) {
+ protected int parseFrameIdInPartition(int externalFrameId) {
return externalFrameId / getNumPartitions();
}
- private int createNewBuffer(int partition, int size) throws HyracksDataException {
+ protected int createNewBuffer(int partition, int size) throws HyracksDataException {
ByteBuffer newBuffer = requestNewBufferFromPool(size, partition);
+
if (newBuffer == null) {
return -1;
}
@@ -267,12 +268,12 @@
FrameTupleAccessor innerAccessor = new FrameTupleAccessor(recordDescriptor);
@Override
- IFrameTupleAccessor getInnerAccessor() {
+ protected IFrameTupleAccessor getInnerAccessor() {
return innerAccessor;
}
@Override
- void resetInnerAccessor(TuplePointer tuplePointer) {
+ protected void resetInnerAccessor(TuplePointer tuplePointer) {
partitionArray[parsePartitionId(tuplePointer.getFrameIndex())]
.getFrame(parseFrameIdInPartition(tuplePointer.getFrameIndex()), tempInfo);
innerAccessor.reset(tempInfo.getBuffer(), tempInfo.getStartOffset(), tempInfo.getLength());
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableDeletableTupleMemoryManager.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableDeletableTupleMemoryManager.java
index b053cac..a2788ad 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableDeletableTupleMemoryManager.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableDeletableTupleMemoryManager.java
@@ -174,12 +174,12 @@
new DeletableFrameTupleAppender(recordDescriptor);
@Override
- IFrameTupleAccessor getInnerAccessor() {
+ protected IFrameTupleAccessor getInnerAccessor() {
return bufferAccessor;
}
@Override
- void resetInnerAccessor(TuplePointer tuplePointer) {
+ protected void resetInnerAccessor(TuplePointer tuplePointer) {
bufferAccessor.reset(frames.get(tuplePointer.getFrameIndex()));
}
};
diff --git a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableFrameMemoryManager.java b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableFrameMemoryManager.java
index 50db2ec..7e368b1 100644
--- a/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableFrameMemoryManager.java
+++ b/hyracks-fullstack/hyracks/hyracks-dataflow-std/src/main/java/org/apache/hyracks/dataflow/std/buffermanager/VariableFrameMemoryManager.java
@@ -24,6 +24,7 @@
import java.util.List;
import org.apache.hyracks.api.comm.FrameHelper;
+import org.apache.hyracks.api.dataflow.value.RecordDescriptor;
import org.apache.hyracks.api.exceptions.HyracksDataException;
import org.apache.hyracks.util.IntSerDeUtils;
@@ -122,6 +123,31 @@
}
@Override
+ public void removeFrame(int frameIndex) {
+
+ }
+
+ @Override
+ public int next() {
+ return 0;
+ }
+
+ @Override
+ public boolean exists() {
+ return false;
+ }
+
+ @Override
+ public void resetIterator() {
+
+ }
+
+ @Override
+ public ITupleAccessor getTupleAccessor(RecordDescriptor rd) {
+ return null;
+ }
+
+ @Override
public void close() {
numPhysicalFrames = 0;
numLogicalFrames = 0;
--
To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/11364
To unsubscribe, or for help writing mail filters, visit https://asterix-gerrit.ics.uci.edu/settings
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Change-Id: Ia61c5c7d950c672e582bb1b7f32bfc389c0442d3
Gerrit-Change-Number: 11364
Gerrit-PatchSet: 1
Gerrit-Owner: Caleb Herbel
Gerrit-MessageType: newchange