why isn't it possible to join two lists in redis or: redis list as a black hole
Oren Dobzinski
isn't it supported in redis? what about adding elements of a set or a
sorted set to a list or other inter data structure operations? I know
it's possible to iterate over the elements of a data structure and add
them one by one, but it won't help me since I'm doing these operations
on the redis side, inside a big pipeline by using the S*STORE
operations.
Whenever I need to SORT anything it needs to go into a list, which is
sort of a data black hole, since I can't continue doing other
operations on that list without reading elements from the list on the
client side.
thanks,
oren
Josiah Carlson
> Joining 2 lists together sounds like a basic and useful operation. Why
> isn't it supported in redis? what about adding elements of a set or a
> sorted set to a list or other inter data structure operations? I know
> it's possible to iterate over the elements of a data structure and add
> them one by one, but it won't help me since I'm doing these operations
> on the redis side, inside a big pipeline by using the S*STORE
> operations.
I don't know for sure, but part of me thinks it's likely because
moving or copying data from one structure to another requires a large
enough set of (source type, destination type) pairs that it didn't
seem reasonable to implement them all. With scripting, you can likely
do almost everything that you wanted to do, but if it runs long, it
will get killed.
> Whenever I need to SORT anything it needs to go into a list, which is
> sort of a data black hole, since I can't continue doing other
> operations on that list without reading elements from the list on the
> client side.
You can also sort sets, fetch data from keys and hashes during sorts.
Regards,
- Josiah
Dvir Volk
--
You received this message because you are subscribed to the Google Groups "Redis DB" group.
To post to this group, send email to redi...@googlegroups.com.
To unsubscribe from this group, send email to redis-db+u...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/redis-db?hl=en.
Jokea
> lpush list2 bar
> ljoin list1 list2 list3 -- join list1 and list2, store in list3
> lpop list3 --- what do you expect to pop from list3, 'foo' or 'bar'?
Regards,
jokea
Oren Dobzinski 写道:
Salvatore Sanfilippo
> Joining 2 lists together sounds like a basic and useful operation. Why
> isn't it supported in redis? what about adding elements of a set or a
> sorted set to a list or other inter data structure operations?
I think that a lot of this operations would get misused. We
implemented abstract data types with specific big-O characteristics
for different operations to give developers full control and different
tradeoffs, however some operations are intrinsically slow (that is,
O(N)), and sometimes without good reasons. LREM is O(N) but is needed,
and when used judiciously is actually O(1) most of the time if your
application is designed to delete with higher probability something
that is toward head or tail.
Concatenating two lists IMHO does not makes enough sense in this
regard, it's O(N), but it's not a fundamentally useful operation. The
effect would be that programmers not familiar with what happens when
time complexity is O(N) and gets misused, would end with a Redis-based
application that used a lot of CPU time without a good reason.
Exporting only a given set of operations Redis tries to put you in the
right track to design good applications using the data structures in a
sensible way. When there is a different need, being it legitimate or
not, there is scripting in Redis 2.6 (work in progress, but it's near
to be released as RC1) that allows you do to all the sort of things.
Cheers,
Salvatore
--
Salvatore 'antirez' Sanfilippo
open source developer - VMware
http://invece.org
"We are what we repeatedly do. Excellence, therefore, is not an act,
but a habit." -- Aristotele
Didier Spezia
Salvatore Sanfilippo
> what Redis could propose is a LSPLICE operation to attach (i.e. move)
> the content of a list into another list.
>
> Splicing a linked-list is a O(1) operation, and traditional implementation
> of this data type usually provides it.
Hi Didier, I agree that this is a good operation, for a couple of reasons:
1) You can't splice from Lua in O(1), but in O(N). While you can
concatenate in Lua and in C in O(N) anyway.
2) It is a fundamental operation.
3) It sounds useful in different cases to have partial results and
then to atomically accumulate results in some other list.
Probably it should allow to specify where to splice, on head or on
tail, like in:
list1 = a b c
list 2 = d e f
LSPLICEL list1 list2 -> list1 deleted, list2 = a b c d e f
LSPLICER list1 list2 -> list1 deleted, list2 = d e f a b c
Special cases:
LSPLICE[RL] list1 list1 -> no operation is performed.
LSPLICE[RL] non-existing-key list > no operation is performed
Note that this is a cross-key operation and as thus will not be part
of Redis Cluster.
Note 2: with ziplists this is not an O(1) operation, but it is
actually very fast as it's a matter of small memcpy() and fixing an
offset if we support that directly at ziplist.c level.
Comments welcomed, if enough people are interested this may become an
approved feature request for post-2.6 times.
Oren Dobzinski
Thanks for the detailed response. Your arguments against adding non-
fundamental O(N) operations totally make sense. SPLICE as defined
above is actually what I need, not joining two lists and storing them
on a third, so I'm all for it. What about other options for SPLICE,
such as a range of elements in the first list to copy or a position in
the second one to copy to (other than just to the left or right end)?
or do you want to keep it clean and simple?
Also, to further elaborate on a point I was trying to make before,
SPLICE will help make redis lists less of a data black hole since you
would be able to efficiently move elements from one list to another
without reading them first on the client side. It was possible to move
elements from list to list before, but only one by one, using
RPOPLPUSH & co. Still, once you have a list you can't turn it into a
set or a sorted set, though you can turn sets and sorted sets into
lists by using SORT. So even with SPLICE, if you have a list (say you
got it by using SORT on a set) and you need to perform some operations
against sets or sorted sets you are forced to read the elements of the
list on the client side and add them one by one to a set or sorted
set. This is problematic if the list is long or if you are in the
middle of a pipeline and simply can't ready these values.
Scripting will indeed solve this problem by allowing users to turn
lists into sets or sorted sets without involving the client, but it
might be a more expensive operation than a hypothetic native-redis one
in terms of CPU since lua is going to be involved (of course it will
be O(N) in both cases).
tl;dr:
1) SPLICE sounds very useful, with or without the range-to-copy and
position-st-target options
2) lists are still a black hole and IMHO it would be useful to let
users turn them into sets or sorted sets, just as "SORT myset BY
nosort STORE mylist" lets them turn sets and sorted sets into lists.
(UNSORT ??!)
thanks,
oren
On Feb 21, 5:54 am, Salvatore Sanfilippo <anti...@gmail.com> wrote:
