Proposal: sort by multiple properties in an array

[breml]

I have an array (or slice) of struct with multiple properties like this:

type Data []struct{
  key1 string
  key2 string
  counter int
}

Now I would like to sort this inside of expr-lang by multiple properties, some ascending, some descending. In SQL I would do something like this: ... ORDER BY counter DESC, key1 ASC, key2 ASC.

I tried with nested sortBy like this: sortBy(sortBy(sortBy(Data, .key2, "asc"), .key1, "asc"), .counter, "desc") but this did not work (I am not sure about the reason). Therefore I ended up implementing my own custom function, which I called multiSortBy, which I can call like this: multiSortBy(Data, ".counter", "desc", ".key1", "asc", ".key2", "asc"). This comes with the limitation, that in user provided functions, it is not possible (to my knowledge) to use predicates as it is in the built in functions, which limits the possibilities with my implementation of multiSortBy.

Therefore I propose to introduce a new function to expr-lang, which allows to sort by multiple criteria.

(If I missed something about sorting by multiple columns with the already present functionality, I would love to learn about those alternatives.)

[thevilledev]

I think the expression looks correct. The current sortBy implementation relies on sort.Sort which can be unstable. There's a separate function sort.Stable that guarantees the order of equal elements is preserved. Maybe we could switch and guarantee correctness? There is a chance of worst-case performance hit though, as in O(n * log(n)) vs. O(n * log(n) * log(n)) in complexity.

Example query that shows the unstableness:

sortBy(sortBy([
  {"g": 0, "v": 0},  {"g": 1, "v": 1},  {"g": 2, "v": 2},  {"g": 3, "v": 3},
  {"g": 0, "v": 4},  {"g": 1, "v": 5},  {"g": 2, "v": 6},  {"g": 3, "v": 7},
  {"g": 0, "v": 8},  {"g": 1, "v": 9},  {"g": 2, "v": 10}, {"g": 3, "v": 11},
  {"g": 0, "v": 12}, {"g": 1, "v": 13}, {"g": 2, "v": 14}, {"g": 3, "v": 15},
  {"g": 0, "v": 16}, {"g": 1, "v": 17}, {"g": 2, "v": 18}, {"g": 3, "v": 19}
], .v), .g)

Group 0 values come back as 0, 16, 4, 12, 8 instead of 0, 4, 8, 12, 16.

[breml]

In my case, the number of records I sort is reasonably small such that I wouldn't care about the performance hit in the worst case. If switching from sort.Sort to sort.Stable is a problem due to the performance hit as well as from a backwards compatibility point of view, then a simple alternative would be to extend expr-lang with something like sortStableBy, which then could be used in the nested form outlined above.
That being said, from a performance point of view, I assume that having something like multiSortBy (or allowing sortBy to have multiple predicates) would be better, since the array is only sorted once where as in the nested variant, it is sorted n times.

[antonmedv]

Or you can use something like tihs:

sortBy([
  {"g": 0, "v": 0},  {"g": 1, "v": 1},  {"g": 2, "v": 2},  {"g": 3, "v": 3},
  {"g": 0, "v": 4},  {"g": 1, "v": 5},  {"g": 2, "v": 6},  {"g": 3, "v": 7},
  {"g": 0, "v": 8},  {"g": 1, "v": 9},  {"g": 2, "v": 10}, {"g": 3, "v": 11},
  {"g": 0, "v": 12}, {"g": 1, "v": 13}, {"g": 2, "v": 14}, {"g": 3, "v": 15},
  {"g": 0, "v": 16}, {"g": 1, "v": 17}, {"g": 2, "v": 18}, {"g": 3, "v": 19}
], string(.g) + "." + string(.v))

[breml]

@antonmedv I played with this approach as well, but it becomes cumbersome pretty quickly. In your example, I am not sure what the resulting type of string(.g) + "." + string(.v) is, but I expect it to be a string, which makes the ordering wrong, since it would get ordered alphabetical (instead of numerical). Therefore, one needs to pad the numbers with 0, assuming a maximum length of the numbers for g and v, e.g. repeat("0", 6-len(string(.g))) + string(.g) + "." + repeat("0", 6-len(string(.v))) + string(.v). If one of the dimensions needs to be sorted descending instead of ascending it becomes even more complicated, since one needs to again take a best guess on an upper limit of .g and .v like this repeat("0", 6-len(string(100000-.g))) + string(1000000-.g) + "." + repeat("0", 6-len(string(.v))) + string(.v).
It becomes really interesting, if one needs to sort ascending for a first string and then descending for another.

In my case, I need to sort first by an int descending (I can make a guess about the upper limit, but based on the users input data, I might be wrong so in order to determine the max reliably, I would need to traverse the input data first), and then by a string ascending and another string ascending. With the strings, an other issue is, that I need to pad the strings on the same length, to make the actual sorting work correctly, which again requires to estimate the length of the strings.

Over all, this does not really lead to a very practical approach and also is not readable or maintainable in my opinion.

[antonmedv]

I agree. Would be nice if somebody can research how similar problem addressed in other languages.

[breml]

@antonmedv you mention "other languages". What do you have in mind exactly? Do you have a set of languages you normally look at for inspiration or as reference, that are similar to expr-lang? Do you mind to share some pointers?

[antonmedv]

I take a look at different languages. Almost all of them. We actually have some features even form Wolfram Mathematica. I like Julia lang. Odin. C#. But more often it is Go/JS.

[breml]

I did a quick search, this is what I have found:

• C#/LINQ (and also the Go variant go-linq) support a thenBy method.
• SQL obviously supports ORDER BY with multiple arguments.
• In jq, the sortBy function accepts multiple arguments, which are applied in order to determine the sort order. As far as I can tell, the issue is, that it does not support sorting the first ascending and the second descending.
• One idea borrowed from Go would be to support sortBy, which instead of the property used for the comparison, would accept a "is less than" expression, which gets two items of the array to be sorted as arguments and returns true if the first is less than the second. (see sort.Slice or Javascript array.Sort(compareFn), in Elm this is called sortWith, which could work for expr-lang as well).
• In Hadoop (map/reduce), there is a concept of "Secondary Sort", which builds on a "Composite Key", similar to the idea you raised in Proposal: sort by multiple properties in an array #933 (comment), but as mentioned, there are multiple problems with this approach.

From what I have found, there are mainly 4 approaches:

1. comparison function
2. tuple of properties + sort direction (asc or desc)
3. composite key
4. stable sort + multiple passes

3 and 4 have serious disadvantages already discussed above, which leaves us with 1 and 2. For me, both would work. 1 seems more flexible (one can implement arbitrary sort orders like the "Game of Thrones characters based on how evil they are" example in the Elm documentation. 2 might produce easier to read and understand code due to the similarity to e.g. SQL ORDER BY and will work in most cases, while a little bit less flexible than 1.

I hope, this helps.

[antonmedv]

I think we need to bring ability to sort by comparison function/predicate.

Something like this:

array | sortBy(#1.Value > #2.Value)