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:47 UTC
(jackrabbit-oak) 01/01: OAK-10577 Advanced repository statistics
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);
+ }
+}