Selectors Subtraction performance scales poorly with the number of columns

[etrotta]

Checks

• I have checked that this issue has not already been reported.
• I have confirmed this bug exists on the latest version of Polars.

Reproducible example

import polars as pl
import polars.selectors as cs
import random

N_COLS = 100_000

df = pl.DataFrame({f'field_{i}': [0] for i in range(N_COLS)})
to_remove = set(random.sample(df.columns, 100))

# Some fast examples with the same output
df.select([col for col in df.columns if col not in to_remove])
df.select(pl.exclude(to_remove))
df.drop(to_remove)

# selectors: Extremely slow
df.select(cs.all() - cs.by_name(to_remove))
df.select(cs.exclude(to_remove))
df.select(~cs.by_name(to_remove))

Log output

No response

Issue description

Seems like the actual operation is implemented in

polars/crates/polars-plan/src/plans/conversion/expr_expansion.rs

Lines 845 to 858 in 7a2f547

	Selector::Sub(lhs, rhs) => {
	replace_selector_inner(*lhs, members, scratch, schema, keys)?;
	let mut rhs_members = Default::default();
	replace_selector_inner(*rhs, &mut rhs_members, scratch, schema, keys)?;
	let mut new_members = PlIndexSet::with_capacity(members.len());
	for e in members.drain(..) {
	if !rhs_members.contains(&e) {
	new_members.insert(e);
	}
	}
	*members = new_members;
	},

Expected behavior

For Selectors to work as fast as the alternatives mentioned above

Installed versions

--------Version info---------
Polars:              1.11.0
Index type:          UInt32
Platform:            Windows-11-10.0.22631-SP0
Python:              3.12.0 (tags/v3.12.0:0fb18b0, Oct  2 2023, 13:03:39) [MSC v.1935 64 bit (AMD64)]
LTS CPU:             False

----Optional dependencies----
adbc_driver_manager  <not installed>
altair               <not installed>
cloudpickle          <not installed>
connectorx           <not installed>
deltalake            <not installed>
fastexcel            0.9.0
fsspec               <not installed>
gevent               <not installed>
great_tables         <not installed>
matplotlib           3.8.2
nest_asyncio         <not installed>
numpy                1.26.4
openpyxl             3.1.2
pandas               2.2.2
pyarrow              15.0.0
pydantic             2.5.2
pyiceberg            <not installed>
sqlalchemy           2.0.29
torch                <not installed>
xlsx2csv             <not installed>
xlsxwriter           <not installed>

[alexander-beedie]

It seems to be a more generic issue than subtract - a quick test shows that any selector combination ("union", "subtract", "xor", and even "not") results in a rapid performance drop as the number of column becomes large; we may have some quadratic behaviour lurking somewhere.

Looking further, I don't think the issue is specific to selector expansion 🤔

[alexander-beedie]

Got it; thanks for the clean test case 👌
PR/fix incoming...