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         64 lpush linkedlist "Linked list"
  41         64 sadd hashtable "Hash table"
  42     } {
  43         set result [create_random_dataset $num $cmd]
  44         assert_encoding $enc tosort
  45
  46         test "$title: SORT BY key" {
  47             assert_equal $result [r sort tosort {BY weight_*}]
  48         }
  49
  50         test "$title: SORT BY hash field" {
  51             assert_equal $result [r sort tosort {BY wobj_*->weight}]
  52         }
  53     }
  54
  55     set result [create_random_dataset 16 lpush]
  56     test "SORT GET #" {
  57         assert_equal [lsort -integer $result] [r sort tosort GET #]
  58     }
  59
  60     test "SORT GET <const>" {
  61         r del foo
  62         set res [r sort tosort GET foo]
  63         assert_equal 16 [llength $res]
  64         foreach item $res { assert_equal {} $item }
  65     }
  66
  67     test "SORT GET (key and hash) with sanity check" {
  68         set l1 [r sort tosort GET # GET weight_*]
  69         set l2 [r sort tosort GET # GET wobj_*->weight]
  70         foreach {id1 w1} $l1 {id2 w2} $l2 {
  71             assert_equal $id1 $id2
  72             assert_equal $w1 [r get weight_$id1]
  73             assert_equal $w2 [r get weight_$id1]
  74         }
  75     }
  76
  77     test "SORT BY key STORE" {
  78         r sort tosort {BY weight_*} store sort-res
  79         assert_equal $result [r lrange sort-res 0 -1]
  80         assert_equal 16 [r llen sort-res]
  81         assert_encoding ziplist sort-res
  82     }
  83
  84     test "SORT BY hash field STORE" {
  85         r sort tosort {BY wobj_*->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 DESC" {
  92         assert_equal [lsort -decreasing -integer $result] [r sort tosort {DESC}]
  93     }
  94
  95     test "SORT ALPHA against integer encoded strings" {
  96         r del mylist
  97         r lpush mylist 2
  98         r lpush mylist 1
  99         r lpush mylist 3
 100         r lpush mylist 10
 101         r sort mylist alpha
 102     } {1 10 2 3}
 103
 104     test "SORT sorted set" {
 105         r del zset
 106         r zadd zset 1 a
 107         r zadd zset 5 b
 108         r zadd zset 2 c
 109         r zadd zset 10 d
 110         r zadd zset 3 e
 111         r sort zset alpha desc
 112     } {e d c b a}
 113
 114     test "SORT sorted set: +inf and -inf handling" {
 115         r del zset
 116         r zadd zset -100 a
 117         r zadd zset 200 b
 118         r zadd zset -300 c
 119         r zadd zset 1000000 d
 120         r zadd zset +inf max
 121         r zadd zset -inf min
 122         r zrange zset 0 -1
 123     } {min c a b d max}
 124
 125     test "SORT regression for issue #19, sorting floats" {
 126         r flushdb
 127         set floats {1.1 5.10 3.10 7.44 2.1 5.75 6.12 0.25 1.15}
 128         foreach x $floats {
 129             r lpush mylist $x
 130         }
 131         assert_equal [lsort -real $floats] [r sort mylist]
 132     }
 133
 134     tags {"slow"} {
 135         set num 100
 136         set res [create_random_dataset $num lpush]
 137
 138         test "SORT speed, $num element list BY key, 100 times" {
 139             set start [clock clicks -milliseconds]
 140             for {set i 0} {$i < 100} {incr i} {
 141                 set sorted [r sort tosort {BY weight_* LIMIT 0 10}]
 142             }
 143             set elapsed [expr [clock clicks -milliseconds]-$start]
 144             puts -nonewline "\n  Average time to sort: [expr double($elapsed)/100] milliseconds "
 145             flush stdout
 146         }
 147
 148         test "SORT speed, $num element list BY hash field, 100 times" {
 149             set start [clock clicks -milliseconds]
 150             for {set i 0} {$i < 100} {incr i} {
 151                 set sorted [r sort tosort {BY wobj_*->weight LIMIT 0 10}]
 152             }
 153             set elapsed [expr [clock clicks -milliseconds]-$start]
 154             puts -nonewline "\n  Average time to sort: [expr double($elapsed)/100] milliseconds "
 155             flush stdout
 156         }
 157
 158         test "SORT speed, $num element list directly, 100 times" {
 159             set start [clock clicks -milliseconds]
 160             for {set i 0} {$i < 100} {incr i} {
 161                 set sorted [r sort tosort {LIMIT 0 10}]
 162             }
 163             set elapsed [expr [clock clicks -milliseconds]-$start]
 164             puts -nonewline "\n  Average time to sort: [expr double($elapsed)/100] milliseconds "
 165             flush stdout
 166         }
 167
 168         test "SORT speed, $num element list BY <const>, 100 times" {
 169             set start [clock clicks -milliseconds]
 170             for {set i 0} {$i < 100} {incr i} {
 171                 set sorted [r sort tosort {BY nokey LIMIT 0 10}]
 172             }
 173             set elapsed [expr [clock clicks -milliseconds]-$start]
 174             puts -nonewline "\n  Average time to sort: [expr double($elapsed)/100] milliseconds "
 175             flush stdout
 176         }
 177     }
 178 }