...

Please keep the discussion on the mailing list rather than commenting on the wiki (wiki discussions get unwieldy fast).

Motivation

...

The concepts of reverseRange and reverseAll

...

Use bounded query to achieve reverseRange and use unbounded query to achieve reverseAll.

Proposed Changes

...

are not tied to any specific method or class. Rather, they represent functionalities we wish to achieve. Currently, with RangeQuery, we can use methods like withRange(), withLowerBound(), withUpperBound(), and withNoBounds().

Utilizing these, the query returns results ordered by their keys.

Take IQv2StoreIntegrationTest as an example: we have two partitions with four key-value pairs:

• <0,0> in Partition0
• <1,1> in Partition1
• <2,2> in Partition0
• <3,3> in Partition1

When we use RangeQuery.withRange(1,3), the returned result is:

• Partition0: [2]
• Partition1: [1, 3]

To achieve the functionalities of reverseRange and reverseAll, we can

...

introduce a method named withDescendingKeys() for reversed queries. For example, by using RangeQuery.withRange(1,3).withDescendingKeys(), the expected result would be:

• Partition0: [2]
• Partition1: [3, 1]

This means the results are in the reverse order of their keys.

To ensure that we can achieve this functionality, the keys in both RocksDB  and InMemoryKeyValueStore  should be sorted. We know that RocksDB  keys are inherently sorted. After investigation, we found that InMemoryKeyValueStore  uses a TreeMap, implying its keys are also sorted. Therefore, performing the aforementioned queries is feasible.

Proposed Changes

According to KIP-969, this KIP introduces the isKeyAscending variable to determine whether keys are sorted in ascending order. It employs the withDescendingKeys() method to specify that the keys should be ordered in descending sequence, and the isKeyAscending() method to retrieve the value of isKeyAscending. I've incorporated these variables and methods into the RangeQuery class and modified some method inputs. As a result, we can now use withDescendingKeys() to obtain results in reverse order.

We add a variable reverse  in RangeQuery , the default value is false, we want do reverseRange or reverseAll, we can set it to true.

Then we generate two public methods:

The first one is isReverse() , if this method return true, do reverseQuery otherwise do rangeQuery

the second method is setReverse() , if we want the query do reverseQuery, we can use this method to set the reverse  to true, so this time, rangeQuery Stand for reverseQuery.

Use bounded reverseQuery to achieve reverseRange and use unbounded reverseQuery to achieve reverseAll.

/**
 * Interactive query for issuing range queries and scans over KeyValue stores.
 * <p>
 *  A range query retrieves a set of records, specified using an upper and/or lower bound on the keys.
 * <p>
 * A scan query retrieves all records contained in the store.
 * <p>
 * If the reverse is false, do rangeQuery. If the reverse is true do reverseQuery
 */
@Evolving
public final class RangeQuery<K, V> implements Query<KeyValueIterator<K, V>> {
...
    private boolean reverse;
/
@Evolving
public final class RangeQuery<K, V> implements Query<KeyValueIterator<K, V>> {


    ...

    private final boolean isKeyAscending;

    private RangeQuery(final Optional<K> lower, final Optional<K> upper, final boolean isKeyAscending) {
        this.lower = lower;
        this.upper = upper;
        this.isKeyAscending = isKeyAscending;
    }

    /**
     * Interactive range query using a lower and upper bound to filter the keys returned.
     * @param lower The key that specifies the lower bound of the range
     * @param upper The key that specifies the upper bound of the range
     * @param <K> The key type
     * @param <V> The value type
     */
    public static <K, V> RangeQuery<K, V> withRange(final K lower, final K upper) {
        return new RangeQuery<>(Optional.ofNullable(lower), Optional.ofNullable(upper), true);
    }

    /**
     * Determines if the query keys are in ascending order.
     * @return true if ascending, false otherwise.
     */
    public boolean isKeyAscending() {
        return isKeyAscending;
    }

    /**
     * Set the query to return keys in descending order.
     * @return a new RangeQuery instance with descending flag set.
     */
    public RangeQuery<K, V> withDescendingKeys() {
        return new RangeQuery<>(this.lower, this.upper, false);
    }

    /**
     * Check whether the Query is reverseQuery Interactive range query using an upper bound to filter the keys returned.
     * If both <K,V> are null, RangQuery returns a full range scan.
     * @param upper The key that specifies the upper bound of the range
     * @param <K> The key type
     * @param <V> The value type
     */
    public boolean isReverse( static <K, V> RangeQuery<K, V> withUpperBound(final K upper) {
        return reverse new RangeQuery<>(Optional.empty(), Optional.of(upper), true);
    }

    /**
     * Interactive range query using a lower bound to filter the keys returned.
     * Set the Query to reverseQuery@param lower The key that specifies the lower bound of the range
     * @param <K> The key type
     * @param <V> The value type
     */
    public static <K, V> RangeQuery<K, V> withLowerBound(final K lower) {
        return new RangeQuery<>(Optional.of(lower), Optional.empty(), true);
    }

    /**
     * Interactive scan query that returns all records in the store.
     * @param <K> The key type
     * @param <V> The value type
     */
    public void setReversestatic <K, V> RangeQuery<K, V> withNoBounds() {
        return this.reverse = truenew RangeQuery<>(Optional.empty(), Optional.empty(), true);
    }

    ...
}

Test Plan

This time, we aim our goal is to implement reverseRange and reverseAllfunctionalities. While these terms are used for clarity, in practice, they correspond to RangeQuery.withRange().withDescendingKeys() and RangeQuery.withNoBounds().withDescendingKeys(), respectively. To ensure the accuracy accurate retrieval of the results for both functionalities, modifications adjustments to IQv2StoreIntegrationTest  are necessary. Previouslyrequired. In our previous approach, we stored query results in a set, which doesn't retain maintain order. I've since switched transitioned to using a list to store the query results. This allows us to discern the differences between rangeQuery and reverseQuery.for storing query results, enabling us to distinguish between rangeQuery and reverseQuery. Here, rangeQuery refers to standard queries (those not using withDescendingKeys()) such as withRange(), withLowerBound(), withUpperBound(), and withNoBounds(). In contrast, reverseQuery denotes queries that employ the withDescendingKeys() method.

We've transitioned the expectedValue from a Set to a List and arranged the partition numbers in order. This organization assists us in predicting the results. If the partition numbers were random, predicting the outcome would be challenging. Ultimately, this enables us to obtain and store the answer in the expectedValue. Consequently, the results between rangeQuery and reverseQuery will differ.

public class IQv2StoreIntegrationTest {
...
 @SuppressWarnings("unchecked")
    public <V> void shouldHandleRangeQuery(
		final Optional<Integer> lower,
        final Optional<Integer> upper,
        final boolean isKeyAscending,
        final Function<V, Integer> valueExtactor,
        final List<Integer> expectedValue) {

        final RangeQuery<Integer, V> query;

        if (isKeyAscending) {
            query = RangeQuery.withRange(lower.orElse(null), upper.orElse(null));
        } else {
            query = (RangeQuery<Integer, V>) RangeQuery.withRange(lower.orElse(null), upper.orElse(null)).withDescendingKeys();
        }
        ...
        } else {
            final List<Integer> actualValue = new ArrayList<>();
           ...
            final List<Integer> partitions = new ArrayList<>(queryResult.keySet());
            partitions.sort(null);
            for (final int partition : partitions) {
		...
		}
   ...
}

Compatibility, Deprecation, and Migration Plan

• Because we have already have RangeQuery  Utilizing the existing RangeQuery class, so we can update make some code to achieve reverseRange and reverseAllmodifications to realize the concepts of reverseRange  and reverseAll . To reiterate, reverseRange  and reverseAll  are not classes or methods but merely concepts.
• Since nothing is deprecated in this KIP, users have no need to migrate unless they want to.

Rejected Alternatives

At first, we planned to implement ReverseRangeQuery  from scratch. However, after discussions, we decided to reuse some of the RangeQuery  code, allowing RangeQuery  to possess the reverseQuery functionality. Therefore, in the end, we chose not to add a new ReverseRangeQuery  class but instead to enhance the RangeQuery  with new featuresAfter initial plans to create a ReverseRangeQuery from the ground up, we opted to leverage existing code from the RangeQuery class following further discussions.

@Evolving
public final class ReverseRangeQuery<K, V> implements Query<KeyValueIterator<K, V>> {

    private final Optional<K> lower;
    private final Optional<K> upper;

    private ReverseRangeQuery(final Optional<K> lower, final Optional<K> upper) {
        this.lower = lower;
        this.upper = upper;
    }

    /**
     * Interactive range query using a lower and upper bound to filter the keys returned.
     * @param lower The key that specifies the lower bound of the range
     * @param upper The key that specifies the upper bound of the range
     * @param <K> The key type
     * @param <V> The value type
     */
    public static <K, V> ReverseRangeQuery<K, V> withRange(final K lower, final K upper) {
        return new ReverseRangeQuery<>(Optional.ofNullable(lower), Optional.ofNullable(upper));
    }

    /**
     * Interactive range query using an upper bound to filter the keys returned.
     * If both <K,V> are null, RangQuery returns a full range scan.
     * @param upper The key that specifies the upper bound of the range
     * @param <K> The key type
     * @param <V> The value type
     */
    public static <K, V> ReverseRangeQuery<K, V> withUpperBound(final K upper) {
        return new ReverseRangeQuery<>(Optional.empty(), Optional.of(upper));
    }

    /**
     * Interactive range query using a lower bound to filter the keys returned.
     * @param lower The key that specifies the lower bound of the range
     * @param <K> The key type
     * @param <V> The value type
     */
    public static <K, V> ReverseRangeQuery<K, V> withLowerBound(final K lower) {
        return new ReverseRangeQuery<>(Optional.of(lower), Optional.empty());
    }

    /**
     * Interactive scan query that returns all records in the store.
     * @param <K> The key type
     * @param <V> The value type
     */
    public static <K, V> ReverseRangeQuery<K, V> withNoBounds() {
        return new ReverseRangeQuery<>(Optional.empty(), Optional.empty());
    }

    /**
     * The lower bound of the query, if specified.
     */
    public Optional<K> getLowerBound() {
        return lower;
    }

    /**
     * The upper bound of the query, if specified
     */
    public Optional<K> getUpperBound() {
        return upper;
    }
}

...