gruuya commented on PR #7180: URL: https://github.com/apache/arrow-datafusion/pull/7180#issuecomment-1670296640
Alright, @alamb @yjshen, this is probably the final, best-effort, attempt so
far, with the simplest implementation.
I've set a hard cut-off for eager sorting at 100 rows so that the pronounced
regressions for bigger fetches are avoided (at least for the 1.0 scale factor
in the benchmarks). It also happens that most of the memory savings occur for K
<= 100, in addition to probably 80% of usages in practice falling into that
range.
<details><summary>sorting benchmarks</summary>
```text
┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
┃ Query ┃ main ┃ top-k-eager-sorting ┃ Change ┃
┡━━━━━━━━━━━━━━╇━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
│ Qsort utf8 │ 28233.61ms │ 29131.55ms │ no change │
│ fetch None │ │ │ │
│ Qsort int │ 36739.73ms │ 37069.77ms │ no change │
│ fetch None │ │ │ │
│ Qsort │ 29974.54ms │ 30505.64ms │ no change │
│ decimal │ │ │ │
│ fetch None │ │ │ │
│ Qsort │ 40214.81ms │ 40837.69ms │ no change │
│ integer │ │ │ │
│ tuple fetch │ │ │ │
│ None │ │ │ │
│ Qsort utf8 │ 29429.65ms │ 29552.35ms │ no change │
│ tuple fetch │ │ │ │
│ None │ │ │ │
│ Qsort mixed │ 34435.12ms │ 34964.91ms │ no change │
│ tuple fetch │ │ │ │
│ None │ │ │ │
│ Qsort utf8 │ 1709.85ms │ 1813.60ms │ 1.06x slower │
│ fetch │ │ │ │
│ Some(1) │ │ │ │
│ Qsort int │ 1842.45ms │ 1734.15ms │ +1.06x faster │
│ fetch │ │ │ │
│ Some(1) │ │ │ │
│ Qsort │ 1680.46ms │ 1669.21ms │ no change │
│ decimal │ │ │ │
│ fetch │ │ │ │
│ Some(1) │ │ │ │
│ Qsort │ 1745.56ms │ 1869.70ms │ 1.07x slower │
│ integer │ │ │ │
│ tuple fetch │ │ │ │
│ Some(1) │ │ │ │
│ Qsort utf8 │ 1965.73ms │ 2339.40ms │ 1.19x slower │
│ tuple fetch │ │ │ │
│ Some(1) │ │ │ │
│ Qsort mixed │ 1813.14ms │ 2046.39ms │ 1.13x slower │
│ tuple fetch │ │ │ │
│ Some(1) │ │ │ │
│ Qsort utf8 │ 1712.66ms │ 1823.54ms │ 1.06x slower │
│ fetch │ │ │ │
│ Some(10) │ │ │ │
│ Qsort int │ 1832.73ms │ 1738.45ms │ +1.05x faster │
│ fetch │ │ │ │
│ Some(10) │ │ │ │
│ Qsort │ 1699.42ms │ 1662.90ms │ no change │
│ decimal │ │ │ │
│ fetch │ │ │ │
│ Some(10) │ │ │ │
│ Qsort │ 1762.86ms │ 1855.61ms │ 1.05x slower │
│ integer │ │ │ │
│ tuple fetch │ │ │ │
│ Some(10) │ │ │ │
│ Qsort utf8 │ 1974.07ms │ 2323.84ms │ 1.18x slower │
│ tuple fetch │ │ │ │
│ Some(10) │ │ │ │
│ Qsort mixed │ 1854.64ms │ 2025.10ms │ 1.09x slower │
│ tuple fetch │ │ │ │
│ Some(10) │ │ │ │
│ Qsort utf8 │ 1733.28ms │ 1834.81ms │ 1.06x slower │
│ fetch │ │ │ │
│ Some(100) │ │ │ │
│ Qsort int │ 1845.74ms │ 1751.06ms │ +1.05x faster │
│ fetch │ │ │ │
│ Some(100) │ │ │ │
│ Qsort │ 1685.38ms │ 1680.20ms │ no change │
│ decimal │ │ │ │
│ fetch │ │ │ │
│ Some(100) │ │ │ │
│ Qsort │ 1799.54ms │ 1911.41ms │ 1.06x slower │
│ integer │ │ │ │
│ tuple fetch │ │ │ │
│ Some(100) │ │ │ │
│ Qsort utf8 │ 2008.06ms │ 2368.46ms │ 1.18x slower │
│ tuple fetch │ │ │ │
│ Some(100) │ │ │ │
│ Qsort mixed │ 1855.62ms │ 2085.46ms │ 1.12x slower │
│ tuple fetch │ │ │ │
│ Some(100) │ │ │ │
│ Qsort utf8 │ 1728.54ms │ 1728.53ms │ no change │
│ fetch │ │ │ │
│ Some(101) │ │ │ │
│ Qsort int │ 1867.64ms │ 1865.83ms │ no change │
│ fetch │ │ │ │
│ Some(101) │ │ │ │
│ Qsort │ 1691.19ms │ 1693.69ms │ no change │
│ decimal │ │ │ │
│ fetch │ │ │ │
│ Some(101) │ │ │ │
│ Qsort │ 1784.79ms │ 1801.06ms │ no change │
│ integer │ │ │ │
│ tuple fetch │ │ │ │
│ Some(101) │ │ │ │
│ Qsort utf8 │ 1999.16ms │ 2000.34ms │ no change │
│ tuple fetch │ │ │ │
│ Some(101) │ │ │ │
│ Qsort mixed │ 1869.82ms │ 1877.08ms │ no change │
│ tuple fetch │ │ │ │
│ Some(101) │ │ │ │
│ Qsort utf8 │ 1774.79ms │ 1786.39ms │ no change │
│ fetch │ │ │ │
│ Some(1000) │ │ │ │
│ Qsort int │ 1959.51ms │ 1933.94ms │ no change │
│ fetch │ │ │ │
│ Some(1000) │ │ │ │
│ Qsort │ 1714.06ms │ 1715.05ms │ no change │
│ decimal │ │ │ │
│ fetch │ │ │ │
│ Some(1000) │ │ │ │
│ Qsort │ 1940.85ms │ 1943.97ms │ no change │
│ integer │ │ │ │
│ tuple fetch │ │ │ │
│ Some(1000) │ │ │ │
│ Qsort utf8 │ 2103.61ms │ 2108.73ms │ no change │
│ tuple fetch │ │ │ │
│ Some(1000) │ │ │ │
│ Qsort mixed │ 2032.56ms │ 2060.30ms │ no change │
│ tuple fetch │ │ │ │
│ Some(1000) │ │ │ │
└──────────────┴────────────┴─────────────────────┴───────────────┘
```
</details>
Still not sure whether this is merge-worthy, but seems like the best
trade-off between run-times and memory profiles so far.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
