dbpunk-labs/db3

Support filter condition `>, <, >=, <=`

jingchen2222 opened this issue · 3 comments

jingchen2222 commented

Motivations

  • Would you like to implement this feature? [y/n]

Solution

Alternatives

Additional context

jingchen2222 commented

Todo list:

  • Implement query for >, <, >=, <=
jingchen2222 commented

Background

DB3 supports query with filters with filter Operators like

      LESS_THAN = 1;


      // The given `field` is less than or equal to the given `value`.
      //
      // Requires:
      //
      // * That `field` come first in `order_by`.
      LESS_THAN_OR_EQUAL = 2;


      // The given `field` is greater than the given `value`.
      //
      // Requires:
      //
      // * That `field` come first in `order_by`.
      GREATER_THAN = 3;


      // The given `field` is greater than or equal to the given `value`.
      //
      // Requires:
      //
      // * That `field` come first in `order_by`.
      GREATER_THAN_OR_EQUAL = 4;


      // The given `field` is equal to the given `value`.
      EQUAL = 5;


      // The given `field` is not equal to the given `value`.
      //
      // Requires:
      //
      // * No other `NOT_EQUAL`, `NOT_IN`, `IS_NOT_NULL`, or `IS_NOT_NAN`.
      // * That `field` comes first in the `order_by`.
      NOT_EQUAL = 6;

https://github.com/dbpunk-labs/db3/blob/main/src/proto/proto/db3_database.proto#L228-L260

Now, we only support EQUAL = operator. We plan to support <,<=,>,>=. In order to implement above features, we need to support low-level query functionality in merkdb.

Solution

After discussion with @imotai #404 (comment), we decide to support complex filter based on iterator

  1. Seek iterator lower and upper bound based on the filter condition
  2. iterator to collection results
imotai commented

Solution

Step 1: Add RangeFrom and RangeTo enum into QueryItem

pub enum QueryItem {
    Key(Vec<u8>),
    Range(Range<Vec<u8>>),
    RangeInclusive(RangeInclusive<Vec<u8>>),
}

https://github.com/dbpunk-labs/merkdb/blob/1e043db99ec1560723a37fdbfddeefbae1c0938a/src/proofs/query/mod.rs#L112-L116

Step 2: Implement merge, contains, cmp Step 3: Support query with new QueryItem, refactoring the QueryItem so that it take use of Bound to cmp range

using iterator is a better solution

  • 👍1