NVIDIA / NVIDIA/cuCollections

[ENHANCEMENT]: Add count_if and retrieve_if APIs to static_multiset

Open
#800 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

helps: rapids type: feature request
Dominant language
Cuda
Stars
667
Forks
120
Avg merge
7d 5h
Merged PRs (30d)
4

Description

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

static_multiset currently has insert_if and contains_if with stencil/predicate support, but the count, count_outer, retrieve, and retrieve_outer APIs lack corresponding _if variants.

In cuDF's hash join, we want to use a bloom filter to pre-filter probe rows before counting/retrieving matches. The bloom filter produces a per-row boolean predicate. With count_if / retrieve_if, we could skip probe rows that the bloom filter rejects, avoiding unnecessary hash table lookups.

Describe the solution you'd like

Proposed API (following the existing insert_if / contains_if pattern):

  // Count matches only for probe keys where pred(*(stencil + i)) is true.                                                                                                                                                                                                                                                                      
  // Keys where the predicate is false contribute 0 to the count (inner)                                                                                                                                                                                                                                                                        
  // or 1 (outer, for left/full join semantics).                                                                                                                                                                                                                                                                                                
  size_type count_if(InputIt first, InputIt last, StencilIt stencil, Predicate pred, ...);                                                                                                                                                                                                                                                      
  size_type count_outer_if(InputIt first, InputIt last, StencilIt stencil, Predicate pred, ...);                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                
  // Retrieve matches only for probe keys where pred(*(stencil + i)) is true.                                                                                                                                                                                                                                                                   
  retrieve_if(InputIt first, InputIt last, StencilIt stencil, Predicate pred, ...);                                                                                                                                                                                                                                                             
  retrieve_outer_if(InputIt first, InputIt last, StencilIt stencil, Predicate pred, ...);      
Describe alternatives you've considered

No response

Additional context

No response

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by locating static_multiset and its existing insert_if and contains_if implementations, then compare the count, count_outer, retrieve, and retrieve_outer APIs. Done means the corresponding predicate-and-stencil variants are added with inner and outer semantics matching the request, with coverage for accepted and rejected predicates.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
backend-api-design
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
62/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.