Use PrefixSort in Window

[aditi-pandit]

Depends on https://github.com/facebookincubator/velox/pull/9541

[netlify[bot]]

✅ Deploy Preview for meta-velox canceled.

Name	Link
🔨 Latest commit	2e585b3982a06d865381209cb8724de6778c4f3e
🔍 Latest deploy log	https://app.netlify.com/sites/meta-velox/deploys/6686d50d9653990008c38e5d

[aditi-pandit]

@mbasmanova : Benchmark results : https://gist.github.com/aditi-pandit/29eb8941915c1829c17c8c8fe358d281

The results are encouraging when there are fewer key values in the input (5-10% for 16 keys. 5 % for 300 keys). But when the number of keys increase the performance is comparable to std::sort.

It won't hurt to use it in the WIndow operator. Though the improvements are very modest.

[aditi-pandit]

@mbasmanova, @skadilover : We lost some permissions to push to facebookincubator/velox repo today so I had to make a new PR. https://github.com/facebookincubator/velox/pull/10417. Closing this one now.