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

[jingchen2222]

Motivations

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

Solution

Alternatives

Additional context

[jingchen2222]

Todo list:

• [x] Implement query for >, <, >=, <=

[jingchen2222]

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 https://github.com/dbpunk-labs/db3/issues/404#issuecomment-1506432489, 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]

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