You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@asterixdb.apache.org by il...@apache.org on 2015/12/05 01:50:18 UTC
[5/8] incubator-asterixdb-hyracks git commit: Checkpointing: more or
less stable version
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/util/LSMBTreeUtils.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/util/LSMBTreeUtils.java b/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/util/LSMBTreeUtils.java
index 0087d95..b0fae8b 100644
--- a/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/util/LSMBTreeUtils.java
+++ b/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/util/LSMBTreeUtils.java
@@ -29,12 +29,11 @@ import org.apache.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrameFactory;
import org.apache.hyracks.storage.am.btree.frames.BTreeNSMLeafFrameFactory;
import org.apache.hyracks.storage.am.btree.impls.BTree;
import org.apache.hyracks.storage.am.common.api.IFreePageManagerFactory;
-import org.apache.hyracks.storage.am.common.api.IPrimitiveIntegerValueProviderFactory;
+import org.apache.hyracks.storage.am.common.api.IOrdinalPrimitiveValueProviderFactory;
import org.apache.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
import org.apache.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
import org.apache.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
import org.apache.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
-import org.apache.hyracks.storage.am.common.statistics.StatisticsFactory;
import org.apache.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
import org.apache.hyracks.storage.am.lsm.btree.impls.ExternalBTree;
import org.apache.hyracks.storage.am.lsm.btree.impls.ExternalBTreeWithBuddy;
@@ -55,6 +54,7 @@ import org.apache.hyracks.storage.am.lsm.common.impls.BTreeFactory;
import org.apache.hyracks.storage.am.lsm.common.impls.LSMComponentFilterFactory;
import org.apache.hyracks.storage.am.lsm.common.impls.LSMComponentFilterManager;
import org.apache.hyracks.storage.am.lsm.common.impls.TreeIndexFactory;
+import org.apache.hyracks.storage.am.statistics.common.StatisticsFactory;
import org.apache.hyracks.storage.common.buffercache.IBufferCache;
import org.apache.hyracks.storage.common.file.IFileMapProvider;
@@ -65,7 +65,7 @@ public class LSMBTreeUtils {
ILSMMergePolicy mergePolicy, ILSMOperationTracker opTracker, ILSMIOOperationScheduler ioScheduler,
ILSMIOOperationCallback ioOpCallback, boolean needKeyDupCheck, ITypeTraits[] filterTypeTraits,
IBinaryComparatorFactory[] filterCmpFactories, int[] btreeFields, int[] filterFields, boolean durable,
- boolean collectStatistics, IPrimitiveIntegerValueProviderFactory statsValueProviderFactory) {
+ boolean collectStatistics, IOrdinalPrimitiveValueProviderFactory statsFieldProviderFactory) {
LSMBTreeTupleWriterFactory insertTupleWriterFactory = new LSMBTreeTupleWriterFactory(typeTraits,
cmpFactories.length, false);
LSMBTreeTupleWriterFactory deleteTupleWriterFactory = new LSMBTreeTupleWriterFactory(typeTraits,
@@ -103,7 +103,7 @@ public class LSMBTreeUtils {
StatisticsFactory statisticsFactory = null;
if (collectStatistics)
statisticsFactory = new StatisticsFactory(diskBufferCache, diskFileMapProvider, bloomFilterKeyFields,
- statsValueProviderFactory);
+ typeTraits, statsFieldProviderFactory.createOrdinalPrimitiveValueProvider());
ILSMIndexFileManager fileNameManager = new LSMBTreeFileManager(diskFileMapProvider, file, diskBTreeFactory);
@@ -120,7 +120,7 @@ public class LSMBTreeUtils {
int[] bloomFilterKeyFields, double bloomFilterFalsePositiveRate, ILSMMergePolicy mergePolicy,
ILSMOperationTracker opTracker, ILSMIOOperationScheduler ioScheduler, ILSMIOOperationCallback ioOpCallback,
int startWithVersion, boolean durable, boolean collectStatistics,
- IPrimitiveIntegerValueProviderFactory statsValueProviderFactory) {
+ IOrdinalPrimitiveValueProviderFactory statsKeyValueProviderFactory) {
LSMBTreeTupleWriterFactory insertTupleWriterFactory = new LSMBTreeTupleWriterFactory(typeTraits,
cmpFactories.length, false);
LSMBTreeTupleWriterFactory deleteTupleWriterFactory = new LSMBTreeTupleWriterFactory(typeTraits,
@@ -159,7 +159,7 @@ public class LSMBTreeUtils {
StatisticsFactory statisticsFactory = null;
if (collectStatistics)
statisticsFactory = new StatisticsFactory(diskBufferCache, diskFileMapProvider, bloomFilterKeyFields,
- statsValueProviderFactory);
+ typeTraits, statsKeyValueProviderFactory.createOrdinalPrimitiveValueProvider());
// the disk only index uses an empty ArrayList for virtual buffer caches
ExternalBTree lsmTree = new ExternalBTree(interiorFrameFactory, insertLeafFrameFactory, deleteLeafFrameFactory,
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/BytePrimitiveIntegerValueProviderFactory.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/BytePrimitiveIntegerValueProviderFactory.java b/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/BytePrimitiveIntegerValueProviderFactory.java
deleted file mode 100644
index f04c5c2..0000000
--- a/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/BytePrimitiveIntegerValueProviderFactory.java
+++ /dev/null
@@ -1,57 +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.hyracks.storage.am.lsm.common.impls;
-
-import org.apache.hyracks.data.std.primitive.BytePointable;
-import org.apache.hyracks.storage.am.common.api.IPrimitiveIntegerValueProvider;
-import org.apache.hyracks.storage.am.common.api.IPrimitiveIntegerValueProviderFactory;
-
-public class BytePrimitiveIntegerValueProviderFactory implements IPrimitiveIntegerValueProviderFactory {
- private static final long serialVersionUID = 1L;
-
- public static final BytePrimitiveIntegerValueProviderFactory INSTANCE = new BytePrimitiveIntegerValueProviderFactory();
-
- private BytePrimitiveIntegerValueProviderFactory() {
- }
-
- @Override
- public IPrimitiveIntegerValueProvider createPrimitiveIntegerValueProvider() {
- return new IPrimitiveIntegerValueProvider() {
- @Override
- public long getValue(byte[] bytes, int offset) {
- return BytePointable.getByte(bytes, offset);
- }
-
- @Override
- public long minDomainValue(byte[] bytes, int offset) {
- return Byte.MIN_VALUE;
- }
-
- @Override
- public long maxDomainValue(byte[] bytes, int offset) {
- return Byte.MAX_VALUE;
- }
-
- @Override
- public int maxLevel(byte[] bytes, int offset) {
- return Byte.SIZE;
- }
- };
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/IntegerPrimitiveIntegerValueProviderFactory.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/IntegerPrimitiveIntegerValueProviderFactory.java b/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/IntegerPrimitiveIntegerValueProviderFactory.java
deleted file mode 100644
index ab57ce2..0000000
--- a/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/IntegerPrimitiveIntegerValueProviderFactory.java
+++ /dev/null
@@ -1,57 +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.hyracks.storage.am.lsm.common.impls;
-
-import org.apache.hyracks.data.std.primitive.IntegerPointable;
-import org.apache.hyracks.storage.am.common.api.IPrimitiveIntegerValueProvider;
-import org.apache.hyracks.storage.am.common.api.IPrimitiveIntegerValueProviderFactory;
-
-public class IntegerPrimitiveIntegerValueProviderFactory implements IPrimitiveIntegerValueProviderFactory {
- private static final long serialVersionUID = 1L;
-
- public static final IntegerPrimitiveIntegerValueProviderFactory INSTANCE = new IntegerPrimitiveIntegerValueProviderFactory();
-
- private IntegerPrimitiveIntegerValueProviderFactory() {
- }
-
- @Override
- public IPrimitiveIntegerValueProvider createPrimitiveIntegerValueProvider() {
- return new IPrimitiveIntegerValueProvider() {
- @Override
- public long getValue(byte[] bytes, int offset) {
- return IntegerPointable.getInteger(bytes, offset);
- }
-
- @Override
- public long minDomainValue(byte[] bytes, int offset) {
- return Integer.MIN_VALUE;
- }
-
- @Override
- public long maxDomainValue(byte[] bytes, int offset) {
- return Integer.MAX_VALUE;
- }
-
- @Override
- public int maxLevel(byte[] bytes, int offset) {
- return Integer.SIZE;
- }
- };
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/LongPrimitiveIntegerValueProviderFactory.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/LongPrimitiveIntegerValueProviderFactory.java b/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/LongPrimitiveIntegerValueProviderFactory.java
deleted file mode 100644
index b82d464..0000000
--- a/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/LongPrimitiveIntegerValueProviderFactory.java
+++ /dev/null
@@ -1,57 +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.hyracks.storage.am.lsm.common.impls;
-
-import org.apache.hyracks.data.std.primitive.LongPointable;
-import org.apache.hyracks.storage.am.common.api.IPrimitiveIntegerValueProvider;
-import org.apache.hyracks.storage.am.common.api.IPrimitiveIntegerValueProviderFactory;
-
-public class LongPrimitiveIntegerValueProviderFactory implements IPrimitiveIntegerValueProviderFactory {
- private static final long serialVersionUID = 1L;
-
- public static final LongPrimitiveIntegerValueProviderFactory INSTANCE = new LongPrimitiveIntegerValueProviderFactory();
-
- private LongPrimitiveIntegerValueProviderFactory() {
- }
-
- @Override
- public IPrimitiveIntegerValueProvider createPrimitiveIntegerValueProvider() {
- return new IPrimitiveIntegerValueProvider() {
- @Override
- public long getValue(byte[] bytes, int offset) {
- return LongPointable.getLong(bytes, offset);
- }
-
- @Override
- public long minDomainValue(byte[] bytes, int offset) {
- return Long.MIN_VALUE;
- }
-
- @Override
- public long maxDomainValue(byte[] bytes, int offset) {
- return Long.MAX_VALUE;
- }
-
- @Override
- public int maxLevel(byte[] bytes, int offset) {
- return Long.SIZE;
- }
- };
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/ShortPrimitiveIntegerValueProviderFactory.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/ShortPrimitiveIntegerValueProviderFactory.java b/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/ShortPrimitiveIntegerValueProviderFactory.java
deleted file mode 100644
index 35ba601..0000000
--- a/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/ShortPrimitiveIntegerValueProviderFactory.java
+++ /dev/null
@@ -1,57 +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.hyracks.storage.am.lsm.common.impls;
-
-import org.apache.hyracks.data.std.primitive.ShortPointable;
-import org.apache.hyracks.storage.am.common.api.IPrimitiveIntegerValueProvider;
-import org.apache.hyracks.storage.am.common.api.IPrimitiveIntegerValueProviderFactory;
-
-public class ShortPrimitiveIntegerValueProviderFactory implements IPrimitiveIntegerValueProviderFactory {
- private static final long serialVersionUID = 1L;
-
- public static final ShortPrimitiveIntegerValueProviderFactory INSTANCE = new ShortPrimitiveIntegerValueProviderFactory();
-
- private ShortPrimitiveIntegerValueProviderFactory() {
- }
-
- @Override
- public IPrimitiveIntegerValueProvider createPrimitiveIntegerValueProvider() {
- return new IPrimitiveIntegerValueProvider() {
- @Override
- public long getValue(byte[] bytes, int offset) {
- return ShortPointable.getShort(bytes, offset);
- }
-
- @Override
- public long minDomainValue(byte[] bytes, int offset) {
- return Short.MIN_VALUE;
- }
-
- @Override
- public long maxDomainValue(byte[] bytes, int offset) {
- return Short.MAX_VALUE;
- }
-
- @Override
- public int maxLevel(byte[] bytes, int offset) {
- return Short.SIZE;
- }
- };
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/BytePrimitiveValueProviderFactory.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/BytePrimitiveValueProviderFactory.java b/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/BytePrimitiveValueProviderFactory.java
new file mode 100644
index 0000000..3af577e
--- /dev/null
+++ b/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/BytePrimitiveValueProviderFactory.java
@@ -0,0 +1,55 @@
+/*
+ * 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.storage.am.rtree.impls;
+
+import org.apache.hyracks.data.std.primitive.BytePointable;
+import org.apache.hyracks.storage.am.common.api.IOrdinalPrimitiveValueProvider;
+import org.apache.hyracks.storage.am.common.api.IOrdinalPrimitiveValueProviderFactory;
+import org.apache.hyracks.storage.am.common.api.IPrimitiveValueProvider;
+import org.apache.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+
+public class BytePrimitiveValueProviderFactory
+ implements IPrimitiveValueProviderFactory, IOrdinalPrimitiveValueProviderFactory {
+ private static final long serialVersionUID = 1L;
+
+ public static final BytePrimitiveValueProviderFactory INSTANCE = new BytePrimitiveValueProviderFactory();
+
+ private BytePrimitiveValueProviderFactory() {
+ }
+
+ @Override
+ public IPrimitiveValueProvider createPrimitiveValueProvider() {
+ return new IPrimitiveValueProvider() {
+ @Override
+ public double getValue(byte[] bytes, int offset) {
+ return BytePointable.getByte(bytes, offset);
+ }
+ };
+ }
+
+ @Override
+ public IOrdinalPrimitiveValueProvider createOrdinalPrimitiveValueProvider() {
+ return new IOrdinalPrimitiveValueProvider() {
+ @Override
+ public long getOrdinalValue(byte[] bytes, int offset) {
+ return BytePointable.getByte(bytes, offset);
+ }
+ };
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/IntegerPrimitiveValueProviderFactory.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/IntegerPrimitiveValueProviderFactory.java b/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/IntegerPrimitiveValueProviderFactory.java
index 13eddd4..017424e 100644
--- a/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/IntegerPrimitiveValueProviderFactory.java
+++ b/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/IntegerPrimitiveValueProviderFactory.java
@@ -19,10 +19,13 @@
package org.apache.hyracks.storage.am.rtree.impls;
import org.apache.hyracks.data.std.primitive.IntegerPointable;
+import org.apache.hyracks.storage.am.common.api.IOrdinalPrimitiveValueProvider;
+import org.apache.hyracks.storage.am.common.api.IOrdinalPrimitiveValueProviderFactory;
import org.apache.hyracks.storage.am.common.api.IPrimitiveValueProvider;
import org.apache.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
-public class IntegerPrimitiveValueProviderFactory implements IPrimitiveValueProviderFactory {
+public class IntegerPrimitiveValueProviderFactory
+ implements IPrimitiveValueProviderFactory, IOrdinalPrimitiveValueProviderFactory {
private static final long serialVersionUID = 1L;
public static final IntegerPrimitiveValueProviderFactory INSTANCE = new IntegerPrimitiveValueProviderFactory();
@@ -39,4 +42,14 @@ public class IntegerPrimitiveValueProviderFactory implements IPrimitiveValueProv
}
};
}
+
+ @Override
+ public IOrdinalPrimitiveValueProvider createOrdinalPrimitiveValueProvider() {
+ return new IOrdinalPrimitiveValueProvider() {
+ @Override
+ public long getOrdinalValue(byte[] bytes, int offset) {
+ return IntegerPointable.getInteger(bytes, offset);
+ }
+ };
+ }
}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/LongPrimitiveValueProviderFactory.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/LongPrimitiveValueProviderFactory.java b/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/LongPrimitiveValueProviderFactory.java
new file mode 100644
index 0000000..81fcc34
--- /dev/null
+++ b/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/LongPrimitiveValueProviderFactory.java
@@ -0,0 +1,55 @@
+/*
+ * 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.storage.am.rtree.impls;
+
+import org.apache.hyracks.data.std.primitive.LongPointable;
+import org.apache.hyracks.storage.am.common.api.IOrdinalPrimitiveValueProvider;
+import org.apache.hyracks.storage.am.common.api.IOrdinalPrimitiveValueProviderFactory;
+import org.apache.hyracks.storage.am.common.api.IPrimitiveValueProvider;
+import org.apache.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+
+public class LongPrimitiveValueProviderFactory
+ implements IPrimitiveValueProviderFactory, IOrdinalPrimitiveValueProviderFactory {
+ private static final long serialVersionUID = 1L;
+
+ public static final LongPrimitiveValueProviderFactory INSTANCE = new LongPrimitiveValueProviderFactory();
+
+ private LongPrimitiveValueProviderFactory() {
+ }
+
+ @Override
+ public IPrimitiveValueProvider createPrimitiveValueProvider() {
+ return new IPrimitiveValueProvider() {
+ @Override
+ public double getValue(byte[] bytes, int offset) {
+ return LongPointable.getLong(bytes, offset);
+ }
+ };
+ }
+
+ @Override
+ public IOrdinalPrimitiveValueProvider createOrdinalPrimitiveValueProvider() {
+ return new IOrdinalPrimitiveValueProvider() {
+ @Override
+ public long getOrdinalValue(byte[] bytes, int offset) {
+ return LongPointable.getLong(bytes, offset);
+ }
+ };
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/ShortPrimitiveValueProviderFactory.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/ShortPrimitiveValueProviderFactory.java b/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/ShortPrimitiveValueProviderFactory.java
new file mode 100644
index 0000000..eed1661
--- /dev/null
+++ b/hyracks/hyracks-storage-am-rtree/src/main/java/org/apache/hyracks/storage/am/rtree/impls/ShortPrimitiveValueProviderFactory.java
@@ -0,0 +1,55 @@
+/*
+ * 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.storage.am.rtree.impls;
+
+import org.apache.hyracks.data.std.primitive.ShortPointable;
+import org.apache.hyracks.storage.am.common.api.IOrdinalPrimitiveValueProvider;
+import org.apache.hyracks.storage.am.common.api.IOrdinalPrimitiveValueProviderFactory;
+import org.apache.hyracks.storage.am.common.api.IPrimitiveValueProvider;
+import org.apache.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+
+public class ShortPrimitiveValueProviderFactory
+ implements IPrimitiveValueProviderFactory, IOrdinalPrimitiveValueProviderFactory {
+ private static final long serialVersionUID = 1L;
+
+ public static final ShortPrimitiveValueProviderFactory INSTANCE = new ShortPrimitiveValueProviderFactory();
+
+ private ShortPrimitiveValueProviderFactory() {
+ }
+
+ @Override
+ public IPrimitiveValueProvider createPrimitiveValueProvider() {
+ return new IPrimitiveValueProvider() {
+ @Override
+ public double getValue(byte[] bytes, int offset) {
+ return ShortPointable.getShort(bytes, offset);
+ }
+ };
+ }
+
+ @Override
+ public IOrdinalPrimitiveValueProvider createOrdinalPrimitiveValueProvider() {
+ return new IOrdinalPrimitiveValueProvider() {
+ @Override
+ public long getOrdinalValue(byte[] bytes, int offset) {
+ return ShortPointable.getShort(bytes, offset);
+ }
+ };
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-statistics/pom.xml
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-statistics/pom.xml b/hyracks/hyracks-storage-am-statistics/pom.xml
new file mode 100644
index 0000000..4df9e0a
--- /dev/null
+++ b/hyracks/hyracks-storage-am-statistics/pom.xml
@@ -0,0 +1,32 @@
+<project
+ xmlns="http://maven.apache.org/POM/4.0.0"
+ xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+ xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <artifactId>hyracks-storage-am-statistics</artifactId>
+
+ <parent>
+ <groupId>org.apache.hyracks</groupId>
+ <artifactId>hyracks</artifactId>
+ <version>0.2.17-SNAPSHOT</version>
+ </parent>
+
+ <licenses>
+ <license>
+ <name>Apache License, Version 2.0</name>
+ <url>http://www.apache.org/licenses/LICENSE-2.0.txt</url>
+ <distribution>repo</distribution>
+ <comments>A business-friendly OSS license</comments>
+ </license>
+ </licenses>
+
+ <dependencies>
+ <dependency>
+ <groupId>org.apache.hyracks</groupId>
+ <artifactId>hyracks-storage-am-common</artifactId>
+ <version>0.2.17-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ </dependencies>
+</project>
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/common/StatisticsFactory.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/common/StatisticsFactory.java b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/common/StatisticsFactory.java
new file mode 100644
index 0000000..84e7829
--- /dev/null
+++ b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/common/StatisticsFactory.java
@@ -0,0 +1,31 @@
+package org.apache.hyracks.storage.am.statistics.common;
+
+import org.apache.hyracks.api.dataflow.value.ITypeTraits;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.api.io.FileReference;
+import org.apache.hyracks.storage.am.common.api.IOrdinalPrimitiveValueProvider;
+import org.apache.hyracks.storage.am.statistics.wavelet.WaveletSynopsis;
+import org.apache.hyracks.storage.common.buffercache.IBufferCache;
+import org.apache.hyracks.storage.common.file.IFileMapProvider;
+
+public class StatisticsFactory {
+ private final IBufferCache bufferCache;
+ private final IFileMapProvider fileMapProvider;
+ private final int[] statsFields;
+ private final ITypeTraits[] statsFieldTypeTraits;
+ private final IOrdinalPrimitiveValueProvider statsFieldValueProvider;
+
+ public StatisticsFactory(IBufferCache bufferCache, IFileMapProvider fileMapProvider, int[] statsFields,
+ ITypeTraits[] statsFieldTypeTraits, IOrdinalPrimitiveValueProvider statsFieldValueProvider) {
+ this.bufferCache = bufferCache;
+ this.fileMapProvider = fileMapProvider;
+ this.statsFields = statsFields;
+ this.statsFieldTypeTraits = statsFieldTypeTraits;
+ this.statsFieldValueProvider = statsFieldValueProvider;
+ }
+
+ public WaveletSynopsis createWaveletStatistics(FileReference file) throws HyracksDataException {
+ return new WaveletSynopsis(bufferCache, fileMapProvider, file, statsFields, 10, statsFieldTypeTraits,
+ statsFieldValueProvider);
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/common/Synopsis.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/common/Synopsis.java b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/common/Synopsis.java
new file mode 100644
index 0000000..64ae309
--- /dev/null
+++ b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/common/Synopsis.java
@@ -0,0 +1,22 @@
+package org.apache.hyracks.storage.am.statistics.common;
+
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.api.io.FileReference;
+import org.apache.hyracks.storage.am.common.api.IIndexBulkLoader;
+import org.apache.hyracks.storage.am.common.impls.AbstractFileManager;
+import org.apache.hyracks.storage.common.buffercache.IBufferCache;
+import org.apache.hyracks.storage.common.file.IFileMapProvider;
+
+public abstract class Synopsis extends AbstractFileManager {
+
+ public Synopsis(IBufferCache bufferCache, IFileMapProvider fileMapProvider, FileReference file) {
+ super(bufferCache, fileMapProvider, file);
+ }
+
+ public abstract void addElement(long key, double frequency);
+
+ public abstract IIndexBulkLoader createBuilder() throws HyracksDataException;
+
+ public abstract int getNumPages() throws HyracksDataException;
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/common/SynopsisType.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/common/SynopsisType.java b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/common/SynopsisType.java
new file mode 100644
index 0000000..045b398
--- /dev/null
+++ b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/common/SynopsisType.java
@@ -0,0 +1,7 @@
+package org.apache.hyracks.storage.am.statistics.common;
+
+public enum SynopsisType {
+ None,
+ Wavelet,
+ Sketch
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/common/TypeTraitsDomainUtils.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/common/TypeTraitsDomainUtils.java b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/common/TypeTraitsDomainUtils.java
new file mode 100644
index 0000000..d5e82f0
--- /dev/null
+++ b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/common/TypeTraitsDomainUtils.java
@@ -0,0 +1,26 @@
+package org.apache.hyracks.storage.am.statistics.common;
+
+import org.apache.hyracks.api.dataflow.value.ITypeTraits;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+
+// Class methods obtain numeric domain bounds by considering appropriate ITypeTraits assuming that numeric domain is signed
+public class TypeTraitsDomainUtils {
+
+ public static long minDomainValue(ITypeTraits typeTraits) throws HyracksDataException {
+ return ~maxDomainValue(typeTraits);
+ }
+
+ public static long maxDomainValue(ITypeTraits typeTraits) throws HyracksDataException {
+ if (!typeTraits.isFixedLength())
+ throw new HyracksDataException("Cannot calculate domain for variable size type");
+ // subtract 1 from fixedLength assuming that 1 byte is reserved for type tag
+ return (1l << (((typeTraits.getFixedLength() - 1) * 8) - 1)) - 1;
+ }
+
+ public static int maxLevel(ITypeTraits typeTraits) throws HyracksDataException {
+ if (!typeTraits.isFixedLength())
+ throw new HyracksDataException("Cannot calculate domain for variable size type");
+ // subtract 1 from fixedLength assuming that 1 byte is reserved for type tag
+ return ((typeTraits.getFixedLength() - 1) * 8);
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/GroupCountSketch.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/GroupCountSketch.java b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/GroupCountSketch.java
new file mode 100644
index 0000000..0fdeab3
--- /dev/null
+++ b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/GroupCountSketch.java
@@ -0,0 +1,90 @@
+package org.apache.hyracks.storage.am.statistics.sketch;
+
+public class GroupCountSketch extends Sketch {
+
+ private final int levels;
+ private final int depth;
+ private final int buckets;
+ private final int subbuckets;
+ private final int fanoutLog;
+ private final double counters[][][][];
+ private final long[][] hashSeeds;
+
+ public GroupCountSketch(int levels, int depth, int width, int fanoutLog/*double prob, double accuracy*/) {
+ this.levels = levels;
+ this.depth = depth;
+ this.buckets = width;
+ this.fanoutLog = fanoutLog;
+ this.subbuckets = width * width;
+
+ counters = new double[this.levels][this.depth][this.buckets][this.subbuckets];
+ hashSeeds = new long[this.depth][8];
+ initSeeds(this.depth, 8, hashSeeds);
+ }
+
+ public void update(long item, double diff) {
+ int i, j, h, f, mult;
+ long group;
+
+ for (i = 0; i < depth; i++) {
+ mult = HashGenerator.fourwise(this.hashSeeds[i][4], this.hashSeeds[i][5], this.hashSeeds[i][6],
+ this.hashSeeds[i][7], item);
+
+ f = HashGenerator.hash31(this.hashSeeds[i][2], this.hashSeeds[i][3], item);
+ f = f % (this.subbuckets);
+
+ for (j = 0, group = item; j < levels; j++, group >>= fanoutLog) {
+
+ h = HashGenerator.hash31(this.hashSeeds[i][0], this.hashSeeds[i][1], group);
+ h = h % (this.buckets);
+
+ if ((mult & 1) == 1)
+ this.counters[j][i][h][f] += diff;
+ else
+ this.counters[j][i][h][f] -= diff;
+ }
+ }
+ }
+
+ public double count(int group, int level) {
+ int h, f, mult;
+ double[] estimates = new double[depth];
+
+ for (int i = 0; i < depth; i++) {
+ h = HashGenerator.hash31(this.hashSeeds[i][0], this.hashSeeds[i][1], group);
+ h = h % (this.buckets);
+
+ f = HashGenerator.hash31(this.hashSeeds[i][2], this.hashSeeds[i][3], group);
+ f = f % (this.subbuckets);
+
+ mult = HashGenerator.fourwise(this.hashSeeds[i][4], this.hashSeeds[i][5], this.hashSeeds[i][6],
+ this.hashSeeds[i][7], group);
+ if ((mult & 1) == 1)
+ estimates[i] += this.counters[level][i][h][f];
+ else
+ estimates[i] -= this.counters[level][i][h][f];
+ }
+
+ return getMedian(estimates, depth);
+ }
+
+ public double energyEst(int group, int level) {
+ // estimate the F2 moment of the vector (sum of squares)
+
+ int i, j;
+ double z;
+
+ double estimates[] = new double[depth];
+ for (i = 0; i < depth; i++) {
+ int h = HashGenerator.hash31(this.hashSeeds[i][0], this.hashSeeds[i][1], group);
+ h = h % (this.buckets);
+ z = 0;
+ for (j = 0; j < this.subbuckets; j++) {
+ z += Math.pow(this.counters[level][i][h][j], 2.0);
+ }
+ estimates[i] = z;
+ }
+
+ return getMedian(estimates, depth);
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/HashGenerator.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/HashGenerator.java b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/HashGenerator.java
new file mode 100644
index 0000000..9ad1caa
--- /dev/null
+++ b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/HashGenerator.java
@@ -0,0 +1,33 @@
+package org.apache.hyracks.storage.am.statistics.sketch;
+
+public class HashGenerator {
+
+ private static int MOD = 2147483647;
+ private static int HL = 31;
+
+ public static int hash31(long a, long b, long x) {
+
+ long result;
+
+ // return a hash of x using a and b mod (2^31 - 1)
+ // may need to do another mod afterwards, or drop high bits
+ // depending on d, number of bad guys
+ // 2^31 - 1 = 2147483647
+
+ // result = ((long long) a)*((long long) x)+((long long) b);
+ result = (a * x) + b;
+ result = ((result >> HL) + result) & MOD;
+
+ return (int) result;
+ }
+
+ public static int fourwise(long a, long b, long c, long d, long x) {
+ int result;
+
+ // returns values that are 4-wise independent by repeated calls
+ // to the pairwise independent routine.
+
+ result = hash31(hash31(hash31(x, a, b), x, c), x, d);
+ return result;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/QuickSelect.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/QuickSelect.java b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/QuickSelect.java
new file mode 100644
index 0000000..80c461d
--- /dev/null
+++ b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/QuickSelect.java
@@ -0,0 +1,47 @@
+package org.apache.hyracks.storage.am.statistics.sketch;
+
+import java.util.Random;
+
+public class QuickSelect {
+
+ private static Random rand = new Random();
+
+ private static int partition(double[] arr, int left, int right, int pivot) {
+ double pivotVal = arr[pivot];
+ swap(arr, pivot, right);
+ int storeIndex = left;
+ for (int i = left; i < right; i++) {
+ if (arr[i] < pivotVal) {
+ swap(arr, i, storeIndex);
+ storeIndex++;
+ }
+ }
+ swap(arr, right, storeIndex);
+ return storeIndex;
+ }
+
+ public static double select(double[] arr, int n) {
+ int left = 0;
+ int right = arr.length - 1;
+ while (right >= left) {
+ int pivotIndex = partition(arr, left, right, rand.nextInt(right - left + 1) + left);
+ if (pivotIndex == n) {
+ return arr[pivotIndex];
+ } else if (pivotIndex < n) {
+ left = pivotIndex + 1;
+ } else {
+ right = pivotIndex - 1;
+ }
+ }
+ return 0;
+ }
+
+ private static void swap(double[] arr, int i1, int i2) {
+ if (i1 != i2) {
+ double temp = arr[i1];
+ arr[i1] = arr[i2];
+ arr[i2] = temp;
+ }
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/Sketch.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/Sketch.java b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/Sketch.java
new file mode 100644
index 0000000..65cc731
--- /dev/null
+++ b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/Sketch.java
@@ -0,0 +1,24 @@
+package org.apache.hyracks.storage.am.statistics.sketch;
+
+import java.util.Random;
+
+public abstract class Sketch {
+
+ protected void initSeeds(int k, int m, long[][] hashSeeds) {
+ Random prng = new Random();
+
+ int j, i;
+ for (i = 0; i < k; i++) {
+ for (j = 0; j < m; j++) {
+ hashSeeds[i][j] = Math.abs(prng.nextLong()); //(int) prng.genInt();
+ // initialise the hash functions
+ // prng_int() should return a random integer
+ // uniformly distributed in the range 0..2^31
+ }
+ }
+ }
+
+ protected static double getMedian(double[] data, int length) {
+ return QuickSelect.select(data, data.length / 2);
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/SketchSynopsis.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/SketchSynopsis.java b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/SketchSynopsis.java
new file mode 100644
index 0000000..fff8ce8
--- /dev/null
+++ b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/sketch/SketchSynopsis.java
@@ -0,0 +1,83 @@
+package org.apache.hyracks.storage.am.statistics.sketch;
+
+//public class SketchSynopsis extends Synopsis implements IIndexBulkLoader {
+//
+// private final int levelNum;
+// private final int fanoutLog;
+// private final double epsilon;
+// private final GroupCountSketch gcSketch;
+// private final IBufferCache bufferCache;
+// private final IFileMapProvider fileMapProvider;
+// private final FileReference file;
+// private final int[] keyFields;
+// private final int fileId = -1;
+// private final boolean isActivated = false;
+//
+// public SketchSynopsis(IBufferCache bufferCache, IFileMapProvider fileMapProvider, FileReference file,
+// int[] keyFields, int domainSize, double delta, double epsilon, int fanOut) {
+// super(bufferCache, fileMapProvider, file);
+// this.keyFields = keyFields;
+// this.fanoutLog = (int) (Math.log(fanOut) / Math.log(2.0));
+// this.levelNum = domainSize / fanoutLog;
+// this.epsilon = epsilon;
+// final int depth = (int) Math.ceil(Math.log(1 / delta));
+// final int width = (int) Math.ceil(1 / epsilon);
+// gcSketch = new GroupCountSketch(this.levelNum + 1, depth, width, fanoutLog);
+// }
+//
+// public void update(long item, double diff) {
+// //translate position to coefficient
+// item += 1 << (levelNum * fanoutLog);
+// //transform update into wavelet domain
+// long div = 1;
+// for (int i = 0; i < levelNum; i++) {
+// // Long coeffIdx = (long) ((1 << ((levelNum - i) * fanoutLog)) + item);
+// item >>= (fanoutLog - 1);
+// int sign = (item & 1) == 0 ? 1 : -1;
+// item >>= 1;
+// double normCoeff = WaveletCoefficient.getNormalizationCoefficient(levelNum * fanoutLog,
+// (i + 1) * fanoutLog);
+// div = (1 << ((i + 1) * fanoutLog));
+//
+// gcSketch.update(item, diff * sign / (normCoeff * div));
+// }
+// gcSketch.update(0, diff / div);
+// }
+//
+// @Override
+// public void add(ITupleReference tuple) throws IndexException, HyracksDataException {
+// // TODO Auto-generated method stub
+//
+// }
+//
+// @Override
+// public void end() throws IndexException, HyracksDataException {
+// // TODO Auto-generated method stub
+//
+// }
+//
+// @Override
+// public void create() {
+// // TODO Auto-generated method stub
+//
+// }
+//
+// @Override
+// public void activate() {
+// // TODO Auto-generated method stub
+//
+// }
+//
+// @Override
+// public IIndexBulkLoader createBuilder(long numElements) {
+// // TODO Auto-generated method stub
+// return null;
+// }
+//
+// @Override
+// public void addElement(Object key, Object value) {
+// // TODO Auto-generated method stub
+//
+// }
+//
+//}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/wavelet/WaveletCoefficient.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/wavelet/WaveletCoefficient.java b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/wavelet/WaveletCoefficient.java
new file mode 100644
index 0000000..d2924e6
--- /dev/null
+++ b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/wavelet/WaveletCoefficient.java
@@ -0,0 +1,91 @@
+package org.apache.hyracks.storage.am.statistics.wavelet;
+
+import java.util.Objects;
+
+import org.apache.hyracks.data.std.primitive.DoublePointable;
+
+public class WaveletCoefficient /*implements Comparable<WaveletCoefficient>*/ {
+
+ private double value;
+ private int level;
+ private long index;
+
+ public WaveletCoefficient(double value, int level, long index) {
+ this.value = value;
+ this.level = level;
+ this.index = index;
+ }
+
+ public long getIndex() {
+ return index;
+ }
+
+ public double getValue() {
+ return value;
+ }
+
+ public int getLevel() {
+ return level;
+ }
+
+ public void setValue(Double value) {
+ this.value = value;
+ }
+
+ public void setLevel(int level) {
+ this.level = level;
+ }
+
+ public void setIndex(long index) {
+ this.index = index;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (!(o instanceof WaveletCoefficient))
+ return false;
+ WaveletCoefficient coeff = (WaveletCoefficient) o;
+ return (coeff.value - value) < DoublePointable.getEpsilon() && (coeff.level == level) && (coeff.index == index);
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(value, level, index);
+ }
+
+ public static double getNormalizationCoefficient(int maxLevel, int level) {
+ return (1 << ((maxLevel - level) / 2)) * ((((maxLevel - level) % 2) == 0) ? 1 : Math.sqrt(2));
+ }
+
+ // Returns index of the parent coefficient
+ public long getParentCoeffIndex(long domainMin, long maxLevel) {
+ // Special case for values on level 0
+ if (level == 0)
+ // Convert position to proper coefficient index
+ return (index >> 1) - (domainMin >> 1) + (1l << (maxLevel - 1));
+ else
+ return index >>> 1;
+ }
+
+ // Returns true if the coefficient's dyadic range covers tuple with the given position
+ public boolean covers(long tuplePosition, long maxLevel, long domainMin) {
+ if (level < 0)
+ return true;
+ else if (level == 0)
+ return index == tuplePosition;
+ else
+ return index == (((tuplePosition - domainMin) >>> 1) + (1l << (maxLevel - 1))) >>> (level - 1);
+ }
+
+ // public static <K extends INumeric> int getLevel(K coeffPointable, int maxLevel) {
+ // long coeffIdx = coeffPointable.longValue();
+ // if (coeffIdx == 0)
+ // return maxLevel;
+ // int level = -1;
+ // while (coeffIdx > 0) {
+ // coeffIdx = coeffIdx >> 1;
+ // level++;
+ // }
+ // return maxLevel - level;
+ // }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/wavelet/WaveletSynopsis.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/wavelet/WaveletSynopsis.java b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/wavelet/WaveletSynopsis.java
new file mode 100644
index 0000000..922c82c
--- /dev/null
+++ b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/wavelet/WaveletSynopsis.java
@@ -0,0 +1,363 @@
+package org.apache.hyracks.storage.am.statistics.wavelet;
+
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.PriorityQueue;
+import java.util.Stack;
+
+import org.apache.hyracks.api.dataflow.value.ISerializerDeserializer;
+import org.apache.hyracks.api.dataflow.value.ITypeTraits;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.api.io.FileReference;
+import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
+import org.apache.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
+import org.apache.hyracks.dataflow.common.data.marshalling.Integer64SerializerDeserializer;
+import org.apache.hyracks.storage.am.common.api.IIndexBulkLoader;
+import org.apache.hyracks.storage.am.common.api.IOrdinalPrimitiveValueProvider;
+import org.apache.hyracks.storage.am.common.api.IndexException;
+import org.apache.hyracks.storage.am.statistics.common.Synopsis;
+import org.apache.hyracks.storage.am.statistics.common.TypeTraitsDomainUtils;
+import org.apache.hyracks.storage.common.buffercache.IBufferCache;
+import org.apache.hyracks.storage.common.buffercache.ICachedPage;
+import org.apache.hyracks.storage.common.file.BufferedFileHandle;
+import org.apache.hyracks.storage.common.file.IFileMapProvider;
+
+public class WaveletSynopsis extends Synopsis {
+
+ private final static int METADATA_PAGE_ID = 0;
+ private final static int NUM_PAGES_OFFSET = 0;
+ private final static int NUM_ELEMENTS_OFFSET = NUM_PAGES_OFFSET + 4;
+ private final static int SYNOPSIS_KEY_SIZE = 4;
+ private final static int SYNOPSIS_VALUE_SIZE = 8;
+
+ private final int[] fields;
+ private final IOrdinalPrimitiveValueProvider fieldValueProvider;
+ private final ITypeTraits[] fieldTypeTraits;
+ @SuppressWarnings("rawtypes")
+ private final ISerializerDeserializer synopsisKeySerde = Integer64SerializerDeserializer.INSTANCE;
+
+ @SuppressWarnings("rawtypes")
+ private final ISerializerDeserializer synopsisValueSerde = DoubleSerializerDeserializer.INSTANCE;
+
+ private final PriorityQueue<WaveletCoefficient> coefficients;
+ private final long threshold;
+
+ private final int numPages;
+
+ public WaveletSynopsis(IBufferCache bufferCache, IFileMapProvider fileMapProvider, FileReference file, int[] fields,
+ int threshold, ITypeTraits[] fieldTypeTraits, IOrdinalPrimitiveValueProvider fieldValueProvider) {
+ super(bufferCache, fileMapProvider, file);
+ this.fields = fields;
+ this.fieldValueProvider = fieldValueProvider;
+ this.fieldTypeTraits = fieldTypeTraits;
+ this.threshold = threshold;
+ this.coefficients = new PriorityQueue<>(threshold, new Comparator<WaveletCoefficient>() {
+
+ @Override
+ // default comparator based on absolute coefficient value
+ public int compare(WaveletCoefficient o1, WaveletCoefficient o2) {
+ return Double.compare(Math.abs(o1.getValue()), Math.abs(o2.getValue()));
+ }
+ });
+ this.numPages = (int) Math
+ .ceil(threshold * (SYNOPSIS_KEY_SIZE + SYNOPSIS_VALUE_SIZE) / (double) bufferCache.getPageSize());
+ }
+
+ @Override
+ public synchronized void create() throws HyracksDataException {
+ super.create();
+
+ initWaveletSynopsisMetaData();
+ bufferCache.closeFile(fileId);
+ }
+
+ @Override
+ public synchronized void deactivate() throws HyracksDataException {
+ super.deactivate();
+ }
+
+ @Override
+ public int getNumPages() throws HyracksDataException {
+ if (!isActivated) {
+ throw new HyracksDataException("The synopsis is not activated.");
+ }
+ return numPages;
+ }
+
+ private void initWaveletSynopsisMetaData() throws HyracksDataException {
+ ICachedPage metaPage = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, METADATA_PAGE_ID), true);
+ metaPage.acquireWriteLatch();
+ try {
+ metaPage.getBuffer().putInt(NUM_PAGES_OFFSET, 0);
+ metaPage.getBuffer().putLong(NUM_ELEMENTS_OFFSET, 0L);
+ } finally {
+ metaPage.releaseWriteLatch(true);
+ bufferCache.unpin(metaPage);
+ }
+ }
+
+ @Override
+ // Adds a new coefficient to the transform, subject to thresholding
+ public void addElement(long index, double value) {
+ WaveletCoefficient newCoeff;
+ if (coefficients.size() < threshold)
+ newCoeff = new WaveletCoefficient(value, -1, index);
+ else {
+ newCoeff = coefficients.poll();
+ newCoeff.setValue(value);
+ newCoeff.setIndex(index);
+ }
+ coefficients.add(newCoeff);
+ }
+
+ // Appends value to the coefficient with given index. If such coefficient is not found creates a new coeff
+ public void apendToElement(long index, double appendValue) {
+ // TODO: do something better than linear search
+ for (WaveletCoefficient coeff : coefficients) {
+ if (coeff.getIndex() == index) {
+ coeff.setValue(coeff.getValue() + appendValue);
+ return;
+ }
+ }
+ addElement(index, appendValue);
+ }
+
+ @Override
+ public IIndexBulkLoader createBuilder() throws HyracksDataException {
+ try {
+ return new SparseTransformBuilder();
+ } catch (HyracksDataException e) {
+ // deactivate();
+ // destroy();
+ throw e;
+ }
+ }
+
+ public class SparseTransformBuilder implements IIndexBulkLoader {
+ private final Stack<WaveletCoefficient> avgStack;
+ private final long domainEnd;
+ private final long domainStart;
+ private final int maxLevel;
+ private Long prevPosition;
+ private ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(2);
+
+ public SparseTransformBuilder() throws HyracksDataException {
+ if (fields.length > 1)
+ throw new HyracksDataException("Only statistics on non-composite fields are allowed");
+ avgStack = new Stack<>();
+ //add first dummy average
+ // TODO: use object pool
+ avgStack.push(new WaveletCoefficient(0.0, -1, -1l));
+ domainStart = TypeTraitsDomainUtils.minDomainValue(fieldTypeTraits[fields[0]]);
+ domainEnd = TypeTraitsDomainUtils.maxDomainValue(fieldTypeTraits[fields[0]]);
+ maxLevel = TypeTraitsDomainUtils.maxLevel(fieldTypeTraits[fields[0]]);
+ prevPosition = null;
+
+ persistWaveletSynopsisMetaData();
+ }
+
+ private void persistWaveletSynopsisMetaData() throws HyracksDataException {
+ ICachedPage metaPage = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, METADATA_PAGE_ID), false);
+ metaPage.acquireWriteLatch();
+ try {
+ metaPage.getBuffer().putInt(NUM_PAGES_OFFSET, numPages);
+ metaPage.getBuffer().putLong(NUM_ELEMENTS_OFFSET, threshold);
+ } finally {
+ metaPage.releaseWriteLatch(true);
+ bufferCache.unpin(metaPage);
+ }
+ }
+
+ // Modifies the wavelet coefficients in case when tuple was already transformed
+ private void modifyTuple(WaveletCoefficient topCoeff, double tupleValue) {
+ // the tuple on the top is always right end of dyadic range
+ long rightCoeffId = topCoeff.getIndex();
+ for (long i = topCoeff.getLevel(); i > 0; i--) {
+ // update coefficients, corresponding to all subranges having current position as they right end
+ apendToElement(rightCoeffId, (i == 0 ? 1 : -1) * tupleValue / (1l << i));
+ rightCoeffId = rightCoeffId << 1 | 1;
+ }
+ // put modified top coefficient back to the stack
+ topCoeff.setValue(topCoeff.getValue() + tupleValue / (1l << topCoeff.getLevel()));
+ avgStack.push(topCoeff);
+
+ }
+
+ // Returns the parent wavelet coefficient for a given coefficient in the transform tree
+ private WaveletCoefficient moveLevelUp(WaveletCoefficient childCoeff) {
+ // TODO: use object pool
+ return new WaveletCoefficient(childCoeff.getValue() / 2.0, childCoeff.getLevel() + 1,
+ childCoeff.getParentCoeffIndex(domainStart, maxLevel));
+ }
+
+ // Calculates the position of the next tuple (on level 0) after given wavelet coefficient
+ private long getTransformPosition(WaveletCoefficient coeff) {
+ if (coeff.getLevel() < 0)
+ return domainStart;
+ else if (coeff.getLevel() == 0)
+ return coeff.getIndex() + 1;
+ else
+ return ((((coeff.getIndex() + 1) << (coeff.getLevel() - 1)) - (1l << (maxLevel - 1))) << 1)
+ + domainStart;
+ }
+
+ // Combines two coeffs on the same level by averaging them and producing next level coefficient
+ private WaveletCoefficient average(WaveletCoefficient leftCoeff, WaveletCoefficient rightCoeff, long domainMin,
+ int maxLevel, boolean normalize) {
+ // assert (leftCoeff.getLevel() == rightCoeff.getLevel());
+ long coeffIdx = leftCoeff.getParentCoeffIndex(domainMin, maxLevel);
+ // put detail wavelet coefficient to the coefficient queue
+ addElement(coeffIdx, (leftCoeff.getValue() - rightCoeff.getValue()) / (2.0 * (normalize
+ ? WaveletCoefficient.getNormalizationCoefficient(maxLevel, leftCoeff.getLevel() + 1) : 1)));
+ // TODO: use object pool
+ return new WaveletCoefficient((leftCoeff.getValue() + rightCoeff.getValue()) / 2.0,
+ leftCoeff.getLevel() + 1, coeffIdx);
+ }
+
+ // Pushes given coefficient on the stack, possibly triggering domino effect
+ private void pushToStack(WaveletCoefficient newCoeff) {
+ // if the coefficient on the top of the stack has the same level as new coefficient, they should be combined
+ while (!avgStack.isEmpty() && avgStack.peek().getLevel() == newCoeff.getLevel()) {
+ WaveletCoefficient topCoeff = avgStack.pop();
+ // Guard against dummy coefficients
+ if (topCoeff.getLevel() >= 0) {
+ // combine newCoeff and topCoeff by averaging them. Result coeff's level is greater than parent's level by 1
+ newCoeff = average(topCoeff, newCoeff, domainStart, maxLevel, true);
+ }
+ }
+ // Guard against dummy coefficients
+ if (newCoeff.getLevel() >= 0)
+ avgStack.push(newCoeff);
+ }
+
+ private void transformTuple(WaveletCoefficient topCoeff, long tuplePosition, double tupleValue) {
+ // 1st part: Upward transform
+ WaveletCoefficient newCoeff = moveLevelUp(topCoeff);
+ // Move the current top coefficient 1 level up as far as possible (until it will cover current position)
+ while (!newCoeff.covers(tuplePosition, maxLevel, domainStart)
+ && (avgStack.size() > 0 ? avgStack.peek().getLevel() > (newCoeff.getLevel() - 1) : true)
+ && topCoeff.getLevel() >= 0) {
+ topCoeff = newCoeff;
+ addElement(newCoeff.getIndex(), newCoeff.getValue());
+ newCoeff = moveLevelUp(newCoeff);
+ }
+ newCoeff = topCoeff;
+ // put the top coefficient (possibly modified) back on to the stack
+ pushToStack(newCoeff);
+
+ // 2nd part: Downward transform
+ if (avgStack.size() > 0)
+ newCoeff = avgStack.peek();
+ // calculate the tuple position, where the transform currently stopped
+ long transformPosition = getTransformPosition(newCoeff);
+ // put all the coefficients, corresponding to dyadic ranges between current tuple position & transformPosition on the stack
+ computeDyadicSubranges(tuplePosition, transformPosition);
+ // put the last coefficient, corresponding to current tuple position on to the stack
+ // TODO: use object pool
+ pushToStack(new WaveletCoefficient(tupleValue, 0, tuplePosition));
+ }
+
+ // Method calculates decreasing level dyadic intervals between tuplePosition&currTransformPosition and saves corresponding coefficients in the avgStack
+ private void computeDyadicSubranges(long tuplePosition, long currTransformPosition) {
+ while (tuplePosition != currTransformPosition) {
+ WaveletCoefficient newCoeff;
+ if (avgStack.size() > 0)
+ // starting with the sibling of the top coefficient on the stack
+ // TODO: use object pool
+ newCoeff = new WaveletCoefficient(0.0, avgStack.peek().getLevel(), avgStack.peek().getIndex() + 1);
+ // special case when there is no coeffs on the stack.
+ else {
+ // Starting descent from top coefficient, i.e. the one with index == 1, level == maxLevel
+ // TODO: use object pool
+ newCoeff = new WaveletCoefficient(0.0, maxLevel, 1l);
+ }
+ // decrease the coefficient level until it stops covering tuplePosition
+ while (newCoeff.covers(tuplePosition, maxLevel, domainStart)) {
+ newCoeff.setLevel(newCoeff.getLevel() - 1);
+ if (newCoeff.getLevel() == 0) {
+ newCoeff.setIndex(((newCoeff.getIndex() - (1l << (maxLevel - 1))) << 1) + domainStart);
+ } else
+ newCoeff.setIndex(newCoeff.getIndex() << 1);
+ }
+ // we don't add newCoeff to the wavelet coefficient collection, since it's value is 0. Keep it only in average stack
+ pushToStack(newCoeff);
+ currTransformPosition = getTransformPosition(newCoeff);
+ }
+ }
+
+ @Override
+ public void add(ITupleReference tuple) throws IndexException, HyracksDataException {
+
+ WaveletCoefficient topCoeff = avgStack.pop();
+ long currTuplePosition = fieldValueProvider.getOrdinalValue(tuple.getFieldData(fields[0]),
+ tuple.getFieldStart(fields[0]));
+ double currTupleValue = 1.0;
+
+ // check whether tuple with this position was already seen
+ if (prevPosition != null && currTuplePosition == prevPosition) {
+ modifyTuple(topCoeff, currTupleValue);
+ } else {
+ transformTuple(topCoeff, currTuplePosition, currTupleValue);
+ }
+ prevPosition = currTuplePosition;
+ }
+
+ @Override
+ public void end() throws IndexException, HyracksDataException {
+ WaveletCoefficient topCoeff = avgStack.pop();
+ if (topCoeff.getIndex() > 0) {
+ if (prevPosition == null || prevPosition != domainEnd) {
+ //complete transform by submitting dummy tuple with the last position avaiable for given domain
+ transformTuple(topCoeff, domainEnd, 0.0);
+ topCoeff = avgStack.pop();
+ }
+ //assert(avgStack.size() == 1);
+ // now the transform is complete the top coefficient on the stack is global average, i.e. coefficient with index==0
+ addElement(0l, topCoeff.getValue());
+
+ persistStatistics();
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ private void persistStatistics() throws HyracksDataException {
+ List<WaveletCoefficient> persistCoefficients = new ArrayList<>(coefficients);
+ // sorting coefficients according their indices to enable fast binary search
+ Collections.sort(persistCoefficients, new Comparator<WaveletCoefficient>() {
+ @Override
+ public int compare(WaveletCoefficient o1, WaveletCoefficient o2) {
+ return Long.compare(o1.getIndex(), o2.getIndex());
+ }
+ });
+ Iterator<WaveletCoefficient> it = persistCoefficients.iterator();
+ int currentPageId = 1;
+ while (currentPageId <= numPages) {
+ ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, currentPageId), true);
+ ByteBuffer buffer = page.getBuffer();
+ page.acquireWriteLatch();
+ try {
+ while (it.hasNext()
+ && (buffer.limit() - buffer.position()) >= SYNOPSIS_KEY_SIZE + SYNOPSIS_VALUE_SIZE) {
+ tupleBuilder.reset();
+ WaveletCoefficient coeff = it.next();
+ tupleBuilder.addField(synopsisKeySerde, coeff.getIndex());
+ tupleBuilder.addField(synopsisValueSerde, coeff.getValue());
+ buffer.put(tupleBuilder.getByteArray(), 0, tupleBuilder.getSize());
+ }
+ } finally {
+ page.releaseWriteLatch(true);
+ bufferCache.unpin(page);
+ }
+ ++currentPageId;
+ }
+
+ }
+
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/wavelet/WaveletTuple.java
----------------------------------------------------------------------
diff --git a/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/wavelet/WaveletTuple.java b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/wavelet/WaveletTuple.java
new file mode 100644
index 0000000..8707c1d
--- /dev/null
+++ b/hyracks/hyracks-storage-am-statistics/src/main/java/org/apache/hyracks/storage/am/statistics/wavelet/WaveletTuple.java
@@ -0,0 +1,47 @@
+package org.apache.hyracks.storage.am.statistics.wavelet;
+
+import java.util.Objects;
+
+public class WaveletTuple implements Comparable<WaveletTuple> {
+ private long position;
+ private double frequency;
+
+ public WaveletTuple(long position, double frequency) {
+ this.position = position;
+ this.frequency = frequency;
+ }
+
+ public long getPosition() {
+ return position;
+ }
+
+ public void setPosition(long position) {
+ this.position = position;
+ }
+
+ public double getFrequency() {
+ return frequency;
+ }
+
+ public void setFrequency(double frequency) {
+ this.frequency = frequency;
+ }
+
+ @Override
+ public int compareTo(WaveletTuple o) {
+ return Long.compare(position, o.position);
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (!(o instanceof WaveletTuple))
+ return false;
+ WaveletTuple tuple = (WaveletTuple) o;
+ return tuple.position == position;
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(position);
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/e05a1921/hyracks/pom.xml
----------------------------------------------------------------------
diff --git a/hyracks/pom.xml b/hyracks/pom.xml
index 86b1551..463d851 100644
--- a/hyracks/pom.xml
+++ b/hyracks/pom.xml
@@ -86,6 +86,7 @@
<module>hyracks-storage-am-lsm-btree</module>
<module>hyracks-storage-am-lsm-rtree</module>
<module>hyracks-storage-am-rtree</module>
+ <module>hyracks-storage-am-statistics</module>
<module>hyracks-test-support</module>
<module>hyracks-tests</module>
<module>hyracks-server</module>