X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/ab72b4833d2054231437acccec36f32f07290075..ece77037e9601f9f5d2321cc5a779aef10a4c563:/tests/unit/sort.tcl diff --git a/tests/unit/sort.tcl b/tests/unit/sort.tcl index 2985c3d9..5a181641 100644 --- a/tests/unit/sort.tcl +++ b/tests/unit/sort.tcl @@ -1,20 +1,20 @@ -start_server default.conf {} { - test {SORT ALPHA against integer encoded strings} { - r del mylist - r lpush mylist 2 - r lpush mylist 1 - r lpush mylist 3 - r lpush mylist 10 - r sort mylist alpha - } {1 10 2 3} - - test {Create a random list and a random set} { +start_server { + tags {"sort"} + overrides { + "list-max-ziplist-value" 16 + "list-max-ziplist-entries" 32 + "set-max-intset-entries" 32 + } +} { + proc create_random_dataset {num cmd} { set tosort {} + set result {} array set seenrand {} - for {set i 0} {$i < 10000} {incr i} { + r del tosort + for {set i 0} {$i < $num} {incr i} { + # Make sure all the weights are different because + # Redis does not use a stable sort but Tcl does. while 1 { - # Make sure all the weights are different because - # Redis does not use a stable sort but Tcl does. randpath { set rint [expr int(rand()*1000000)] } { @@ -23,138 +23,92 @@ start_server default.conf {} { if {![info exists seenrand($rint)]} break } set seenrand($rint) x - r lpush tosort $i - r sadd tosort-set $i + r $cmd tosort $i r set weight_$i $rint r hset wobj_$i weight $rint lappend tosort [list $i $rint] } set sorted [lsort -index 1 -real $tosort] - set res {} - for {set i 0} {$i < 10000} {incr i} { - lappend res [lindex $sorted $i 0] + for {set i 0} {$i < $num} {incr i} { + lappend result [lindex $sorted $i 0] + } + set _ $result + } + + foreach {num cmd enc title} { + 16 lpush ziplist "Ziplist" + 1000 lpush linkedlist "Linked list" + 10000 lpush linkedlist "Big Linked list" + 16 sadd intset "Intset" + 1000 sadd hashtable "Hash table" + 10000 sadd hashtable "Big Hash table" + } { + set result [create_random_dataset $num $cmd] + assert_encoding $enc tosort + + test "$title: SORT BY key" { + assert_equal $result [r sort tosort BY weight_*] + } + + test "$title: SORT BY key with limit" { + assert_equal [lrange $result 5 9] [r sort tosort BY weight_* LIMIT 5 5] } - format {} - } {} - test {SORT with BY against the newly created list} { - r sort tosort {BY weight_*} - } $res + test "$title: SORT BY hash field" { + assert_equal $result [r sort tosort BY wobj_*->weight] + } + } - test {SORT with BY (hash field) against the newly created list} { - r sort tosort {BY wobj_*->weight} - } $res + set result [create_random_dataset 16 lpush] + test "SORT GET #" { + assert_equal [lsort -integer $result] [r sort tosort GET #] + } - test {SORT with GET (key+hash) with sanity check of each element (list)} { - set err {} + test "SORT GET " { + r del foo + set res [r sort tosort GET foo] + assert_equal 16 [llength $res] + foreach item $res { assert_equal {} $item } + } + + test "SORT GET (key and hash) with sanity check" { set l1 [r sort tosort GET # GET weight_*] set l2 [r sort tosort GET # GET wobj_*->weight] foreach {id1 w1} $l1 {id2 w2} $l2 { - set realweight [r get weight_$id1] - if {$id1 != $id2} { - set err "ID mismatch $id1 != $id2" - break - } - if {$realweight != $w1 || $realweight != $w2} { - set err "Weights mismatch! w1: $w1 w2: $w2 real: $realweight" - break - } + assert_equal $id1 $id2 + assert_equal $w1 [r get weight_$id1] + assert_equal $w2 [r get weight_$id1] } - set _ $err - } {} - - test {SORT with BY, but against the newly created set} { - r sort tosort-set {BY weight_*} - } $res - - test {SORT with BY (hash field), but against the newly created set} { - r sort tosort-set {BY wobj_*->weight} - } $res - - test {SORT with BY and STORE against the newly created list} { - r sort tosort {BY weight_*} store sort-res - r lrange sort-res 0 -1 - } $res - - test {SORT with BY (hash field) and STORE against the newly created list} { - r sort tosort {BY wobj_*->weight} store sort-res - r lrange sort-res 0 -1 - } $res - - test {SORT direct, numeric, against the newly created list} { - r sort tosort - } [lsort -integer $res] - - test {SORT decreasing sort} { - r sort tosort {DESC} - } [lsort -decreasing -integer $res] - - test {SORT speed, sorting 10000 elements list using BY, 100 times} { - set start [clock clicks -milliseconds] - for {set i 0} {$i < 100} {incr i} { - set sorted [r sort tosort {BY weight_* LIMIT 0 10}] - } - set elapsed [expr [clock clicks -milliseconds]-$start] - puts -nonewline "\n Average time to sort: [expr double($elapsed)/100] milliseconds " - flush stdout - format {} - } {} - - test {SORT speed, as above but against hash field} { - set start [clock clicks -milliseconds] - for {set i 0} {$i < 100} {incr i} { - set sorted [r sort tosort {BY wobj_*->weight LIMIT 0 10}] - } - set elapsed [expr [clock clicks -milliseconds]-$start] - puts -nonewline "\n Average time to sort: [expr double($elapsed)/100] milliseconds " - flush stdout - format {} - } {} - - test {SORT speed, sorting 10000 elements list directly, 100 times} { - set start [clock clicks -milliseconds] - for {set i 0} {$i < 100} {incr i} { - set sorted [r sort tosort {LIMIT 0 10}] - } - set elapsed [expr [clock clicks -milliseconds]-$start] - puts -nonewline "\n Average time to sort: [expr double($elapsed)/100] milliseconds " - flush stdout - format {} - } {} - - test {SORT speed, pseudo-sorting 10000 elements list, BY , 100 times} { - set start [clock clicks -milliseconds] - for {set i 0} {$i < 100} {incr i} { - set sorted [r sort tosort {BY nokey LIMIT 0 10}] - } - set elapsed [expr [clock clicks -milliseconds]-$start] - puts -nonewline "\n Average time to sort: [expr double($elapsed)/100] milliseconds " - flush stdout - format {} - } {} - - test {SORT regression for issue #19, sorting floats} { - r flushdb - foreach x {1.1 5.10 3.10 7.44 2.1 5.75 6.12 0.25 1.15} { - r lpush mylist $x - } - r sort mylist - } [lsort -real {1.1 5.10 3.10 7.44 2.1 5.75 6.12 0.25 1.15}] - - test {SORT with GET #} { + } + + test "SORT BY key STORE" { + r sort tosort BY weight_* store sort-res + assert_equal $result [r lrange sort-res 0 -1] + assert_equal 16 [r llen sort-res] + assert_encoding ziplist sort-res + } + + test "SORT BY hash field STORE" { + r sort tosort BY wobj_*->weight store sort-res + assert_equal $result [r lrange sort-res 0 -1] + assert_equal 16 [r llen sort-res] + assert_encoding ziplist sort-res + } + + test "SORT DESC" { + assert_equal [lsort -decreasing -integer $result] [r sort tosort DESC] + } + + test "SORT ALPHA against integer encoded strings" { r del mylist - r lpush mylist 1 r lpush mylist 2 + r lpush mylist 1 r lpush mylist 3 - r mset weight_1 10 weight_2 5 weight_3 30 - r sort mylist BY weight_* GET # - } {2 1 3} - - test {SORT with constant GET} { - r sort mylist GET foo - } {{} {} {}} - - test {SORT against sorted sets} { + r lpush mylist 10 + r sort mylist alpha + } {1 10 2 3} + + test "SORT sorted set" { r del zset r zadd zset 1 a r zadd zset 5 b @@ -164,7 +118,7 @@ start_server default.conf {} { r sort zset alpha desc } {e d c b a} - test {Sorted sets +inf and -inf handling} { + test "SORT sorted set: +inf and -inf handling" { r del zset r zadd zset -100 a r zadd zset 200 b @@ -174,4 +128,125 @@ start_server default.conf {} { r zadd zset -inf min r zrange zset 0 -1 } {min c a b d max} + + test "SORT regression for issue #19, sorting floats" { + r flushdb + set floats {1.1 5.10 3.10 7.44 2.1 5.75 6.12 0.25 1.15} + foreach x $floats { + r lpush mylist $x + } + assert_equal [lsort -real $floats] [r sort mylist] + } + + test "SORT with STORE returns zero if result is empty (github isse 224)" { + r flushdb + r sort foo store bar + } {0} + + test "SORT with STORE does not create empty lists (github issue 224)" { + r flushdb + r lpush foo bar + r sort foo alpha limit 10 10 store zap + r exists zap + } {0} + + test "SORT with STORE removes key if result is empty (github issue 227)" { + r flushdb + r lpush foo bar + r sort emptylist store foo + r exists foo + } {0} + + test "SORT with BY and STORE should still order output" { + r del myset mylist + 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 sort myset alpha by _ store mylist + r lrange mylist 0 -1 + } {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 will complain with numerical sorting and bad doubles (1)" { + r del myset + r sadd myset 1 2 3 4 not-a-double + set e {} + catch {r sort myset} e + set e + } {*ERR*double*} + + test "SORT will complain with numerical sorting and bad doubles (2)" { + r del myset + r sadd myset 1 2 3 4 + r mset score:1 10 score:2 20 score:3 30 score:4 not-a-double + set e {} + catch {r sort myset by score:*} e + set e + } {*ERR*double*} + + test "SORT BY sub-sorts lexicographically if score is the same" { + 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 + 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} { + set score:$ele 100 + } + r sort myset by score:* + } {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 GET with pattern ending with just -> does not get hash field" { + r del mylist + r lpush mylist a + r set x:a-> 100 + r sort mylist by num get x:*-> + } {100} + + tags {"slow"} { + set num 100 + set res [create_random_dataset $num lpush] + + test "SORT speed, $num element list BY key, 100 times" { + set start [clock clicks -milliseconds] + for {set i 0} {$i < 100} {incr i} { + set sorted [r sort tosort BY weight_* LIMIT 0 10] + } + set elapsed [expr [clock clicks -milliseconds]-$start] + if {$::verbose} { + puts -nonewline "\n Average time to sort: [expr double($elapsed)/100] milliseconds " + flush stdout + } + } + + test "SORT speed, $num element list BY hash field, 100 times" { + set start [clock clicks -milliseconds] + for {set i 0} {$i < 100} {incr i} { + set sorted [r sort tosort BY wobj_*->weight LIMIT 0 10] + } + set elapsed [expr [clock clicks -milliseconds]-$start] + if {$::verbose} { + puts -nonewline "\n Average time to sort: [expr double($elapsed)/100] milliseconds " + flush stdout + } + } + + test "SORT speed, $num element list directly, 100 times" { + set start [clock clicks -milliseconds] + for {set i 0} {$i < 100} {incr i} { + set sorted [r sort tosort LIMIT 0 10] + } + set elapsed [expr [clock clicks -milliseconds]-$start] + if {$::verbose} { + puts -nonewline "\n Average time to sort: [expr double($elapsed)/100] milliseconds " + flush stdout + } + } + + test "SORT speed, $num element list BY , 100 times" { + set start [clock clicks -milliseconds] + for {set i 0} {$i < 100} {incr i} { + set sorted [r sort tosort BY nokey LIMIT 0 10] + } + set elapsed [expr [clock clicks -milliseconds]-$start] + if {$::verbose} { + puts -nonewline "\n Average time to sort: [expr double($elapsed)/100] milliseconds " + flush stdout + } + } + } }