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: +inf and -inf handling" {
 122         r del zset
 123         r zadd zset -100 a
 124         r zadd zset 200 b
 125         r zadd zset -300 c
 126         r zadd zset 1000000 d
 127         r zadd zset +inf max
 128         r zadd zset -inf min
 129         r zrange zset 0 -1
 130     } {min c a b d max}
 131
 132     test "SORT regression for issue #19, sorting floats" {
 133         r flushdb
 134         set floats {1.1 5.10 3.10 7.44 2.1 5.75 6.12 0.25 1.15}
 135         foreach x $floats {
 136             r lpush mylist $x
 137         }
 138         assert_equal [lsort -real $floats] [r sort mylist]
 139     }
 140
 141     test "SORT with STORE returns zero if result is empty (github isse 224)" {
 142         r flushdb
 143         r sort foo store bar
 144     } {0}
 145
 146     test "SORT with STORE does not create empty lists (github issue 224)" {
 147         r flushdb
 148         r lpush foo bar
 149         r sort foo alpha limit 10 10 store zap
 150         r exists zap
 151     } {0}
 152
 153     test "SORT with STORE removes key if result is empty (github issue 227)" {
 154         r flushdb
 155         r lpush foo bar
 156         r sort emptylist store foo
 157         r exists foo
 158     } {0}
 159
 160     test "SORT with BY <constant> and STORE should still order output" {
 161         r del myset mylist
 162         r sadd myset a b c d e f g h i l m n o p q r s t u v z
 163         r sort myset alpha by _ store mylist
 164         r lrange mylist 0 -1
 165     } {a b c d e f g h i l m n o p q r s t u v z}
 166
 167     test "SORT will complain with numerical sorting and bad doubles (1)" {
 168         r del myset
 169         r sadd myset 1 2 3 4 not-a-double
 170         set e {}
 171         catch {r sort myset} e
 172         set e
 173     } {*ERR*double*}
 174
 175     test "SORT will complain with numerical sorting and bad doubles (2)" {
 176         r del myset
 177         r sadd myset 1 2 3 4
 178         r mset score:1 10 score:2 20 score:3 30 score:4 not-a-double
 179         set e {}
 180         catch {r sort myset by score:*} e
 181         set e
 182     } {*ERR*double*}
 183
 184     test "SORT BY sub-sorts lexicographically if score is the same" {
 185         r del myset
 186         r sadd myset u v z a b c d e f g h i l m n o p q r s t
 187         foreach ele {a b c d e f g h i l m n o p q r s t u v z} {
 188             set score:$ele 100
 189         }
 190         r sort myset by score:*
 191     } {a b c d e f g h i l m n o p q r s t u v z}
 192
 193     tags {"slow"} {
 194         set num 100
 195         set res [create_random_dataset $num lpush]
 196
 197         test "SORT speed, $num element list BY key, 100 times" {
 198             set start [clock clicks -milliseconds]
 199             for {set i 0} {$i < 100} {incr i} {
 200                 set sorted [r sort tosort BY weight_* LIMIT 0 10]
 201             }
 202             set elapsed [expr [clock clicks -milliseconds]-$start]
 203             if {$::verbose} {
 204                 puts -nonewline "\n  Average time to sort: [expr double($elapsed)/100] milliseconds "
 205                 flush stdout
 206             }
 207         }
 208
 209         test "SORT speed, $num element list BY hash field, 100 times" {
 210             set start [clock clicks -milliseconds]
 211             for {set i 0} {$i < 100} {incr i} {
 212                 set sorted [r sort tosort BY wobj_*->weight LIMIT 0 10]
 213             }
 214             set elapsed [expr [clock clicks -milliseconds]-$start]
 215             if {$::verbose} {
 216                 puts -nonewline "\n  Average time to sort: [expr double($elapsed)/100] milliseconds "
 217                 flush stdout
 218             }
 219         }
 220
 221         test "SORT speed, $num element list directly, 100 times" {
 222             set start [clock clicks -milliseconds]
 223             for {set i 0} {$i < 100} {incr i} {
 224                 set sorted [r sort tosort LIMIT 0 10]
 225             }
 226             set elapsed [expr [clock clicks -milliseconds]-$start]
 227             if {$::verbose} {
 228                 puts -nonewline "\n  Average time to sort: [expr double($elapsed)/100] milliseconds "
 229                 flush stdout
 230             }
 231         }
 232
 233         test "SORT speed, $num element list BY <const>, 100 times" {
 234             set start [clock clicks -milliseconds]
 235             for {set i 0} {$i < 100} {incr i} {
 236                 set sorted [r sort tosort BY nokey LIMIT 0 10]
 237             }
 238             set elapsed [expr [clock clicks -milliseconds]-$start]
 239             if {$::verbose} {
 240                 puts -nonewline "\n  Average time to sort: [expr double($elapsed)/100] milliseconds "
 241                 flush stdout
 242             }
 243         }
 244     }
 245 }