[FEA] drop_duplicates and distinct_count behavior/implementation is very inefficient

[jrhemstad]

Is your feature request related to a problem? Please describe.

#9411 made me take a closer look at cudf::drop_duplicates and cudf::distinct_count.

Unlike std::unique, both of these APIs will drop/count all unique rows across the entire table (as opposed to only contiguous equivalent rows).

On the surface, this seems convenient for a user because they don't have to worry about sorting their dataframe if they want to get only the unique rows. However, it has an insidious impact on performance.

Imagine if you were to call distinct_count and then drop_duplicates. The way these functions are currently implemented, they both require doing a sort of the inputs.

Instead, if distinct_count and drop_duplicates worked like std::unique and the user had to first sort the input, then only one sort would be needed. Alternatively, the data may already be sorted (as is the case with Python indexes), where no sort would be necessary.

The current behavior is very sub-optimal for performance as it can require 2 redundant multi-column sorts. Multi-column sorts are among the most expensive operations in libcudf, so this is a bad thing.

(Furthermore, if the data isn't already sorted, using a sort-based implementation is likely to be much slower than a hash-based implementation, so we should look at refactoring these implementations).

Describe the solution you'd like

I'd like to do two things:

1. Update drop_duplicates/distinct_count to work like std::unique, i.e., it only considers contiguous equivalent elements.
   • This would require the data be presorted to preserve the existing behavior. Note that this also requires the user to describe how the data is sorted for things like null_order and such. We can look at groupby for an example of how we've handled this there.
2. Add unordered_drop_duplicates and unordered_distinct_count that behave like the current APIs.
   • We should look at using a hash-based implementation for the unordered_* algorithms as it will likely be much faster

Describe alternatives you've considered

Why not preserve the existing APIs and add ordered_drop_duplicates and ordered_distinct_count?

While this is certainly an option, I think that the behavior I described above would be more canonical for C++.

Why have both unordered_* and ordered versions?

If the data is already sorted, there's a good chance a sort based implementation could be faster than hash-based, but we can test that and see.

[harrism]

Why not rename the new ordered version of drop_duplicates to cudf::unique?

[harrism]

Just for reference in thinking about naming and semantics, I also note that std (our eternal inspiration) does not have a unique_count. Typical approaches to implementing it:

std::vector<int> v{...};
int unique_count = std::set<int>(v.begin(), v.end()).size();

std::vector<int> v{...};
std::sort(v.begin(), v.end());
int unique_count = std::unique(v.begin(), v.end()) - v.begin();

I think we discussed this in the past, and decided that due to the costs of materializing columns / tables, it's better to provide an algorithm that actually counts the unique items with a scan than to require the user to build their own as in method 2. The hashing approach you mention would be similar to approach 1 and probably would be faster in a lot of not pre-sorted cases.

I can't remember why we decided to call it distinct_count instead of unique_count. I bet @codereport was involved or would have an opinion on the naming!

[shwina]

The Pandas API is explicit about not having sorting behaviour:

Signature: s.unique() -> 'ArrayLike'
Docstring:
Return unique values of Series object.

Uniques are returned in order of appearance. Hash table-based unique,
therefore does NOT sort.

So for Python, we'll likely have to do the regular trick of tacking on a sequence column and later sorting by it, at least until an unordered_disctinct_count is available.

[devavret]

One more thing: I've found that for a very small subset (single column, non-nullable, integer representation) sorting is actually much faster than hashing. But I suppose that can become an implementation detail in unordered_drop_duplicates

[harrism]

Given the Python observation, why not call cudf::drop_duplicates just cudf::unique() to match both STL and Pandas and have it be unordered? Users need to sort first if they want it ordered.

[codereport]

I bet @codereport was involved or would have an opinion on the naming!

I think it was actually called unique_count at one point and I pointed out that "unique" has semantics in C++ that didn't align with what the libcudf algorithm was doing. So we ended up changing it to distinct_count as "distinct" doesn't have any specific C++ semantics.

Other side note: it is regarded as a mistake that we called our containers:

• map / set (for sorted tree implementations)
• unordered_map / unordered_set (for hashing implementations)

instead of:

• sorted_map / sorted_set (for sorted tree implementations)
• map / set (for hashing implementations)

The "sortedness" is an extra requirement that the user should have to think about if they want it. "Unsortedness" should be the default (Python got it right with Set / Map and SortedSet / SortedMap

[harrism]

Other side note: it is regarded as a mistake that we called our containers:

map / set (for sorted tree implementations)
unordered_map / unordered_set (for hashing implementations)

I don't know of such classes in libcudf. "we"?

[harrism]

I think it was actually called unique_count at one point and I pointed out that "unique" has semantics in C++ that didn't align with what the libcudf algorithm was doing. So we ended up changing it to distinct_count as "distinct" doesn't have any specific C++ semantics.

But now Jake is suggesting changing the non-ordering semantics to match std::unique. Are there other semantics that should stop us using that name?

[jrhemstad]

Given the Python observation, why not call cudf::drop_duplicates just cudf::unique() to match both STL and Pandas and have it be unordered? Users need to sort first if they want it ordered.

But the behavior of std::unique doesn't match Pandas unique. If we go with the unique/unordered_unique naming, Pandas would use the unordered_unique.

[harrism]

Hmmm, perhaps I misunderstood @shwina 's message.

What does Pandas unique return for [4, 4, 0, 1, 2, 2, 4, 4]? std:unique would return [4, 0, 1, 2, 4].

[jrhemstad]

https://pandas.pydata.org/docs/reference/api/pandas.unique.html

Hash table-based unique. Uniques are returned in order of appearance. This does NOT sort.

The fact that it calls out it uses a hash table means it's doing a total unique.

[shwina]

What does Pandas unique return for [4, 4, 0, 1, 2, 2, 4, 4]? std:unique would return [4, 0, 1, 2, 4].

Pandas would return [4, 0, 1, 2].

[codereport]

Other side note: it is regarded as a mistake that we called our containers:
map / set (for sorted tree implementations)
unordered_map / unordered_set (for hashing implementations)

I don't know of such classes in libcudf. "we"?

"We" refers to the C++ community at large. And it was just a general comment about the "unordered_" prefix that is used in the C++ Standard Library.

[harrism]

The fact that it calls out it uses a hash table means it's doing a total unique

Let's make sure to make our docs more clear. Understanding what our APIs do shouldn't require inference from implementation details.

[jrhemstad]

As a promising anecdote, @gaohao95 has already experimented with a hash-based solution of drop_duplicates with cuCollections and reports it's 100x faster than the current sort-based solution.

[github-actions]

This issue has been labeled inactive-30d due to no recent activity in the past 30 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be labeled inactive-90d if there is no activity in the next 60 days.

[ttnghia]

As a promising anecdote, @gaohao95 has already experimented with a hash-based solution of drop_duplicates with cuCollections and reports it's 100x faster than the current sort-based solution.

@jrhemstad Is there any draft PR yet? I am implementing cudf::contains for structs and have similar need for structs hashing. I planned to modify the existsing unordered_multiset implementation to support structs but not sure if the solution above (using cuCollection) is worth to wait.