Is it normal for a query to take up forever (3-5 minutes, no response)

[isidentical]

So I have a DB with this schema, and I wanted to query all ast::Dict's where there are keys, the first one is a ast::Constant and the second one is an ast::Call (sorry for extra parens, autogenerated);

SELECT ast::Dict FILTER (count(.keys) = 2) AND (array_agg(enumerate(.keys)) = [(((0), (SELECT ast::Constant))), (((1), (SELECT ast::Call)))]) LIMIT 10

but this takes forever on an instance where there are about 16k nodes

asttests> SELECT count(ast::Dict);
{16556}
asttests> SELECT count((SELECT ast::Dict FILTER count(.keys) = 2));
{4097}
asttests> SELECT count(ast::expr);
{2051462}

Any idea that how I can optimize such a case?

Edit-1: 30 minutes, still no response for the query

System specs: i5 6600K, a fast SSD, 8 GB ram

[elprans]

array_agg(enumerate(.keys)) = [(((0), (SELECT ast::Constant)))

That's not how you check for the type of an object. Your query selects all Constant and Call objects from the database unconstrained and then performs the comparison X*Y times for every Dict object.

If you want to use equality instead of IS to test for types, you must compare with the schema::ObjectType instances instead, like this:

WITH
    Constant := (SELECT schema::ObjectType FILTER .name = 'ast::Constant'),
    Call := (SELECT schema::ObjectType FILTER .name = 'ast::Call')
SELECT
    ast::Dict
FILTER
    array_agg(.keys.__type__.id) = [Constant.id, Call.id];

However, there's another issue here: links are unordered, so you can't rely on the order in .keys implicitly, you must specify an explicit ordering. This is usually done with a property on a link, like so:

type Dict {
    multi link keys -> Node {
        property index -> int64;
    }
}

and then the query above becomes:

WITH
    Constant := (SELECT schema::ObjectType FILTER .name = 'ast::Constant'),
    Call := (SELECT schema::ObjectType FILTER .name = 'ast::Call')
SELECT
    ast::Dict
FILTER
    array_agg((SELECT .keys ORDER BY @index).__type__.id) = [Constant.id, Call.id];

(Explicit .id reference is normally not necessary to compare objecs, but in this case it's necessary to workaround the "cannot determine type of empty array" bug).

[elprans]

if we wanted to search for both type and value, what would be an example query

Use the [IS ] type assertion in paths, like this:

SELECT
    ast::Dict
FILTER
    count(.keys) = 2
    AND
    (SELECT .keys ORDER BY @index LIMIT 1)[IS ast::Constant].value = 123
    AND
    (SELECT .keys ORDER BY @index OFFSET 1 LIMIT 1)[IS ast::Call].func.py_id = "print"
LIMIT 10

[isidentical]

I was testing this query;

WITH
    Constant := (SELECT schema::ObjectType FILTER .name = 'ast::Constant'),
    Call := (SELECT schema::ObjectType FILTER .name = 'ast::Call')
SELECT
    ast::Dict
FILTER
    array_agg((SELECT .keys ORDER BY @index).__type__.id) = [Constant.id, Call.id];

but after seeing that it doesn't match anything (which I asserted that there are matches in the DB), I tried this and suprisingly it works;

SELECT
    ast::Dict{lineno, col_offset, end_lineno, end_col_offset, _module: {filename}}
FILTER
    count(.keys) = 2
    AND len(array_agg((SELECT .keys ORDER BY @index).__type__.id)) = 1
LIMIT 10

Looks like there is only one item in the array of types (it makes sense, since if I try to do something like this array_agg((SELECT .keys ORDER BY @index).__type__.id) = [Constant.id]; it works but on multiple items (1>) doesn't work. And then I tried this (ensured there are 2 keys and it gave me an id of a single type);

asttests> SELECT array_agg((SELECT ast::Dict {keys} FILTER count(.keys) = 2 LIMIT 1).keys.__type__.id);
{[e9a2f74b-fda4-11ea-afbe-d3054fd0a5ce]}
asttests> SELECT schema::ObjectType{name} FILTER .id = <uuid>"e9a2f74b-fda4-11ea-afbe-d3054fd0a5ce";
{Object {name: 'ast::Constant'}}

Any idea that what I am doing wrong?

[isidentical]

I was able to solve it with a for statement array_agg((FOR KEY in {(SELECT .keys ORDER BY @index)} UNION KEY.__type__.id)) = [Constant.id, Call.id] albeit I don't know whether it was the right approach or not.

[elprans]

array_agg((SELECT .keys ORDER BY @index).__type__.id)

What happens here is that the ordering by @index gets lost, because you're joining the __type__ relation. EdgeQL is set-based and so every operation, including path navigation produces sets with arbitrary order. One exception are sets produced directly by a statement with ORDER BY, so array_agg((SELECT .keys ORDER BY @index)) will produce expected ordering, but array_agg((SELECT .keys ORDER BY @index).__type__.id) will not.

The query with FOR .. IN has the same problem, but it works incidentally, because the generated SQL is slightly different.

As for the real solution, my advice would be to avoid using array comparisons, and instead compare set elements directly:

WITH
    Constant := (SELECT schema::ObjectType FILTER .name = 'ast::Constant'),
    Call := (SELECT schema::ObjectType FILTER .name = 'ast::Call')
SELECT
    ast::Dict{lineno, col_offset, end_lineno, end_col_offset, _module: {filename}}
FILTER
    count(.keys) = 2
    AND
    (SELECT .keys ORDER BY @index LIMIT 1) IS ast::Constant
    AND
    (SELECT .keys ORDER BY @index OFFSET 1 LIMIT 1) IS ast::Call

If you MUST use arrays, then the correct fix would be to compare indexed tuples:

WITH
    Constant := (SELECT schema::ObjectType FILTER .name = 'ast::Constant'),
    Call := (SELECT schema::ObjectType FILTER .name = 'ast::Call')
SELECT
    ast::Dict{lineno, col_offset, end_lineno, end_col_offset, _module: {filename}}
FILTER
    count(.keys) = 2
    AND
    array_agg((SELECT tup := (.keys.__type__.id, .keys@index) ORDER BY tup.1)) = [(Constant.id, 0), (Call.id, 1)];

[isidentical]

I see, explanation is much appreciated. Sorry for bothering constantly, I dont have much experience with databases (at least something other than sqlite), but can say that EdgeDB was an awesome experience so far (I have a QL format that compiles to EdgeQL, if you are interested in what I've been building with all those stuff, there is the link for my compiler. It is still in very pre-mature state, but will continue to build stuff around it, hopefully. Thank you all so much!

[1st1]

It's an interesting project you're working on! I've noticed this file -- https://github.com/isidentical/pyasdl/blob/master/generators/PythonAST.ql -- which looks like a GraphQL schema. If so, I just wanted to note that EdgeDB can automatically reflect its schema to GraphQL.

[isidentical]

Yeah, while searching for ways to represent the AST as a schema, I initially find out graphQL, but it wasn't exactly what I wish (such as algebraic types are just unions etc.). And then after talking with a friend, I found out EdgeDB which is just awesome and perfectly fine for needs (like base types etc.) I have both the GraphQL generator and an EdgeQL generator. This is my current schema