Skip to content

fixed complexity of bzmpop and zmpop commands#11026

Merged
oranagra merged 2 commits intoredis:unstablefrom
pavel-krush:unstable
Jul 24, 2022
Merged

fixed complexity of bzmpop and zmpop commands#11026
oranagra merged 2 commits intoredis:unstablefrom
pavel-krush:unstable

Conversation

@pavel-krush
Copy link
Contributor

@pavel-krush pavel-krush commented Jul 22, 2022 •
edited by oranagra
Loading

Swap M and N in the complexity formula of [B]ZMPOP
#11022

enjoy-binbin
enjoy-binbin reviewed Jul 22, 2022
View reviewed changes
Copy link
Contributor

@enjoy-binbin enjoy-binbin left a comment •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

please try to run python3 utils/generate-command-code.py
or just modify command.c, i am sure you can find it

redis/src/commands.c

Line 7345 in d00b8af

{"bzmpop","Remove and return members with scores in a sorted set or block until one is available","O(K) + O(N*log(M)) where K is the number of provided keys, N being the number of elements in the sorted set, and M being the number of elements popped.","7.0.0",CMD_DOC_NONE,NULL,NULL,COMMAND_GROUP_SORTED_SET,BZMPOP_History,BZMPOP_tips,bzmpopCommand,-5,CMD_WRITE|CMD_BLOCKING,ACL_CATEGORY_SORTEDSET,{{NULL,CMD_KEY_RW|CMD_KEY_ACCESS|CMD_KEY_DELETE,KSPEC_BS_INDEX,.bs.index={2},KSPEC_FK_KEYNUM,.fk.keynum={0,1,1}}},blmpopGetKeys,.args=BZMPOP_Args},

redis/src/commands.c

Line 7358 in d00b8af

{"zmpop","Remove and return members with scores in a sorted set","O(K) + O(N*log(M)) where K is the number of provided keys, N being the number of elements in the sorted set, and M being the number of elements popped.","7.0.0",CMD_DOC_NONE,NULL,NULL,COMMAND_GROUP_SORTED_SET,ZMPOP_History,ZMPOP_tips,zmpopCommand,-4,CMD_WRITE,ACL_CATEGORY_SORTEDSET,{{NULL,CMD_KEY_RW|CMD_KEY_ACCESS|CMD_KEY_DELETE,KSPEC_BS_INDEX,.bs.index={1},KSPEC_FK_KEYNUM,.fk.keynum={0,1,1}}},zmpopGetKeys,.args=ZMPOP_Args},

enjoy-binbin
enjoy-binbin approved these changes Jul 23, 2022
View reviewed changes
Copy link
Contributor

@enjoy-binbin enjoy-binbin left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

thanks, LGTM

@oranagra oranagra linked an issue Jul 24, 2022 that may be closed by this pull request
BZMPOP ZMPOP complexity #11022
Closed
@oranagra oranagra merged commit 5879e49 into redis:unstable Jul 24, 2022
@enjoy-binbin enjoy-binbin mentioned this pull request Aug 2, 2022
Closed
oranagra pushed a commit that referenced this pull request Sep 21, 2022
@pavel-krush @oranagra
fixed complexity of bzmpop and zmpop commands (#11026)
61a59b5 
Swap M and N in the complexity formula of [B]ZMPOP

Co-authored-by: Pavel Krush <[email protected]>
(cherry picked from commit 5879e49)
@oranagra oranagra mentioned this pull request Sep 21, 2022
Merged
enjoy-binbin pushed a commit to enjoy-binbin/redis that referenced this pull request Jul 31, 2023
@pavel-krush @enjoy-binbin
fixed complexity of bzmpop and zmpop commands (redis#11026)
8bc0354 
Swap M and N in the complexity formula of [B]ZMPOP

Co-authored-by: Pavel Krush <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@oranagra oranagra oranagra approved these changes

+1 more reviewer

@enjoy-binbin enjoy-binbin enjoy-binbin approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

None yet

Projects

Redis 7.0
Status: Done
Redis 7.0 Backport
Status: Done

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

BZMPOP ZMPOP complexity

3 participants

@pavel-krush @oranagra @enjoy-binbin