You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by al...@apache.org on 2024/10/01 23:05:50 UTC
(datasketches-bigquery) 01/01: frequent strings sketch
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch fs_sketch
in repository https://gitbox.apache.org/repos/asf/datasketches-bigquery.git
commit e05645ab4deb0e8ae3458d6797260880f8770c05
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Tue Oct 1 16:05:27 2024 -0700
frequent strings sketch
---
fi/Makefile | 68 ++++++++++++++++
fi/fs_sketch.cpp | 77 ++++++++++++++++++
fi/sqlx/frequent_strings_sketch_build.sqlx | 104 ++++++++++++++++++++++++
fi/sqlx/frequent_strings_sketch_get_result.sqlx | 47 +++++++++++
fi/sqlx/frequent_strings_sketch_merge.sqlx | 103 +++++++++++++++++++++++
fi/sqlx/frequent_strings_sketch_to_string.sqlx | 43 ++++++++++
fi/test/frequent_strings_sketch_test.sql | 32 ++++++++
7 files changed, 474 insertions(+)
diff --git a/fi/Makefile b/fi/Makefile
new file mode 100644
index 0000000..074fd3a
--- /dev/null
+++ b/fi/Makefile
@@ -0,0 +1,68 @@
+# 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.
+
+EMCC=emcc
+EMCFLAGS=-I../datasketches-cpp/common/include \
+ -I../datasketches-cpp/fi/include \
+ --no-entry \
+ -sWASM_BIGINT=1 \
+ -sEXPORTED_FUNCTIONS=[_malloc,_free] \
+ -sENVIRONMENT=shell \
+ -sTOTAL_MEMORY=1024MB \
+ -O3 \
+ --bind
+
+ARTIFACTS=fs_sketch.mjs fs_sketch.js fs_sketch.wasm
+
+all: $(ARTIFACTS)
+
+%.mjs: %.cpp
+ $(EMCC) $< $(EMCFLAGS) -sSINGLE_FILE=1 -o $@
+
+# this rule creates a non-es6 loadable library
+%.js: %.cpp
+ $(EMCC) $< $(EMCFLAGS) -sSINGLE_FILE=1 -o $@
+
+%.wasm: %.cpp
+ $(EMCC) $< $(EMCFLAGS) -sSTANDALONE_WASM=1 -o $@
+
+clean:
+ $(RM) $(ARTIFACTS)
+
+upload: all
+ @for file in $(ARTIFACTS); do \
+ gcloud storage cp $$file gs://$(GCS_BUCKET)/ ; \
+ done
+
+# some functions (with shorter name) can call other functions (with suffix)
+# so reversing the order should create full-signature functions first
+reverse = $(if $(wordlist 2,2,$(1)),$(call reverse,$(wordlist 2,$(words $(1)),$(1))) $(firstword $(1)),$(1))
+
+create:
+ @for file in $(call reverse,$(wildcard sqlx/*.sqlx)); do \
+ echo creating $$file; \
+ ../substitute_and_run.sh $$file ; \
+ done
+
+install: upload create
+
+test:
+ @for file in $(wildcard test/*sql); do \
+ ../substitute_and_run.sh $$file ; \
+ done
+
+.PHONY: all clean install upload create test
diff --git a/fi/fs_sketch.cpp b/fi/fs_sketch.cpp
new file mode 100644
index 0000000..8f813a2
--- /dev/null
+++ b/fi/fs_sketch.cpp
@@ -0,0 +1,77 @@
+/*
+ * 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.
+ */
+
+#include <emscripten/bind.h>
+
+#include <frequent_items_sketch.hpp>
+
+using frequent_strings_sketch = datasketches::frequent_items_sketch<std::string>;
+
+const emscripten::val Uint8Array = emscripten::val::global("Uint8Array");
+
+EMSCRIPTEN_BINDINGS(frequent_strings_sketch) {
+ emscripten::function("getExceptionMessage", emscripten::optional_override([](intptr_t ptr) {
+ return std::string(reinterpret_cast<std::exception*>(ptr)->what());
+ }));
+
+ emscripten::class_<frequent_strings_sketch>("frequent_strings_sketch")
+ .constructor(emscripten::optional_override([](uint8_t lg_max_map_size) {
+ return new frequent_strings_sketch(lg_max_map_size);
+ }))
+ .function("isEmpty", &frequent_strings_sketch::is_empty)
+ .function("update", emscripten::optional_override([](frequent_strings_sketch& self, const std::string& str, uint64_t weight) {
+ self.update(str, weight);
+ }))
+ .function("merge", emscripten::optional_override([](frequent_strings_sketch& self, const std::string& bytes) {
+ self.merge(frequent_strings_sketch::deserialize(bytes.data(), bytes.size()));
+ }))
+ .function("serializeAsUint8Array", emscripten::optional_override([](const frequent_strings_sketch& self) {
+ auto bytes = self.serialize();
+ return Uint8Array.new_(emscripten::typed_memory_view(bytes.size(), bytes.data()));
+ }))
+ .class_function("deserialize", emscripten::optional_override([](const std::string& bytes) {
+ return new frequent_strings_sketch(frequent_strings_sketch::deserialize(bytes.data(), bytes.size()));
+ }), emscripten::allow_raw_pointers())
+ .class_function("toString", emscripten::optional_override([](const std::string& bytes) {
+ return frequent_strings_sketch::deserialize(bytes.data(), bytes.size()).to_string();
+ }))
+ .class_function("getResult", emscripten::optional_override([](const std::string& bytes, const std::string& err_type_str, uint64_t threshold) {
+ datasketches::frequent_items_error_type err_type;
+ if (err_type_str == "NO_FALSE_NEGATIVES") {
+ err_type = datasketches::NO_FALSE_NEGATIVES;
+ } else if (err_type_str == "NO_FALSE_POSITIVES") {
+ err_type = datasketches::NO_FALSE_POSITIVES;
+ } else {
+ throw std::invalid_argument("unrecognized error type " + err_type_str);
+ }
+ const auto sketch = frequent_strings_sketch::deserialize(bytes.data(), bytes.size());
+ const auto rows = threshold > 0 ? sketch.get_frequent_items(err_type, threshold) : sketch.get_frequent_items(err_type);
+ emscripten::val result(emscripten::val::array());
+ for (const auto& row: rows) {
+ emscripten::val r(emscripten::val::object());
+ r.set("item", row.get_item());
+ r.set("estimate", row.get_estimate());
+ r.set("lower_bound", row.get_lower_bound());
+ r.set("upper_bound", row.get_upper_bound());
+ result.call<void>("push", r);
+ }
+ return result;
+ }))
+ ;
+}
diff --git a/fi/sqlx/frequent_strings_sketch_build.sqlx b/fi/sqlx/frequent_strings_sketch_build.sqlx
new file mode 100644
index 0000000..00f9541
--- /dev/null
+++ b/fi/sqlx/frequent_strings_sketch_build.sqlx
@@ -0,0 +1,104 @@
+/*
+ * 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.
+ */
+
+config { hasOutput: true }
+
+CREATE OR REPLACE AGGREGATE FUNCTION ${self()}(item STRING, weight INT64, lg_max_map_size BYTEINT NOT AGGREGATE)
+RETURNS BYTES
+LANGUAGE js
+OPTIONS (
+ library=["gs://$GCS_BUCKET/fs_sketch.mjs"],
+ description = '''Creates a sketch that represents frequencies of the given column.
+
+Param item: the column of STRING values.
+Param weight: the amount by which the weight of the item should be increased.
+Param lg_max_map_size: the sketch accuracy/size parameter as a BYTEINT not less than 3.
+Returns: a Frequent Strings Sketch, as bytes.
+
+For more information:
+ - https://datasketches.apache.org/docs/Frequency/FrequencySketches.html
+'''
+) AS R"""
+import ModuleFactory from "gs://$GCS_BUCKET/fs_sketch.mjs";
+var Module = await ModuleFactory();
+
+// UDAF interface
+export function initialState(lg_max_map_size) {
+ return { lg_max_map_size: Number(lg_max_map_size) };
+}
+
+export function aggregate(state, item, weight) {
+ try {
+ if (state.sketch == null) {
+ state.sketch = new Module.frequent_strings_sketch(state.lg_max_map_size);
+ }
+ state.sketch.update(item, BigInt(weight));
+ } catch (e) {
+ if (e.message != null) throw e;
+ throw new Error(Module.getExceptionMessage(e));
+ }
+}
+
+export function serialize(state) {
+ if (state.sketch == null) return state; // for transition deserialize-serialize
+ try {
+ // for prior transition deserialize-aggregate
+ // merge aggregated and serialized state
+ if (state.sketch != null && state.serialized != null) {
+ sketch.merge(state.serialized);
+ }
+ return {
+ lg_max_map_size: state.lg_max_map_size,
+ serialized: state.sketch.serializeAsUint8Array()
+ };
+ } catch (e) {
+ if (e.message != null) throw e;
+ throw new Error(Module.getExceptionMessage(e));
+ } finally {
+ state.sketch.delete();
+ }
+}
+
+export function deserialize(serialized) {
+ return serialized;
+}
+
+export function merge(state, other_state) {
+ try {
+ if (state.sketch == null) {
+ state.sketch = new Module.frequent_strings_sketch(state.lg_max_map_size);
+ }
+ if (state.serialized != null) {
+ state.sketch.merge(state.serialized);
+ state.serialized = null;
+ }
+ if (other_state.serialized != null) {
+ state.sketch.merge(other_state.serialized);
+ other_state.serialized = null;
+ }
+ } catch (e) {
+ if (e.message != null) throw e;
+ throw new Error(Module.getExceptionMessage(e));
+ }
+}
+
+export function finalize(state) {
+ return serialize(state).serialized;
+}
+""";
diff --git a/fi/sqlx/frequent_strings_sketch_get_result.sqlx b/fi/sqlx/frequent_strings_sketch_get_result.sqlx
new file mode 100644
index 0000000..4637646
--- /dev/null
+++ b/fi/sqlx/frequent_strings_sketch_get_result.sqlx
@@ -0,0 +1,47 @@
+/*
+ * 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.
+ */
+
+config { hasOutput: true }
+
+CREATE OR REPLACE FUNCTION ${self()}(sketch BYTES, error_type STRING, threshold INT64)
+RETURNS ARRAY<STRUCT<item STRING, estimate INT64, lower_bound INT64, upper_bound INT64>>
+LANGUAGE js
+OPTIONS (
+ library=["gs://$GCS_BUCKET/fs_sketch.js"],
+ js_parameter_encoding_mode='STANDARD',
+ description = '''Returns an array of rows that include frequent items, estimates, lower and upper bounds
+given an error_type and a threshold.
+
+Param sketch: the given sketch as sketch encoded bytes.
+Param error_type: determines whether no false positives or no false negatives are desired.
+Param threshold: a threshold to include items in the result list.
+If NULL, the maximum error of the sketch is used as a threshold.
+Returns: an array of frequent items with frequency estimates, lower and upper bounds.
+
+For more information:
+ - https://datasketches.apache.org/docs/Frequency/FrequencySketches.html
+'''
+) AS R"""
+try {
+ return Module.frequent_strings_sketch.getResult(sketch, error_type, threshold ? threshold : 0);
+} catch (e) {
+ if (e.message != null) throw e;
+ throw new Error(Module.getExceptionMessage(e));
+}
+""";
diff --git a/fi/sqlx/frequent_strings_sketch_merge.sqlx b/fi/sqlx/frequent_strings_sketch_merge.sqlx
new file mode 100644
index 0000000..ac8ec4e
--- /dev/null
+++ b/fi/sqlx/frequent_strings_sketch_merge.sqlx
@@ -0,0 +1,103 @@
+/*
+ * 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.
+ */
+
+config { hasOutput: true }
+
+CREATE OR REPLACE AGGREGATE FUNCTION ${self()}(sketch BYTES, lg_max_map_size BYTEINT NOT AGGREGATE)
+RETURNS BYTES
+LANGUAGE js
+OPTIONS (
+ library=["gs://$GCS_BUCKET/fs_sketch.mjs"],
+ description = '''Merges sketches from the given column.
+
+Param sketch: the column of values.
+Param lg_max_map_size: the sketch accuracy/size parameter as an integer not less than 3.
+Returns: a serialized Frequent Strings sketch as BYTES.
+
+For more information:
+ - https://datasketches.apache.org/docs/Frequency/FrequencySketches.html
+'''
+) AS R"""
+import ModuleFactory from "gs://$GCS_BUCKET/fs_sketch.mjs";
+var Module = await ModuleFactory();
+
+// UDAF interface
+export function initialState(lg_max_map_size) {
+ return { lg_max_map_size: Number(lg_max_map_size) };
+}
+
+export function aggregate(state, sketch) {
+ try {
+ if (state.sketch == null) {
+ state.sketch = new Module.frequent_strings_sketch(state.lg_max_map_size);
+ }
+ state.sketch.merge(sketch);
+ } catch (e) {
+ if (e.message != null) throw e;
+ throw new Error(Module.getExceptionMessage(e));
+ }
+}
+
+export function serialize(state) {
+ if (state.sketch == null) return state; // for transition deserialize-serialize
+ try {
+ // for prior transition deserialize-aggregate
+ // merge aggregated and serialized state
+ if (state.sketch != null && state.serialized != null) {
+ sketch.merge(state.serialized);
+ }
+ return {
+ lg_max_map_size: state.lg_max_map_size,
+ serialized: state.sketch.serializeAsUint8Array()
+ };
+ } catch (e) {
+ if (e.message != null) throw e;
+ throw new Error(Module.getExceptionMessage(e));
+ } finally {
+ state.sketch.delete();
+ }
+}
+
+export function deserialize(serialized) {
+ return serialized;
+}
+
+export function merge(state, other_state) {
+ try {
+ if (state.sketch == null) {
+ state.sketch = new Module.frequent_strings_sketch(state.lg_max_map_size);
+ }
+ if (state.serialized != null) {
+ state.sketch.merge(state.serialized);
+ state.serialized = null;
+ }
+ if (other_state.serialized != null) {
+ state.sketch.merge(other_state.serialized);
+ other_state.serialized = null;
+ }
+ } catch (e) {
+ if (e.message != null) throw e;
+ throw new Error(Module.getExceptionMessage(e));
+ }
+}
+
+export function finalize(state) {
+ return serialize(state).serialized;
+}
+""";
diff --git a/fi/sqlx/frequent_strings_sketch_to_string.sqlx b/fi/sqlx/frequent_strings_sketch_to_string.sqlx
new file mode 100644
index 0000000..2243e0f
--- /dev/null
+++ b/fi/sqlx/frequent_strings_sketch_to_string.sqlx
@@ -0,0 +1,43 @@
+/*
+ * 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.
+ */
+
+config { hasOutput: true }
+
+CREATE OR REPLACE FUNCTION ${self()}(sketch BYTES)
+RETURNS STRING
+LANGUAGE js
+OPTIONS (
+ library=["gs://$GCS_BUCKET/fs_sketch.js"],
+ js_parameter_encoding_mode='STANDARD',
+ description = '''Returns a summary string that represents the state of the given sketch.
+
+Param sketch: the given sketch as sketch encoded bytes.
+Returns: a string that represents the state of the given sketch.
+
+For more information:
+ - https://datasketches.apache.org/docs/Frequency/FrequencySketches.html
+'''
+) AS R"""
+try {
+ return Module.frequent_strings_sketch.toString(sketch);
+} catch (e) {
+ if (e.message != null) throw e;
+ throw new Error(Module.getExceptionMessage(e));
+}
+""";
diff --git a/fi/test/frequent_strings_sketch_test.sql b/fi/test/frequent_strings_sketch_test.sql
new file mode 100644
index 0000000..221fb40
--- /dev/null
+++ b/fi/test/frequent_strings_sketch_test.sql
@@ -0,0 +1,32 @@
+/*
+ * 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.
+ */
+
+select $BQ_DATASET.frequent_strings_sketch_to_string($BQ_DATASET.frequent_strings_sketch_build(str, 1, 5)) from unnest(["a", "b", "c"]) as str;
+
+create or replace table $BQ_DATASET.fs_sketch(sketch bytes);
+
+insert into $BQ_DATASET.fs_sketch
+(select $BQ_DATASET.frequent_strings_sketch_build(str, 1, 5) from unnest(["a", "b", "c", "d"]) as str);
+
+insert into $BQ_DATASET.fs_sketch
+(select $BQ_DATASET.frequent_strings_sketch_build(str, 1, 5) from unnest(["a", "a", "c"]) as str);
+
+select $BQ_DATASET.frequent_strings_sketch_get_result($BQ_DATASET.frequent_strings_sketch_merge(sketch, 5), "NO_FALSE_NEGATIVES", null) from $BQ_DATASET.fs_sketch;
+
+drop table $BQ_DATASET.fs_sketch;
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org