Filter and reducer queries

[jb55]

To enable algorithms and aggregation queries, we need a new concept: filters and reducers.

We should implement cursors first as it may simplify this design:

• Cursors #34

Filters

The simplest thing that we should implement first is filters. This would allow you to perform a nostr query, filtering notes based on arbitrary conditions.

The reason we want this inside the query engine is mainly for memory and efficiency reasons. If the query is acting across thousands of records, we shouldn't need to pull everything out of the database to act on it.

This becomes increasingly important in cursor queries, allowing you to filter as your query walks along an index.

Example

An example filter query could be (in pseudocode):

{"kinds":[1], "filter": "pubkey_trust_score(note.pubkey) > 5"}

Where filter is a nostrscript. Of course in nostrdb, we don't need to pass this in the filter itself, we can just pass it as an argument to the query. In the future this could be a wasm nostrscript.

Reducers/Folds

See: https://en.wikipedia.org/wiki/Fold_(higher-order_function)

An even more powerful concept is allowing reducers instead of a filter. Reducer allow you to accumulate a value during a query. For example:

{"kinds":[1], "reducer": {"code": "$acc + 1", "init": 0}}

This would implement a count of the number of kind 1 notes in your database.

you can implement a filter from a reducer, so it is more general:

{"kinds":[1], "reducer": {"code": "pubkey_trust_score($note.pubkey) > 5 ? $acc.push($note) : nil", "init": []}}

Encoding

We can use something like messagepack to pass this value back to the API consumer/client. This would allow the client to unpack the accumulated value, what the client does with that is up for them to decide and integrate into their UI.

Future: Environment?

Maybe these nostrscripts read and write to some environment. This would allow query algorithms to change over time. This is probably out of scope of nostrdb, maybe this environment can be configured by the client.

[alltheseas]

enables algorithms/algo-store user centered feature damus-io/damus#1302