commit ceb5ab5c991d433f5188e5833971b1843d997a6e
parent 4b6d1d088b36064e1240a1cbf2cde60dbf2c095d
Author: William Casarin <jb55@jb55.com>
Date: Fri, 5 Jan 2024 20:45:45 -0800
Query Plans
Instead of running queries off filters directly, we do some simple
heuristics and determine a reasonable query plan for the given filter.
To test this, also add a kind index query plan and add a test for it.
We still need tag, author, and created_at index scans. This is up next!
Diffstat:
3 files changed, 235 insertions(+), 204 deletions(-)
diff --git a/src/nostrdb.c b/src/nostrdb.c
@@ -203,13 +203,22 @@ struct ndb {
// lmdb environ handles, etc
};
-// We get the KeyMatchResult function from the scan_cursor_type
-// This function is used to match the key for the corresponding cursor type.
-// For example, KIND scanners will look for a kind
-enum ndb_scan_cursor_type {
- NDB_SCAN_KIND,
- NDB_SCAN_PK_KIND,
- NDB_SCAN_ID,
+///
+/// Query Plans
+///
+/// There are general strategies for performing certain types of query
+/// depending on the filter. For example, for large contact list queries
+/// with many authors, we simply do a descending scan on created_at
+/// instead of doing 1000s of pubkey scans.
+///
+/// Query plans are calculated from filters via `ndb_filter_plan`
+///
+enum ndb_query_plan {
+ NDB_PLAN_KINDS,
+ NDB_PLAN_IDS,
+ NDB_PLAN_AUTHORS,
+ NDB_PLAN_CREATED,
+ NDB_PLAN_TAGS,
};
// A clustered key with an id and a timestamp
@@ -1498,7 +1507,8 @@ int ndb_write_last_profile_fetch(struct ndb *ndb, const unsigned char *pubkey,
// after the first element, so we have to go back one.
static int ndb_cursor_start(MDB_cursor *cur, MDB_val *k, MDB_val *v)
{
- // Position cursor at the next key greater than or equal to the specified key
+ // Position cursor at the next key greater than or equal to the
+ // specified key
if (mdb_cursor_get(cur, k, v, MDB_SET_RANGE)) {
// Failed :(. It could be the last element?
if (mdb_cursor_get(cur, k, v, MDB_LAST))
@@ -2293,8 +2303,9 @@ static int ndb_filter_group_add_filters(struct ndb_filter_group *group,
return 1;
}
-static int ndb_filter_int(struct ndb_filter *filter,
- enum ndb_filter_fieldtype typ, uint64_t *lim)
+
+static struct ndb_filter_elements *
+ndb_filter_get_elems(struct ndb_filter *filter, enum ndb_filter_fieldtype typ)
{
int i;
struct ndb_filter_elements *els;
@@ -2302,259 +2313,265 @@ static int ndb_filter_int(struct ndb_filter *filter,
for (i = 0; i < filter->num_elements; i++) {
els = filter->elements[i];
if (els->field.type == typ) {
- *lim = els->elements[0].integer;
- return 1;
+ return els;
}
}
- return 0;
+ return NULL;
}
-static int ndb_filter_get_limit(struct ndb_filter *filter, uint64_t *lim)
+static union ndb_filter_element *
+ndb_filter_get_elem(struct ndb_filter *filter, enum ndb_filter_fieldtype typ)
{
- return ndb_filter_int(filter, NDB_FILTER_LIMIT, lim);
+ struct ndb_filter_elements *els;
+ if ((els = ndb_filter_get_elems(filter, typ)))
+ return &els->elements[0];
+ return NULL;
}
-static int ndb_filter_get_until(struct ndb_filter *filter, uint64_t *lim)
+static uint64_t *ndb_filter_get_int(struct ndb_filter *filter,
+ enum ndb_filter_fieldtype typ)
{
- return ndb_filter_int(filter, NDB_FILTER_UNTIL, lim);
+ union ndb_filter_element *el = NULL;
+ if (!(el = ndb_filter_get_elem(filter, typ)))
+ return 0;
+ return &el->integer;
}
-static int ndb_filter_get_since(struct ndb_filter *filter, uint64_t *lim)
+static inline int push_query_result(struct ndb_query_results *results,
+ struct ndb_query_result *result)
{
- return ndb_filter_int(filter, NDB_FILTER_SINCE, lim);
+ return cursor_push(&results->cur, (unsigned char*)result, sizeof(*result));
}
-static int ndb_query_filter_kind(struct ndb_txn *txn, struct ndb_filter *filter,
- MDB_cursor *cur, uint64_t kind, uint64_t since,
- int *matched, struct ndb_query_result *res)
+static int compare_query_results(const void *pa, const void *pb)
{
- MDB_val k, v;
- uint64_t note_id;
- struct ndb_u64_tsid tsid, *ptsid;
-
- res->note = NULL;
-
- ndb_u64_tsid_init(&tsid, kind, since);
-
- k.mv_data = &tsid;
- k.mv_size = sizeof(tsid);
-
- if (!ndb_cursor_start(cur, &k, &v))
- return 0;
+ struct ndb_query_result *a, *b;
- ptsid = (struct ndb_u64_tsid *)k.mv_data;
- note_id = *(uint64_t*)v.mv_data;
+ a = (struct ndb_query_result *)pa;
+ b = (struct ndb_query_result *)pb;
- if (kind == ptsid->u64)
- *matched |= 1 << NDB_FILTER_KINDS;
- else
+ if (a->note->created_at == b->note->created_at) {
+ return memcmp(a->note->id, b->note->id, 32);
+ } else if (a->note->created_at > b->note->created_at) {
+ return -1;
+ } else {
return 1;
+ }
+}
- // get the note because we need it to match against the filter
- if (!(res->note = ndb_get_note_by_key(txn, note_id, NULL)))
- return 1;
+static void ndb_query_result_init(struct ndb_query_result *res,
+ struct ndb_note *note,
+ uint64_t note_id)
+{
+ *res = (struct ndb_query_result){
+ .note_id = note_id,
+ .note = note,
+ };
+}
- // Sure this particular lookup matched the index query, but does it
- // match the entire filter? Check! We also pass in things we've already
- // matched via the filter so we don't have to check again. This can be
- // pretty important for filters with a large number of entries.
- if (!ndb_filter_matches_with(filter, res->note, *matched))
+static int query_is_full(struct ndb_query_results *results, int limit)
+{
+ if (results->cur.p >= results->cur.end)
return 1;
- return 2;
+ return cursor_count(&results->cur, sizeof(struct ndb_query_result)) >= limit;
}
-static int ndb_query_filter_id(struct ndb_txn *txn, struct ndb_filter *filter,
- MDB_cursor *cur, const unsigned char *id,
- uint64_t since, int *matched,
- struct ndb_query_result *res)
+static int ndb_query_plan_execute_ids(struct ndb_txn *txn,
+ struct ndb_filter *filter,
+ struct ndb_query_results *results,
+ int limit
+ )
{
+ MDB_cursor *cur;
+ MDB_dbi db;
MDB_val k, v;
- uint64_t note_id;
+ int matched, rc, i;
+ struct ndb_filter_elements *ids;
+ struct ndb_note *note;
+ struct ndb_query_result res;
struct ndb_tsid tsid, *ptsid;
+ uint64_t note_id, until, *pint;
+ unsigned char *id;
- res->note = NULL;
+ matched = 0;
+ until = UINT64_MAX;
- ndb_tsid_init(&tsid, (unsigned char *)id, since);
+ if (!(ids = ndb_filter_get_elems(filter, NDB_FILTER_IDS)))
+ return 0;
- k.mv_data = &tsid;
- k.mv_size = sizeof(tsid);
+ if ((pint = ndb_filter_get_int(filter, NDB_FILTER_UNTIL)))
+ until = *pint;
- if (!ndb_cursor_start(cur, &k, &v))
+ db = txn->lmdb->dbs[NDB_DB_NOTE_ID];
+ if ((rc = mdb_cursor_open(txn->mdb_txn, db, &cur)))
return 0;
- ptsid = (struct ndb_tsid *)k.mv_data;
- note_id = *(uint64_t*)v.mv_data;
+ // for each id in our ids filter, find in the db
+ for (i = 0; i < ids->count; i++) {
+ if (query_is_full(results, limit))
+ break;
- if (memcmp(id, ptsid->id, 32) == 0)
- *matched |= 1 << NDB_FILTER_AUTHORS;
- else
- return 1;
+ id = (unsigned char*)ids->elements[i].id;
+ ndb_tsid_init(&tsid, (unsigned char *)id, until);
- // get the note because we need it to match against the filter
- if (!(res->note = ndb_get_note_by_key(txn, note_id, NULL)))
- return 1;
+ k.mv_data = &tsid;
+ k.mv_size = sizeof(tsid);
- // Sure this particular lookup matched the index query, but does it
- // match the entire filter? Check! We also pass in things we've already
- // matched via the filter so we don't have to check again. This can be
- // pretty important for filters with a large number of entries.
- if (!ndb_filter_matches_with(filter, res->note, *matched))
- return 1;
+ if (!ndb_cursor_start(cur, &k, &v))
+ continue;
- return 2;
-}
+ ptsid = (struct ndb_tsid *)k.mv_data;
+ note_id = *(uint64_t*)v.mv_data;
-static inline int push_query_result(struct cursor *res,
- struct ndb_query_result *result)
-{
- return cursor_push(res, (unsigned char*)result, sizeof(*result));
-}
+ if (memcmp(id, ptsid->id, 32) == 0)
+ matched |= 1 << NDB_FILTER_AUTHORS;
+ else
+ continue;
-static int compare_query_results(const void *pa, const void *pb)
-{
- struct ndb_query_result *a, *b;
+ // get the note because we need it to match against the filter
+ if (!(note = ndb_get_note_by_key(txn, note_id, NULL)))
+ continue;
- a = (struct ndb_query_result *)pa;
- b = (struct ndb_query_result *)pb;
+ // Sure this particular lookup matched the index query, but
+ // does it match the entire filter? Check! We also pass in
+ // things we've already matched via the filter so we don't have
+ // to check again. This can be pretty important for filters
+ // with a large number of entries.
+ if (!ndb_filter_matches_with(filter, note, matched))
+ continue;
- if (a->note->created_at == b->note->created_at) {
- return memcmp(a->note->id, b->note->id, 32);
- } else if (a->note->created_at > b->note->created_at) {
- return -1;
- } else {
- return 1;
+ ndb_query_result_init(&res, note, note_id);
+ if (!push_query_result(results, &res))
+ break;
}
-}
-static int query_is_full(struct cursor *results, int limit)
-{
- if (results->p >= results->end)
- return 1;
-
- return cursor_count(results, sizeof(struct ndb_query_result)) >= limit;
+ mdb_cursor_close(cur);
+ return 1;
}
-static int ndb_query_filter(struct ndb_txn *txn, struct ndb_filter *filter,
- struct ndb_query_result *results, int capacity,
- int *results_out)
+static int ndb_query_plan_execute_kinds(struct ndb_txn *txn,
+ struct ndb_filter *filter,
+ struct ndb_query_results *results,
+ int limit)
{
- struct ndb_filter_elements *els;
- struct ndb_query_result res;
- struct cursor results_arr;
- uint64_t limit, since, until, kind;
- const unsigned char *id;
- int i, k, rc, matched;
MDB_cursor *cur;
MDB_dbi db;
+ MDB_val k, v;
+ struct ndb_note *note;
+ struct ndb_u64_tsid tsid, *ptsid;
+ struct ndb_filter_elements *kinds;
+ struct ndb_query_result res;
+ uint64_t kind, note_id;
+ int i, rc;
- since = UINT64_MAX;
- until = UINT64_MAX;
- limit = capacity;
-
- ndb_filter_get_limit(filter, &limit);
- ndb_filter_get_since(filter, &since);
- ndb_filter_get_until(filter, &until);
+ // we should have kinds in a kinds filter!
+ if (!(kinds = ndb_filter_get_elems(filter, NDB_FILTER_KINDS)))
+ return 0;
- limit = min(capacity, limit);
- make_cursor((unsigned char *)results,
- ((unsigned char *)results) + limit * sizeof(*results),
- &results_arr);
+ db = txn->lmdb->dbs[NDB_DB_NOTE_KIND];
- for (i = 0; i < filter->num_elements; i++) {
- matched = 0;
- if (query_is_full(&results_arr, limit))
- goto done;
+ if ((rc = mdb_cursor_open(txn->mdb_txn, db, &cur)))
+ return 0;
- els = filter->elements[i];
- switch (els->field.type) {
- case NDB_FILTER_IDS:
- db = txn->lmdb->dbs[NDB_DB_NOTE_ID];
- if ((rc = mdb_cursor_open(txn->mdb_txn, db, &cur)))
- return 0;
+ for (i = 0; i < kinds->count; i++) {
+ if (query_is_full(results, limit))
+ break;
- // for each id in our ids filter, find in the db
- for (k = 0; k < els->count; k++) {
- if (query_is_full(&results_arr, limit)) {
- mdb_cursor_close(cur);
- goto done;
- }
+ kind = kinds->elements[i].integer;
+ ndb_debug("kind %" PRIu64 "\n", kind);
+ ndb_u64_tsid_init(&tsid, kind, UINT64_MAX);
- id = els->elements[k].id;
- if (!(rc = ndb_query_filter_id(txn, filter, cur,
- id, since,
- &matched,
- &res))) {
- // there was a fatal error
- mdb_cursor_close(cur);
- return 0;
- }
+ k.mv_data = &tsid;
+ k.mv_size = sizeof(tsid);
- // no match, just try next id
- if (rc == 1)
- continue;
+ if (!ndb_cursor_start(cur, &k, &v))
+ continue;
- // rc > 1, matched!
- if (!push_query_result(&results_arr, &res)) {
- // this should never happen, but if
- // it fails to push that means there
- // are no more result to push,
- // so just return
- mdb_cursor_close(cur);
- goto done;
- }
+ // for each id in our ids filter, find in the db
+ while (!query_is_full(results, limit)) {
+ ptsid = (struct ndb_u64_tsid *)k.mv_data;
+ if (ptsid->u64 != kind)
+ break;
- // look for more ids... continue!
+ note_id = *(uint64_t*)v.mv_data;
+ if ((note = ndb_get_note_by_key(txn, note_id, NULL))) {
+ ndb_query_result_init(&res, note, note_id);
+ if (!push_query_result(results, &res))
+ break;
}
- mdb_cursor_close(cur);
- break;
- case NDB_FILTER_AUTHORS:
- break;
- case NDB_FILTER_KINDS:
- db = txn->lmdb->dbs[NDB_DB_NOTE_KIND];
- if ((rc = mdb_cursor_open(txn->mdb_txn, db, &cur)))
- return 0;
+ if (mdb_cursor_get(cur, &k, &v, MDB_PREV))
+ break;
+ }
+ }
- // for each id in our ids filter, find in the db
- for (k = 0; k < els->count; k++) {
- if (query_is_full(&results_arr, limit)) {
- mdb_cursor_close(cur);
- goto done;
- }
+ mdb_cursor_close(cur);
+ return 1;
+}
- kind = els->elements[k].integer;
- if (!(rc = ndb_query_filter_kind(txn, filter,
- cur, kind,
- since,
- &matched,
- &res))) {
- // there was a fatal error
- mdb_cursor_close(cur);
- return 0;
- }
+static enum ndb_query_plan ndb_filter_plan(struct ndb_filter *filter)
+{
+ struct ndb_filter_elements *ids, *kinds, *authors, *tags;
- // rc > 1, matched!
- if (!push_query_result(&results_arr, &res)) {
- mdb_cursor_close(cur);
- goto done;
- }
- }
+ ids = ndb_filter_get_elems(filter, NDB_FILTER_IDS);
+ kinds = ndb_filter_get_elems(filter, NDB_FILTER_KINDS);
+ authors = ndb_filter_get_elems(filter, NDB_FILTER_AUTHORS);
+ tags = ndb_filter_get_elems(filter, NDB_FILTER_TAGS);
- mdb_cursor_close(cur);
- break;
- case NDB_FILTER_GENERIC:
- break;
- case NDB_FILTER_SINCE:
- case NDB_FILTER_UNTIL:
- case NDB_FILTER_LIMIT:
- break;
- }
+ // this is rougly similar to the heuristic in strfry's dbscan
+ if (ids) {
+ return NDB_PLAN_IDS;
+ } else if (tags) {
+ return NDB_PLAN_TAGS;
+ } else if (authors) {
+ return NDB_PLAN_AUTHORS;
+ } else if (kinds) {
+ return NDB_PLAN_KINDS;
+ }
+
+ return NDB_PLAN_CREATED;
+}
+
+
+static int ndb_query_filter(struct ndb_txn *txn, struct ndb_filter *filter,
+ struct ndb_query_result *res, int capacity,
+ int *results_out)
+{
+ struct ndb_query_results results;
+ uint64_t limit, *pint;
+ limit = capacity;
+
+ if ((pint = ndb_filter_get_int(filter, NDB_FILTER_LIMIT)))
+ limit = *pint;
+
+ limit = min(capacity, limit);
+ make_cursor((unsigned char *)res,
+ ((unsigned char *)res) + limit * sizeof(*res),
+ &results.cur);
+
+ switch (ndb_filter_plan(filter)) {
+ // We have a list of ids, just open a cursor and jump to each once
+ case NDB_PLAN_IDS:
+ if (!ndb_query_plan_execute_ids(txn, filter, &results, limit))
+ return 0;
+ break;
+
+ // We have just kinds, just scan the kind index
+ case NDB_PLAN_KINDS:
+ if (!ndb_query_plan_execute_kinds(txn, filter, &results, limit))
+ return 0;
+ break;
+
+ // TODO: finish query execution plans!
+ case NDB_PLAN_CREATED:
+ case NDB_PLAN_AUTHORS:
+ case NDB_PLAN_TAGS:
+ return 0;
}
-done:
- *results_out = cursor_count(&results_arr, sizeof(*results));
+ *results_out = cursor_count(&results.cur, sizeof(*res));
return 1;
}
diff --git a/src/nostrdb.h b/src/nostrdb.h
@@ -399,6 +399,11 @@ struct ndb_block_iterator {
struct ndb_query_result {
struct ndb_note *note;
+ uint64_t note_id;
+};
+
+struct ndb_query_results {
+ struct cursor cur;
};
// CONFIG
diff --git a/test.c b/test.c
@@ -1146,7 +1146,7 @@ static void test_query()
{
struct ndb *ndb;
struct ndb_txn txn;
- struct ndb_filter filter, *f = &filter;
+ struct ndb_filter filters[2], *f;
struct ndb_config config;
struct ndb_query_result results[4];
int count, cap;
@@ -1173,12 +1173,14 @@ static void test_query()
const char *ev2 = "[\"EVENT\",\"s\",{\"id\": \"0a350c5851af6f6ce368bab4e2d4fe442a1318642c7fe58de5392103700c10fc\",\"pubkey\": \"dfa3fc062f7430dab3d947417fd3c6fb38a7e60f82ffe3387e2679d4c6919b1d\",\"created_at\": 1704404822,\"kind\": 1,\"tags\": [],\"content\": \"hello2\",\"sig\": \"48a0bb9560b89ee2c6b88edcf1cbeeff04f5e1b10d26da8564cac851065f30fa6961ee51f450cefe5e8f4895e301e8ffb2be06a2ff44259684fbd4ea1c885696\"}]";
- const char *ev3 = "[\"EVENT\",\"s\",{\"id\": \"20d2b66e1a3ac4a2afe22866ad742091b6267e6e614303de062adb33e12c9931\",\"pubkey\": \"7987bfb2632d561088fc8e3c30a95836f822e4f53633228ec92ae2f5cd6690aa\",\"created_at\": 1704408561,\"kind\": 2,\"tags\": [],\"content\": \"what\",\"sig\": \"cc8533bf177ac87771a5218a04bed24f7a1706f0b2d92700045cdeb38accc5507c6c8de09525e43190df3652012b554d4efe7b82ab268a87ff6f23da44e16a8f\"}";
+ const char *ev3 = "[\"EVENT\",\"s\",{\"id\": \"20d2b66e1a3ac4a2afe22866ad742091b6267e6e614303de062adb33e12c9931\",\"pubkey\": \"7987bfb2632d561088fc8e3c30a95836f822e4f53633228ec92ae2f5cd6690aa\",\"created_at\": 1704408561,\"kind\": 2,\"tags\": [],\"content\": \"what\",\"sig\": \"cc8533bf177ac87771a5218a04bed24f7a1706f0b2d92700045cdeb38accc5507c6c8de09525e43190df3652012b554d4efe7b82ab268a87ff6f23da44e16a8f\"}]";
- const char *ev4 = "[\"EVENT\",\"s\",{\"id\": \"8a2057c13c1c57b536eab78e6c55428732d33b6b5b234c1f5eab2b5918c37fa1\",\"pubkey\": \"303b5851504da5caa14142e9e2e1b1b60783c48d6f137c205019d46d09244c26\",\"created_at\": 1704408730,\"kind\": 2,\"tags\": [],\"content\": \"hmm\",\"sig\": \"e7cd3029042d41964192411929cade59592840af766da6420077ccc57a61405312db6ca879150db01f53c3b81c477cec5d6bd49f9dc10937267cacf7e5c784b3\"}";
+ const char *ev4 = "[\"EVENT\",\"s\",{\"id\": \"8a2057c13c1c57b536eab78e6c55428732d33b6b5b234c1f5eab2b5918c37fa1\",\"pubkey\": \"303b5851504da5caa14142e9e2e1b1b60783c48d6f137c205019d46d09244c26\",\"created_at\": 1704408730,\"kind\": 2,\"tags\": [],\"content\": \"hmm\",\"sig\": \"e7cd3029042d41964192411929cade59592840af766da6420077ccc57a61405312db6ca879150db01f53c3b81c477cec5d6bd49f9dc10937267cacf7e5c784b3\"}]";
assert(ndb_init(&ndb, test_dir, &config));
+
+ f = &filters[0];
ndb_filter_init(f);
ndb_filter_start_field(f, NDB_FILTER_IDS);
ndb_filter_add_id_element(f, id);
@@ -1186,11 +1188,14 @@ static void test_query()
ndb_filter_end_field(f);
assert((subid = ndb_subscribe(ndb, f, 1)));
+
assert(ndb_process_event(ndb, ev, strlen(ev)));
assert(ndb_process_event(ndb, ev2, strlen(ev2)));
assert(ndb_process_event(ndb, ev3, strlen(ev3)));
assert(ndb_process_event(ndb, ev4, strlen(ev4)));
- assert(ndb_wait_for_notes(ndb, subid, note_ids, 4));
+
+ for (count = 0; count < 2;)
+ count += ndb_wait_for_notes(ndb, subid, note_ids+count, 4-count);
ndb_begin_query(ndb, &txn);
assert(ndb_query(&txn, f, 1, results, cap, &count));
@@ -1202,11 +1207,15 @@ static void test_query()
ndb_filter_add_int_element(f, 2);
ndb_filter_end_field(f);
ndb_filter_start_field(f, NDB_FILTER_LIMIT);
- ndb_filter_add_int_element(f, 1);
+ ndb_filter_add_int_element(f, 2);
ndb_filter_end_field(f);
+ count = 0;
assert(ndb_query(&txn, f, 1, results, cap, &count));
- assert(count == 1);
+ ndb_print_kind_keys(&txn);
+ assert(count == 2);
+ assert(!strcmp(ndb_note_content(results[0].note), "hmm"));
+ assert(!strcmp(ndb_note_content(results[1].note), "what"));
ndb_end_query(&txn);
ndb_destroy(ndb);
