You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Why are categoricals not implemented using Arrow Dictionaries? #7429
I have searched the above polars tags on Stack Overflow for similar questions.
I have asked my usage related question on Stack Overflow.
Link to question on Stack Overflow
No response
Question about Polars
I tried hard to find history/discussions on this topic, but couldn't find any.
In the documentation it says
Most data types follow the exact implementation from Arrow, with exception of Utf8 (this is actually LargeUtf8), Categorical, and Object (support is limited).
Question: Why are categoricals implemented with a custom type instead of Arrow's Dictionary?
Question: Why are categoricals implemented with a custom type instead of Arrow's Dictionary?
In short.
Arrow's dictionaries start for each dictionary with a mapping from 0, (and if I am not mistaken, each chunked array can have its own dictionary), this means before you can compare the raw values you have to unify those dictionaries and remap all the keys.
A 0 key from dictionary 1 is not necessarily the same as 0 key from dictionary 2.
In Polars you can enable a string cache that makes sure that e.g. 0 key always matches with Z value, this makes comparing 2 columns (e.g during filtering or joining) a lot faster as no numbers need to be remapped.
importpolarsasplCreatecategoricalswiththesamestringcache.
In [200]: withpl.StringCache():
...: df=pl.DataFrame(
...: [
...: pl.Series("a", ["Z", "A", "B", "Z", "B", "A"], dtype=pl.Categorical),
...: pl.Series("b", ["A", "B", "A", "Z", "B", "A"], dtype=pl.Categorical),
...: ]
...: )
...:
# With string cache, categoricals are comparable:# -in dict 1: `0` = "Z"# - in dict 2 : `0` = "Z"In [203]: df.with_columns(pl.col(pl.Categorical).to_physical().suffix("_physical"))
Out[203]:
shape: (6, 4)
┌─────┬─────┬────────────┬────────────┐
│ a ┆ b ┆ a_physical ┆ b_physical │
│ --- ┆ --- ┆ --- ┆ --- │
│ cat ┆ cat ┆ u32 ┆ u32 │
╞═════╪═════╪════════════╪════════════╡
│ Z ┆ A ┆ 0 ┆ 1 │
│ A ┆ B ┆ 1 ┆ 2 │
│ B ┆ A ┆ 2 ┆ 1 │
│ Z ┆ Z ┆ 0 ┆ 0 │
│ B ┆ B ┆ 2 ┆ 2 │
│ A ┆ A ┆ 1 ┆ 1 │
└─────┴─────┴────────────┴────────────┘
# Filtering is easy:In [202]: df.filter(pl.col("a") ==pl.col("b"))
Out[202]:
shape: (3, 2)
┌─────┬─────┐
│ a ┆ b │
│ --- ┆ --- │
│ cat ┆ cat │
╞═════╪═════╡
│ Z ┆ Z │
│ B ┆ B │
│ A ┆ A │
└─────┴─────┘
# Without string cache:n [209]: df_no_string_cache=pl.DataFrame(
...: [
...: pl.Series("a", ["Z", "A", "B", "Z", "B", "A"], dtype=pl.Categorical),
...: pl.Series("b", ["A", "B", "A", "Z", "B", "A"], dtype=pl.Categorical),
...: ]
...: )
# Without string cache, categoricals are not comparable:# -in dict 1: `0` = "Z"# - in dict 2 : `0` = "A"In [210]: df_no_string_cache.with_columns(pl.col(pl.Categorical).to_physical().suffix("_physical"))
Out[210]:
shape: (6, 4)
┌─────┬─────┬────────────┬────────────┐
│ a ┆ b ┆ a_physical ┆ b_physical │
│ --- ┆ --- ┆ --- ┆ --- │
│ cat ┆ cat ┆ u32 ┆ u32 │
╞═════╪═════╪════════════╪════════════╡
│ Z ┆ A ┆ 0 ┆ 0 │
│ A ┆ B ┆ 1 ┆ 1 │
│ B ┆ A ┆ 2 ┆ 0 │
│ Z ┆ Z ┆ 0 ┆ 2 │
│ B ┆ B ┆ 2 ┆ 1 │
│ A ┆ A ┆ 1 ┆ 0 │
└─────┴─────┴────────────┴────────────┘
# Comparing categoricals with different string caches is not supported.In [211]: df_no_string_cache.filter(pl.col("a") ==pl.col("b"))
---------------------------------------------------------------------------ComputeErrorTraceback (mostrecentcalllast)
<ipython-input-211-1962e08805dd>in<module>---->1df_no_string_cache.filter(pl.col("a") ==pl.col("b"))
~/software/anaconda3/envs/polars/lib/python3.8/site-packages/polars/internals/dataframe/frame.pyinfilter(self, predicate)
32413242returnself._from_pydf(
->3243self.lazy()
3244 .filter(predicate) # type: ignore[arg-type]3245 .collect(no_optimization=True)
~/software/anaconda3/envs/polars/lib/python3.8/site-packages/polars/internals/lazyframe/frame.pyincollect(self, type_coercion, predicate_pushdown, projection_pushdown, simplify_expression, no_optimization, slice_pushdown, common_subplan_elimination, streaming)
1428streaming,
1429 )
->1430returnpli.wrap_df(ldf.collect())
14311432defsink_parquet(
ComputeError: Cannotcomparecategoricalsoriginatingfromdifferentsources. Considersettingaglobalstringcache.
# For Arrow dictionaries,:# -in dict 1: `0` = "Z"# - in dict 2 : `0` = "A"In [204]: df.to_arrow()
Out[204]:
pyarrow.Tablea: dictionary<values=large_string, indices=uint32, ordered=0>b: dictionary<values=large_string, indices=uint32, ordered=0>----a: [ --dictionary:
["Z","A","B"] --indices:
[0,1,2,0,2,1]]
b: [ --dictionary:
["A","B","Z"] --indices:
[0,1,0,2,1,0]]
Thanks for the great answer! You might want to fix quote formatting @ghuls
IIUC Polars disallows inefficient categorical comparisons by forcing people to use StringCache so that the physical representation for all columns is identical. So, Polars doesn’t actually solve the problem of different physical representations, but it circumvents it by forcing users to make sure the representation is identical.
Which makes a lot of sense IMO, but I wonder why we can’t have the same thing with Arrow? I imagine that we can gradually build up a Dictionary type with all the categories, similar to how a StringCache is built up.
Arrow's dictionaries start for each dictionary with a mapping from 0, (and if I am not mistaken, each chunked array can have its own dictionary), this means before you can compare the raw values you have to unify those dictionaries and remap all the keys.
A 0 key from dictionary 1 is not necessarily the same as 0 key from dictionary 2.
@ghuls While this is certainly true, as has been discussed a few times here what's lacking is enum-like dtypes which are prevalent in some fields. The dictionary itself may be extremely small, like {-1: 'red', 0: 'yellow', 1: 'green'}, and "unifying dictionaries", even if done on every single query, will then take microseconds (or rather, fractions of microseconds, for examples like this), whereas your actual queries may take many seconds or minutes.
In other words, if the user wants to pay the (often negligible price) of dtype reunification on all queries, this might be a huge win semantically. If your dict is containing hundreds/thousands of elements, then you're probably doing something wrong and should use unordered categories instead with opaque level values.
As for unifying mappings, there's probably some smarter ways – for example (a random thought), using refcounted dictionaries and then just comparing pointers. There's also all sorts of questions though that arise e.g. which operations should (or should not) succeed if mapping don't precisely match each other, and are those dictionary dtypes meant to be frozen once created or can you spawn new ones automatically (e.g. when concatenating dtypes that are overlapping and matching on the overlapping values but not equivalent overall).
As for unifying mappings, there's probably some smarter ways – for example (a random thought), using refcounted dictionaries and then just comparing pointers.
We already do this. :) On unifying maps. I do think we can extend the dtype with a boolean indication if unifying should be allowed. I do want to keep that default to false as I believe the global string cache is often the way to go.
Which makes a lot of sense IMO, but I wonder why we can’t have the same thing with Arrow? I imagine that we can gradually build up a Dictionary type with all the categories, similar to how a StringCache is built up.
Well, a bit differently, no? From what I've read in source, isn't it more like
if lhs.mapping.ptr() != rhs.mapping.ptr!(){bail!("use global string cache!!!");}
whereas you could try and unify things lazily behind the scenes (or explicitly, by user's request)?
I do want to keep that default to false as I believe the global string cache is often the way to go
I think the default=false makes sense for unordered categoricals, whereas for user-defined "enums" (if polars ever supports them) the default=true might make more sense. Chances are, those will be super-tiny anyway, and the logic in handling unary/binary ops where those dicts differ slightly might be different as well.
But yea, back to the topic, it looks like the logic for unifying dictionaries is already both in polars and arrow itself, and refcounted rev mappings are already being used in categoricals, so it's just the question of adding support for user-defined dictionaries ("enums"). This would be definitely a humongous step forward (speaking for myself, but from what I've seen on SO and in the repo, this is a common use case for lots of people).
Activity
ghuls commentedon Mar 8, 2023
In short.
Arrow's dictionaries start for each dictionary with a mapping from 0, (and if I am not mistaken, each chunked array can have its own dictionary), this means before you can compare the raw values you have to unify those dictionaries and remap all the keys.
A
0key from dictionary 1 is not necessarily the same as0key from dictionary 2.In Polars you can enable a string cache that makes sure that e.g.
0key always matches withZvalue, this makes comparing 2 columns (e.g during filtering or joining) a lot faster as no numbers need to be remapped.jonashaag commentedon Mar 8, 2023
Thanks for the great answer! You might want to fix quote formatting @ghuls
IIUC Polars disallows inefficient categorical comparisons by forcing people to use
StringCacheso that the physical representation for all columns is identical. So, Polars doesn’t actually solve the problem of different physical representations, but it circumvents it by forcing users to make sure the representation is identical.Which makes a lot of sense IMO, but I wonder why we can’t have the same thing with Arrow? I imagine that we can gradually build up a Dictionary type with all the categories, similar to how a StringCache is built up.
aldanor commentedon Mar 10, 2023
@ghuls While this is certainly true, as has been discussed a few times here what's lacking is enum-like dtypes which are prevalent in some fields. The dictionary itself may be extremely small, like
{-1: 'red', 0: 'yellow', 1: 'green'}, and "unifying dictionaries", even if done on every single query, will then take microseconds (or rather, fractions of microseconds, for examples like this), whereas your actual queries may take many seconds or minutes.In other words, if the user wants to pay the (often negligible price) of dtype reunification on all queries, this might be a huge win semantically. If your dict is containing hundreds/thousands of elements, then you're probably doing something wrong and should use unordered categories instead with opaque level values.
As for unifying mappings, there's probably some smarter ways – for example (a random thought), using refcounted dictionaries and then just comparing pointers. There's also all sorts of questions though that arise e.g. which operations should (or should not) succeed if mapping don't precisely match each other, and are those dictionary dtypes meant to be frozen once created or can you spawn new ones automatically (e.g. when concatenating dtypes that are overlapping and matching on the overlapping values but not equivalent overall).
ritchie46 commentedon Mar 10, 2023
We already do this. :) On unifying maps. I do think we can extend the dtype with a boolean indication if unifying should be allowed. I do want to keep that default to
falseas I believe the global string cache is often the way to go.ghuls commentedon Mar 10, 2023
Pyarrow has this functionality too, if called explicitly (at least within a table):
https://arrow.apache.org/docs/python/generated/pyarrow.Table.html#pyarrow.Table.unify_dictionaries
ritchie46 commentedon Mar 10, 2023
We also do this in the
is_inoperation I believe. As there the maps are often really small.alexander-beedie commentedon Mar 10, 2023
Having a real
Enumdtype would be awesome :)aldanor commentedon Mar 10, 2023
Well, a bit differently, no? From what I've read in source, isn't it more like
whereas you could try and unify things lazily behind the scenes (or explicitly, by user's request)?
I think the default=false makes sense for unordered categoricals, whereas for user-defined "enums" (if polars ever supports them) the default=true might make more sense. Chances are, those will be super-tiny anyway, and the logic in handling unary/binary ops where those dicts differ slightly might be different as well.
But yea, back to the topic, it looks like the logic for unifying dictionaries is already both in polars and arrow itself, and refcounted rev mappings are already being used in categoricals, so it's just the question of adding support for user-defined dictionaries ("enums"). This would be definitely a humongous step forward (speaking for myself, but from what I've seen on SO and in the repo, this is a common use case for lots of people).
stinodego commentedon Aug 9, 2023
Feel free to open a new feature request, I think it would be a great addition. Either to the Categorical type or a new, separate data type.
I will close this issue as the original question has been answered.