improve performance for scan command when matching pattern or data type #12209

judeng · 2023-05-22T09:37:14Z

Optimized the performance of the SCAN command in a few ways:

Move the key filtering (by MATCH pattern) in the scan callback, so as to avoid collecting them for later filtering.
Reduce a many memory allocations and copying (use a reference to the original sds, instead of creating an robj, an excessive 2 mallocs and one string duplication)
Compare TYPE filter directly (as integers), instead of inefficient string compare per key.
fixed a small bug: when scan zset and hash types, maxiterations uses a more accurate number to avoid wrong double maxiterations.

Changes postponed for a later version (8.0):

Prepare to move the TYPE filtering to the scan callback as well. this was put on hold since it has side effects that can be considered a breaking change, which is that we will not attempt to do lazy expire (delete) a key that was filtered by not matching the TYPE (changing it would mean TYPE filter starts behaving the same as MATCH filter already does in that respect).
when the specified key TYPE filter is an unknown type, server will reply a error immediately instead of doing a full scan that comes back empty handed.

Benchmark result:
For different scenarios, we obtained about 30% more performance improvement:

scene 1: scan the key space with different filter

	no filter	scan pattern and 100% unmatched	scan pattern and 50% unmatched	scan type and 100% matched	scan type and 100% unmatched	scan type and 50% matched
unstable	31173	50279	36174	22936	32931	27603
pr	40264	110661	53689	32028	50437	37736
improvement	29.16%	120.09%	48.42%	39.64%	53.16%	36.71%

scene 2: hscan key which use ht encoding

hscan(hashtable encoding)	100% matched	hscan pattern and 100% unmatched
unstable	17740	32457
this pr	22734	108945
improvement	28.15%	235.66%

scene 3: sscan key which use intset encoding

sscan intset	100% matched	sscan pattern and 20% matched
unstable	7529	14567
pr	7418	21763
imporovement	-1.47%	49.40%

scene 4: zscan key which use listpack encoding

zscan listpack	100% matched	zscan pattern and 10% matched
unstable	18422	28857
this pr	18826	83565
imporovement	2.19%	189.58%

…fying a definite type

judeng · 2023-05-22T11:11:49Z

CI failed again and seem that nothing to with this pr...
but I didn't find out why, @enjoy-binbin could you help me to have a look? thanks! refer https://github.com/redis/redis/actions/runs/5044212812/jobs/9046965683?pr=12209#step:6:1253

enjoy-binbin · 2023-05-22T11:29:10Z

don't worry, it looks like the failure has nothing to do with this PR.
the test framework occasionally does this.

vitarb · 2023-05-23T21:19:43Z

Do we have any confirmation from benchmarks or profiling which show that this provides any performance benefits?
Also it looks like module code is already using something similar https://github.com/redis/redis/blob/unstable/src/module.c#L10895 should we try to unify our approach?

src/db.c

judeng · 2023-05-29T07:10:30Z

Do we have any confirmation from benchmarks or profiling which show that this provides any performance benefits?
Also it looks like module code is already using something similar https://github.com/redis/redis/blob/unstable/src/module.c#L10895 should we try to unify our approach?

@vitarb thank you and sorry for the late reply, we indeed need a benchmark and I will test it when all advises are fixed.
I'm not good at aboult module, IMO the code is reusable enough, both scan command and module use the dictScan function, but have a different callback function.

judeng · 2023-05-31T09:09:00Z

@vitarb @oranagra hi, here is the perfomance result:

scan keys which have expirtion time

scan	match all	scan pattern and 100% unmatched	scan pattern and 50% unmatched	scan type and 100% matched	scan type and 100% unmatched	scan type and 50% matched
unstable	24785	60916	33435	16693	26946	21249
this pr	24925	169997	40288	22913	130979	42820

hscan key which use dict encoding

hscan	100% matched	hscan pattern and 100% unmatched
unstable	17949	31693
this pr	18088	143322

sscan key wich use intset encoding

sscan intset	100% matched	sscan pattern and 20% matched
unstable	7529	10255
this pr	7819	22122

zscan key which use listpack encoding

zscan listpack	100% matched	zscan pattern and 10% matched
unstable	18794	28605
this pr	20004	81147

src/db.c

Co-authored-by: sundb <[email protected]>

src/db.c

Co-authored-by: sundb <[email protected]>

…-scan

oranagra

thanks. mostly LGTM>

src/db.c

judeng · 2023-06-16T13:38:00Z

@oranagra I just finished it according to your last review and compare the benchmark performance bettwen before and after the lastest commit.

benchmark command: scan 0 type string count 1000

scan	100% type matched	100% type unmatched
before	2432	7811
after	2491	8537

benchmark command:sscan set1 0 count 1000, set1 is a key with intset encoding.
benchmark command:sscan hash1 0 count 1000, hash1 is a key with hash encoding, and every field is bigger the 44bytes(avoid
use emb str object).

command	sscan	hscan
before	18959	114058
after	19099	121752

result analysis:

when type string convert to interger, if the key 100% match the type, the performance bottleneck seems to be on the reply, and the performance increase is negligible. But when all key can't match the type, that is, reply is always empty, we gain a 9% increase.
Using the sds instread of robj, when filed is small that always used the emb string object, there is nothing different in performance. But when the robj is raw string at before, we gain a 7% increase.

src/server.h

… sensitive

src/db.c

tests/unit/moduleapi/datatype.tcl

oranagra · 2023-06-26T13:09:00Z

@judeng thanks for following all my requests (both the tips to incrementally further improve SCAN compared to what this PR initially meant to do), and also the rollback process, tests and comments.
i'm quite happy with the final result.

one last comment to handle IMHO is #12209 (comment)
i.e. next to the currently disabled SCAN unknown type test, add a temporary one that does the opposite (prove that unknown types don't filter anything).

after that, please refresh the top comment, which i'll use as a squash-merge commit comment. if you can also include some raw benchmark numbers to give an idea of the impact of this PR on performance. and then i'll merge it.

judeng · 2023-06-26T14:22:40Z

Looks all set, I'm going to retest the performance impact tomorrow.

oranagra · 2023-06-26T16:11:44Z

@judeng I updated the top comment. let me know if you see any problem.
i.e. the current version doesn't have any behavior changes (we moved them all to 8.0)

oranagra · 2023-06-26T17:10:45Z

i checked out this PR, to do two things:

run coverage report, in which i found that the listDelNode after expireIfNeeded was uncovered (apparently all the tests for expiring keys used TYPE filter).
run all the new tests against the old version, to make sure we didn't have any unnoticed behavior change.

oranagra · 2023-06-26T17:12:39Z

full CI: https://github.com/redis/redis/actions/runs/5381646678

oranagra · 2023-06-26T18:25:55Z

run coverage report, in which i found that the listDelNode after expireIfNeeded was uncovered (apparently all the tests for expiring keys used TYPE filter).

i now realize that this was already covered by expire.tcl (i only tested coverage by running scan.tcl).
but that test seems to be focused on MULTI-EXEC and replication, so i suppose we better keep the one i added.

src/db.c

Co-authored-by: sundb <[email protected]>

judeng · 2023-06-27T10:24:12Z

@oranagra I have updated the performance test results in the top comment, it seems that except for the type filter, the other results have not changed much

oranagra · 2023-06-27T11:21:34Z

Thanks.
is the first column, the one who says "match all" completely unfiltered?
i understand that none of these tests use volatile keys, right?

judeng · 2023-06-27T12:24:49Z

is the first column, the one who says "match all" completely unfiltered?

yes, I used the match *, actually it is eqaul with no any filters.

i understand that none of these tests use volatile keys, right?

yes, I used the no-volatile keys to better display the perfermance improvement :-)

oranagra · 2023-06-27T13:45:34Z

merged.
@judeng thank you for your dedicated work.
feel free to issue another PR to delete / uncomment lines, which i'll merge to unstable once 7.2 is out. (just so that we don't forget).
feel free to re-do some benchmark to show what additional improvements it brigs.

oranagra · 2023-07-02T17:42:16Z

@judeng can you make a PR? i'm afraid to forget...

judeng · 2023-07-03T05:38:51Z

@oranagra Sorry, I didn't forget about it, just had a couple of nasty accidents last week so I didn't have time, I'll to work on it this week.

Move the TYPE filtering to the scan callback so that avoided the `lookupKey` operation. This is the follow-up to #12209 . In this thread we introduced two breaking changes： 1. we will not attempt to do lazy expire (delete) a key that was filtered by not matching the TYPE (like we already do for MATCH pattern). 2. when the specified key TYPE filter is an unknown type, server will reply a error immediately instead of doing a full scan that comes back empty handed.

…2395) Move the TYPE filtering to the scan callback so that avoided the `lookupKey` operation. This is the follow-up to redis#12209 . In this thread we introduced two breaking changes： 1. we will not attempt to do lazy expire (delete) a key that was filtered by not matching the TYPE (like we already do for MATCH pattern). 2. when the specified key TYPE filter is an unknown type, server will reply a error immediately instead of doing a full scan that comes back empty handed.

avoid double checking expire time for scan command when command speci…

eb21808

…fying a definite type

judeng added 2 commits May 23, 2023 19:52

avoid lookupkey when scan with a definite type

c2eaf52

add some comments

e73f303

judeng changed the title ~~avoid double checking expire time for scan command when command specifying a definite type~~ improve performance for scan command when command specifying a definite data type May 23, 2023

revert wrong file

ba949f2

oranagra reviewed May 24, 2023

View reviewed changes

src/db.c Outdated Show resolved Hide resolved

src/db.c Show resolved Hide resolved

improve performance

ebb715d

judeng changed the title ~~improve performance for scan command when command specifying a definite data type~~ improve performance for scan command when matching pattern or data type May 30, 2023

judeng added 3 commits May 30, 2023 18:07

add sampled count

d4c0a3d

fix regression of intset scan

e610262

improve listpack

b9cf087

judeng mentioned this pull request Jun 1, 2023

use embedded string object and more efficient ll2string for long long value convert to string #12250

Merged

fix test failed case

a6de5a9

sundb reviewed Jun 5, 2023

View reviewed changes

src/db.c Outdated Show resolved Hide resolved

src/db.c Outdated Show resolved Hide resolved

Update src/db.c

8a4a2ee

Co-authored-by: sundb <[email protected]>

sundb reviewed Jun 6, 2023

View reviewed changes

src/db.c Outdated Show resolved Hide resolved

sundb reviewed Jun 6, 2023

View reviewed changes

src/db.c Show resolved Hide resolved

judeng and others added 5 commits June 7, 2023 19:24

Update src/db.c

f2659c9

Co-authored-by: sundb <[email protected]>

Update src/db.c

2430d60

Co-authored-by: sundb <[email protected]>

Merge branch 'unstable' of github.com:redis/redis into optimize-scan

d44ca46

Merge branch 'optimize-scan' of github.com:judeng/redis into optimize…

497c64d

…-scan

update comment

0b7ccbd

oranagra reviewed Jun 11, 2023

View reviewed changes

src/db.c Outdated Show resolved Hide resolved

src/db.c Outdated Show resolved Hide resolved

compare the object type directively instead of matching string:w

708b857

oranagra reviewed Jun 26, 2023

View reviewed changes

src/server.h Show resolved Hide resolved

fix bug and add test case to cover the scenario module name with case…

ee0fcbd

… sensitive

oranagra reviewed Jun 26, 2023

View reviewed changes

src/db.c Outdated Show resolved Hide resolved

tests/unit/moduleapi/datatype.tcl Show resolved Hide resolved

tests/unit/moduleapi/datatype.tcl Outdated Show resolved Hide resolved

delete error comments

47b7367

judeng added 2 commits June 26, 2023 21:56

add test cases

f66c89e

add comments for test case

c7c3728

add coverage for expireIfNeeded deletions

35dacf2

improve comment

dad663b

sundb reviewed Jun 27, 2023

View reviewed changes

src/db.c Outdated Show resolved Hide resolved

Update src/db.c

2fc4f6d

Co-authored-by: sundb <[email protected]>

oranagra merged commit 07ed0ea into redis:unstable Jun 27, 2023

oranagra added release-notes indication that this issue needs to be mentioned in the release notes and removed state:major-decision Requires core team consensus labels Jun 27, 2023

judeng mentioned this pull request Jul 8, 2023

improve performance for scan command when matching data type #12395

Merged

oranagra mentioned this pull request Jul 10, 2023

Relase 7.2-RC3 #12402

Merged

sundb mentioned this pull request Jun 5, 2024

improve performance for scan command when matching data type #13324

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

improve performance for scan command when matching pattern or data type #12209

improve performance for scan command when matching pattern or data type #12209

judeng commented May 22, 2023 •

edited by oranagra

Loading

judeng commented May 22, 2023

enjoy-binbin commented May 22, 2023

vitarb commented May 23, 2023 •

edited

Loading

judeng commented May 29, 2023 •

edited

Loading

judeng commented May 31, 2023

oranagra left a comment

judeng commented Jun 16, 2023 •

edited

Loading

oranagra commented Jun 26, 2023

judeng commented Jun 26, 2023

oranagra commented Jun 26, 2023

oranagra commented Jun 26, 2023

oranagra commented Jun 26, 2023 •

edited

Loading

oranagra commented Jun 26, 2023

judeng commented Jun 27, 2023

oranagra commented Jun 27, 2023

judeng commented Jun 27, 2023

oranagra commented Jun 27, 2023

oranagra commented Jul 2, 2023

judeng commented Jul 3, 2023

improve performance for scan command when matching pattern or data type #12209

improve performance for scan command when matching pattern or data type #12209

Conversation

judeng commented May 22, 2023 • edited by oranagra Loading

judeng commented May 22, 2023

enjoy-binbin commented May 22, 2023

vitarb commented May 23, 2023 • edited Loading

judeng commented May 29, 2023 • edited Loading

judeng commented May 31, 2023

oranagra left a comment

Choose a reason for hiding this comment

judeng commented Jun 16, 2023 • edited Loading

oranagra commented Jun 26, 2023

judeng commented Jun 26, 2023

oranagra commented Jun 26, 2023

oranagra commented Jun 26, 2023

oranagra commented Jun 26, 2023 • edited Loading

oranagra commented Jun 26, 2023

judeng commented Jun 27, 2023

oranagra commented Jun 27, 2023

judeng commented Jun 27, 2023

oranagra commented Jun 27, 2023

oranagra commented Jul 2, 2023

judeng commented Jul 3, 2023

judeng commented May 22, 2023 •

edited by oranagra

Loading

vitarb commented May 23, 2023 •

edited

Loading

judeng commented May 29, 2023 •

edited

Loading

judeng commented Jun 16, 2023 •

edited

Loading

oranagra commented Jun 26, 2023 •

edited

Loading