tests/unit/sort.tcl

   1 start_server {
   2     tags {"sort"}
   3     overrides {
   4         "list-max-ziplist-value" 16
   5         "list-max-ziplist-entries" 32
   6         "set-max-intset-entries" 32
   7     }
   8 } {
   9     proc create_random_dataset {num cmd} {
  10         set tosort {}
  11         set result {}
  12         array set seenrand {}
  13         r del tosort
  14         for {set i 0} {$i < $num} {incr i} {
  15             # Make sure all the weights are different because
  16             # Redis does not use a stable sort but Tcl does.
  17             while 1 {
  18                 randpath {
  19                     set rint [expr int(rand()*1000000)]
  20                 } {
  21                     set rint [expr rand()]
  22                 }
  23                 if {![info exists seenrand($rint)]} break
  24             }
  25             set seenrand($rint) x
  26             r $cmd tosort $i
  27             r set weight_$i $rint
  28             r hset wobj_$i weight $rint
  29             lappend tosort [list $i $rint]
  30         }
  31         set sorted [lsort -index 1 -real $tosort]
  32         for {set i 0} {$i < $num} {incr i} {
  33             lappend result [lindex $sorted $i 0]
  34         }
  35         set _ $result
  36     }
  37
  38     foreach {num cmd enc title} {
  39         16 lpush ziplist "Ziplist"
  40         1000 lpush linkedlist "Linked list"
  41         10000 lpush linkedlist "Big Linked list"
  42         16 sadd intset "Intset"
  43         1000 sadd hashtable "Hash table"
  44         10000 sadd hashtable "Big Hash table"
  45     } {
  46         set result [create_random_dataset $num $cmd]
  47         assert_encoding $enc tosort
  48
  49         test "$title: SORT BY key" {
  50             assert_equal $result [r sort tosort BY weight_*]
  51         }
  52
  53         test "$title: SORT BY key with limit" {
  54             assert_equal [lrange $result 5 9] [r sort tosort BY weight_* LIMIT 5 5]
  55         }
  56
  57         test "$title: SORT BY hash field" {
  58             assert_equal $result [r sort tosort BY wobj_*->weight]
  59         }
  60     }
  61
  62     set result [create_random_dataset 16 lpush]
  63     test "SORT GET #" {
  64         assert_equal [lsort -integer $result] [r sort tosort GET #]
  65     }
  66
  67     test "SORT GET <const>" {
  68         r del foo
  69         set res [r sort tosort GET foo]
  70         assert_equal 16 [llength $res]
  71         foreach item $res { assert_equal {} $item }
  72     }
  73
  74     test "SORT GET (key and hash) with sanity check" {
  75         set l1 [r sort tosort GET # GET weight_*]
  76         set l2 [r sort tosort GET # GET wobj_*->weight]
  77         foreach {id1 w1} $l1 {id2 w2} $l2 {
  78             assert_equal $id1 $id2
  79             assert_equal $w1 [r get weight_$id1]
  80             assert_equal $w2 [r get weight_$id1]
  81         }
  82     }
  83
  84     test "SORT BY key STORE" {
  85         r sort tosort BY weight_* store sort-res
  86         assert_equal $result [r lrange sort-res 0 -1]
  87         assert_equal 16 [r llen sort-res]
  88         assert_encoding ziplist sort-res
  89     }
  90
  91     test "SORT BY hash field STORE" {
  92         r sort tosort BY wobj_*->weight store sort-res
  93         assert_equal $result [r lrange sort-res 0 -1]
  94         assert_equal 16 [r llen sort-res]
  95         assert_encoding ziplist sort-res
  96     }
  97
  98     test "SORT DESC" {
  99         assert_equal [lsort -decreasing -integer $result] [r sort tosort DESC]
 100     }
 101
 102     test "SORT ALPHA against integer encoded strings" {
 103         r del mylist
 104         r lpush mylist 2
 105         r lpush mylist 1
 106         r lpush mylist 3
 107         r lpush mylist 10
 108         r sort mylist alpha
 109     } {1 10 2 3}
 110
 111     test "SORT sorted set" {
 112         r del zset
 113         r zadd zset 1 a
 114         r zadd zset 5 b
 115         r zadd zset 2 c
 116         r zadd zset 10 d
 117         r zadd zset 3 e
 118         r sort zset alpha desc
 119     } {e d c b a}
 120
 121     test "SORT sorted set BY nosort should retain ordering" {
 122         r del zset
 123         r zadd zset 1 a
 124         r zadd zset 5 b
 125         r zadd zset 2 c
 126         r zadd zset 10 d
 127         r zadd zset 3 e
 128         r multi
 129         r sort zset by nosort asc
 130         r sort zset by nosort desc
 131         r exec
 132     } {{a c e b d} {d b e c a}}
 133
 134     test "SORT sorted set BY nosort + LIMIT" {
 135         r del zset
 136         r zadd zset 1 a
 137         r zadd zset 5 b
 138         r zadd zset 2 c
 139         r zadd zset 10 d
 140         r zadd zset 3 e
 141         assert_equal [r sort zset by nosort asc limit 0 1] {a}
 142         assert_equal [r sort zset by nosort desc limit 0 1] {d}
 143         assert_equal [r sort zset by nosort asc limit 0 2] {a c}
 144         assert_equal [r sort zset by nosort desc limit 0 2] {d b}
 145         assert_equal [r sort zset by nosort limit 5 10] {}
 146         assert_equal [r sort zset by nosort limit -10 100] {a c e b d}
 147     }
 148
 149     test "SORT sorted set BY nosort works as expected from scripts" {
 150         r del zset
 151         r zadd zset 1 a
 152         r zadd zset 5 b
 153         r zadd zset 2 c
 154         r zadd zset 10 d
 155         r zadd zset 3 e
 156         r eval {
 157             return {redis.call('sort','zset','by','nosort','asc'),
 158                     redis.call('sort','zset','by','nosort','desc')}
 159         } 0
 160     } {{a c e b d} {d b e c a}}
 161
 162     test "SORT sorted set: +inf and -inf handling" {
 163         r del zset
 164         r zadd zset -100 a
 165         r zadd zset 200 b
 166         r zadd zset -300 c
 167         r zadd zset 1000000 d
 168         r zadd zset +inf max
 169         r zadd zset -inf min
 170         r zrange zset 0 -1
 171     } {min c a b d max}
 172
 173     test "SORT regression for issue #19, sorting floats" {
 174         r flushdb
 175         set floats {1.1 5.10 3.10 7.44 2.1 5.75 6.12 0.25 1.15}
 176         foreach x $floats {
 177             r lpush mylist $x
 178         }
 179         assert_equal [lsort -real $floats] [r sort mylist]
 180     }
 181
 182     test "SORT with STORE returns zero if result is empty (github isse 224)" {
 183         r flushdb
 184         r sort foo store bar
 185     } {0}
 186
 187     test "SORT with STORE does not create empty lists (github issue 224)" {
 188         r flushdb
 189         r lpush foo bar
 190         r sort foo alpha limit 10 10 store zap
 191         r exists zap
 192     } {0}
 193
 194     test "SORT with STORE removes key if result is empty (github issue 227)" {
 195         r flushdb
 196         r lpush foo bar
 197         r sort emptylist store foo
 198         r exists foo
 199     } {0}
 200
 201     test "SORT with BY <constant> and STORE should still order output" {
 202         r del myset mylist
 203         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
 204         r sort myset alpha by _ store mylist
 205         r lrange mylist 0 -1
 206     } {a aa aaa azz b c d e f g h i l m n o p q r s t u v z}
 207
 208     test "SORT will complain with numerical sorting and bad doubles (1)" {
 209         r del myset
 210         r sadd myset 1 2 3 4 not-a-double
 211         set e {}
 212         catch {r sort myset} e
 213         set e
 214     } {*ERR*double*}
 215
 216     test "SORT will complain with numerical sorting and bad doubles (2)" {
 217         r del myset
 218         r sadd myset 1 2 3 4
 219         r mset score:1 10 score:2 20 score:3 30 score:4 not-a-double
 220         set e {}
 221         catch {r sort myset by score:*} e
 222         set e
 223     } {*ERR*double*}
 224
 225     test "SORT BY sub-sorts lexicographically if score is the same" {
 226         r del myset
 227         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
 228         foreach ele {a aa aaa azz b c d e f g h i l m n o p q r s t u v z} {
 229             set score:$ele 100
 230         }
 231         r sort myset by score:*
 232     } {a aa aaa azz b c d e f g h i l m n o p q r s t u v z}
 233
 234     test "SORT GET with pattern ending with just -> does not get hash field" {
 235         r del mylist
 236         r lpush mylist a
 237         r set x:a-> 100
 238         r sort mylist by num get x:*->
 239     } {100}
 240
 241     tags {"slow"} {
 242         set num 100
 243         set res [create_random_dataset $num lpush]
 244
 245         test "SORT speed, $num element list BY key, 100 times" {
 246             set start [clock clicks -milliseconds]
 247             for {set i 0} {$i < 100} {incr i} {
 248                 set sorted [r sort tosort BY weight_* LIMIT 0 10]
 249             }
 250             set elapsed [expr [clock clicks -milliseconds]-$start]
 251             if {$::verbose} {
 252                 puts -nonewline "\n  Average time to sort: [expr double($elapsed)/100] milliseconds "
 253                 flush stdout
 254             }
 255         }
 256
 257         test "SORT speed, $num element list BY hash field, 100 times" {
 258             set start [clock clicks -milliseconds]
 259             for {set i 0} {$i < 100} {incr i} {
 260                 set sorted [r sort tosort BY wobj_*->weight LIMIT 0 10]
 261             }
 262             set elapsed [expr [clock clicks -milliseconds]-$start]
 263             if {$::verbose} {
 264                 puts -nonewline "\n  Average time to sort: [expr double($elapsed)/100] milliseconds "
 265                 flush stdout
 266             }
 267         }
 268
 269         test "SORT speed, $num element list directly, 100 times" {
 270             set start [clock clicks -milliseconds]
 271             for {set i 0} {$i < 100} {incr i} {
 272                 set sorted [r sort tosort LIMIT 0 10]
 273             }
 274             set elapsed [expr [clock clicks -milliseconds]-$start]
 275             if {$::verbose} {
 276                 puts -nonewline "\n  Average time to sort: [expr double($elapsed)/100] milliseconds "
 277                 flush stdout
 278             }
 279         }
 280
 281         test "SORT speed, $num element list BY <const>, 100 times" {
 282             set start [clock clicks -milliseconds]
 283             for {set i 0} {$i < 100} {incr i} {
 284                 set sorted [r sort tosort BY nokey LIMIT 0 10]
 285             }
 286             set elapsed [expr [clock clicks -milliseconds]-$start]
 287             if {$::verbose} {
 288                 puts -nonewline "\n  Average time to sort: [expr double($elapsed)/100] milliseconds "
 289                 flush stdout
 290             }
 291         }
 292     }
 293 }