Filter Selectivity

Filter selectivity is a statistical measure, expressed as a value between 0.0 and 1.0 (or 0% to 100%), that estimates the fraction of rows in a table or index that will satisfy a specific filter condition. It is calculated as:

Selectivity = (Estimated Number of Matching Rows) / (Total Number of Rows)

• A selectivity of 0.01 (1%) indicates a highly selective filter, likely returning a small result set.
• A selectivity of 0.9 (90%) indicates a non-selective filter, returning most records. Optimizers use this value to choose between index scans, full table scans, and join algorithms.

The query optimizer uses selectivity estimates to generate the lowest-cost execution plan. Key decisions influenced by selectivity include:

• Access Path Selection: Choosing between a full vector/index scan versus using a specific metadata index.
• Join Order: Determining the optimal sequence for joining multiple tables, typically processing the most selective filters first to reduce intermediate result sizes.
• Operator Choice: Deciding whether to use a nested-loop join (good for highly selective outer tables) or a hash join (better for larger, less filtered datasets). In vector databases, it critically informs the choice between pre-filtering and post-filtering strategies.

Selectivity is not a fixed property; it depends on data distribution and the predicate itself. Key factors are:

• Data Cardinality: The number of distinct values in a column. High cardinality (e.g., user_id) typically leads to higher selectivity for equality filters.
• Predicate Type: An equality filter (category = 'sports') is generally more predictable than a range filter (price > 100).
• Data Skew: Real-world data is often skewed. A filter on country='US' might have low selectivity in a global dataset but high selectivity in a dataset for Japan.
• Correlated Columns: Selectivity estimates for conjunctive filters (AND) assume independence, but if city and zip_code are correlated, the actual selectivity may be much higher than the product of individual selectivities.

Databases use various methods to estimate selectivity without scanning all data:

• Histograms: The most common technique. The system divides column value ranges into buckets and stores the frequency of values in each, enabling accurate estimates for equality and range predicates.
• HyperLogLog & Distinct Counts: Used to estimate the cardinality of a column, which is essential for equality filter estimates.
• Sampling: Running the filter on a small, random sample of pages to extrapolate the overall selectivity.
• Static Catalog Statistics: Pre-computed statistics like n_distinct, most_common_vals, and correlation stored in the system catalog (e.g., pg_statistics in PostgreSQL).

In hybrid search systems, filter selectivity directly dictates the optimal retrieval strategy:

• High-Selectivity Filters (e.g., user_id=123): Favor pre-filtering. Applying the strict filter first creates a very small candidate set, making the subsequent Approximate Nearest Neighbor (ANN) search over vectors cheap and accurate.
• Low-Selectivity Filters (e.g., is_published=true): Favor post-filtering. Performing a broad ANN search first and then applying the weak filter avoids the overhead of integrating the filter into the graph traversal of indexes like HNSW. Poor selectivity estimation can lead the optimizer to choose a post-filtering plan for a highly selective query, causing massive unnecessary vector comparisons.

Filter selectivity interacts with several core database optimization principles:

• Filter Pushdown: The optimizer strives to push high-selectivity filters down to the storage layer to minimize data movement. High selectivity makes pushdown highly beneficial.
• Bitmap Index Scans: For medium-selectivity filters on multiple columns, the database may perform bitmap index scans, combining bitmaps using AND/OR before fetching the rows.
• Conjunctive vs. Disjunctive Queries: The selectivity of a conjunctive query (AND) is the product of individual selectivities (assuming independence). A disjunctive query (OR) has selectivity calculated as 1 - product(1 - sel_i).
• Cost-Based Optimization (CBO): Selectivity is a primary input into the cost formulas that compare potential execution plans.

The process by which a database system's optimizer analyzes a search query and its metadata filters to generate an efficient execution plan. The optimizer uses estimated filter selectivity to decide the order of operations, such as whether to apply a filter before or after a vector search, to minimize computational cost and latency.

A critical query optimization technique where filtering predicates are evaluated as early as possible in the execution pipeline, ideally within the storage engine. High-selectivity filters are prime candidates for pushdown. This minimizes the amount of data that must be loaded and processed by subsequent stages (like vector search), dramatically improving performance.

• Example: A filter for user_id = 123 is executed directly on the database nodes holding the data, rather than on a central coordinator.

Two fundamental strategies for applying metadata constraints in vector search, directly governed by filter selectivity estimates.

• Pre-Filtering: Apply high-selectivity filters first to create a small candidate set, then perform the expensive vector search. Efficient when filters eliminate most records.
• Post-Filtering: Perform a broad vector search first, then apply filters to the results. Used when filters have low selectivity or when the unfiltered vector search is already fast.

The choice between these strategies is a key decision informed by filter selectivity.

A specialized database index structure that enables extremely fast filtering operations, which are essential for estimating and leveraging filter selectivity. It represents the set of records containing a specific attribute value using a compact array of bits (a bitmap).

• How it helps: Allows for rapid set intersection (AND) and union (OR) operations. A query optimizer can quickly scan these bitmaps to estimate the selectivity of a filter (e.g., how many bits are set in the category='electronics' bitmap) before executing the full query.

Refers to Approximate Nearest Neighbor (ANN) search algorithms that have been modified to natively respect hard metadata constraints during the graph or tree traversal. This is a complex extension where the index structure itself is aware of filters.

• Challenge: Maintaining search speed and recall while skipping over nodes that don't match the filter predicates.
• Implementation: Algorithms like HNSW with Filters or DiskANN with tags integrate filtering logic directly into the graph traversal, using selectivity estimates to guide the search path.

The two primary logical structures for combining multiple filters, where selectivity estimation becomes combinatorial.

• Conjunctive Query (AND): category='books' AND price < 20. The overall selectivity is the product of individual selectivities (assuming independence), typically resulting in a very high-selectivity filter.
• Disjunctive Query (OR): category='books' OR author='Smith'. The overall selectivity is the sum of individual selectivities minus the overlap, often resulting in a lower-selectivity (broader) filter.

Accurately modeling the selectivity of these compound predicates is essential for the optimizer to choose the correct table scan or index access method.