question about SCAN cursor MATCH pattern speed

[Doug Davis]

Hello,

Here: https://redis.io/commands/scan it says:

Time complexity: O(1) for every call. O(N) for a complete iteration, including enough command calls for the cursor to return back to 0. N is the number of elements inside the collection.

So, the time to execute a full iteration grows in proportion to the size of the collection (which I'm thinking means the number of keys stored in Redis, correct?).

Is this true even if a pattern is passed in that matches one key (for example)?  

If the pattern only matches one key then will a scan through a collection that has a million keys take approximately 1,000 times longer than a scan through a collection with a 1,000 keys?  Or am I misunderstanding?

Thanks,

Doug

[Doug Davis]

Looking again... I'm thinking "collection" is the number of matched keys.

- Doug

[Jan-Erik Rediger]

A full iteration is O(N) with N being the number of ALL keys in the database.
Even if you add a MATCH [patter] it still has to scan all keys to reach
a decision.

So yes, if you have 1,000 times more keys, it will take 1,000 times
longer to do a full iteration (but at least you won't block the server)

On Wed, Jul 12, 2017 at 12:53:27PM -0700, Doug Davis wrote:
>
> Looking again... I'm thinking "collection" is the number of matched keys.
> - Doug
>
> On Wednesday, July 12, 2017 at 3:46:52 PM UTC-4, Doug Davis wrote:
> >
> > Hello,
> >
> > Here: https://redis.io/commands/scan it says:
> >

> > *Time complexity:* O(1) for every call. O(N) for a complete iteration,

> > including enough command calls for the cursor to return back to 0. N is the
> > number of elements inside the collection.
> >
> > So, the time to execute a full iteration grows in proportion to the size
> > of the collection (which I'm thinking means the number of keys stored in
> > Redis, correct?).
> >
> > Is this true even if a pattern is passed in that matches one key (for
> > example)?
> >
> > If the pattern only matches one key then will a scan through a collection
> > that has a million keys take approximately 1,000 times longer than a scan
> > through a collection with a 1,000 keys? Or am I misunderstanding?
> >
> > Thanks,
> > Doug
> >
>

> --
> You received this message because you are subscribed to the Google Groups "Redis DB" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to redis-db+u...@googlegroups.com.
> To post to this group, send email to redi...@googlegroups.com.
> Visit this group at https://groups.google.com/group/redis-db.
> For more options, visit https://groups.google.com/d/optout.

[Doug Davis]

Ok thanks, wishful thinking I guess.  I was thinking that Redis would have some type of better indexing to do that, but I guess that would slow set() down.

- Doug

> To unsubscribe from this group and stop receiving emails from it, send an email to redis-db+unsubscribe@googlegroups.com.

> To post to this group, send email to redi...@googlegroups.com.
> Visit this group at https://groups.google.com/group/redis-db.
> For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to a topic in the Google Groups "Redis DB" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/redis-db/d3Pdy71rF0I/unsubscribe.
To unsubscribe from this group and all its topics, send an email to redis-db+unsubscribe@googlegroups.com.