This is an automated email from the ASF dual-hosted git repository.
git-hulk pushed a commit to branch unstable
in repository https://gitbox.apache.org/repos/asf/kvrocks.git
The following commit(s) were added to refs/heads/unstable by this push:
new 3583e5dd3 refactor: avoid sorting inputs for ZINTERCARD (#3697)
3583e5dd3 is described below
commit 3583e5dd316c8918f7d36931fe361ab890a59594
Author: nkysg <[email protected]>
AuthorDate: Mon Oct 26 19:27:41 2026 +0800
refactor: avoid sorting inputs for ZINTERCARD (#3697)
Summary
Avoid sorting and copying all input member lists when calculating
`ZINTERCARD`.
- Use `std::min_element` to select the smallest input set as the
intersection base.
- Iterate over all remaining sets while skipping the selected base
iterator.
- Replace the per-member map counter with a local counter.
The previous implementation sorted every input list only to select the
smallest one, copied that list, and allocated map entries for each
candidate member.
## Tests
- Added `ZINTERCARD` coverage where the smallest input is not the first
key.
- Added `LIMIT` coverage for the same input order.
- `gofmt -w tests/gocase/unit/type/zset/zset_test.go`
- LLVM 18 `clang-tidy` on `src/types/redis_zset.cc`.
## AI-assisted contribution
OpenAI Codex was used to draft the unit tests for this change.
---
src/types/redis_zset.cc | 20 ++++++++++----------
tests/gocase/unit/type/zset/zset_test.go | 21 +++++++++++++++++++++
2 files changed, 31 insertions(+), 10 deletions(-)
diff --git a/src/types/redis_zset.cc b/src/types/redis_zset.cc
index 26a2aee70..1ea50ae91 100644
--- a/src/types/redis_zset.cc
+++ b/src/types/redis_zset.cc
@@ -717,23 +717,23 @@ rocksdb::Status ZSet::InterCard(engine::Context &ctx,
const std::vector<std::str
if (!s.ok() || mscores.empty()) return s;
mscores_list.emplace_back(std::move(mscores));
}
- std::sort(mscores_list.begin(), mscores_list.end(),
- [](const MemberScores &v1, const MemberScores &v2) { return
v1.size() < v2.size(); });
-
- auto base_mscores = mscores_list[0];
- std::map<std::string, size_t> member_counters;
+ const auto base_it =
+ std::min_element(mscores_list.cbegin(), mscores_list.cend(),
+ [](const MemberScores &v1, const MemberScores &v2) {
return v1.size() < v2.size(); });
+ const auto &base_mscores = *base_it;
uint64_t cardinality = 0;
for (const auto &base_ms : base_mscores) {
- member_counters[base_ms.member] = 1;
- for (size_t i = 1; i < mscores_list.size(); i++) {
- for (const auto &ms : mscores_list[i]) {
+ size_t member_count = 1;
+ for (auto it = mscores_list.cbegin(); it != mscores_list.cend(); ++it) {
+ if (it == base_it) continue;
+ for (const auto &ms : *it) {
if (base_ms.member == ms.member) {
- member_counters[ms.member]++;
+ member_count++;
break;
}
}
}
- if (member_counters[base_ms.member] == mscores_list.size()) {
+ if (member_count == mscores_list.size()) {
cardinality++;
if (limit > 0 && cardinality >= limit) {
*inter_cnt = limit;
diff --git a/tests/gocase/unit/type/zset/zset_test.go
b/tests/gocase/unit/type/zset/zset_test.go
index 0f9fa6f44..4dead0626 100644
--- a/tests/gocase/unit/type/zset/zset_test.go
+++ b/tests/gocase/unit/type/zset/zset_test.go
@@ -1295,6 +1295,27 @@ func basicTests(t *testing.T, rdb *redis.Client, ctx
context.Context, enabledRES
})
+ t.Run(fmt.Sprintf("ZINTERCARD with non-first smallest input - %s",
encoding), func(t *testing.T) {
+ createZset(rdb, ctx, "zset_large", []redis.Z{
+ {Score: 1, Member: "a"},
+ {Score: 2, Member: "b"},
+ {Score: 3, Member: "c"},
+ {Score: 4, Member: "d"},
+ })
+ createZset(rdb, ctx, "zset_small", []redis.Z{
+ {Score: 1, Member: "a"},
+ {Score: 2, Member: "b"},
+ })
+ createZset(rdb, ctx, "zset_medium", []redis.Z{
+ {Score: 1, Member: "a"},
+ {Score: 2, Member: "b"},
+ {Score: 3, Member: "e"},
+ })
+
+ require.Equal(t, int64(2), rdb.ZInterCard(ctx, 0, "zset_large",
"zset_small", "zset_medium").Val())
+ require.Equal(t, int64(1), rdb.ZInterCard(ctx, 1, "zset_large",
"zset_small", "zset_medium").Val())
+ })
+
t.Run(fmt.Sprintf("ZMSCORE - %s", encoding), func(t *testing.T) {
rdb.Del(ctx, "zset")
createZset(rdb, ctx, "zset", []redis.Z{
