Repository: geldata/gel
Pull request: Avoid doing semi-joins after a sequence of single links
If we have a query like
```
select Post filter .owner.person.id = <uuid>$uid
```
where `owner` is `single`, there is no need to do a semi-join on
`.person`. This can have major performance impacts.

Fixes #4160.

Problem statement:
Slow query when filtering by second link
- EdgeDB Version: 1.4+ffe1237 
- OS Version: your CloudFormation template

Simplified schema:
```
Person { multi link personPosts := .<person[is Profile].profilePosts; }
Profile {
  link person -> Person {
    delegated constraint exclusive;
  }
  multi link profilePosts := .<owner[is Post];
}
IGProfile {}
TTProfile {}
Post { required link owner -> Profile; }
IGPost { overloaded required link owner -> IGProfile; }
TTPost { overloaded required link owner -> TTProfile; }
```

These queries are both fast:
```
select Post filter .owner.id = <uuid>"";
select Person { personPosts } filter .id = <uuid>"";
```

But this one take 5+ seconds:
```
select Post filter .owner.person.id = <uuid>"";
```

Number of objects:
Person: 100
Profile: 150k
Post: 431k

I'm happy to share more details if it would be helpful.

Hints from issue discussion:
Interesting. I was able to reproduce this slowness.

If we do the select on just one of the post types, like
```
select TTPost filter .owner.person.id = <uuid>'3752263c-12a0-11ed-80df-cbe9314dd309';
```
it is much faster, but still kind of slow: 250ms vs 2.6ms for one of the shape ones.
I think the crux of the issue is that we are doing a semi-join on `.person` because `Post.owner` isn't visible.
If we do 
```
select Post filter (for x in .owner union (x.person.id = <uuid>$uid))
```
or
```
select Post filter (.owner, .owner.person.id = <uuid>$uid).1
```
then it is fast.

I think it should be possible to disable the semi-join in this case, since `Post` is visible and `.owner` is single

Commit message: Avoid doing semi-joins after a sequence of single links

If we have a query like
```
select Post filter .owner.person.id = <uuid>$uid
```
where `owner` is `single`, there is no need to do a semi-join on
`.person`. This can have major performance impacts.

Fixes #4160.

Patch to review:
diff --git a/edb/pgsql/compiler/relgen.py b/edb/pgsql/compiler/relgen.py
index 4591a248f90..cbd25d6d0e9 100644
--- a/edb/pgsql/compiler/relgen.py
+++ b/edb/pgsql/compiler/relgen.py
@@ -964,6 +964,32 @@ def process_set_as_path_type_intersection(
         ir_set, stmt, aspects=['value', 'source'], ctx=ctx)
 
 
+def _source_path_is_visible(
+        ir_source: irast.Set,
+        ctx: context.CompilerContextLevel) -> bool:
+    """Check if the path is 'visible enough' to avoid a semi-join.
+
+    This means that it has a visible prefix followed by single pointers.
+    This is an optimization that allows us to avoid doing a semi-join
+    when there is a chain of single links referenced (probably in a filter
+    or a computable).
+    """
+    if ctx.scope_tree.is_visible(ir_source.path_id):
+        return True
+
+    while (
+        ir_source.rptr
+        and ir_source.rptr.dir_cardinality.is_single()
+        and not ir_source.expr
+    ):
+        ir_source = ir_source.rptr.source
+
+        if ctx.scope_tree.is_visible(ir_source.path_id):
+            return True
+
+    return False
+
+
 def process_set_as_path(
         ir_set: irast.Set, stmt: pgast.SelectStmt, *,
         ctx: context.CompilerContextLevel) -> SetRVars:
@@ -984,6 +1010,8 @@ def process_set_as_path(
     root_source_is_visible = ctx.scope_tree.is_visible(backtrack_src.path_id)
     source_is_visible = ctx.scope_tree.is_visible(ir_source.path_id)
 
+    source_is_single = _source_path_is_visible(ir_source, ctx=ctx)
+
     rvars = []
 
     # Type intersection paths have their own entire code path.
@@ -1008,7 +1036,7 @@ def process_set_as_path(
         ctx.disable_semi_join |= new_paths
 
     semi_join = (
-        not source_is_visible and
+        not source_is_single and
         not root_source_is_visible and
         ir_set.path_id not in ctx.disable_semi_join and
         not (is_linkprop or is_primitive_ref) and
diff --git a/tests/test_edgeql_sql_codegen.py b/tests/test_edgeql_sql_codegen.py
index 01f100ad304..164a387fe0b 100644
--- a/tests/test_edgeql_sql_codegen.py
+++ b/tests/test_edgeql_sql_codegen.py
@@ -229,3 +229,15 @@ def test_codegen_filtered_link_no_semijoin(self):
             " IN ", sql,
             "unexpected semi-join",
         )
+
+    def test_codegen_chained_single_no_semijoin(self):
+        sql = self._compile('''
+            select Issue {
+               z := .owner.todo
+            }
+       ''')
+
+        self.assertNotIn(
+            " IN ", sql,
+            "unexpected semi-join",
+        )


Code review comments:
diff_hunk: @@ -964,6 +964,32 @@ def process_set_as_path_type_intersection(
         ir_set, stmt, aspects=['value', 'source'], ctx=ctx)
 
 
+def _source_path_is_visible(
path: edb/pgsql/compiler/relgen.py
text: @user1:
I would use something like `_needs_semi_join`