Scripting: Force SORT BY constant determinism inside SORT itself.

SORT is able to return (faster than when ordering) unordered output if
the "BY" clause is used with a constant value. However we try to play
well with scripting requirements of determinism providing always sorted
outputs when SORT (and other similar commands) are called by Lua
scripts.

However we used the general mechanism in place in scripting in order to
reorder SORT output, that is, if the command has the "S" flag set, the
Lua scripting engine will take an additional step when converting a
multi bulk reply to Lua value, calling a Lua sorting function.

This is suboptimal as we can do it faster inside SORT itself.
This is also broken as issue #545 shows us: basically when SORT is used
with a constant BY, and additionally also GET is used, the Lua scripting
engine was trying to order the output as a flat array, while it was
actually a list of key-value pairs.

What we do know is to recognized if the caller of SORT is the Lua client
(since we can check this using the REDIS_LUA_CLIENT flag). If so, and if
a "don't sort" condition is triggered by the BY option with a constant
string, we force the lexicographical sorting.

This commit fixes this bug and improves the performance, and at the same
time simplifies the implementation. This does not mean I'm smart today,
it means I was stupid when I committed the original implementation ;)

diff --git a/src/redis.c b/src/redis.c
index fb6624eb402918f6e2c6af26c56515b84bd53ebb..1fad059a5bab18f42c5fb8a621043cc875b6c772 100644 (file)
--- a/src/redis.c
+++ b/src/redis.c
@@ -222,7 +222,7 @@ struct redisCommand redisCommandTable[] = {
     {"replconf",replconfCommand,-1,"ars",0,NULL,0,0,0,0,0},
     {"flushdb",flushdbCommand,1,"w",0,NULL,0,0,0,0,0},
     {"flushall",flushallCommand,1,"w",0,NULL,0,0,0,0,0},
     {"replconf",replconfCommand,-1,"ars",0,NULL,0,0,0,0,0},
     {"flushdb",flushdbCommand,1,"w",0,NULL,0,0,0,0,0},
     {"flushall",flushallCommand,1,"w",0,NULL,0,0,0,0,0},

-    {"sort",sortCommand,-2,"wmS",0,NULL,1,1,1,0,0},
+    {"sort",sortCommand,-2,"wm",0,NULL,1,1,1,0,0},

     {"info",infoCommand,-1,"rlt",0,NULL,0,0,0,0,0},
     {"monitor",monitorCommand,1,"ars",0,NULL,0,0,0,0,0},
     {"ttl",ttlCommand,2,"r",0,NULL,1,1,1,0,0},
     {"info",infoCommand,-1,"rlt",0,NULL,0,0,0,0,0},
     {"monitor",monitorCommand,1,"ars",0,NULL,0,0,0,0,0},
     {"ttl",ttlCommand,2,"r",0,NULL,1,1,1,0,0},

diff --git a/src/redis.h b/src/redis.h
index c3fe9a2db02f4e86087e15360b175ca8c4220d85..9c9b72f878a5135a7514e9322f9a47254616da34 100644 (file)
--- a/src/redis.h
+++ b/src/redis.h
@@ -570,7 +570,6 @@ struct redisServer {
     list *unblocked_clients; /* list of clients to unblock before next loop */
     /* Sort parameters - qsort_r() is only available under BSD so we
      * have to take this state global, in order to pass it to sortCompare() */
     list *unblocked_clients; /* list of clients to unblock before next loop */
     /* Sort parameters - qsort_r() is only available under BSD so we
      * have to take this state global, in order to pass it to sortCompare() */

-    int sort_dontsort;

     int sort_desc;
     int sort_alpha;
     int sort_bypattern;
     int sort_desc;
     int sort_alpha;
     int sort_bypattern;

diff --git a/src/scripting.c b/src/scripting.c
index be52a11410c0d3b25b98271439fbdee778d7b063..35b654f7739c490b806cbe5896d30766cbb98ad9 100644 (file)
--- a/src/scripting.c
+++ b/src/scripting.c
@@ -282,8 +282,6 @@ int luaRedisGenericCommand(lua_State *lua, int raise_error) {
      * reply as expected. */
     if ((cmd->flags & REDIS_CMD_SORT_FOR_SCRIPT) &&
         (reply[0] == '*' && reply[1] != '-')) {
      * reply as expected. */
     if ((cmd->flags & REDIS_CMD_SORT_FOR_SCRIPT) &&
         (reply[0] == '*' && reply[1] != '-')) {

-        /* Skip this step if command is SORT but output was already sorted */
-        if (cmd->proc != sortCommand || server.sort_dontsort)

             luaSortArray(lua);
     }
     sdsfree(reply);
             luaSortArray(lua);
     }
     sdsfree(reply);

diff --git a/src/sort.c b/src/sort.c
index c1ed5517f2fc00d4edbf453445cfcc4d5d9f7b76..e5178cd0dfadfd860c0a72daa045d52dad47bab9 100644 (file)
--- a/src/sort.c
+++ b/src/sort.c
@@ -215,8 +215,11 @@ void sortCommand(redisClient *c) {
 
     /* If we have STORE we need to force sorting for deterministic output
      * and replication. We use alpha sorting since this is guaranteed to
 
     /* If we have STORE we need to force sorting for deterministic output
      * and replication. We use alpha sorting since this is guaranteed to

-     * work with any input. */
-    if (storekey && dontsort) {
+     * work with any input.
+     *
+     * We also want determinism when SORT is called from Lua scripts, so
+     * in this case we also force alpha sorting. */
+    if ((storekey || c->flags & REDIS_LUA_CLIENT) && dontsort) {

         dontsort = 0;
         alpha = 1;
         sortby = NULL;
         dontsort = 0;
         alpha = 1;
         sortby = NULL;


@@ -326,7 +329,6 @@ void sortCommand(redisClient *c) {
     }
     if (end >= vectorlen) end = vectorlen-1;
 
     }
     if (end >= vectorlen) end = vectorlen-1;
 

-    server.sort_dontsort = dontsort;

     if (dontsort == 0) {
         server.sort_desc = desc;
         server.sort_alpha = alpha;
     if (dontsort == 0) {
         server.sort_desc = desc;
         server.sort_alpha = alpha;

diff --git a/tests/unit/scripting.tcl b/tests/unit/scripting.tcl
index 6d60e419871117dd5e9a414ecf517fe924b3cda7..0579187166a7e1e89d5b1f060fa399ed51bf9d5f 100644 (file)
--- a/tests/unit/scripting.tcl
+++ b/tests/unit/scripting.tcl
@@ -203,23 +203,23 @@ start_server {tags {"scripting"}} {
         r eval {return redis.call('smembers','myset')} 0
     } {a aa aaa azz b c d e f g h i l m n o p q r s t u v z}
 
         r eval {return redis.call('smembers','myset')} 0
     } {a aa aaa azz b c d e f g h i l m n o p q r s t u v z}
 

-    test "SORT is normally not re-ordered by the scripting engine" {
+    test "SORT is normally not alpha re-ordered for the scripting engine" {

         r del myset
         r sadd myset 1 2 3 4 10
         r eval {return redis.call('sort','myset','desc')} 0
     } {10 4 3 2 1}
 
         r del myset
         r sadd myset 1 2 3 4 10
         r eval {return redis.call('sort','myset','desc')} 0
     } {10 4 3 2 1}
 

-    test "SORT BY <constant> output gets ordered by scripting" {
+    test "SORT BY <constant> output gets ordered for scripting" {

         r del myset
         r sadd myset a b c d e f g h i l m n o p q r s t u v z aa aaa azz
         r eval {return redis.call('sort','myset','by','_')} 0
     } {a aa aaa azz b c d e f g h i l m n o p q r s t u v z}
 
         r del myset
         r sadd myset a b c d e f g h i l m n o p q r s t u v z aa aaa azz
         r eval {return redis.call('sort','myset','by','_')} 0
     } {a aa aaa azz b c d e f g h i l m n o p q r s t u v z}
 

-    test "SORT output containing NULLs is well handled by scripting" {
+    test "SORT BY <constant> with GET gets ordered for scripting" {

         r del myset
         r sadd myset a b c
         r eval {return redis.call('sort','myset','by','_','get','#','get','_:*')} 0
         r del myset
         r sadd myset a b c
         r eval {return redis.call('sort','myset','by','_','get','#','get','_:*')} 0

-    } {{} {} {} a b c}
+    } {a {} b {} c {}}

 
     test "redis.sha1hex() implementation" {
         list [r eval {return redis.sha1hex('')} 0] \
 
     test "redis.sha1hex() implementation" {
         list [r eval {return redis.sha1hex('')} 0] \