
Seafowl has supported UDFs [for some time now](https://www.splitgraph.com/blog/seafowl-wasm-udfs), and they continue to offer an exciting way for Seafowl users to significantly extend functionality in a fully sandboxed environment. Recently, in response to user request, we added a Golang example.

<ButtonLink href="https://github.com/splitgraph/seafowl-udf-go/">
  See the code
</ButtonLink>

<br />

[See the UDF docs](https://seafowl.io/docs/guides/custom-udf-wasm).

To learn more about compiling Golang to WASM, read on.

## Handling UDF requirements
There are certain requirements incumbent on the UDF implementer when it comes to running UDFs in Seafowl, and Golang is included. Today we cover a partial list:
- reading data in from the host through linear raw memory
- returning the computed result as a msgpack-encoded buffer
- working around Golang default syntax (e.g. TitleCase function exports)
- compiling Golang into WASM

## Reading data in
As discussed previously, when you register a Seafowl UDF it's required to [specify certain parameters](https://github.com/splitgraph/seafowl-udf-go/blob/2e49dd7a110213a7c49b19845cd537a59164c034/create_udf.sh#L11-L16) including e.g. `wasm_export` (e.g. addi64), `return_type` (e.g. BIGINT), `input_types` (e.g. BIGINT).

This is important because raw memory is the medium for passing data between Seafowl and the UDF. By specifying the parameter types upfront at UDF registration time, both Seafowl host and UDF know how to properly encode/decode the data they share with each other. That's why the function [`addi64`](https://github.com/splitgraph/seafowl-udf-go/blob/master/main.go#L12), expects a _pointer to a buffer_ vs conventional Go function params.

## Writing data out
Conversely, when we return the result to Seafowl, we need to return a buffer that includes the length of the result [first](https://github.com/splitgraph/seafowl-udf-go/blob/2e49dd7a110213a7c49b19845cd537a59164c034/udf.go#L115), with the actual msgpack-encoded result appended [afterwards](https://github.com/splitgraph/seafowl-udf-go/blob/2e49dd7a110213a7c49b19845cd537a59164c034/udf.go#L14).

This allows Seafowl's query engine to return the result of the UDF in the typical way.

## TitleCase function export workaround
Golang conventionally uses TitleCase to indicate when a function should be exported from its module scope. Some may find it [cute](https://youtu.be/M3BM9TB-8yA?t=879) and this convention is presumably fine in traditional Golang, but in certain contexts like UDFs, we are required to provide `alloc`/`dealloc` functions _in lower case_ - which poses a fun hurdle.

Fortunately, while researching how `tinygo` works, I learned it supports annotating functions regardless of casing via
`//export $functionName`

For example:
```go
//export alloc
func alloc(size uintptr) unsafe.Pointer {
	...
}
```

And Seafowl will be able to call this function in the required way.

## Compiling Golang into WASM
In August 2023 the Golang team shipped WASI/WASM [support](https://go.dev/blog/go1.21#a-new-port-to-wasi), so the following approach we used may no longer be strictly necessary these days.

When we tackled this project, Golang did not yet support WASM natively so looking elsewhere, we found [Tinygo](https://tinygo.org/docs/concepts/faq/what-is-tinygo/).

It turns out we can generate a WASM module ready for import into Seafowl via:
`tinygo build -o seafowl-udf-go.wasm -target=wasi`

NOTE: it's necessary to include `-target=wasi`.

## Recap

In this post we reviewed some of the steps taken to port the [Rust-based UDF](https://github.com/splitgraph/seafowl-udf-rust) into Golang. This was my first Golang project and I appreciated the opportunity to work at the lower level, learn about byteslice manipulation, msgpack serialization, WASI and more.

If you build a cool UDF, please consider letting us know!


#### Image credits
<ValeIgnore>[liantomtit](https://unsplash.com/@liantomtit), [evanescentlight](https://unsplash.com/@evanescentlight)</ValeIgnore>


We return to the wide world of WASM. In our previous round we implemented a UDF using Rust; today we're porting it to Golang.

Writing UDFs in Golang

[The Splitgraph Console](https://www.splitgraph.com/splitgraph/domestic_us_flights/-/console)
now analyzes the SQL query on the fly and displays the referenced tables in the
sidebar for easier query comprehension. The feature is powered by
[tree-sitter](https://tree-sitter.github.io/tree-sitter/) running in WASM.

<ButtonLink href="https://www.splitgraph.com/query?sqlQuery=SELECT%0A++++%22EmployeeId%22%2C%0A++++%22LastName%22%2C%0A++++%22FirstName%22%2C%0A++++%22Title%22%2C%0A++++%22ReportsTo%22%2C%0A++++%22BirthDate%22%2C%0A++++%22HireDate%22%2C%0A++++%22Address%22%2C%0A++++%22City%22%2C%0A++++%22State%22%2C%0A++++%22Country%22%2C%0A++++%22PostalCode%22%2C%0A++++%22Phone%22%2C%0A++++%22Fax%22%2C%0A++++%22Email%22%0AFROM%0A++++%22demodemo123%2Fchinook-from-sqlite%3A0df8bfcc3c837a68d20be83830af20781f6f6d4515ee0da60b06cc9850c31918%22.%22Employee%22%0ALIMIT+100%3B&id=006102fd-c5ef-47e7-ada3-40a7040006d6&flavor=splitgraph&initial-namespace=demodemo123">
  Try it out live
</ButtonLink>

<br />

Interested in how we got it working? Read on!

[The Splitgraph Console](https://www.splitgraph.com/splitgraph/domestic_us_flights/-/console)
offers an IDE-like experience for interacting with Splitgraph and the data it
exposes. One fundamental feature is
[the query editor](https://www.splitgraph.com/query?sqlQuery=SELECT%0A++++%22EmployeeId%22%2C%0A++++%22LastName%22%2C%0A++++%22FirstName%22%2C%0A++++%22Title%22%2C%0A++++%22ReportsTo%22%2C%0A++++%22BirthDate%22%2C%0A++++%22HireDate%22%2C%0A++++%22Address%22%2C%0A++++%22City%22%2C%0A++++%22State%22%2C%0A++++%22Country%22%2C%0A++++%22PostalCode%22%2C%0A++++%22Phone%22%2C%0A++++%22Fax%22%2C%0A++++%22Email%22%0AFROM%0A++++%22demodemo123%2Fchinook-from-sqlite%3A0df8bfcc3c837a68d20be83830af20781f6f6d4515ee0da60b06cc9850c31918%22.%22Employee%22%0ALIMIT+100%3B&id=006102fd-c5ef-47e7-ada3-40a7040006d6&flavor=splitgraph&initial-namespace=demodemo123).
It resembles a code editor and is used for editing SQL (PostgreSQL, in fact)
queries, rather than files.

The query editor has smart features like:

- autocomplete

  We use [`pgcli`](https://pypi.org/project/pgcli/) on the backend to retrieve
  the completions.

- syntax highlighting

  We use
  [the SQL Monaco language configuration](https://github.com/microsoft/monaco-editor/blob/38e1e3d097f84e336c311d071a9ffb5191d4ffd1/src/basic-languages/sql/sql.ts),
  which uses
  [the Monarch library](https://microsoft.github.io/monaco-editor/monarch.html)
  under the hood.

One interesting feature we wanted to have was to introspect the query and
display the tables it references. This would let the user quickly understand and
interact with a subset of repositories and tables, rather than all repositories
and tables within some namespace.

We implemented this feature using
[tree-sitter](https://tree-sitter.github.io/tree-sitter/) compiled to WASM
([web-tree-sitter](https://github.com/tree-sitter/tree-sitter/tree/master/lib/binding_web))
so the parsing happens within the user's browser. The rest of this article
outlines the problems faced and the decisions we took to get the feature
working.

## Parsing in the browser or on the server

The first question we had to answer was whether the parsing process should
happen in the browser, like our syntax highlighting, or on the server, like our
autocomplete.

There are pros and cons to both approaches:

- parsing in the browser has a higher initial cost (fetching and initializing
  the parser), but offers faster feedback during editing, and transfers less
  data during long editing sessions

- the browser can only execute JavaScript or WASM. The parser would have to be
  compiled to either of these languages. This limits our choices, as we cannot
  run arbitrary existing parsers.

- either the browser or the server have to do more work to parse the query. For
  in-browser parsing, this could be slow for low-end devices. For server
  parsing, we could DDoS our servers by having many users ask for parsing of
  their queries.

At this point, either approach would work. We had a slight preference for doing
in-browser parsing for its lower latency and being able to use the parsed AST
for more features in the future.

## Existing SQL parsers

Parsing SQL is a popular problem which has many solutions in various languages.

### libpg_query and its bindings

[libpg_query](https://github.com/pganalyze/libpg_query) is a C library for
parsing PostgreSQL. It uses the same code that the PostgreSQL server uses. This
makes the parsing the most accurate and spec-compliant.

There are bindings for using libpg_query in other languages:

- [pgsql-parser](https://github.com/pyramation/pgsql-parser) for Node.js
- [pg-query-emscripten](https://github.com/pganalyze/pg-query-emscripten) for
  WASM (available in the browser)
- [pg_query.rs](https://github.com/pganalyze/pg_query.rs) for Rust

  Trivia: this is what
  [Supabase's postgres_lsp](https://github.com/supabase/postgres_lsp) uses to
  parse pgSQL.

#### The importance of syntax error recovery

One major downside behind using any library based on `libpg_query` is that it
has no syntax error recovery when the query contains syntax errors. If the
parser encounters an error, it does not attempt to parse the rest of the code.
It all comes down to
[libpg_query having a single `error` field per parse tree](https://github.com/pganalyze/libpg_query/blob/9b21e3295402a0d0ee9a50c468d426c2dbb73ee6/src/pg_query_internal.h#L14).

This makes it unsuitable for usage in code editors. When editing, most of the
time the code has a syntax error, because the user is still typing the word, or
is editing some more complex statement.

For example, given the following query:

```sql
SELECT
    "gid",
    "state"
FROM
    "splitgraph/election-geodata:79724cbf5dcd2b260ac0d60e58135123d527ff4d2e1dc709f6da47fa8f4ee71f"."nation"
LIMIT 100;
```

When the user wants to select one more column in a `SELECT` statement:

```sql
SELECT
    "gid",
    ,
    -- look, a syntax error. There cannot be a trailing comma above
    "state"
FROM
    "splitgraph/election-geodata:79724cbf5dcd2b260ac0d60e58135123d527ff4d2e1dc709f6da47fa8f4ee71f"."nation"
LIMIT 100;
```

we should still be able to parse the query and know it references
[splitgraph/election-geodata](https://www.splitgraph.com/splitgraph/election-geodata/-/console)
despite the query having a syntax error.

This makes syntax error recovery a must-have for our parser.

### sql-parser from sql-language-server

[sql-parser](https://github.com/joe-re/sql-language-server/tree/release/packages/sql-parser)
is a JavaScript parser implemented using [Peggy](https://peggyjs.org/) (a
JavaScript parser generator). It is part of the
[sql-language-server](https://github.com/joe-re/sql-language-server).

Lack of syntax error recovery disqualifies this library. It also did not support
using schemas in table names (e.g. `"splitgraph/election-geodata"."nation"` was
considered a syntax error, but `"splitgraph/election-geodata"` was not).

### tree-sitter

[tree-sitter](https://tree-sitter.github.io/tree-sitter/) is a parser generator.
The generated parsers include syntax error recovery. When there is a syntax
error, only a few AST nodes get marked as `ERROR`, but the rest of the code is
parsed like normal. It also supports incremental parsing. This means doing a
re-parse of the code after editing it is more efficient than parsing from
scratch if only we provide tree-sitter the previous AST and the description of
the modified range of code.

Both of these qualities make tree-sitter well-suited for code editors. In fact,
it is used in [neovim](https://neovim.io/doc/user/treesitter.html),
[Atom](https://neovim.io/doc/user/treesitter.html),
[Emacs](https://lists.gnu.org/archive/html/emacs-devel/2022-11/msg01443.html),
and [Helix](https://helix-editor.com/), to name a few. Tree-sitter also powers
basic IDE operations in web versions of VSCode (like <https://vscode.dev/>)
thanks to
[the vscode-anycode extension](https://github.com/microsoft/vscode-anycode). It
also powers parsing of bash in
[the bash-language-server](https://github.com/bash-lsp/bash-language-server/blob/f2c7447929bd0ab20f37ec5a44719430aa111d14/server/src/analyser.ts#L74).

See
[Introduction to tree-sitter](https://teknologiumum.com/posts/introductory-to-treesitter)
for a more detailed description of what tree-sitter can do.

Tree-sitter has bindings in many languages. The ones relevant to us are:

- [web-tree-sitter](https://github.com/tree-sitter/tree-sitter/tree/master/lib/binding_web)
  for WASM,
- [node-tree-sitter](https://github.com/tree-sitter/node-tree-sitter) for
  Node.js.

As for the grammar,
[tree-sitter-sql](https://github.com/DerekStride/tree-sitter-sql/) is a
well-maintained SQL grammar used in Neovim. In our testing, it successfully
parsed the pgSQL we threw at it, and the parts it stumbled on were fixed in just
a handful of days.

All of the above led us to decide tree-sitter is the right choice for parsing
pgSQL in the Console.

## Extracting referenced tables from the query

Tree-sitter parses the query into an AST.
[The corpus tests of the grammar](https://github.com/DerekStride/tree-sitter-sql/blob/main/test/corpus/select.txt)
show the stringified AST node types. Now the challenge becomes extracting the
referenced tables from that AST.

Neovim's `:InspectTree` command is extremely useful at understanding the AST
while interactively editing code.

![Neovim with the source query in the left window and the parsed AST in the
right window. The `relation` AST node is selected in the AST window and the
table reference is highlighted in the query.](/static-v2/images/blog/parsing-pgsql-with-tree-sitter/tree-sitter-inspect-tree-parsed-ast.png)

Here we can also see the AST parsed from a query that has a syntax error.



![Neovim with the source query in the left window and the parsed AST in the
right window. There is a syntax error in the query, but the parsed AST still contains a `relation`.](/static-v2/images/blog/parsing-pgsql-with-tree-sitter/tree-sitter-inspect-tree-error-recovery.png)



Tree-sitter also supports
[declaratively querying the AST](https://tree-sitter.github.io/tree-sitter/using-parsers#pattern-matching-with-queries)
using queries written as
[S-expressions](https://en.wikipedia.org/wiki/S-expression). It takes away the
burden of walking the AST and looking for subtrees that match a certain shape.
We ended up with the following query to capture the referenced tables:

```txt
(
  relation (
    (
      object_reference
      schema: (identifier)
      name: (identifier)
    ) @reference
  )
)
```



![Neovim with the source query in the left window, the parsed AST in the
right-top window, and the tree-sitter query playground in the right-bottom. The matched `relation` AST node and source code is highlighted.](/static-v2/images/blog/parsing-pgsql-with-tree-sitter/tree-sitter-playground-relation-query.png)



This query ended up capturing the table reference we care about.

### Extracting parts of a table reference

Tree-sitter gives us back the table reference as a string like
`"splitgraph/election-geodata:79724cbf5dcd2b260ac0d60e58135123d527ff4d2e1dc709f6da47fa8f4ee71f"."nation"`.
Now it is our job to extract the namespace, repository name, image tag, and the
table name from this reference.

This felt like a good job for a regular expression. We ended up with the
following one and wrote a bunch of test cases to make sure it also tolerates
errors (e.g. a missing table name at the end when the user is still typing it):

```ts
const tableReferenceRegExp = /^"((?<namespace>[^/]+)?)(\/((?<repositoryName>[^":]+)?)(:((?<imageTag>[^"]+)?))?"?(\."?((?<tableName>[^"]+)?)"?)?)?$/;
```

It uses
[named capturing groups](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Regular_expressions/Named_capturing_group)
to make extracting the reference parts easier.

## Result

Tying these pieces together, the Splitgraph Console query editor now supports
displaying referenced tables in the sidebar as a tree. It updates nearly
instantly. We added a debounce to avoid updating the UI so often.

![Splitgraph Console query editor with referenced tables shown in the sidebar.](/static-v2/images/blog/parsing-pgsql-with-tree-sitter/splitgraph-console-with-referenced-tables.png)

We found that the tree-sitter parsing process usually takes less than 1ms on a
laptop. Using 6x CPU throttling in Chrome still leads to a usable UI.

<video width="100%" height="360" controls>
  <source
    src="/static-v2/demo-videos/query-editor-parsing-referenced-tables.mp4"
    type="video/mp4"
  />
</video>

## Check it out

Boost your SQL writing experience with live query introspection.

<ButtonLink href="https://www.splitgraph.com/query?sqlQuery=SELECT%0A++++%22EmployeeId%22%2C%0A++++%22LastName%22%2C%0A++++%22FirstName%22%2C%0A++++%22Title%22%2C%0A++++%22ReportsTo%22%2C%0A++++%22BirthDate%22%2C%0A++++%22HireDate%22%2C%0A++++%22Address%22%2C%0A++++%22City%22%2C%0A++++%22State%22%2C%0A++++%22Country%22%2C%0A++++%22PostalCode%22%2C%0A++++%22Phone%22%2C%0A++++%22Fax%22%2C%0A++++%22Email%22%0AFROM%0A++++%22demodemo123%2Fchinook-from-sqlite%3A0df8bfcc3c837a68d20be83830af20781f6f6d4515ee0da60b06cc9850c31918%22.%22Employee%22%0ALIMIT+100%3B&id=006102fd-c5ef-47e7-ada3-40a7040006d6&flavor=splitgraph&initial-namespace=demodemo123">
  Try it now
</ButtonLink>

<br />

---

## Bonus: supabase/postgres_lsp discussion

As we were working on integrating tree-sitter in the Splitgraph Console,
Supabase was working on the
[postgres_lsp](https://github.com/supabase/postgres_lsp), a language server for
PostgreSQL.

Creating a language server involves much more work than just the parser. It can
provide diagnostics, autocomplete, semantic highlighting, code actions, "Go to
definition", and
[many other features](https://microsoft.github.io/language-server-protocol/specifications/lsp/3.17/specification/#languageFeatures).

The parser is still at the core of a language server. Omitting error recovery
from the parser used in a language server can lead to frustrating experience for
the users.

For example, with semantic highlighting, the user will have a jarring experience
if the query stops being highlighted each other keystroke due to intermittent
parsing errors.

Autocomplete also is problematic to get working when suggestions are only
available when the query is valid. Most of the time the user will request
suggestions for a half-written query, which, most likely, is not a valid query
yet. If the server does not implement syntax error recovery during parsing, it
will keep yielding empty or wrong suggestions.

TypeScript server (`tsserver`) which is used in the TypeScript Language Server,
has advanced syntax error recovery which offers stellar TypeScript authoring
experience. Syntax error recovery is heavily integrated into the parser, for
example:

- [nodes are annotated when surrounding nodes have errors](https://github.com/microsoft/TypeScript/blob/b4cd9d8fdd1a3a9a8324069a7a6f4336538aa688/src/compiler/parser.ts#L1578),
- [missing nodes are created when there are errors in the AST](https://github.com/microsoft/TypeScript/blob/b4cd9d8fdd1a3a9a8324069a7a6f4336538aa688/src/compiler/parser.ts#L2582),
- [parsing functions are aware whether the parser is in "error recovery" mode](https://github.com/microsoft/TypeScript/blob/b4cd9d8fdd1a3a9a8324069a7a6f4336538aa688/src/compiler/parser.ts#L2785)
  and adjust their behavior.

At the time of writing this article (2023-08-09), postgres_lsp employs some
measures to handle syntax errors returned by
[pg_query.rs](https://github.com/pganalyze/pg_query.rs)
([source](https://github.com/supabase/postgres_lsp/blob/1250f5ed14a0e86b2b7fa581214284c67b960621/crates/parser/src/statement.rs#L123)).
Their LSP is still at a very early stage and only supports semantic highlighting
(and keeps crashing quite often), which makes it hard to assess. We are very
interested to see if using a parser with no syntax error recovery as a base will
be a viable solution.

That said, we are extremely excited that there is development in this space.

We used tree-sitter to show the tables referenced in the query inside the Splitgraph Console.

Parsing pgSQL with tree-sitter in WASM


## Measuring Urbanness

Sometimes a hard-to-measure property has significant impact on performance. For example, it's safe to assume sexier lingerie sells better,
but devising an algorithm to classify the "sexiness" of an article of clothing based on its design is far from trivial.

Another ill-defined quality impacting countless more measurable metrics is "urbanness", an individual's preference for densely or sparsely populated areas.
All sorts of trends, from [voting patterns](https://government.cornell.edu/news/exploring-widening-chasm-between-urban-and-rural-voters),
to life expectancy and religious affiliation all have marked differences in urban versus rural populations.

Statistically, it makes sense to classify someone as urban or rural based on their current residence, regardless of where they may have lived in the past.
On an individual level, it's not always so clear-cut. I currently live in a city with a population of over 1.5 million,
but I've also lived in a small town (less than 4000 residents). Today, a census would classify me as urban, but is that who I really am?

I decided to find out using photo location data. Smartphones usually encode the longitude and latitude in the EXIF data of photographs.
Over the years, I've collected thousands of photos (21808 to be exact), enough to give me a representative sample of where I prefer to spend my time.

## Classifying locations

The geometric center of a city is not always its most densely populated spot. What's a better proxy for "urbanness"?

If urban individuals are those who choose to spend their time in the city, areas offering many places to "hang out" are probably ideal locations for spotting urbanites.
Conversely, if one frequents such areas, chances are they can be labelled as urban. And what could possibly be a more urban place to hang out than the largest coffeehouse chain in the world, Starbucks?

Following in the footsteps of [Golden Arches Theory of Conflict Prevention](https://en.wikipedia.org/wiki/The_Lexus_and_the_Olive_Tree#Golden_Arches_theory),
let's define the equally tongue in cheek **Omnipresent [Siren](https://stories.starbucks.com/stories/2016/who-is-starbucks-siren/) Metric of Urbanness** (OSM) as the number of Starbucks locations within 2 kilometers of any given point on the globe.

Conveniently, there's a dataset of Starbucks locations [which can be downloaded from Kaggle](https://www.kaggle.com/datasets/starbucks/store-locations?resource=download), which I used to classify my photos by this metric.

## Loading photo coordinates

An easy way to extract EXIF metadata from images is to let Google Photos do it for you. For users of Google Photos, [Google Takeout](https://takeout.google.com/) offers a way to download photos along with their EXIF data extracted to separate JSON files.
Although not covered here, it's also possible to read location data (and much more) directly from images using [exiftool](https://exiftool.org/).

After downloading and extracting the Google Takeout archives, I ran the following to get a CSV file with the coordinates of each photo:

```bash
# enter Google Photos directory within Takeout directory
cd 'Takeout/Google Photos'
# extract image metadata from JSON files
find 'Photos from'* -name '*.json' -exec jq -c '{latitude: .geoData.latitude, longitude: .geoData.longitude, timestamp: .photoTakenTime.timestamp, filename: input_filename}' {} >> unfiltered_image_attributes.ndjson \;
# only keep image metadata with GPS data (non-smartphone cameras don't write location data)
grep -v '{"latitude":0,' unfiltered_image_attributes.ndjson  > filtered_image_attributes.ndjson
# write CSV header
echo "latitude,longitude,timestamp,filename" > photo_attributes.csv
# write CSV data
jq -r '([.latitude, .longitude, .timestamp, .filename]) | @csv' < filtered_image_attributes.ndjson >> photo_attributes.csv
```

## Loading data into Seafowl

Seafowl has great CSV support. To see it in action, [install Seafowl](https://seafowl.io/docs/guides/installing) if you haven't yet, then run:

```bash
curl -v -F "data=@starbucks_directory.csv" "http://localhost:8080/upload/public/starbucks_directory"
curl -v -F "data=@photo_attributes.csv" "http://localhost:8080/upload/public/photo_attributes"
```

Note that I changed the CSV header of the [Kaggle Starbucks dataset](https://www.kaggle.com/datasets/starbucks/store-locations?resource=download) for more convenient querying to:
```
brand,store_number,store_name,ownership_type,street_address,city,state,country,post_code,phone_number,timezone,longitude,latitude
```

## Calculating distances

Seafowl doesn't come with built-in functions for calculating the distance between two points on the planet,
but fortunately there is an excellent [Rust library](https://docs.rs/geoutils/latest/geoutils/) we can use.

To call it from Seafowl queries, we must create a user-defined function (UDF) and compile it to [WebAssembly](/blog/seafowl-wasm-udfs).
The code for the UDF is available [on GitHub](https://github.com/splitgraph/seafowl-udf-geo).

After running the [`create_udf.sh`](https://github.com/splitgraph/seafowl-udf-geo/blob/main/create_udf.sh) script, the previously unavailable `distance()` function may be used in queries
like so:

```sql
-- calculate the distance between Berlin and Paris in meters
-- distance(longitude_1, latitude_1, longitude_2, latitude_2) -> distance in meters
SELECT distance(52.5200, 13.4050, 48.8566, 2.3522)
```
We're ready to start classifying our photo collection by the Omnipresent Siren Metric!

## Calculating proximity: the naive approach

A simple way to calculate nearby Starbucks count for each photo is to find the distance to each Starbucks, then filter out distant Starbucks in the `WHERE` clause:

```sql
SELECT
    filename,
    COUNT(0) AS nearby_starbucks_count
FROM (
    SELECT
        filename,
        photo_lat,
        photo_lon,
        starbucks_lat,
        starbucks_lon,
        distance(photo_lat, photo_lon, starbucks_lat, starbucks_lon) as dist
    FROM (
        SELECT
            filename,
            latitude as photo_lat,
            longitude as photo_lon
        FROM photo_attributes
    ) p
    JOIN (
        SELECT
            latitude as starbucks_lat,
            longitude as starbucks_lon
        FROM starbucks_directory
    ) s ON true
) t
WHERE t.dist < 2000 -- distance is in meters, in this case a 2km radius
GROUP BY 1
ORDER BY 2
```

One of the great advantages of using an SQL database is that we can ask how a query will be executed with the `EXPLAIN SELECT ...` statement.
The logical plan for this query is:

```
Sort: nearby_starbucks_count ASC NULLS LAST
  Projection: t.filename, COUNT(Int64(0)) AS nearby_starbucks_count
    Aggregate: groupBy=[[t.filename]], aggr=[[COUNT(Int64(0))]]
      Projection: t.filename, alias=t
        Projection: p.filename, alias=t
          Filter: distance(p.photo_lat, p.photo_lon, s.starbucks_lat, s.starbucks_lon) < Float64(2000)
            CrossJoin:
              Projection: p.filename, p.photo_lat, p.photo_lon, alias=p
                Projection: photo_attributes.filename, photo_attributes.latitude AS photo_lat, photo_attributes.longitude AS photo_lon, alias=p
                  TableScan: photo_attributes projection=[filename, latitude, longitude]
              Projection: s.starbucks_lat, s.starbucks_lon, alias=s
                Projection: starbucks_directory.latitude AS starbucks_lat, starbucks_directory.longitude AS starbucks_lon, alias=s
                  TableScan: starbucks_directory projection=[latitude, longitude]
```

Notice the `CrossJoin` (also called Cartesian product)! It's the type of join between two tables where every row in table A is joined with every row in table B.
The resulting table will have a total row count of `rows in A * rows in B`.
The `distance()` function is pretty fast: a single call returns in 5-6 microseconds on my laptop. Even so, calculating all `25600 * 21808 = 558284800` distances took me about an hour.
Can we do better?

## Calculating proximity: using pre-filtered pairs

Calculating the precise distance between two points on a globe is more complex than on a plane.
Still, we can use a rough heuristic to filter out photo - Starbucks pairs which are obviously much farther away than 2 km.
At the equator, one degree latitude / longitude corresponds to 111km. I've never been so close to the poles that 2 degrees would be less than 2km apart, so any Starbucks
more than two degrees latitude or longitude away from the photo's location will surely be out of the 2km range.

### Pre-filtering pairs
First, I created a table of candidate pairs based on differences in latitude and longitude:

```sql
CREATE TABLE filtered_pairs_less_than_2_degrees_apart AS WITH
    all_pairings AS (
        SELECT
                filename,
                photo_lat,
                photo_lon,
                starbucks_lat,
                starbucks_lon,
                ABS(photo_lat - starbucks_lat) AS diff_lat,
                ABS(photo_lon - starbucks_lon) AS diff_lon
        FROM (
            SELECT
                filename,
                photo_lat,
                photo_lon,
                starbucks_lat,
                starbucks_lon
            FROM (
                SELECT
                    filename,
                    latitude as photo_lat,
                    longitude as photo_lon
                FROM photo_attributes
            ) p
            JOIN (
                SELECT
                    latitude as starbucks_lat,
                    longitude as starbucks_lon
                FROM starbucks_directory
            ) s ON true) r
    )
SELECT *
FROM all_pairings
-- A difference of 2 degrees or more latitude or longitude will definitely
-- result in more than 2 kilometers between the points in the range we're
-- working with.
WHERE diff_lat < 2.0 AND diff_lon < 2.0;
```

The `filtered_pairs_less_than_2_degrees_apart` table has 687911 rows, less than 1% of the rows resulting from the cross join in the previous query.

### Calculating the distance of candidate pairs
The following query filters the pairs further based on the precise distance:

```sql
CREATE TABLE filtered_pairs_less_than_2_km_apart AS SELECT * FROM (
    SELECT
        filename,
        photo_lat,
        photo_lon,
        starbucks_lat,
        starbucks_lon,
        distance(photo_lat, photo_lon, starbucks_lat, starbucks_lon) as dist
    FROM filtered_pairs_less_than_2_degrees_apart) t
-- Filter the list according to the actual distance in meters, so
-- < 2000 results in a 2km radius.
WHERE t.dist < 2000;
```

This second filter throws out over 94% of the rows in the `filtered_pairs_less_than_2_degrees_apart` table, leaving only
Starbucks locations within the 2km radius of each photograph.

The `filtered_pairs_less_than_2_km_apart` table contains 39715 rows, the same number we got with the original hour-long calculation, but the two
`CREATE TABLE` queries take a total of 15.1 seconds, less than 1% of the original runtime.

## My most urban photograph

There's a clear winner among the 21808 contestants for "most urban" photo, with an OSM of 68:

![Sheep in Shanghai](/static-v2/images/blog/20221209-seafowl-geo-distance-udf/IMG_6092.JPG)

Directing the [Starbucks Store Locator](https://www.starbucks.com/store-locator?map=31.232686,121.460572,15z) to the coordinates where the photo was captured helps explain why.
Considering Shanghai has the most Starbucks locations of any city on Earth, more than double that of Seoul at second place, it's not surprising that my "winning" photo was taken there.

## How urban am I

To find out, I needed the number of photographs for each OSM score:

```sql
-- query.sql
SELECT
    nearby_starbucks_count,
    COUNT(0) as num_photos
FROM (
    SELECT
        filename,
        COUNT(0) AS nearby_starbucks_count
    FROM filtered_pairs_less_than_2_km_apart
    GROUP BY 1
) t
GROUP BY 1
ORDER BY 1 ASC;
```

I used the following bash command to get the results of the query as CSV with the help of `jq`:

```bash
curl  -H "Content-Type: application/json" http://localhost:8080/q -d@- << END |
{"query": $(cat "query.sql" | jq -Rsa .)}
END
jq -r '[.nearby_starbucks_count, .num_photos] | @csv' > photos_by_osm.csv
```

Using the [Node.js Seafowl client](https://github.com/splitgraph/seafowl/blob/main/examples/clients/node/seafowl-client.js) is also an option:

```bash
seafowl/examples/clients/node/seafowl-client.js -f filtered_step3_simplified_osm_histogram.sql | tail -n +2 | jq -r '.[] | [.nearby_starbucks_count, .num_photos]' | @csv > photos_by_osm.csv'
```

With most of my photos having an OSM of 0, the answer seems to be that I'm not very urban, especially when compared to someone who feels at home in Shanghai:

![Number of photos by OSM](/static-v2/images/blog/20221209-seafowl-geo-distance-udf/number_of_photos_by_osm.svg)

## Urbanness over time

If "urbanness" is an innate quality unlikely to change much once our adult personality has developed, any reliable indicator should be pretty stable over time.
Looking at the number of photos I've taken with OSM ≥ 1 each month makes it seem like that is indeed the case.

![OSM ≥ 1 photo count by month](/static-v2/images/blog/20221209-seafowl-geo-distance-udf/osm_gte_1_photo_count_by_month.svg)

The exception is a trip to Shanghai in October of 2015 when I took the picture with the plastic sheep shown above.

## Conclusion

It was fun analyzing where I've taken photos over the last decade. Seafowl has been a convenient tool throughout the process:
- CSV import made it easy to work with data from [Kaggle](https://www.kaggle.com/datasets/starbucks/store-locations?resource=download) and Google Photos.
- We can easily extend Seafowl's builtin functions with [our own UDFs](https://github.com/splitgraph/seafowl-udf-geo).
- JSON output is convenient in most cases and can easily be converted to CSV using `jq` when necessary.

I look forward to all the cool stuff people build with this fast new database!


I used Seafowl to analyze how much of a city slicker I am—with geographic user-defined WASM functions and caffeine addiction!

Deciding if I'm urban with WebAssembly and Seafowl


## Do we really need User-Defined Functions?

User-defined functions (UDFs) are bits of application-specific logic which can be invoked within database queries, extending the builtin capabilities of the database.
You might be wondering why not keep application-specific logic in the _application_ layer? Are user-defined functions (UDFs) the relic of a past when databases were designed to be directly queried by end-users?

Far from it! Placing domain-specific logic in the database is often the best (sometimes only) way to implement functionality such as:
- Security policies such as PostgreSQL's [RLS feature](https://www.postgresql.org/docs/current/ddl-rowsecurity.html), which rely on UDFs to enforce application-specific security policies.
- Custom aggregation functions similar to `MIN`, `MAX` and `AVG` which must run within the database to avoid shipping the entire set of input rows to the client to calculate output.
- General, application-independent domain specific capabilities such as working with JSON fields, calculating geographical distances or full text search, extending the core DB's capabilities without having to modify the database itself.
- Finally, if raw and cleaned data live in the same database, it makes sense to use the database to transform that data with tools like [dbt](https://www.getdbt.com/) instead of passing it through a separate process -- and UDFs might be needed to implement some special functionality for that. [^1]

UDFs are an essential building block supported by the majority of databases one way or another, and in this regard Seafowl is no exception. What makes Seafowl special is its commitment to running "at the edge": as close to the user as possible, which means pretty much anywhere.
But if Seafowl is to run _anywhere_, UDFs referenced by Seafowl queries should be just as portable.
How can Seafowl offer UDF authors a platform which makes this possible?

## Platforms

Like any program, a UDF targets a specific platform. This platform should be hardware-independent so UDFs keep working if the database is moved to a different machine, but also efficient enough to process large datasets in acceptable time.

Mature databases often have a custom language for defining UDFs such as [PostgreSQL's PL/PGSQL](https://www.postgresql.org/docs/current/plpgsql.html) or [PL/SQL](https://www.oracle.com/database/technologies/appdev/plsql.html).
For simple functions just beyond the capabilities of an SQL statement, these languages offer an ideal solution.
For more complex functionality or code with lots of dependencies, many developers choose a general programming language, preferably one used in the application layer.

PostgreSQL and Redis both support authoring UDFs in Lua, for example. As a high-level language,
Lua abstracts away the lower layers of the stack such as the CPU's instruction set or the flavor of the C standard library.
Instead, the platform becomes the Lua virtual machine and standard library.
Lua is designed to be embedded in the host process, allowing scripts to efficiently invoke native functions exposed by the host.
It isn't the only scripting language embedded in databases. PostgreSQL for example supports many scripting languages including javascript and python.
While the source of the UDF may be portable, Lua, Javascript, Python, Ruby rely on native modules typically written in C or C++ for performance-intensive code such as crypto libraries.
These modules are co-located with the database and must be recompiled for each architecture supported by the database, limiting the portability of UDFs using these functions.

Custom logic written in compiled languages such as C++, Rust or Java is more difficult to invoke from a native database process, requiring
either running the UDF in a separate process or compiling against the C ABI of the database and executing it with full access to the database.
The security implications of the second option rule out this approach for UDFs.

Inter-process communication (IPC) with a separate JVM process provides a portable solution supported by [Oracle](https://docs.oracle.com/cd/B19306_01/java.102/b14187/chfive.htm) and [IBM DB2](https://www.ibm.com/docs/en/db2-for-zos/11?topic=java-stored-procedures-user-defined-functions),
but introduces a performance penalty for each UDF invocation along with additional corner cases arising from the need to synchronize a JVM process with the database.
For example, should updating the Java bytecode for a UDF impact running transactions?
If not, how many versions of the UDF must be kept in memory and how should the database keep track of which is the current version in each transaction?
When is it safe to remove classes upon which a previous version of the UDF depends?
If a transaction defining a UDF is rolled back, which classes' bytecode needs to be ejected from the JVM?
The list goes on and on, and it's mostly independent of Java, stemming instead from the marriage of a transactional database and another process which dynamically loads UDF code.

To summarize, there's hardly a silver bullet: each solution for providing UDFs has its pros and cons.
Worse, none of the solutions considered so far are truly portable in the sense that they can be used in the browser, on dedicated servers and desktops without serious limitations.

## Enter WebAssembly

Predating Seafowl and Splitgraph by decades, developers of large native applications faced a similar conundrum.
As new devices and platforms appeared, customers wanted to run their applications in previously unsupported environments.
Porting existing applications to new platforms was the traditional remedy, a slow and expensive process.

In the 90s, Java tried to address this problem, promising developers they could "write once, run everywhere".
As Java eventually found success in the very different niches of backend services and Android devices,
its early focus on "running everywhere" understandably changed to working best where it's used.

With the explosion of web apps, the browser appeared as yet another platform for applications to support, albeit a highly unusual one:
instead of a CPU instruction set, developers were to target a high level language, JavaScript.
Garbage collection came with the package, but integers were out (JavaScript has only floating point numbers).
Being so different from other platforms, porting existing applications to the web seemed more difficult than a complete rewrite in many cases.

Even green field projects struggled to find a stack sufficiently portable and efficient to ensure the application's long-term growth in desktop, mobile and browser environments.

As the performance of computers in general and JavaScript engines in particular improved, it became feasible to emulate a CPU in JavaScript.
A single C/C++ codebase could now be compiled to run natively on desktops or mobile devices, but also run in the browser with [emscripten](https://emscripten.org/), which targeted the javascript-powered CPU emulator.
It was hacky, but it worked and the world started to [take notice](https://kripken.github.io/mloc_emscripten_talk/#/).

With growing demand for efficiently running compiled code in the browser, Chrome, Firefox and Safari started to include new virtual machine called WebAssembly (WASM), very different from the high-level javascript VM:
- It wasn't optimized for a specific programming language like V8 or the JVM.
- It doesn't support sophisticated just-in-time compilation.
- It doesn't even have a garbage collector.

Instead, the WebAssembly specification provides a limited set of low-level instructions and linear memory model.
Thanks to the relative ease of implementation, today there are [many](https://wasmer.io/) [high](https://wasmedge.org/) [quality](https://github.com/wasm3/wasm3) [implementations](https://wasmtime.dev/), allowing code targeting WebAssembly to run
anywhere from embedded devices to [browsers](https://developer.mozilla.org/en-US/docs/WebAssembly), [CDNs](https://blog.cloudflare.com/announcing-wasi-on-workers/), and yes- in [databases](https://seafowl.io/docs/guides/custom-udf-wasm) as well.

## WebAssembly as a platform for UDFs

How does WebAssembly as a platform for implementing UDFs compare to scripting languages like Lua or more traditional compiled solutions like Java or C?
Since WebAssembly is designed to be used in very diverse environments, it cannot afford to make many assumptions:
- Memory is a sequence of bytes: there is no support for typed memory.
- As mentioned earlier, there is no garbage collector.
- WebAssembly code has no access to host process resources such as the filesystem, `stdout` or environment variables unless explicitly provided via functions that the WASM module can call at runtime.
- Catering to multi-tenant scenarios, hosts have find-grained control over how much computational power they grant a WASM function.
- The builtin types are limited to 32 and 64 bit floating point and integer numbers, bytes and booleans.

That last point presents a significant challenge when using WebAssembly for authoring UDFs. Many of the [types](https://seafowl.io/docs/reference/types) supported by Seafowl such as `TEXT` and `DECIMAL`
cannot be simply represented solely by scalar numeric values.

One option is to limit UDFs to consuming and returning types natively supported by WebAssembly (this is [ScyllaDB's approach](https://www.scylladb.com/2022/04/14/wasmtime/)).

For Seafowl's UDFs, we wanted users to be able to work with any datatype including strings, decimal numbers and dates.

In WebAssembly, memory is just a sequence of bytes and pointers are just 32 bit integers, similar to an array index.
Any object which can be serialized to a byte stream can be passed by the host to a WebAssembly function by first writing the serialized bytes to WASM memory,
then invoking the function with a pointer to the freshly written memory address as its argument.
Similarly, the WASM function can serialize it's output as a byte stream to which it returns a pointer.

Seafowl uses [MessagePack](https://msgpack.org/index.html) for serialization - think of it like a faster binary version of JSON.

## We're just getting started

Today, Seafowl supports creating UDFs in any programming language which compiles to WASM. Check out our [Rust example UDF repository](https://github.com/splitgraph/seafowl-udf-rust)! Any Seafowl type may be used for input values and return type.

One of the biggest advantages of using UDFs is aggregated records _within the database_. As of 2022 December, Seafowl does not yet support user-defined aggregation functions, but this support is planned. When it does arrive, you can be sure it will also use WebAssembly!

[^1]: There's an interesting discussion on this approach in this [Hacker News thread](https://news.ycombinator.com/item?id=33874842).


How can Seafowl users extend the database's builtin capabilities in a safe, portable and efficient way? The answer is WebAssembly, read on to learn how!

Splitgraph has been acquired by EDB! Read the blog post.

wasm

Writing UDFs in Golang

Parsing pgSQL with tree-sitter in WASM

Deciding if I'm urban with WebAssembly and Seafowl

Extending Seafowl with WebAssembly

Product

Support

Company

Splitgraph

Splitgraph has been acquired by EDB! Read the blog post.

wasm

Writing UDFs in Golang

Parsing pgSQL with tree-sitter in WASM

Deciding if I'm urban with WebAssembly and Seafowl

Extending Seafowl with WebAssembly

Product

Support

Company

Community

Splitgraph