Iterate a LIST or SET in Lua without loading all in memory

[Robert DiFalco]

Is there an efficient way to iterate over the members of a LIST in LUA without loading them all into memory? I assume LRANGE would load them all into memory while LINDEX would become slow as I incremented the index counter. 

[Nils Kilden-Pedersen]

You can iterate manually, using LRANGE slices.

On Tue, Sep 2, 2014 at 12:27 PM, Robert DiFalco <robert....@gmail.com> wrote:

Is there an efficient way to iterate over the members of a LIST in LUA without loading them all into memory? I assume LRANGE would load them all into memory while LINDEX would become slow as I incremented the index counter. 

--
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 http://groups.google.com/group/redis-db.
For more options, visit https://groups.google.com/d/optout.

[Robert DiFalco]

Thanks Nils, but I'm guessing that won't be super efficient for a large list. I assume the LIST is stored internally as a linked list. As a result, to get a range that doesn't not start's at N, REDIS has to iterate through the list to get to N giving it O(N) performance. It's a shame there is no construct with LUA to just iterate through the links.

But in the end for a 1000 element list, iterating with LINDEX would be SUPER slow whereas LRANGE at 100 is just a little slow (i.e. REDIS only has to iterate to position 100 times instead of 1000 times).

  

--
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/oXOcPBxHvN0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to redis-db+u...@googlegroups.com.

[Nils Kilden-Pedersen]

On Tue, Sep 2, 2014 at 12:55 PM, Robert DiFalco <robert....@gmail.com> wrote:

Thanks Nils, but I'm guessing that won't be super efficient for a large list. I assume the LIST is stored internally as a linked list. As a result, to get a range that doesn't not start's at N, REDIS has to iterate through the list to get to N giving it O(N) performance. It's a shame there is no construct with LUA to just iterate through the links.

Yes, Redis lists do not work well for a lot of use cases with very large lists.

[Matt Stancliff]

On Sep 2, 2014, at 1:55 PM, Robert DiFalco <robert....@gmail.com> wrote:

> Thanks Nils, but I'm guessing that won't be super efficient for a large list. I assume the LIST is stored internally as a linked list. As a result, to get a range that doesn't not start's at N, REDIS has to iterate through the list to get to N giving it O(N) performance. It's a shame there is no construct with LUA to just iterate through the links.

See the Circular List section of http://redis.io/commands/rpoplpush — "a client can visit all the elements of an N-elements list, one after the other, inO(N) without transferring the full list from the server to the client using a single LRANGE operation.”


-Matt

[Josiah Carlson]

As an alternative to the earlier discussion, SSCAN will let you incrementally scan over a SET, though it is not as efficient in that context.

If all you are looking to do is to efficiently paginate over a sequence, and you can do what you want with SETs, then you can use a score of 0 or 1* for all of your items in the ZSET, and pagination is trivial.

* If you don't need an SDIFF-equivalent for this, you can use scores of 0. If you want something like SDIFF for ZSETs, use scores of 1.

 - Josiah

On Tue, Sep 2, 2014 at 11:28 AM, Matt Stancliff <mstan...@gopivotal.com> wrote:

On Sep 2, 2014, at 1:55 PM, Robert DiFalco <robert....@gmail.com> wrote:

> Thanks Nils, but I'm guessing that won't be super efficient for a large list. I assume the LIST is stored internally as a linked list. As a result, to get a range that doesn't not start's at N, REDIS has to iterate through the list to get to N giving it O(N) performance. It's a shame there is no construct with LUA to just iterate through the links.

See the Circular List section of http://redis.io/commands/rpoplpush -- "a client can visit all the elements of an N-elements list, one after the other, inO(N) without transferring the full list from the server to the client using a single LRANGE operation."


-Matt