Filter Optimization: selected_handles

[dsblank]

This document explains the filter optimization system built into Gramps 6.0 and describes how developers can extend it in new or existing filter rules.

Currently this isn't very well documented, and we could do more to make the contracts around selected_handles be more explicit. Ideas welcome.

When this document is complete, we should add it to a place for developers to have easy access.

I'd like to thank @stevenyoungs for help in designing, developing, and testing the system so far.

---

History: prepare() and apply_to_one()

The prepare() / apply_to_one() / reset() contract on Rule is not new to Gramps 6 (although we renamed apply to apply_to_one). Many rules have always used prepare() to do expensive work once (graph traversals, bookmark lookups, etc.) and then answered apply_to_one() with a cheap set-membership check.

What Gramps 6 did was standardize the attribute name. Previously each rule used its own internal variable name for the precomputed set. Gramps 6 requires that every rule which does this stores its result in an attribute called selected_handles:

def prepare(self, db: Database, user) -> None:
    self.selected_handles: Set[str] = set()
    root = db.get_person_from_gramps_id(self.list[0])
    self._walk_descendants(root)

def reset(self) -> None:
    self.selected_handles.clear()

def apply_to_one(self, db: Database, person: Person) -> bool:
    return person.handle in self.selected_handles

That naming convention is what makes the optimizer possible: any code can inspect a rule and ask "does this rule have a selected_handles?" without knowing anything else about the rule.

---

The Problem the Optimizer Solves

Even with selected_handles populated by prepare(), the old filter engine still looped over every object in the database:

# old behaviour — still iterates the whole database
for handle in db.get_person_handles():
    person = db.get_person_from_handle(handle)
    if rule.apply_to_one(db, person):   # → handle in selected_handles
        final_list.append(handle)

That loop is O(N) in the total number of people, even when only 3 of them match. The per-object get_person_from_handle() call means loading every person from storage.

---

The Optimizer: Turning Filtering Inside Out

The Optimizer class (optimizer.py) runs after all prepare() calls but before the per-object loop. It inspects every rule in the filter:

• If a rule has selected_handles, those handles are collected.
• If a rule has find_filter() (it embeds another named filter), the optimizer
  recurses into that filter's rules.

It then combines the per-rule sets according to the filter's logical operator:

Logical op	What the optimizer does
and	Intersects all selected_handles sets across rules
or	Cannot intersect; optimizer does not prune

The intersection — called handles_in — is the set of handles that could possibly match the filter. The per-object loop is then gated on this set:

for handle in possible_handles:
    if handles_in is not None and handle not in handles_in:
        continue   # skip: cannot match any AND rule
    obj = self.get_object(db, handle)
    if apply_logical_op(db, obj, self.flist) != self.invert:
        final_list.append(obj.handle)

For a filter with one rule and a small selected_handles, this can reduce 10k get_person_from_handle()` calls to 3.

Skipping the loop entirely (PR #2160)

When every rule in a filter has selected_handles — i.e. there are no unoptimized rules — the intersected handles_in set is already the exact answer. There is no need to call apply_to_one() at all. PR #2160 detects this case and returns handles_in directly without entering the loop.

This is the key insight: once all prepare() calls finish, the filter is done. The set operations are the filter. No objects need to be loaded from storage; no apply_to_one() calls are made.

---

Rules that Embed Another Filter: find_filter()

Some rules delegate to a user-defined custom filter by name (e.g. "People matching filter <name>"). These implement find_filter() to return the embedded GenericFilter:

def find_filter(self):
    filters = gramps.gen.filters.CustomFilters.get_filters_dict(self.namespace)
    return filters.get(self.list[0])

The optimizer calls find_filter() when a rule lacks selected_handles, then recurses into the returned filter to collect its rules' selected_handles sets. A "Matches filter" rule transparently benefits from any selected_handles optimization in the embedded filter's rules — no extra work needed.

Using filter.apply() instead of apply_to_one() inside rules (PR #2153)

Rules that use another filter as a source (e.g. "descendants of people matching filter X") previously called apply_to_one() per object, bypassing the optimizer entirely. PR #2153 changes these to call filter.apply(db) instead. apply() runs the full optimizer pipeline and returns matching handles directly; only those handles are then used for the outer traversal.

---

Direct SQL + the Optimizer: The Full Optimization (PR #2177)

The optimizer removes the Python loop. But prepare() still does its work in Python — walking the family graph, loading objects one at a time from the database. PR #2177 adds register_rule_override() to let a database backend replace that Python traversal with a single native query.

Registering an override

A database subclass calls register_rule_override() to associate a rule with an override class:

class IsMaleOverride(RuleOverride):
    def prepare(self, original, db, user) -> None:
        self.selected_handles: set[str] = set(
            db.select_from_person(
                what="person.handle",
                where="person.gender == Person.MALE",
            )
        )

db.register_rule_override(("person", "isMale"), IsMaleOverride)

The override populates selected_handles from one SQL query rather than a Python loop. The result is the same attribute; the optimizer sees and uses it identically.

The full pipeline

The combination of all three layers reduces filtering to:

1. prepare() via SQL override — one indexed query per rule, no Python object loading.
2. Optimizer intersects the sets — pure Python set operations on the returned handles.
3. No loop (PR Optimizer: skip loop when all rules are optimized #2160) — if all rules are optimized, the intersected set is returned immediately.

For a SQL-backed database, a complex multi-rule AND filter can reduce entirely to a handful of SQL queries and a set intersection — no objects loaded, no Python loop, no apply_to_one() calls.

Override mechanics

• The key is (namespace, rule.name) — matching the rule's class.
• The original rule method is passed as original so overrides can delegate: original(self.rule, db, user).
• Overrides are bypassed automatically when db.is_proxy() is True (Living and Privacy proxies), so privacy logic is never skipped.
• RuleOverride provides no-op defaults for both methods; subclasses only override what they accelerate.

---

Adding selected_handles to a New Rule

from typing import Set
from gramps.gen.db import Database

class MyRule(Rule):
    def prepare(self, db: Database, user) -> None:
        self.selected_handles: Set[str] = set()
        # populate: graph traversal, bookmark list, ID lookup, etc.

    def reset(self) -> None:
        self.selected_handles.clear()

    def apply_to_one(self, db: Database, obj) -> bool:
        return obj.handle in self.selected_handles

When to add it:

• The matching set can be determined in prepare() without inspecting every object (graph traversal from a known root, bookmark list, ID lookup).
• The matching set is small relative to the full database.

When NOT to add it:

• The rule must inspect each object individually (e.g. "birth year before X", "name contains Y") — there is no precomputable set.

---

Rules Currently Implementing selected_handles

Generic base

File	Description
rules/_hasgrampsid.py	Looks up an object by its Gramps ID

Person rules

File	Description
person/_hasidof.py	Person with a specific Gramps ID
person/_isdefaultperson.py	The home person
person/_isbookmarked.py	Bookmarked people
person/_isancestorof.py	Ancestors of a specified person
person/_isdescendantof.py	Descendants of a specified person
person/_isdescendantfamilyof.py	Families in the descendant tree
person/_isrelatedwith.py	All people related to a specified person (BFS)
person/_isancestoroffiltermatch.py	Ancestors of filter-matched people
person/_isdescendantoffiltermatch.py	Descendants of filter-matched people
person/_ischildoffiltermatch.py	Children of filter-matched people
person/_isparentoffiltermatch.py	Parents of filter-matched people
person/_issiblingoffiltermatch.py	Siblings of filter-matched people
person/_isdescendantfamilyoffiltermatch.py	Descendant families of filter-matched people
person/_isduplicatedancestorof.py	People who appear more than once as ancestors
person/_relationshippathbetween.py	People on the relationship path between two persons
person/_relationshippathbetweenbookmarks.py	Relationship path between bookmarked people
person/_deeprelationshippathbetween.py	Deep relationship path between two persons
person/_islessthannthgenerationancestorof.py	Ancestors within N generations
person/_ismorethannthgenerationancestorof.py	Ancestors beyond N generations
person/_islessthannthgenerationdescendantof.py	Descendants within N generations
person/_ismorethannthgenerationdescendantof.py	Descendants beyond N generations
person/_islessthannthgenerationancestorofbookmarked.py	Ancestors of bookmarked people within N generations
person/_islessthannthgenerationancestorofdefaultperson.py	Ancestors of home person within N generations

Family rules

File	Description
family/_hasidof.py	Family with a specific Gramps ID
family/_isbookmarked.py	Bookmarked families
family/_isancestorof.py	Ancestor families of a specified family
family/_isdescendantof.py	Descendant families of a specified family

Other object types

File	Description
citation/_hasidof.py	Citation with a specific Gramps ID
event/_hasidof.py	Event with a specific Gramps ID
media/_hasidof.py	Media object with a specific Gramps ID
note/_hasidof.py	Note with a specific Gramps ID
place/_hasidof.py	Place with a specific Gramps ID
repository/_hasidof.py	Repository with a specific Gramps ID
source/_hasidof.py	Source with a specific Gramps ID

---

Debugging

The filter system logs timing at the DEBUG level:

import logging
logging.getLogger(".filter.results").setLevel(logging.DEBUG)
logging.getLogger(".filter.optimizer").setLevel(logging.DEBUG)

Each apply() call logs:

• Prepare time — time in all rule.prepare() calls.
• Apply time — time in the main loop (zero if the loop was skipped).
• Starting possible_handles — handle count before optimizer pruning.

If Apply time dominates, a rule in the filter lacks selected_handles and is forcing the full loop. Adding selected_handles to that rule (or a SQL override for it) is the highest-leverage change.

---

NOTE: there is also a relationship with DataDict, but I'll describe that later.

NOTE: future work is also described in #2280