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.