You are viewing a plain text version of this content. The canonical link for it is here.
Posted to oak-commits@jackrabbit.apache.org by th...@apache.org on 2023/12/05 14:07:46 UTC
(jackrabbit-oak) branch OAK-10577 created (now a2adba73bd)
This is an automated email from the ASF dual-hosted git repository.
thomasm pushed a change to branch OAK-10577
in repository https://gitbox.apache.org/repos/asf/jackrabbit-oak.git
at a2adba73bd OAK-10577 Advanced repository statistics
This branch includes the following new commits:
new a2adba73bd OAK-10577 Advanced repository statistics
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
(jackrabbit-oak) 01/01: OAK-10577 Advanced repository statistics
Posted by th...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
thomasm pushed a commit to branch OAK-10577
in repository https://gitbox.apache.org/repos/asf/jackrabbit-oak.git
commit a2adba73bda763ef2a3da2a7350c9ec3ae723607
Author: Thomas Mueller <th...@apache.org>
AuthorDate: Tue Dec 5 15:06:19 2023 +0100
OAK-10577 Advanced repository statistics
---
.../document/flatfile/analysis/Property.java | 64 +++++++
.../indexer/document/flatfile/analysis/Reader.java | 189 +++++++++++++++++++++
.../document/flatfile/analysis/StatsCollector.java | 31 ++++
.../document/flatfile/analysis/Storage.java | 83 +++++++++
.../flatfile/analysis/modules/BinarySize.java | 109 ++++++++++++
.../analysis/modules/BinarySizeEmbedded.java | 106 ++++++++++++
.../analysis/modules/BinarySizeHistogram.java | 122 +++++++++++++
.../analysis/modules/CountMinMeanSketch.java | 81 +++++++++
.../flatfile/analysis/modules/CountMinSketch.java | 75 ++++++++
.../document/flatfile/analysis/modules/Hash.java | 58 +++++++
.../analysis/modules/HyperLogLog3Linear64.java | 97 +++++++++++
.../flatfile/analysis/modules/NodeCount.java | 83 +++++++++
.../flatfile/analysis/modules/PathFilter.java | 61 +++++++
.../flatfile/analysis/modules/PropertyStats.java | 146 ++++++++++++++++
.../flatfile/analysis/modules/SipHash.java | 70 ++++++++
.../flatfile/analysis/modules/TopKValues.java | 121 +++++++++++++
.../analysis/modules/TopLargestBinaries.java | 125 ++++++++++++++
.../analysis/modules/PropertyCountTest.java | 28 +++
18 files changed, 1649 insertions(+)
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/Property.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/Property.java
new file mode 100644
index 0000000000..b0bda9f11d
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/Property.java
@@ -0,0 +1,64 @@
+/*
+ * 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.jackrabbit.oak.index.indexer.document.flatfile.analysis;
+
+import java.util.Arrays;
+
+public class Property {
+
+ String name;
+ boolean multiple;
+ ValueType type;
+ String[] values;
+
+ public Property(String key, ValueType type, String value) {
+ this(key, ValueType.STRING, new String[] {value}, false);
+ }
+
+ public Property(String key, ValueType type, String[] values, boolean multiple) {
+ this.name = key;
+ this.type = type;
+ this.values = values;
+ this.multiple = multiple;
+ }
+
+ public static enum ValueType {
+ STRING,
+ NUMBER,
+ BOOLEAN,
+ NULL
+ }
+
+ public ValueType getType() {
+ return type;
+ }
+
+ public String[] getValues() {
+ return values;
+ }
+
+ public String toString() {
+ return name + ": " + Arrays.toString(values);
+ }
+
+ public String getName() {
+ return name;
+ }
+
+}
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/Reader.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/Reader.java
new file mode 100644
index 0000000000..e776a7cb1b
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/Reader.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.jackrabbit.oak.index.indexer.document.flatfile.analysis;
+
+import java.io.BufferedInputStream;
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.IOException;
+import java.io.InputStreamReader;
+import java.io.LineNumberReader;
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map.Entry;
+
+import org.apache.jackrabbit.oak.commons.PathUtils;
+import org.apache.jackrabbit.oak.commons.json.JsonObject;
+import org.apache.jackrabbit.oak.commons.json.JsopReader;
+import org.apache.jackrabbit.oak.commons.json.JsopTokenizer;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Property.ValueType;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.modules.NodeCount;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.modules.PropertyStats;
+
+import net.jpountz.lz4.LZ4FrameInputStream;
+
+public class Reader {
+ public static void main(String... args) throws IOException {
+ String fileName = args[0];
+ long fileSize = new File(fileName).length();
+ LZ4FrameInputStream in = new LZ4FrameInputStream(new BufferedInputStream(new FileInputStream(fileName)));
+ LineNumberReader reader = new LineNumberReader(new InputStreamReader(in, StandardCharsets.UTF_8));
+ long start = System.nanoTime();
+
+ ArrayList<StatsCollector> collectors = new ArrayList<>();
+
+ collectors.add(new NodeCount(1000));
+ collectors.add(new PropertyStats());
+// collectors.add(new BinarySize(1));
+// collectors.add(new BinarySize(100_000_000));
+// collectors.add(new BinarySizeEmbedded(1));
+// collectors.add(new BinarySizeEmbedded(100_000));
+// collectors.add(new BinarySizeHistogram(1));
+// collectors.add(new TopLargestBinaries(10));
+// collectors.add(new PathFilter("cqdam.text.txt", new BinarySize(1)));
+// collectors.add(new PathFilter("cqdam.text.txt", new BinarySize(100_000_000)));
+// collectors.add(new PathFilter("cqdam.text.txt", new BinarySizeEmbedded(1)));
+// collectors.add(new PathFilter("cqdam.text.txt", new BinarySizeEmbedded(100_000)));
+// collectors.add(new PathFilter("cqdam.text.txt", new BinarySizeHistogram(1)));
+// collectors.add(new PathFilter("cqdam.text.txt", new TopLargestBinaries(10)));
+
+ for(StatsCollector collector : collectors) {
+ collector.setStorage(new Storage());
+ }
+
+ int count = 0;
+ while (true) {
+ String line = reader.readLine();
+ if (line == null) {
+ break;
+ }
+ if (count < 10) {
+ // System.out.println(line);
+ }
+ if (count % 1000000 == 0) {
+ System.out.println(count + " lines");
+ }
+ int pipeIndex = line.indexOf('|');
+ if (pipeIndex < 0) {
+ System.out.println("Error: no pipe: " + line);
+ continue;
+ }
+ String path = line.substring(0, pipeIndex);
+ List<String> pathElements = new ArrayList<>();
+ PathUtils.elements(path).forEach(pathElements::add);
+ String nodeData = line.substring(pipeIndex + 1);
+ List<Property> properties = parse(nodeData);
+
+ for(StatsCollector collector : collectors) {
+ collector.add(pathElements, properties);
+ }
+
+ count++;
+ if (count > 1000000) {
+ break;
+ }
+ }
+
+ for(StatsCollector collector : collectors) {
+ collector.end();
+ }
+
+ for(StatsCollector collector : collectors) {
+ System.out.println(collector.toString());
+ }
+
+ System.out.println(count + " lines total");
+ long time = System.nanoTime() - start;
+ System.out.println((time / 1_000_000_000) + " seconds");
+ System.out.println((time / count) + " ns/entry");
+ System.out.println(fileSize + " bytes");
+ System.out.println((fileSize / count) + " bytes/entry");
+ in.close();
+ }
+
+ private static List<Property> parse(String nodeData) {
+ ArrayList<Property> properties = new ArrayList<>();
+ JsonObject json = JsonObject.fromJson(nodeData, true);
+ for(Entry<String, String> e : json.getProperties().entrySet()) {
+ String v = e.getValue();
+ Property p;
+ if (v.startsWith("[")) {
+ p = fromJsonArray(e.getKey(), v);
+ } else if (v.startsWith("\"")) {
+ String v2 = JsopTokenizer.decodeQuoted(v);
+ p = new Property(e.getKey(), ValueType.STRING, v2);
+ } else if ("null".equals(v)) {
+ p = new Property(e.getKey(), ValueType.NULL, "");
+ } else if ("true".equals(v)) {
+ p = new Property(e.getKey(), ValueType.BOOLEAN, v);
+ } else if ("false".equals(v)) {
+ p = new Property(e.getKey(), ValueType.BOOLEAN, v);
+ } else {
+ p = new Property(e.getKey(), ValueType.NUMBER, v);
+ }
+ properties.add(p);
+ }
+ if (!json.getChildren().isEmpty()) {
+ throw new IllegalArgumentException("Unexpected children " + json.getChildren());
+ }
+ return properties;
+ }
+
+ public static Property fromJsonArray(String key, String json) {
+ ArrayList<String> result = new ArrayList<>();
+ ValueType type = null;
+ JsopTokenizer tokenizer = new JsopTokenizer(json);
+ tokenizer.read('[');
+ if (!tokenizer.matches(']')) {
+ do {
+ switch (tokenizer.read()) {
+ case JsopTokenizer.STRING:
+ if (type != null && type != ValueType.STRING) {
+ throw new IllegalArgumentException("Unsupported mixed type: " + json);
+ }
+ type = ValueType.STRING;
+ String v = tokenizer.getToken();
+ result.add(v);
+ break;
+ case JsopTokenizer.NUMBER:
+ if (type != null && type != ValueType.NUMBER) {
+ throw new IllegalArgumentException("Unsupported mixed type: " + json);
+ }
+ type = ValueType.NUMBER;
+ result.add(tokenizer.getToken());
+ break;
+ case JsopTokenizer.FALSE:
+ case JsopTokenizer.TRUE:
+ if (type != null && type != ValueType.BOOLEAN) {
+ throw new IllegalArgumentException("Unsupported mixed type: " + json);
+ }
+ type = ValueType.BOOLEAN;
+ result.add(tokenizer.getToken());
+ break;
+ default:
+ throw new IllegalArgumentException("Unsupported type: " + json);
+ }
+ } while (tokenizer.matches(','));
+ tokenizer.read(']');
+ }
+ tokenizer.read(JsopReader.END);
+ return new Property(key, type, result.toArray(new String[result.size()]), true);
+ }
+}
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/StatsCollector.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/StatsCollector.java
new file mode 100644
index 0000000000..ac72dbacb8
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/StatsCollector.java
@@ -0,0 +1,31 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis;
+
+import java.util.List;
+
+public interface StatsCollector {
+
+ void setStorage(Storage storage);
+
+ void add(List<String> pathElements, List<Property> properties);
+
+ void end();
+
+}
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/Storage.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/Storage.java
new file mode 100644
index 0000000000..e54c085bff
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/Storage.java
@@ -0,0 +1,83 @@
+/*
+ * 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.jackrabbit.oak.index.indexer.document.flatfile.analysis;
+
+import java.util.Map.Entry;
+import java.util.Set;
+import java.util.TreeMap;
+
+public class Storage {
+
+ private long storageSize;
+ private final TreeMap<String, Long> data = new TreeMap<>();
+
+ public Long get(String key) {
+ return data.get(key);
+ }
+
+ public long add(String key, long value) {
+ Long old = data.get(key);
+ long newValue;
+ if (old == null) {
+ newValue = value;
+ storageSize += key.length() + 8;
+ } else {
+ newValue = old + value;
+ }
+ data.put(key, newValue);
+ return newValue;
+ }
+
+ public void put(String key, long value) {
+ Long old = data.put(key, value);
+ if (old == null) {
+ storageSize += key.length() + 8;
+ }
+ }
+
+ public void remove(String key) {
+ Long old = data.remove(key);
+ if (old != null) {
+ storageSize -= key.length() + 8;
+ }
+ }
+
+ public Set<Entry<String, Long>> entrySet() {
+ return data.entrySet();
+ }
+
+ public String toString() {
+ return "storage size: " + (storageSize / 1024 / 1024) + " MB; " + data.size() + " entries\n";
+ }
+
+ /**
+ * Return the storage estimated size, in bytes.
+ */
+ public long getStorageSize() {
+ return storageSize;
+ }
+
+ /**
+ * Get the number of entries.
+ */
+ public int size() {
+ return data.size();
+ }
+
+}
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/BinarySize.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/BinarySize.java
new file mode 100644
index 0000000000..a80f05608a
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/BinarySize.java
@@ -0,0 +1,109 @@
+package org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.modules;
+
+import java.util.List;
+import java.util.Map.Entry;
+import java.util.Random;
+
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Property;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.StatsCollector;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Storage;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Property.ValueType;
+
+/*
+ * 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.
+ */
+public class BinarySize implements StatsCollector {
+
+ Storage storage;
+ int resolution;
+ Random random = new Random(1);
+
+ public BinarySize(int resolution) {
+ this.resolution = resolution;
+ }
+
+ @Override
+ public void setStorage(Storage storage) {
+ this.storage = storage;
+ }
+
+ public void add(List<String> pathElements, List<Property> properties) {
+ long size = 0;
+ for(Property p : properties) {
+ if (p.getType() == ValueType.STRING) {
+ for (String v : p.getValues()) {
+ if (!v.startsWith(":blobId:")) {
+ continue;
+ }
+ v = v.substring(":blobId:".length());
+ if (v.startsWith("0x")) {
+ // embedded
+ } else {
+ // reference
+ int hashIndex = v.indexOf('#');
+ String length = v.substring(hashIndex + 1);
+ size += Long.parseLong(length);
+ }
+ }
+ }
+ }
+ if (size == 0) {
+ return;
+ }
+ storage.add("/", size);
+ StringBuilder buff = new StringBuilder();
+ for (int i = 0; i < pathElements.size(); i++) {
+ String pe = pathElements.get(i);
+ buff.append('/').append(pe);
+ String key = buff.toString();
+ if (pe.equals("jcr:content")) {
+ break;
+ }
+ if (i < 3) {
+ storage.add(key, size);
+ } else {
+ long s2 = size / resolution * resolution;
+ if (s2 > 0) {
+ storage.add(key, size);
+ } else {
+ if (random.nextInt(resolution) < size) {
+ storage.add(key, (long) resolution);
+ }
+ }
+ }
+ }
+ }
+
+ public String toString() {
+ StringBuilder buff = new StringBuilder();
+ buff.append("BinarySize GB (resolution: " + resolution + ")\n");
+ for(Entry<String, Long> e : storage.entrySet()) {
+ long v = e.getValue();
+ if (v > 1_000_000_000) {
+ buff.append(e.getKey() + ": " + (v / 1_000_000_000)).append('\n');
+ }
+ }
+ buff.append(storage);
+ return buff.toString();
+ }
+
+ @Override
+ public void end() {
+ }
+
+}
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/BinarySizeEmbedded.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/BinarySizeEmbedded.java
new file mode 100644
index 0000000000..e2aca983ed
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/BinarySizeEmbedded.java
@@ -0,0 +1,106 @@
+/*
+ * 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.jackrabbit.oak.index.indexer.document.flatfile.analysis.modules;
+
+import java.util.List;
+import java.util.Random;
+import java.util.Map.Entry;
+
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Property;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.StatsCollector;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Storage;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Property.ValueType;
+
+public class BinarySizeEmbedded implements StatsCollector {
+
+ Storage storage;
+ int resolution;
+ Random random = new Random(1);
+
+ public BinarySizeEmbedded(int resolution) {
+ this.resolution = resolution;
+ }
+
+ @Override
+ public void setStorage(Storage storage) {
+ this.storage = storage;
+ }
+
+ public void add(List<String> pathElements, List<Property> properties) {
+ long size = 0;
+ for(Property p : properties) {
+ if (p.getType() == ValueType.STRING) {
+ for (String v : p.getValues()) {
+ if (!v.startsWith(":blobId:")) {
+ continue;
+ }
+ v = v.substring(":blobId:".length());
+ if (v.startsWith("0x")) {
+ // embedded
+ size = (v.length() - 2) / 2;
+ } else {
+ // reference
+ }
+ }
+ }
+ }
+ if (size == 0) {
+ return;
+ }
+ storage.add("/", size);
+ StringBuilder buff = new StringBuilder();
+ for (int i = 0; i < pathElements.size(); i++) {
+ String pe = pathElements.get(i);
+ buff.append('/').append(pe);
+ String key = buff.toString();
+ if (pe.equals("jcr:content")) {
+ break;
+ }
+ if (i < 3) {
+ storage.add(key, size);
+ } else {
+ long s2 = size / resolution * resolution;
+ if (s2 > 0) {
+ storage.add(key, size);
+ } else {
+ if (random.nextInt(resolution) < size) {
+ storage.add(key, (long) resolution);
+ }
+ }
+ }
+ }
+ }
+
+ public String toString() {
+ StringBuilder buff = new StringBuilder();
+ buff.append("BinarySizeEmbedded (MB)\n");
+ for(Entry<String, Long> e : storage.entrySet()) {
+ if (e.getValue() > 1_000_000) {
+ buff.append(e.getKey() + ": " + (e.getValue() / 1_000_000)).append('\n');
+ }
+ }
+ buff.append(storage);
+ return buff.toString();
+ }
+
+ @Override
+ public void end() {
+ }
+
+}
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/BinarySizeHistogram.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/BinarySizeHistogram.java
new file mode 100644
index 0000000000..1d2958ee79
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/BinarySizeHistogram.java
@@ -0,0 +1,122 @@
+/*
+ * 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.jackrabbit.oak.index.indexer.document.flatfile.analysis.modules;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map.Entry;
+
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Property;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.StatsCollector;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Storage;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Property.ValueType;
+
+public class BinarySizeHistogram implements StatsCollector {
+
+ int pathLevels;
+ Storage storage;
+
+ private static final String[] SIZES = new String[64];
+
+ static {
+ SIZES[0] = "0";
+ for (long x = 1; x > 0; x += x) {
+ int n = 64 - Long.numberOfLeadingZeros(x);
+ SIZES[n] = String.format("%2d", n) + " (" + (x / 2 + 1) + ".." + x + ")";
+ }
+ }
+
+ public BinarySizeHistogram(int pathLevels) {
+ this.pathLevels = pathLevels;
+ }
+
+ @Override
+ public void setStorage(Storage storage) {
+ this.storage = storage;
+ }
+
+ public void add(List<String> pathElements, List<Property> properties) {
+ ArrayList<Long> embedded = new ArrayList<>();
+ ArrayList<Long> references = new ArrayList<>();
+ for(Property p : properties) {
+ if (p.getType() == ValueType.STRING) {
+ for (String v : p.getValues()) {
+ if (!v.startsWith(":blobId:")) {
+ continue;
+ }
+ v = v.substring(":blobId:".length());
+ if (v.startsWith("0x")) {
+ // embedded
+ long size = (v.length() - 2) / 2;
+ embedded.add(size);
+ } else {
+ // reference
+ int hashIndex = v.indexOf('#');
+ String length = v.substring(hashIndex + 1);
+ long size = Long.parseLong(length);
+ references.add(size);
+ }
+ }
+ }
+ }
+ if (embedded.isEmpty() && references.isEmpty()) {
+ return;
+ }
+ add("/", embedded, references);
+ StringBuilder buff = new StringBuilder();
+ for (int i = 0; i < pathLevels && i < pathElements.size(); i++) {
+ String pe = pathElements.get(i);
+ buff.append('/').append(pe);
+ String key = buff.toString();
+ add(key, embedded, references);
+ }
+ }
+
+ void add(String key, ArrayList<Long> embedded, ArrayList<Long> references) {
+ for(long x : embedded) {
+ int bits = 65 - Long.numberOfLeadingZeros(x);
+ storage.add("embedded " + key + " " + SIZES[bits], 1L);
+ storage.add("embedded total count", 1L);
+ storage.add("embedded total size", x);
+ }
+ for(long x : references) {
+ int bits = 65 - Long.numberOfLeadingZeros(x);
+ storage.add("refs " + key + " " + SIZES[bits], 1L);
+ storage.add("refs total count", 1L);
+ storage.add("refs total size", x);
+ }
+ }
+
+ public String toString() {
+ StringBuilder buff = new StringBuilder();
+ buff.append("BinarySizeHistogram\n");
+ for(Entry<String, Long> e : storage.entrySet()) {
+ if (e.getValue() > 0) {
+ buff.append(e.getKey() + ": " + e.getValue()).append('\n');
+ }
+ }
+ buff.append(storage);
+ return buff.toString();
+ }
+
+ @Override
+ public void end() {
+ }
+
+}
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/CountMinMeanSketch.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/CountMinMeanSketch.java
new file mode 100644
index 0000000000..d1dc214afe
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/CountMinMeanSketch.java
@@ -0,0 +1,81 @@
+/*
+ * 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.jackrabbit.oak.index.indexer.document.flatfile.analysis.modules;
+
+import java.util.Arrays;
+
+/**
+ * The count-min sketch.
+ */
+public class CountMinMeanSketch {
+
+ // number of hash functions (depth, number of rows)
+ private final int k;
+
+ // number of buckets (width, number of columns)
+ private final int m;
+
+ private final long[][] data;
+ private long count;
+
+ /**
+ * Create a new instance.
+ *
+ * @param m the number of buckets per hash function (must be a power of 2)
+ * @param k the number of hash functions
+ */
+ public CountMinMeanSketch(int k, int m) {
+ if (Integer.bitCount(m) != 1) {
+ throw new IllegalArgumentException("Must be a power of 2: " + m);
+ }
+ if ((k & 1) == 0) {
+ throw new IllegalArgumentException("Must be odd: " + k);
+ }
+ this.m = m;
+ this.k = k;
+ data = new long[k][m];
+ }
+
+ public void add(long hash) {
+ for (int i = 0; i < k; i++) {
+ long h2 = Hash.hash64(hash, i);
+ data[i][(int) (h2 & (m - 1))]++;
+ }
+ count++;
+ }
+
+ public long estimate(long hash) {
+ long[] array = new long[k];
+ long min = Long.MAX_VALUE;
+ for (int i = 0; i < k; i++) {
+ long h2 = Hash.hash64(hash, i);
+ long x = data[i][(int) (h2 & (m - 1))];
+ min = Math.min(min, x);
+ array[i] = Math.max(0, x - (count - x) / (m - 1));
+ }
+ Arrays.sort(array);
+ long mean = array[array.length / 2];
+ return Math.min(mean, min);
+ }
+
+ public long getCount() {
+ return count;
+ }
+
+}
\ No newline at end of file
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/CountMinSketch.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/CountMinSketch.java
new file mode 100644
index 0000000000..1c404410b4
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/CountMinSketch.java
@@ -0,0 +1,75 @@
+/*
+ * 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.jackrabbit.oak.index.indexer.document.flatfile.analysis.modules;
+
+/**
+ * The count-min sketch.
+ */
+public class CountMinSketch {
+
+ // number of hash functions (depth, number of rows)
+ private final int k;
+
+ // number of buckets (width, number of columns)
+ private final int m;
+
+ private final long[][] data;
+ private long count;
+
+ /**
+ * Create a new instance.
+ *
+ * @param m the number of buckets per hash function (must be a power of 2)
+ * @param k the number of hash functions
+ */
+ public CountMinSketch(int k, int m) {
+ if (Integer.bitCount(m) != 1) {
+ throw new IllegalArgumentException("Must be a power of 2: " + m);
+ }
+ if ((k & 1) == 0) {
+ throw new IllegalArgumentException("Must be odd: " + k);
+ }
+ this.m = m;
+ this.k = k;
+ data = new long[k][m];
+ }
+
+ public void add(long hash) {
+ for (int i = 0; i < k; i++) {
+ long h2 = Hash.hash64(hash, i);
+ data[i][(int) (h2 & (m - 1))]++;
+ }
+ count++;
+ }
+
+ public long estimate(long hash) {
+ long min = Long.MAX_VALUE;
+ for (int i = 0; i < k; i++) {
+ long h2 = Hash.hash64(hash, i);
+ long x = data[i][(int) (h2 & (m - 1))];
+ min = Math.min(min, x);
+ }
+ return min;
+ }
+
+ public long getCount() {
+ return count;
+ }
+
+}
\ No newline at end of file
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/Hash.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/Hash.java
new file mode 100644
index 0000000000..7863481895
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/Hash.java
@@ -0,0 +1,58 @@
+/*
+ * 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.jackrabbit.oak.index.indexer.document.flatfile.analysis.modules;
+
+public class Hash {
+
+ private static long seed;
+
+ public static void setSeed(long s) {
+ seed = s;
+ }
+
+ public static long randomLong() {
+ return hash64(seed++);
+ }
+
+ public static long hash64(long x, long seed) {
+ x += seed;
+ x = (x ^ (x >>> 33)) * 0xff51afd7ed558ccdL;
+ x = (x ^ (x >>> 33)) * 0xc4ceb9fe1a85ec53L;
+ x = x ^ (x >>> 33);
+ return x;
+ }
+
+ public static long hash64(long x) {
+ return hash64(x, 100);
+ }
+
+ /**
+ * Shrink the hash to a value 0..n. Kind of like modulo, but using
+ * multiplication and shift, which are faster to compute.
+ *
+ * @param hash the hash
+ * @param n the maximum of the result
+ * @return the reduced value
+ */
+ public static int reduce(int hash, int n) {
+ // http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
+ return (int) (((hash & 0xffffffffL) * n) >>> 32);
+ }
+
+}
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/HyperLogLog3Linear64.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/HyperLogLog3Linear64.java
new file mode 100644
index 0000000000..88e4627a1e
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/HyperLogLog3Linear64.java
@@ -0,0 +1,97 @@
+/*
+ * 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.jackrabbit.oak.index.indexer.document.flatfile.analysis.modules;
+
+/**
+ * Cardinality estimation with the HyperLogLog algorithm, using the tail cut
+ * mechanism. Tail cut is described in the paper "Better with Fewer Bits -
+ * Improving the Performance of Cardinality Estimation of Large Data Streams"
+ * from Qingjun Xiao, You Zhou, Shigang Chen, in
+ * http://cse.seu.edu.cn/PersonalPage/csqjxiao/csqjxiao_files/papers/INFOCOM17.pdf
+ *
+ * It uses linear counting for 60 bits, until 36 bits are set, then switches to
+ * HyperLogLog. There, it uses 20 counters of 3 bits each (re-using the linear
+ * counting data), and 4 bits for a base counter, which is increased if all
+ * counters are larger than zero.
+ *
+ * It is a little bit "order-dependent", that is, adding the same entry multiple
+ * times can change the internal state. However, unlike in HyperBitBit, here the
+ * effect is smaller.
+ */
+public class HyperLogLog3Linear64 {
+
+ static long add(long data, long hash) {
+ int base = (int) (data & 0xf);
+ if (base == 0) {
+ int index = (int) (((hash & 0xffffffffL) * 20) >>> 32);
+ int z = Long.numberOfLeadingZeros(hash);
+ index += 20 * Math.min(z, 2);
+ data |= 1L << (4 + index);
+ if (Long.bitCount(data >>> 4) < 36) {
+ return data;
+ }
+ base = 1;
+ long newData = base;
+ for (int i = 0; i < 20; i++) {
+ if ((data >>> (44 + i) & 1) == 1) {
+ newData += 2L << (4 + 3 * i);
+ } else if ((data >>> (24 + i) & 1) == 1) {
+ newData += 1L << (4 + 3 * i);
+ }
+ }
+ data = newData;
+ }
+ int z = Long.numberOfLeadingZeros(hash) - (base - 1);
+ if (z > 0) {
+ int i = (int) (((hash & 0xffffffffL) * 20) >>> 32);
+ int shift = 4 + 3 * i;
+ long old = (data >>> shift) & 0x7;
+ long m = Math.min(0x7, Math.max(z, old));
+ data = (data & ~(0x7L << shift)) | (m << shift);
+ // base shift
+ long s = data | (data >>> 1) | (data >>> 2);
+ if ((s & 0x2492492492492490L) == 0x2492492492492490L) {
+ if (base < 0xf) {
+ data -= 0x2492492492492490L;
+ data += 1;
+ }
+ }
+ }
+ return data;
+ }
+
+ static long estimate(long data) {
+ long base = data & 0xf;
+ if (base == 0) {
+ int x = Long.bitCount(data);
+ int b = 53, m = 1;
+ long est = (long) (-(b / m) * Math.log(1. - (double) x / b));
+ return est;
+ }
+ double sum = 0;
+ long x = data >>> 4;
+ for (int i = 1; i < 20; i++) {
+ long n = x & 0x7;
+ x >>>= 3;
+ sum += 1. / (1L << (base + n));
+ }
+ return (long) (20 * 20 * 0.63375 / sum);
+ }
+
+}
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/NodeCount.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/NodeCount.java
new file mode 100644
index 0000000000..92f8bc12f1
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/NodeCount.java
@@ -0,0 +1,83 @@
+/*
+ * 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.jackrabbit.oak.index.indexer.document.flatfile.analysis.modules;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map.Entry;
+
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Property;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.StatsCollector;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Storage;
+
+public class NodeCount implements StatsCollector {
+
+ final long seed = 42;
+ final int resolution;
+ final long bitMask;
+ Storage storage;
+
+ @Override
+ public void setStorage(Storage storage) {
+ this.storage = storage;
+ }
+
+ public NodeCount(int resolution) {
+ this.resolution = resolution;
+ this.bitMask = (Integer.highestOneBit(resolution) * 2) - 1;
+ }
+
+ public void add(List<String> pathElements, List<Property> properties) {
+ SipHash hash = new SipHash(seed);
+ ArrayList<String> parents = new ArrayList<>();
+ for(String pe : pathElements) {
+ hash = new SipHash(hash, pe.hashCode());
+ parents.add(pe);
+ }
+ // with bitMask=1024: with a probability of 1:1024,
+ if ((hash.hashCode() & bitMask) == 0) {
+ // add 1024
+ long offset = bitMask + 1;
+ storage.add("/", offset);
+ StringBuilder buff = new StringBuilder();
+ for(String p : parents) {
+ buff.append('/').append(p);
+ String pa = buff.toString();
+ storage.add(pa, offset);
+ }
+ }
+ }
+
+ public String toString() {
+ StringBuilder buff = new StringBuilder();
+ buff.append("NodeCount (millions)\n");
+ for(Entry<String, Long> e : storage.entrySet()) {
+ if (e.getValue() > 1_000_000) {
+ buff.append(e.getKey() + ": " + (e.getValue() / 1_000_000)).append('\n');
+ }
+ }
+ buff.append(storage);
+ return buff.toString();
+ }
+
+ @Override
+ public void end() {
+ }
+
+}
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PathFilter.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PathFilter.java
new file mode 100644
index 0000000000..0c63dfc602
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PathFilter.java
@@ -0,0 +1,61 @@
+/*
+ * 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.jackrabbit.oak.index.indexer.document.flatfile.analysis.modules;
+
+import java.util.List;
+
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Property;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.StatsCollector;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Storage;
+
+public class PathFilter implements StatsCollector {
+
+ private final StatsCollector base;
+ private final String path;
+
+ public PathFilter(String path, StatsCollector base) {
+ this.path = path;
+ this.base = base;
+ }
+
+ @Override
+ public void setStorage(Storage storage) {
+ base.setStorage(storage);
+ }
+
+ @Override
+ public void add(List<String> pathElements, List<Property> properties) {
+ for(String pe : pathElements) {
+ if (pe.equals(path)) {
+ base.add(pathElements, properties);
+ break;
+ }
+ }
+ }
+
+ @Override
+ public void end() {
+ base.end();
+ }
+
+ public String toString() {
+ return "PathFilter " + path + " of " + base.toString();
+ }
+
+}
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PropertyStats.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PropertyStats.java
new file mode 100644
index 0000000000..a932ebe9bb
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PropertyStats.java
@@ -0,0 +1,146 @@
+/*
+ * 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.jackrabbit.oak.index.indexer.document.flatfile.analysis.modules;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map.Entry;
+import java.util.TreeMap;
+
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Property;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.StatsCollector;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Storage;
+
+public class PropertyStats implements StatsCollector {
+
+ private static final String COUNT = "count ";
+ private static final String VALUES = "values ";
+ private static final String DISTINCT = "distinct ";
+
+ Storage storage;
+ CountMinSketch propertyCountSketch = new CountMinSketch(63, 64);
+ private final long seed = 42;
+
+ // we start collecting top k values once we have seen this many entries to save memory
+ private final static long MIN_TOP_K = 5_000;
+
+ private final static int TOP_K = 10;
+
+ // we only consider the most common properties
+ // to protect against millions of unique properties
+ private final static long MAX_SIZE = 100_000;
+
+ private final TreeMap<String, TopKValues> topEntries = new TreeMap<>();
+
+ @Override
+ public void setStorage(Storage storage) {
+ this.storage = storage;
+ }
+
+ @Override
+ public void add(List<String> pathElements, List<Property> properties) {
+ for(Property p : properties) {
+ String name = p.getName();
+ long count = storage.add(COUNT + name, 1L);
+ storage.add(VALUES + name, (long) p.getValues().length);
+ addValues(name, p);
+ removeRareEntries();
+ if (count >= MIN_TOP_K) {
+ TopKValues top = topEntries.get(name);
+ if (top == null) {
+ top = new TopKValues(TOP_K);
+ topEntries.put(name, top);
+ }
+ for (String v : p.getValues()) {
+ top.add(v);
+ }
+ }
+ }
+ }
+
+ private void addValues(String name, Property p) {
+ Long old = storage.get(DISTINCT + name);
+ long hll = old == null ? 0 : old;
+ for (String v : p.getValues()) {
+ long hash = Hash.hash64(v.hashCode(), seed);
+ hll = HyperLogLog3Linear64.add(hll, hash);
+ }
+ storage.put(DISTINCT + name, hll);
+ }
+
+ /**
+ * Remove entries with a low count if there are too many entries.
+ */
+ private void removeRareEntries() {
+ if (storage.size() < MAX_SIZE * 2) {
+ return;
+ }
+ ArrayList<Entry<String, Long>> list = new ArrayList<>(storage.entrySet());
+ ArrayList<Long> counts = new ArrayList<>(list.size());
+ for (int i = 0; i < list.size(); i++) {
+ String n = list.get(i).getKey();
+ if (n.startsWith(COUNT)) {
+ counts.add(list.get(i).getValue());
+ }
+ }
+ Collections.sort(counts);
+ long mean = counts.get((int) MAX_SIZE);
+ for (int i = 0; i < list.size(); i++) {
+ Entry<String, Long> e = list.get(i);
+ if (e.getValue() <= mean) {
+ storage.remove(COUNT + e.getKey());
+ storage.remove(VALUES + e.getKey());
+ storage.remove(DISTINCT + e.getKey());
+ }
+ }
+ }
+
+ @Override
+ public void end() {
+ }
+
+ public String toString() {
+ StringBuilder buff = new StringBuilder();
+ buff.append("PropertyCount\n");
+ for(Entry<String, Long> e : storage.entrySet()) {
+ String key = e.getKey();
+ if (key.startsWith(COUNT) && e.getValue() > 100) {
+ String propertyName = key.substring(COUNT.length());
+ long count = e.getValue();
+ long values = storage.get(VALUES + propertyName);
+ long hll = storage.get(DISTINCT + propertyName);
+ buff.append(propertyName).append(": {count:").append(count);
+ if (values != count) {
+ buff.append(", values:").append(values);
+ }
+ buff.append(", distinct:").append(HyperLogLog3Linear64.estimate(hll));
+ TopKValues top = topEntries.get(propertyName);
+ if (top != null) {
+ buff.append(", top:").append(top.toString());
+ }
+ buff.append("}\n");
+ }
+ }
+ buff.append(storage);
+ return buff.toString();
+ }
+
+
+}
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/SipHash.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/SipHash.java
new file mode 100644
index 0000000000..267eaf5529
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/SipHash.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.jackrabbit.oak.index.indexer.document.flatfile.analysis.modules;
+
+/**
+ * An implementation of the SipHash-2-2 function, to prevent hash flooding.
+ */
+public class SipHash {
+
+ private final long v0, v1, v2, v3;
+
+ public SipHash(long seed) {
+ long k0 = seed;
+ long k1 = Long.rotateLeft(seed, 32);
+ v0 = k0 ^ 0x736f6d6570736575L;
+ v1 = k1 ^ 0x646f72616e646f6dL;
+ v2 = k0 ^ 0x6c7967656e657261L;
+ v3 = k1 ^ 0x7465646279746573L;
+ }
+
+ public SipHash(SipHash parent, long m) {
+ long v0 = parent.v0;
+ long v1 = parent.v1;
+ long v2 = parent.v2;
+ long v3 = parent.v3;
+ int repeat = 2;
+ for (int i = 0; i < repeat; i++) {
+ v0 += v1;
+ v2 += v3;
+ v1 = Long.rotateLeft(v1, 13);
+ v3 = Long.rotateLeft(v3, 16);
+ v1 ^= v0;
+ v3 ^= v2;
+ v0 = Long.rotateLeft(v0, 32);
+ v2 += v1;
+ v0 += v3;
+ v1 = Long.rotateLeft(v1, 17);
+ v3 = Long.rotateLeft(v3, 21);
+ v1 ^= v2;
+ v3 ^= v0;
+ v2 = Long.rotateLeft(v2, 32);
+ }
+ v0 ^= m;
+ this.v0 = v0;
+ this.v1 = v1;
+ this.v2 = v2;
+ this.v3= v3;
+ }
+
+ @Override
+ public int hashCode() {
+ long x = v0 ^ v1 ^ v2 ^ v3;
+ return (int) (x ^ (x >>> 16));
+ }
+
+}
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/TopKValues.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/TopKValues.java
new file mode 100644
index 0000000000..88aa833438
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/TopKValues.java
@@ -0,0 +1,121 @@
+/*
+ * 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.jackrabbit.oak.index.indexer.document.flatfile.analysis.modules;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+
+import org.apache.jackrabbit.oak.commons.json.JsopBuilder;
+
+/**
+ * Contains and implements the logic to maintain the top-K values of a property.
+ * Internally, it uses a priority queue that is updated each time a value is
+ * added or modified. In fact, whenever an existing value is updated, we check
+ * if it should be added to the priority queue.
+ */
+public class TopKValues {
+
+ private final int k;
+ private final CountMinSketch sketch = new CountMinSketch(31, 32);
+ private final ArrayList<TopEntry> list = new ArrayList<>();
+ private final HashMap<String, TopEntry> map = new HashMap<>();
+
+ TopKValues(int k) {
+ this.k = k;
+ }
+
+ void add(String value) {
+ long hash = Hash.hash64(value.hashCode());
+ value = shortenIfNeeded(value);
+ sketch.add(hash);
+ long est = sketch.estimate(hash);
+ TopEntry existing = map.get(value);
+ if (existing != null) {
+ existing.count = est;
+ bumpIfNeeded(existing.index);
+ return;
+ }
+ if (list.size() >= k && est < list.get(0).count) {
+ return;
+ }
+ TopEntry e = new TopEntry(value, est);
+ e.index = list.size();
+ list.add(e);
+ bumpIfNeeded(e.index);
+ map.put(value, e);
+ if (list.size() > k) {
+ TopEntry smallest = list.remove(list.size() - 1);
+ map.remove(smallest.value);
+ }
+ }
+
+ void bumpIfNeeded(int index) {
+ while (index > 0) {
+ TopEntry existing = list.get(index);
+ TopEntry next = list.get(index - 1);
+ if (existing.count <= next.count) {
+ break;
+ }
+ list.set(index, next);
+ next.index = index;
+ list.set(index - 1, existing);
+ existing.index = index - 1;
+ index--;
+ }
+ }
+
+ static String shortenIfNeeded(String value) {
+ if (value.length() > 100) {
+ value = value.substring(0, 100) + "...";
+ }
+ return value;
+ }
+
+ public String toString() {
+ JsopBuilder builder = new JsopBuilder();
+ builder.object();
+ for (int i = 0; i < list.size(); i++) {
+ TopEntry x = list.get(i);
+ builder.key(x.value).value(x.count);
+ }
+ builder.endObject();
+ return builder.toString();
+ }
+
+ static class TopEntry implements Comparable<TopEntry> {
+ long count;
+ final String value;
+ int index;
+
+ TopEntry(String value, long count) {
+ this.value = value;
+ this.count = count;
+ }
+
+ @Override
+ public int compareTo(TopEntry o) {
+ return Long.compare(count, o.count);
+ }
+
+ public String toString() {
+ return "[" + index + "]: " + count + " " + value;
+ }
+ }
+
+}
\ No newline at end of file
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/TopLargestBinaries.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/TopLargestBinaries.java
new file mode 100644
index 0000000000..f6e9a2759d
--- /dev/null
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/TopLargestBinaries.java
@@ -0,0 +1,125 @@
+/*
+ * 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.jackrabbit.oak.index.indexer.document.flatfile.analysis.modules;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map.Entry;
+
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Property;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Property.ValueType;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.StatsCollector;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Storage;
+
+public class TopLargestBinaries implements StatsCollector {
+
+ Storage storage;
+ final int k;
+ final ArrayList<TopEntry> top = new ArrayList<>();
+ long totalCount;
+ long totalSize;
+
+ public TopLargestBinaries(int k) {
+ this.k = k;
+ }
+
+ @Override
+ public void setStorage(Storage storage) {
+ this.storage = storage;
+ }
+
+ @Override
+ public void add(List<String> pathElements, List<Property> properties) {
+ ArrayList<Long> references = new ArrayList<>();
+ for(Property p : properties) {
+ if (p.getType() == ValueType.STRING) {
+ for (String v : p.getValues()) {
+ if (!v.startsWith(":blobId:")) {
+ continue;
+ }
+ v = v.substring(":blobId:".length());
+ if (v.startsWith("0x")) {
+ // embedded
+ } else {
+ // reference
+ int hashIndex = v.indexOf('#');
+ String length = v.substring(hashIndex + 1);
+ long size = Long.parseLong(length);
+ references.add(size);
+ }
+ }
+ }
+ }
+ for(long x : references) {
+ if (top.size() >= k && x < top.get(0).size) {
+ continue;
+ }
+ totalCount++;
+ totalSize += x;
+ TopEntry e = new TopEntry(x, pathElements);
+ int index = Collections.binarySearch(top, e);
+ if (index < 0) {
+ index = -index - 1;
+ }
+ top.add(index, e);
+ if (top.size() > k) {
+ top.remove(0);
+ }
+ }
+ }
+
+ public void end() {
+ int i = 0;
+ for(TopEntry e: top) {
+ String path = "#" + String.format("%3d", k - i) + ": /" + String.join("/", e.pathElements);
+ storage.add(path, e.size);
+ i++;
+ }
+ storage.add("total count", totalCount);
+ storage.add("total size", totalSize);
+ }
+
+ static class TopEntry implements Comparable<TopEntry> {
+ final long size;
+ final List<String> pathElements;
+
+ TopEntry(long count, List<String> pathElements) {
+ this.size = count;
+ this.pathElements = pathElements;
+ }
+
+ @Override
+ public int compareTo(TopEntry o) {
+ return Long.compare(size, o.size);
+ }
+ }
+
+ public String toString() {
+ StringBuilder buff = new StringBuilder();
+ buff.append("TopLargestBinaries\n");
+ for(Entry<String, Long> e : storage.entrySet()) {
+ buff.append(e.getKey() + ": " + e.getValue()).append('\n');
+ }
+ buff.append(storage);
+ return buff.toString();
+ }
+
+
+}
diff --git a/oak-run-commons/src/test/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PropertyCountTest.java b/oak-run-commons/src/test/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PropertyCountTest.java
new file mode 100644
index 0000000000..9ab26f6e95
--- /dev/null
+++ b/oak-run-commons/src/test/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PropertyCountTest.java
@@ -0,0 +1,28 @@
+package org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.modules;
+
+import java.util.Arrays;
+
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Property;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Storage;
+import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.Property.ValueType;
+import org.junit.Test;
+
+public class PropertyCountTest {
+
+ @Test
+ public void manyUniqueProperties() {
+ PropertyStats pc = new PropertyStats();
+ pc.setStorage(new Storage());
+ for (int i = 0; i < 1_000_000; i++) {
+ Property p = new Property("unique" + i, ValueType.STRING, "");
+ pc.add(Arrays.asList(""), Arrays.asList(p));
+ }
+ for (int i = 0; i < 10; i++) {
+ for (int j = 0; j < 200; j++) {
+ Property p = new Property("common" + i, ValueType.STRING, "");
+ pc.add(Arrays.asList(""), Arrays.asList(p));
+ }
+ }
+ System.out.println(pc);
+ }
+}