`sort` after `filter` unreasonably  slow
MEMBER
`filter` add an indices mapping on top of the dataset, so `sort` has to gather all the rows that are kept to form a new Arrow table and sort the table. Gathering all the rows can take some time, but is a necessary step. You can try calling `ds = ds.flatten_indices()` before sorting to remove the indices mapping.
2024-07-22T13:55:16Z
https://github.com/huggingface/datasets/issues/7041#issuecomment-2243026472
https://api.github.com/repos/huggingface/datasets/issues/7041
IC_kwDODunzps6Fsd4o
https://api.github.com/repos/huggingface/datasets/issues/comments/2243026472/reactions
2024-07-22T13:55:16Z
https://api.github.com/repos/huggingface/datasets/issues/comments/2243026472
https://avatars.githubusercontent.com/u/42851186?v=4
https://api.github.com/users/lhoestq/events{/privacy}
https://api.github.com/users/lhoestq/followers
https://api.github.com/users/lhoestq/following{/other_user}
https://api.github.com/users/lhoestq/gists{/gist_id}
https://github.com/lhoestq
lhoestq
MDQ6VXNlcjQyODUxMTg2
https://api.github.com/users/lhoestq/orgs
https://api.github.com/users/lhoestq/received_events
https://api.github.com/users/lhoestq/repos
https://api.github.com/users/lhoestq/starred{/owner}{/repo}
https://api.github.com/users/lhoestq/subscriptions
User
https://api.github.com/users/lhoestq
public
NONE
> `filter` add an indices mapping on top of the dataset, so `sort` has to gather all the rows that are kept to form a new Arrow table and sort the table. Gathering all the rows can take some time, but is a necessary step. You can try calling `ds = ds.flatten_indices()` before sorting to remove the indices mapping.

This worked, thank you so much.
2025-04-03T07:58:54Z
https://github.com/huggingface/datasets/issues/7041#issuecomment-2774799493
https://api.github.com/repos/huggingface/datasets/issues/7041
IC_kwDODunzps6lZBSF
https://api.github.com/repos/huggingface/datasets/issues/comments/2774799493/reactions
2025-04-03T07:58:54Z
https://api.github.com/repos/huggingface/datasets/issues/comments/2774799493
https://avatars.githubusercontent.com/u/22513909?v=4
https://api.github.com/users/Alzter/events{/privacy}
https://api.github.com/users/Alzter/followers
https://api.github.com/users/Alzter/following{/other_user}
https://api.github.com/users/Alzter/gists{/gist_id}
https://github.com/Alzter
Alzter
MDQ6VXNlcjIyNTEzOTA5
https://api.github.com/users/Alzter/orgs
https://api.github.com/users/Alzter/received_events
https://api.github.com/users/Alzter/repos
https://api.github.com/users/Alzter/starred{/owner}{/repo}
https://api.github.com/users/Alzter/subscriptions
User
https://api.github.com/users/Alzter
public
### Describe the bug

as the tittle says ...

### Steps to reproduce the bug

`sort` seems to be normal.

```python
from datasets import Dataset
import random

nums = [{"k":random.choice(range(0,1000))} for _ in range(100000)]

ds = Dataset.from_list(nums)

print("start sort")

ds = ds.sort("k")

print("finish sort")
```

but `sort` after `filter` is extremely slow.

```python
from datasets import Dataset
import random

nums = [{"k":random.choice(range(0,1000))} for _ in range(100000)]

ds = Dataset.from_list(nums)

ds = ds.filter(lambda x:x > 100, input_columns="k")

print("start sort")

ds = ds.sort("k")

print("finish sort")
```


### Expected behavior

Is this a bug, or is it a misuse of the `sort` function?

### Environment info

- `datasets` version: 2.20.0
- Platform: Linux-3.10.0-1127.19.1.el7.x86_64-x86_64-with-glibc2.17
- Python version: 3.10.13
- `huggingface_hub` version: 0.23.4
- PyArrow version: 16.1.0
- Pandas version: 2.2.2
- `fsspec` version: 2023.10.0