From 272eb488547638125f1ccce47f6273dc8309bcc7 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Wed, 11 Nov 2020 21:04:17 +0100 Subject: Fix filtering query modes These were incorrect before because the tree was not ordered with respect to the search key. Enabling ZIX_BTREE_SORTED_CHECK (which should probably have a configure option) catches this. --- src/sord.c | 19 ++++++++++++++++++- 1 file changed, 18 insertions(+), 1 deletion(-) (limited to 'src') diff --git a/src/sord.c b/src/sord.c index 5a759c0..557e11d 100644 --- a/src/sord.c +++ b/src/sord.c @@ -840,7 +840,24 @@ sord_find(SordModel* model, const SordQuad pat) ZixBTree* const db = model->indices[index_order]; ZixBTreeIter* cur = NULL; - zix_btree_lower_bound(db, pat, &cur); + + if (mode == FILTER_ALL) { + // No prefix shared with an index at all, linear search (worst case) + cur = zix_btree_begin(db); + } else if (mode == FILTER_RANGE) { + /* Some prefix, but filtering still required. Build a search pattern + with only the prefix to find the lower bound in log time. */ + SordQuad prefix_pat = { NULL, NULL, NULL, NULL }; + const int* const ordering = orderings[index_order]; + for (int i = 0; i < n_prefix; ++i) { + prefix_pat[ordering[i]] = pat[ordering[i]]; + } + zix_btree_lower_bound(db, prefix_pat, &cur); + } else { + // Ideal case, pattern matches an index with no filtering required + zix_btree_lower_bound(db, pat, &cur); + } + if (zix_btree_iter_is_end(cur)) { SORD_FIND_LOG("No match found\n"); zix_btree_iter_free(cur); -- cgit v1.2.1