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:49 UTC

(datasketches-bigquery) branch fs_sketch created (now e05645a)

This is an automated email from the ASF dual-hosted git repository.

alsay pushed a change to branch fs_sketch
in repository https://gitbox.apache.org/repos/asf/datasketches-bigquery.git


      at e05645a  frequent strings sketch

This branch includes the following new commits:

     new e05645a  frequent strings sketch

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.



---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org


(datasketches-bigquery) 01/01: frequent strings sketch

Posted by al...@apache.org.
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