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
- Dominant language
- C
- Stars
- 4.8k
- Forks
- 523
- Avg merge
- 1d 2h
- Merged PRs (30d)
- 9
Description
**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.
```sql
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?**
```sql
-- 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
```
```sql
-- 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
Contributor guide
Research direction
Start by tracing the RESTRICT estimator used by the `@>` operator, comparing the `contsel`/`matchingsel` path with the `agtype_access_operator` expression used by the WHERE form. Run the supplied SQL reproduction and inspect EXPLAIN estimates with and without expression statistics. Done means inline property-map filters consult available per-key statistics and produce the same estimate and join strategy as the equivalent WHERE filter, with the no-statistics fallback preserved.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c, postgresql, sql
- Domain
- databases, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100