• Chen Tianjie's avatar
    Optimize ZRANGE offset location from linear search to skiplist jump. (#12450) · b26e8e32
    Chen Tianjie authored
    ZRANGE BYSCORE/BYLEX with [LIMIT offset count] option was
    using every level in skiplist to jump to the first/last node in range,
    but only use level[0] in skiplist to locate the node at offset, resulting
    in sub-optimal performance using LIMIT:
    ```
    while (ln && offset--) {
        if (reverse) {
            ln = ln->backward;
        } else {
            ln = ln->level[0].forward;
        }
    }
    ```
    It could be slow when offset is very big. We can get the total rank of
    the offset location and use skiplist to jump to it. It is an improvement
    from O(offset) to O(log rank).
    
    Below shows how this is implemented (if the offset is positve):
    
    Use the skiplist to seach for the first element in the range, record its
    rank `rank_0`, so we can have the rank of the target node `rank_t`.
    Meanwhile we record the last node we visited which has zsl->level-1
    levels and its rank `rank_1`. Then we start from the zsl->level-1 node,
    use skiplist to go forward `rank_t-rank_1` nodes to reach the target node.
    
    It is very similiar when the offset is reversed.
    
    Note that if `rank_t` is very close to `rank_0`, we just start from the first
    element in range and go node by node, this for the case when zsl->level-1
    node is to far away and it is quicker to reach the target node by node.
    
    Here is a test using a random generated zset including 10000 elements
    (with different positive scores), doing a bench mark which compares how
    fast the `ZRANGE` command is exucuted before and after the optimization. 
    
    The start score is set to 0 and the count is set to 1 to make sure that
    most of the time is spent on locating the offset.
    ```
    memtier_benchmark -h 127.0.0.1 -p 6379 --command="zrange test 0 +inf byscore limit <offset> 1"
    ```
    | offset | QPS(unstable) | QPS(optimized) |
    |--------|--------|--------|
    | 10 | 73386.02 | 74819.82 |
    | 1000 | 48084.96 | 73177.73 |
    | 2000 | 31156.79 | 72805.83 |
    | 5000 | 10954.83 | 71218.21 |
    
    With the result above, we can see that the original code is greatly
    slowed down when offset gets bigger, and with the optimization the
    speed is almost not affected.
    
    Similiar results are generated when testing reversed offset:
    ```
    memtier_benchmark -h 127.0.0.1 -p 6379 --command="zrange test +inf 0 byscore rev limit <offset> 1"
    ```
    | offset | QPS(unstable) | QPS(optimized) |
    |--------|--------|--------|
    | 10 | 74505.14 | 71653.67 |
    | 1000 | 46829.25 | 72842.75 |
    | 2000 | 28985.48 | 73669.01 |
    | 5000 | 11066.22 | 73963.45 | 
    
    And the same conclusion is drawn from the tests of ZRANGE BYLEX.
    b26e8e32
t_zset.c 152 KB