nostrdb-net: algo for unifying similar subscriptions

[jb55]

This will be useful for our subscription manager

Example:

subA: {"authors": ["a"], "since": 100}
subB: {"authors": ["b"], "since": 200}

Should optimize to:

subAB: {"authors": ["a", "b"], "since": 100}

[v0l]

I have something like this in @snort/system-wasm but its not very well written: https://github.com/v0l/snort/blob/main/packages/system-wasm/src/merge.rs

[jb55]

On Wed, Jan 22, 2025 at 01:08:19PM GMT, Kieran wrote: I have something like this in ***@***.***/system-wasm` but its not very well written: https://github.com/v0l/snort/blob/main/packages/system-wasm/src/merge.rs

interesting I'll take a look

[v0l]

The general algo works like this:

1. Split a filter into "FlatFilters" by Cartesian product

Take the example filter {"kinds":[0,1,2], "authors": ["a","b"]} this is expanded into (FlatFilter):

{"kinds":0,"authors":"a"}
{"kinds":0,"authors":"b"}
{"kinds":1,"authors":"a"}
{"kinds":1,"authors":"b"}
{"kinds":2,"authors":"a"}
{"kinds":2,"authors":"b"}

2. Merge similar

To find "similar" filters you simply measure how "far" one filter is from another by comparing their properties:

For each property of the filter you add up the total distance as computed by the following function:

#[inline(always)]
fn prop_dist<T: Eq>(a: &Option<T>, b: &Option<T>) -> u32 {
    if (a.is_some() && b.is_none()) || (a.is_none() && b.is_some()) {
        return 10;
    } else if a.is_some() && a != b {
        return 1;
    }
    0
}

Then you check if the value is <= 1 which is to say that the filters are the same except for the values of the set properties, ie:

{"kinds":0,"authors":"a"}
{"kinds":0,"authors":"b"}

But not:

{"#e": "ccc","authors":"a"}
{"kinds":0,"authors":"a"}

There is also never a case when filters can be merged when using limit/since/until, as code this looks like:

impl CanMerge for ReqFilter {
    fn can_merge(&self, other: &Self) -> bool {
        if self.since != other.since
            || self.until != other.until
            || self.limit != other.limit
            || self.search != other.search
        {
            return false;
        }

        self.distance(other) <= 1
    }
}

Then you fold your list of "FlatFilters" by checking can_merge and accumulate similar filters and then flatten them into a single filter by adding their prop values into a single "ReqFilter"