8000 ZRANDMEMBER still walks the sorted set: about 20x Redis at a million members · Issue #862 · kividbio/kividb · GitHub
[go: up one dir, main page]

Skip to content

ZRANDMEMBER still walks the sorted set: about 20x Redis at a million members #862

Closed

Description

@murtazayusuf

Left open by #860 (#839). HRANDFIELD is now O(count) and ahead of Redis; ZRANDMEMBER could only be improved within how a sorted set is kept today: a hash map of members and an ordered tree, neither of which can be asked for its Nth member. It walks the member table once up to the last position picked.

1M members, µs per call (one connection, about 50 µs of that is the round trip):

1.2.2 now Redis 8.10.2
ZRANDMEMBER z 1 6,560 995 49
ZRANDMEMBER z 10 6,443 1,852 84

At 10k members and below nothing is lost against Redis.

What removes it: a member table that can be indexed by position (as src/member_set.rs does for sets with HashTable::get_bucket: a random bucket, tried again while empty), or an ordered structure that knows ranks. Either is a change to how sorted sets are stored, so it belongs with the storage work for collections (#825, #297), not a patch on its own. Regression suite 16 (16-random-sample) has the rows to hold it to.

Activity

  1. magic-peach commented on Nov 19, 2026

    @magic-peach
    Collaborator

    @murtazayusuf can I work on this?

  2. murtazayusuf commented on Nov 19, 2026

    @murtazayusuf
    ContributorAuthor

    @magic-peach thanks for offering. This one is tied to the large sorted-set storage that @Parikalp-Bhardwaj is prototyping in #875: ZRANDMEMBER gets fast once the large form can pick a member by rank, and that structure is exactly what is changing there, so a fix on today's layout would be rewritten within days. I'd rather not have you two collide. If Parikalp's design lands without it, it is yours.

    Meanwhile #918 and #922 are waiting on the review items, and #770 is still assigned to you; any of those is the quickest way to get more of your work merged.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    performanceThroughput and latency

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions

      0