Inline property map `{key: value}` is estimated with a fixed selectivity, so multi-hop MATCH flips to a full edge scan + Hash/Merge Join when the key is selective

[NotHimmel]

Describe the bug

MATCH (a:Label {key: value}) compiles the filter to properties @> '{"key": value}'. That operator's RESTRICT estimator does not read any per-key statistics: on the PG18 branch (1.8.0) it is contsel, a fixed 0.001; on 1.7.0 it was matchingsel, which reads the whole properties column's statistics (no information about any single key) and bottoms out at PostgreSQL's 1e-4 floor. Either way a filter on a unique key is estimated as 0.1% / 0.01% of the label instead of 1 row.

On a single-hop lookup this is harmless. On a multi-hop MATCH the overestimated start vertex makes per-vertex index probing look expensive and the planner switches the next hop to a full scan of every edge label table joined with a Hash Join (or Merge Join at larger scale). The same query written as WHERE a.key = value compiles to agtype_access_operator(properties, '"key"') = value, uses eqsel on the expression index's statistics, estimates 1 row, and keeps the nested-loop plan — so the statistics exist, @> just never consults them.

Reported from production (PG 18.4, AGE 1.7.0-rc0, 3M vertices / 9M edges): a 2-hop query went from 1.3 s to 8–12 s after a GIN index was added on properties; SET enable_mergejoin = off brought it back to ~1.4 s. Here the start estimate itself is wrong, and it reproduces on a uniform graph.

How are you accessing AGE (Command line, driver, etc.)?

psql

What data setup do we need to do?

300k vertices with a unique person_id, three edge labels with out-degree 10 each (uniform, no skew), a GIN index on properties. Three tiny extra vertex/edge labels are included only so the Append shape matches a realistic multi-label graph; they are not needed to trigger the flip.

LOAD 'age';
SET search_path = ag_catalog, public;

SELECT create_graph('g');
SELECT create_vlabel('g','VTABLE');
SELECT create_vlabel('g','V2'); SELECT create_vlabel('g','V3'); SELECT create_vlabel('g','V4');
SELECT create_elabel('g','E1TABLE'); SELECT create_elabel('g','E2TABLE'); SELECT create_elabel('g','E3TABLE');
SELECT create_elabel('g','E4'); SELECT create_elabel('g','E5'); SELECT create_elabel('g','E6');

CREATE FUNCTION lid(text) RETURNS int LANGUAGE sql AS $$
  SELECT l.id::int FROM ag_catalog.ag_label l JOIN ag_catalog.ag_graph gr ON gr.graphid = l.graph
  WHERE gr.name = 'g' AND l.name = $1 $$;

INSERT INTO g."VTABLE" (id, properties)
SELECT _graphid(lid('VTABLE'), i::bigint),
       ('{"person_id": "B1_P' || lpad(i::text, 8, '0') || '", "city": "C' || (i % 50) || '", "age": ' || (20 + i % 60) || '}')::agtype
FROM generate_series(1, 300000) i;

-- 30,000 start vertices x 10 out-edges per edge label
INSERT INTO g."E1TABLE" (id, start_id, end_id, properties)
SELECT _graphid(lid('E1TABLE'), ((v-1)*10+k)::bigint), _graphid(lid('VTABLE'), v::bigint),
       _graphid(lid('VTABLE'), (((v::bigint*7919 + k*13) % 30000) + 1)::bigint), '{"t":"E1"}'::agtype
FROM generate_series(1, 30000) v, generate_series(1, 10) k;
INSERT INTO g."E2TABLE" (id, start_id, end_id, properties)
SELECT _graphid(lid('E2TABLE'), ((v-1)*10+k)::bigint), _graphid(lid('VTABLE'), v::bigint),
       _graphid(lid('VTABLE'), (((v::bigint*104729 + k*17) % 30000) + 1)::bigint), '{"t":"E2"}'::agtype
FROM generate_series(1, 30000) v, generate_series(1, 10) k;
INSERT INTO g."E3TABLE" (id, start_id, end_id, properties)
SELECT _graphid(lid('E3TABLE'), ((v-1)*10+k)::bigint), _graphid(lid('VTABLE'), v::bigint),
       _graphid(lid('VTABLE'), (((v::bigint*15485863 + k*19) % 30000) + 1)::bigint), '{"t":"E3"}'::agtype
FROM generate_series(1, 30000) v, generate_series(1, 10) k;
INSERT INTO g."E4" (id, start_id, end_id, properties)
SELECT _graphid(lid('E4'), i::bigint), _graphid(lid('VTABLE'), i::bigint), _graphid(lid('VTABLE'), (i+1)::bigint), '{"t":"E4"}'::agtype FROM generate_series(1,10) i;
INSERT INTO g."E5" (id, start_id, end_id, properties)
SELECT _graphid(lid('E5'), i::bigint), _graphid(lid('VTABLE'), i::bigint), _graphid(lid('VTABLE'), (i+2)::bigint), '{"t":"E5"}'::agtype FROM generate_series(1,10) i;
INSERT INTO g."E6" (id, start_id, end_id, properties)
SELECT _graphid(lid('E6'), i::bigint), _graphid(lid('VTABLE'), i::bigint), _graphid(lid('VTABLE'), (i+3)::bigint), '{"t":"E6"}'::agtype FROM generate_series(1,10) i;

CREATE INDEX vtable_props_gin_idx ON g."VTABLE" USING gin (properties);
CREATE INDEX vtable_pid_aao_idx ON g."VTABLE" (agtype_access_operator(properties, '"person_id"'::agtype));
ANALYZE g."VTABLE"; ANALYZE g."E1TABLE"; ANALYZE g."E2TABLE"; ANALYZE g."E3TABLE";

What is the necessary configuration info needed?

shared_preload_libraries = 'age'. Everything else default (max_parallel_workers_per_gather = 2).

What is the command that caused the error?

-- inline map: bad plan
EXPLAIN (ANALYZE, COSTS ON)
SELECT * FROM cypher('g', $$
  MATCH (a:VTABLE {person_id: 'B1_P00000001'})-->()-->(c) RETURN count(DISTINCT c) $$) AS (n agtype);

Aggregate  (cost=19250.29..19250.30 rows=1)
  ...
  ->  Hash Join  (cost=1002.14..16831.92 rows=365)
        Hash Cond: (_age_default_alias_0.start_id = a.id)
        ->  Parallel Append  (cost=0.00..14845.36 rows=375013)       <- all 900k edges scanned
              ->  Parallel Seq Scan on "E1TABLE" ...
              ->  Parallel Seq Scan on "E2TABLE" ...
              ->  Parallel Seq Scan on "E3TABLE" ...
        ->  Hash
              ->  Bitmap Heap Scan on "VTABLE" a  (cost=40.16..998.39 rows=300)   (actual rows=1)
                    ->  Bitmap Index Scan on vtable_props_gin_idx  (rows=300)
Execution Time: ~365 ms

-- same query, WHERE form: good plan
EXPLAIN (ANALYZE, COSTS ON)
SELECT * FROM cypher('g', $$
  MATCH (a:VTABLE)-->()-->(c) WHERE a.person_id = 'B1_P00000001' RETURN count(DISTINCT c) $$) AS (n agtype);

Aggregate  (cost=151.53..151.54 rows=1)
  ->  Nested Loop  (cost=0.42..151.48 rows=3)
        ->  Nested Loop ...
              ->  Index Scan using vtable_pid_aao_idx on "VTABLE" a  (cost=0.42..8.44 rows=1)   (actual rows=1)
              ->  Append  (cost=0.00..131.79 rows=34)                  <- per-vertex index probes
                    ->  Bitmap Heap Scan on "E1TABLE" ... Recheck Cond: (start_id = a.id)
Execution Time: ~57 ms

Both return the same result. The only difference is the start-vertex estimate: 300 (0.001 × 300,000) vs 1. With rows=300 the planner costs the nested loop at ≈300 × 131.79 ≈ 39,500 and picks the 14,845 hash build over all edges; with rows=1 the nested loop costs ≈132.

The estimate is not a fluke of scale: NL and Hash costs cross at roughly 100–300 estimated start rows, so the flip happens once label_rows × 0.001 passes that — around 300k rows on the PG18 branch. Under 1.7.0's matchingsel (1e-4 floor) the same flip needs ~3M rows, which is where the production report sits; upgrading to 1.8 moves it 10× earlier.

Expected behavior

(a:Label {key: value}) and WHERE a.key = value should produce the same row estimate when statistics for that key exist (expression index or CREATE STATISTICS ... ON (agtype_access_operator(properties, '"key"'))). The @> estimator should consult those statistics instead of returning a constant; when none exist it can keep returning the current constant so installations without expression statistics are unaffected.

#2417 (the matchingsel → contsel revert for #2356) already notes this direction: "A future improvement could add a custom agtype selectivity function that is both cheap and statistics-aware."

Environment

• PostgreSQL 18.3; AGE branch PG18 at PG18/v1.8.0-rc0 (contsel). Mechanism also confirmed on 1.7.0 semantics (matchingsel) at 3M rows.
• Linux x86_64

[NotHimmel]

I've been prototyping a fix and would like a discussion before opening a PR. The idea:
bind @>/@>> to a new RESTRICT estimator that decomposes the constant map the same way enable_containment = off does — one equality per scalar key on agtype_access_operator(properties, '"key"') — and estimates each leaf with examine_variable() + var_eq_const(), so it picks up whatever expression index or CREATE STATISTICS the user already has on that key. Inline map and WHERE n.key = v then estimate identically. It never touches the properties column's stats and never calls agtype_contains(), so the #2356 planning-time regression can't come back (measured +5–16% over contsel vs +83% for matchingsel), and when the relation has no expression statistics at all it returns the same 0.001 contsel does, so existing installs see identical plans.

Does this direction look reasonable?