Query Planning

A core database optimization where filtering predicates are evaluated as early as possible in the execution plan, ideally within the storage engine. This minimizes the volume of data transferred and processed by subsequent stages.

• Key Benefit: Drastically reduces I/O and computational overhead.
• Implementation: The query planner analyzes predicate selectivity to decide which filters to push down to the index or storage layer first.
• Example: A query for "vector_similarity(...) AND category = 'legal' AND date > 2024-01-01" would push the category and date filters to the metadata index before performing the expensive vector search.

Two fundamental strategies for applying metadata constraints in vector search, with significant performance implications.

• Pre-Filtering: Filters are applied first to create a reduced candidate set. The vector similarity search (ANN) runs only on this subset.

  • Best for: Highly selective filters (e.g., user_id = 123).
  • Risk: Can exclude relevant vectors if the filter is too restrictive.

• Post-Filtering: A broad vector search runs first, and the top-K results are then filtered by metadata.

  • Best for: Low-selectivity filters or when recall is paramount.
  • Risk: May return fewer than K results after filtering, hurting user experience.

The query planner must estimate filter selectivity to choose the optimal strategy.

Refers to Approximate Nearest Neighbor search algorithms modified to respect hard metadata constraints during the graph or tree traversal, not just before or after. This is a complex optimization challenge.

• Core Problem: Maintaining search efficiency and recall while skipping invalid nodes.
• HNSW with Filters: A common implementation where the graph traversal algorithm checks node metadata against filter predicates before exploring its connections. This avoids dead-ends but requires careful index design.
• Bitmap Index Integration: Some systems use bitmap indexes on metadata to perform fast set intersections with candidate vector IDs during ANN search.

An architecture where query execution is broken into distinct, sequential stages of increasing accuracy and cost. The query planner defines the pipeline.

• Stage 1 (Recall): A fast, broad search using a bi-encoder for vector similarity or BM25 for keywords. Retrieves 100-1000 candidates.
• Stage 2 (Reranking): A slower, precise cross-encoder model deeply analyzes the query and each candidate to compute a refined relevance score.
• Stage 3 (Business Logic): Final ordering may apply custom rules, diversity sampling, or filtering.

The planner allocates resources and sets candidate set sizes (K) for each stage to meet latency SLAs.

A Domain-Specific Language for declaratively expressing complex search intent. The query planner parses the DSL into an executable abstract syntax tree (AST).

• Function: Allows combining vector similarity, lexical search (BM25), Boolean filters, and aggregations in a single query.
• Example Query: {"must": [{"vector": {"embedding": [0.1, 0.2,...], "k": 10}}, {"range": {"date": {"gte": "2024-01-01"}}}], "should": [{"text": {"query": "machine learning"}}]}
• Planner's Role: Translates this declarative syntax into an optimized physical plan, deciding operation order and algorithm choice (e.g., pre-filter vs. ANN with filters).

The estimated proportion of records in a dataset that will satisfy a given filter predicate. This is the primary statistic used by the query planner to make cost-based decisions.

• Calculation: Selectivity = (Estimated Matching Rows) / (Total Rows). A low selectivity (e.g., 0.1%) means the filter is very restrictive.
• Planner Use Case:
  • High Selectivity Filter (e.g., status = 'active' on 95% of rows): Planner may choose post-filtering.
  • Low Selectivity Filter (e.g., id = 123): Planner will choose pre-filtering or filter pushdown.
• Estimation Methods: Uses histogram statistics, distinct value counts, or Bloom filters for fast membership tests to estimate selectivity.