AcceptDocs#cost() fully consumes iterator, invalidating any possible perf gain

[benwtrent]

Description

I have been digging into the AcceptDocs API and I noticed the following from the java docs:

  /**
   * Return an approximation of the number of accepted documents. This is typically useful to decide
   * whether to consume these accept docs using random access ({@link #bits()}) or sequential access
   * ({@link #iterator()}).
   *
   * <p><b>NOTE</b>: This must not be called after {@link #iterator()}.
   *
   * @return approximate cost
   */
  public abstract int cost() throws IOException;

However the implementation for the most common non-cached iterator:

    public int cost() throws IOException {
      createBitSetAcceptDocsIfNecessary();
      return acceptBitSet.cardinality();
    }

Actually fully consumes the iterator and just calls cardinality (nothing approximate at all...).

Why are we doing that? Why aren't we relying on DocIdSetIterator#cost or at least acceptBitSet.cardinality?

It seems to me the main idea behind AcceptDocs is the ability to bypass realizing the bitset and to just iterate as normal when the filter is very restrictive...

//cc @shubhamvishu

Version and environment details

No response

[shubhamvishu]

Hi @benwtrent, In DocIdSetIteratorAcceptDocs#cost aren't we using the cached version and not calling #cardinality again?. I see you already fixed it in your PR #15343. Maybe I misunderstood something here since I don't see the exact version of #cost function that you have pointed above. I see the current impl on main is,

private void createBitSetAcceptDocsIfNecessary() throws IOException {
      if (acceptBitSet == null) {
        acceptBitSet = Objects.requireNonNull(createBitSet(iterator(), liveDocs, maxDoc));
        cardinality = acceptBitSet.cardinality();
      }
    }
:
.
:
@Override
    public int cost() throws IOException {
      createBitSetAcceptDocsIfNecessary();
      return cardinality;
    }

[benwtrent]

@shubhamvishu we use cost to determine if we should do exact search or not. If we do exact search, we don't need the bitset. It seems weird to always build the bitset just to figure out the supposedly approximate cost.

Either we should have something called "approximate cost" and it's cheap and keep cost or switch the implementation to not fully realize the bitset

Right?

[Vikasht34]

@benwtrent ideally we want do something like this , never materializes the bitset in cost() - it just returns the iterator's cost estimate.

public int cost() throws IOException {
      if (acceptBitSet != null) {
        return cardinality;
      }
      return Math.toIntExact(iteratorSupplier.get().cost());
    }

@finnroblin this might be helpful.

[shubhamvishu]

Either we should have something called "approximate cost" and it's cheap and keep cost or switch the implementation to not fully realize the bitset

@benwtrent I see! So you're suggesting we use iterator.cost() in #cost to get a cheaper (though approximate) estimate, and defer realizing the bitset until #bits is called? That tradeoff makes sense to me, it keeps cost checks lightweight for users.

[benwtrent]

@shubhamvishu yeah, basically, I am thinking we can short cut fully realizing the filter for various things making filtered search way faster (maybe dynamic post filtering even ;)).

[shubhamvishu]

Maybe we can change it to something like :

@Override
    public int cost() throws IOException {
      if (acceptBitSet != null) {
        return cardinality;
      }
      if (liveDocs == null && iterator() instanceof BitSetIterator bitSetIterator) {
        return bitSetIterator.getBitSet().approximateCardinality();
      }
      return Math.toIntExact(iterator().cost());
    }

[benwtrent]

Yeah, that looks pretty good!