cwida / duckpgq-extension Goto Github PK

There is currently a test commented out

Query unexpectedly failed (/Users/dljtw/git/duckpgq/test/sql/duckpgq.test:20)
================================================================================
SELECT duckpgq_openssl_version('Michael');
================================================================================
Actual result:
Binder Error: Registered state not found

Goal of this issue is to figure out what to do with OpenSSL and how to make this function pass. But at the moment I don't think this is main priority.

-- Preamble: Just stumbled upon the extension, very excited, thank you!

Functionality suggestion ( maybe already in pipeline):

Explicit graph data are not that common and often have to be created by recomputing the topology. This is common in the spatial context ( street lanes), where graphs are computed by analyzing topological relationships between member geometries.

The result is a data structure -- the edge table. See for example the behaviour of [pg_routing] (https://docs.pgrouting.org/latest/en/pgr_createTopology.html), potentially with an additional vertices table.

It would be awesome if it was possible to create the input structures in DUCK/PGQ, instead of having to craft them separately.

Following query fails:

-CREATE PROPERTY GRAPH pg3
VERTEX TABLES (
    School  LABEL School IN School_kind (Hogeschool, University)
    )
EDGE TABLES (
    Students    SOURCE KEY ( src ) REFERENCES School ( id )
            DESTINATION KEY ( dst ) REFERENCES Student ( id )
            PROPERTIES ( createDate ) LABEL Knows
    )

auto &table = catalog.GetEntry<TableCatalogEntry>(context, info->schema, edge_table->table_name); leads to many recursive table function calls, eventually leading to a conversion error.

What happens?

The following query does not work:

import pandas as pd
import duckdb
df = pd.DataFrame([1,2,3,4,5])
df2 = pd.DataFrame([[0,1], [1,2], [2,3]])
con = duckdb.connect('')
con.execute('load sqlpgq')
con.execute("""CREATE PROPERTY GRAPH pg VERTEX TABLES ( df LABEL person ) EDGE TABLES ( df2 SOURCE KEY (i) REFERENCES df (j) DESTINATION KEY (i) REFERENCES df (j) LABEL knows);""")

We could add a feature that allows the creation of property graphs from a TableFunction, but we need to add support for the table replacement scan

To Reproduce

See above

OS:

macOs 13 - Apple M1 Pro

DuckDB Version:

latest

DuckDB Client:

python

Full Name:

Daniel ten Wolde

Affiliation:

CWI

Have you tried this on the latest master branch?

• I agree

Have you tried the steps to reproduce? Do they include all relevant data and configuration? Does the issue you report still appear there?

• I agree

Currently the SELECT * is optional for DuckDB's parser. I think it would be also good to make the COLUMNS clause optional. Such that the following queries are equivalent:

SELECT a.id, b.id
FROM GRAPH_TABLE(snb MATCH (a:Person)-[k:knows]->(b:Person))

FROM GRAPH_TABLE(snb MATCH (a:Person)-[k:knows]->(b:Person) COLUMNS(a.id, b.id))

See section 7.1 <table_reference> point a of the SQL/PGQ specifications

This could tie in with making the variable name at the end of the GRAPH_TABLE clause optional (would need to be another issue)

CREATE PROPERTY GRAPH MovieRentals
 VERTEX TABLES (
 Customer, Movie
 )
 EDGE TABLES (
 CustSales SOURCE Customer DESTINATION Movie
 ); 

Would reuse the already existing primary and foreign key constraint that already exist when originally creating the tables

When we want to attach just a weight array to an already an existing array, there should perhaps be a new UDF to attach just a new array for the weights. Currently you would have to recreate the entire CSR

This would be effectively the same as create, but instead of throwing an error when the property graph already exists, it would drop the previous property graph and replace it with the new one

After CSR creation, run connected component analysis. An optimization would be to look at whether the source and destination are in the same connected component (store this in the CSR class). If they are not, you don't need to run the search since there will be no path found.

Similar to cheapest path, template the number of lanes such that the minimal required number of lanes is used depending on the number of source-destination pairs

Should the following query be accepted?

CREATE PROPERTY GRAPH pg
VERTEX TABLES (
    Student PROPERTIES ( * ) LABEL Person,
    School as school_alias  PROPERTIES ( * ) LABEL School IN School_kind (Hogeschool, University)
    )
EDGE TABLES (
    know    SOURCE KEY ( src ) REFERENCES Student ( id )
            DESTINATION KEY ( dst ) REFERENCES Student ( id )
            PROPERTIES ( createDate ) LABEL Knows
    )

Queries starting with EXPLAIN are currently not supported. In the future we would like to support this, see sql/explain_duckpgq.test as an example.

Updating to 0.9.2 caused some tests which passed previously to fail.

• create_property_graph 954f99f

Query unexpectedly failed! (/Users/dljtw/git/duckpgq/test/sql/create_pg/create_property_graph.test:65)!
================================================================================
-CREATE PROPERTY GRAPH pg2
VERTEX TABLES (
    Student as Student_alias PROPERTIES ( id as id_alias, name ) LABEL Person
    )
EDGE TABLES (
    know    SOURCE KEY ( src ) REFERENCES Student_alias ( id )
            DESTINATION KEY ( dst ) REFERENCES Student ( id )
            PROPERTIES ( createDate ) LABEL Knows
    );
================================================================================
Binder Error: Referenced vertex table Student_alias does not exist.

• explain_duckpgq

Query unexpectedly failed! (/Users/dljtw/git/duckpgq/test/sql/explain_duckpgq.test:10)!
================================================================================
-EXPLAIN FROM GRAPH_TABLE (snb
    MATCH (a:Person WHERE a.id = 17592186044461)-[k:knows]-(b:Person)<-[au:hasAuthor]-(m:message WHERE m.creationDate < '2010-10-16')
    COLUMNS (a.id, a.firstName, a.lastName, m.id as messageId, coalesce(m.imageFile, m.content), m.creationDate)
    ) tmp
    ORDER BY creationDate DESC, Messageid ASC
    LIMIT 20;
================================================================================
Binder Error: Unknown DuckPGQ query encountered

• complex_matching #62

Query unexpectedly failed (/Users/dljtw/git/duckpgq/test/sql/path-finding/complex_matching.test:52)
================================================================================
-FROM GRAPH_TABLE (snb
    MATCH o = ANY SHORTEST (p:Person)-[w:knows]-> {1,3}(p2:Person)-[i:hasInterest]->(t:Tag)
    COLUMNS (p.id as p_id, p2.id as p2_id, t.id)
    ) tmp
    limit 10;
================================================================================
Actual result:
Binder Error: Referenced table "t" not found!
Candidate tables: "o"

• shortest path

Wrong result in query! (/Users/dljtw/git/duckpgq/test/sql/path-finding/shortest_path.test:57)!
================================================================================
-FROM GRAPH_TABLE (pg
    MATCH
    p = ANY SHORTEST (a:Person)-[k:knows]->{1,3}(b:Person)
    COLUMNS (path_length(p), p, a.name as name, b.name as b_name)
    ) study;
================================================================================
Mismatch on row 1, column 1
2 <> 1

• snb

Wrong result in query! (/Users/dljtw/git/duckpgq/test/sql/snb/snb.test:158)!
================================================================================
-FROM GRAPH_TABLE (snb
    MATCH (replyAuthor:person)<-[au2:hasAuthor]-(c:message where c.ParentMessageId is not null)-[r:replyOf]->(m:message where m.id = 618475290624)-[au:hasAuthor]->(messageAuthor:person),
    (replyAuthor:person)-[k:knows]-(messageAuthor:person)
    COLUMNS (c.id,c.content,c.creationDate, replyAuthor.id, replyAuthor.firstName, replyAuthor.lastName)
    ) tmp;
================================================================================
Mismatch on row 1, column 1
962072674305 <> 962072674306

• basic_match

Wrong result in query! (/Users/dljtw/git/duckpgq/test/sql/pattern-matching/basic_match.test:160)!
================================================================================
-SELECT study.a_name, count(study.b_name)
FROM GRAPH_TABLE (pg
    MATCH
    (a:Person)-[k:Knows]->(b:Person)
    COLUMNS (a.name as a_name, b.name as b_name)
    ) study
    GROUP BY study.a_name
    ORDER BY count(study.b_name) DESC;
================================================================================
Mismatch on row 3, column 1
Gabor <> Peter

- [ ] duckpgq

Query unexpectedly failed (/Users/dljtw/git/duckpgq/test/sql/duckpgq.test:20)
================================================================================
SELECT duckpgq_openssl_version('Michael');
================================================================================
Actual result:
Binder Error: Registered state not found

The following query from a python environment crashes due to the leading spaces not being truncated:
make python_release

import duckdb

def main()
  con = duckdb.connect()
  con.execute(f"""

  -CREATE PROPERTY GRAPH snb VERTEX TABLES (person LABEL person) EDGE TABLES (person_knows_person SOURCE KEY 
  (personid) REFERENCES person (personid) DESTINATION KEY (friendid) REFERENCES person (personid) LABEL knows) 
  """)
if __name__ == "__main__": 
  main()

For the various algorithms, experiment with the number of lanes to use
8, 16, 32, 64, 128, 256, 512, 1024, 2048

• Shortest path
• Bidirectional path length
• Shortest path length
• Cheapest path length

• cwida/duckdb-pgq#7
• Move to a different file
• Base on the new iterative length code
• Verify with Neo4j
• Make output list of altering vertex id, edge id

The query following fails due to the edge table reference a non-existing vertex table. This is correct, however DuckDB then triggers an internal query: "SELECT database_oid AS seq, database_name AS name, path AS file FROM duckdb_databases() WHERE NOT internal ORDER BY 1". This includes the word path which has become a reserved keyword. Related to cwida/duckdb-pgq#86

-CREATE PROPERTY GRAPH pg3
VERTEX TABLES (
    School  LABEL School IN School_kind (Hogeschool, University)
    )
EDGE TABLES (
    Students    SOURCE KEY ( src ) REFERENCES School ( id )
            DESTINATION KEY ( dst ) REFERENCES Student ( id )
            PROPERTIES ( createDate ) LABEL Knows
    )

See title

SQL/PGQ allows for every column mentioned in the PROPERTIES (list of columns) to have an alias. This is currently not supported

Adding support for this requires that the PropertyGraphTable->column_names will be slightly different.

For a given case Student PROPERTIES (id AS id_alias), the column id should exist in the table Student

This should be used when a weight is defined inside the edge

(a:Person)-[k:Knows COST <some expression>]->*(b:Person)

SQL/PGQ marked cost as a language opportunity
(a:Person)-[k:Knows COST b_expr DefaultOptional)]->(b:Person)
This will be part of a subpath

If given the query (a)-[b where b.val > 100]->*(c)
A way to handle the filter would be to create a csr only on the filtered edges. Have to check if the standard even allows such a thing. Supporting horizontal aggregation 'sum(b.val)' seems tricky though.

Allow one of the columns in the COLUMNS() list to be ELEMENT_ID(), this will return the rowid for that vertex or edge. So it will probably have to be a.element_id() for instance(?)

In this case we have a table student, having the alias student_alias. The alias should then be able to be used in the source and destination key definition.

-CREATE PROPERTY GRAPH pg2
VERTEX TABLES (
    Student as Student_alias PROPERTIES ( id as id_alias, name ) LABEL Person
    )
EDGE TABLES (
    know    SOURCE KEY ( src ) REFERENCES Student_alias ( id )
            DESTINATION KEY ( dst ) REFERENCES Student ( id )
            PROPERTIES ( createDate ) LABEL Knows
    )

Current behaviour:
Binder Error: Referenced vertex table Student_alias does not exist.

Expected behaviour:
No error

Check if the method CheckEdgeTableConstraints should also be called on the any edge type

The following query fails with the following error:
INTERNAL Error: Duplicate table index "1" found

Test from basic_match.test

query II
-SELECT study.a_name, study.b_name
FROM GRAPH_TABLE (pg
    MATCH
    (a:Person)-[k:Knows]-(b:Person)
    WHERE a.name = 'Peter'
    COLUMNS (a.name as a_name, b.name as b_name)
    ) study
    ORDER BY a_name, b_name;
----
Peter	Daniel
Peter	David
Peter	Gabor
Peter	Tavneet

Asked for clarification in Discord https://discord.com/channels/909674491309850675/921100573732909107/1182348485442404503

Following query reproduces the same results but does not run into this issue:

query II
select study.a_name, study.b_name from
    (SELECT DISTINCT a."name" AS a_name, b."name" AS b_name
        FROM know AS k , Student AS b , Student AS a
        WHERE ((((a.id = k.src) AND (b.id = k.dst)) OR ((a.id = k.dst) AND (b.id = k.src)))
        AND (a."name" = 'Peter')))
    AS study
    ORDER BY a_name, b_name;
----
Peter	Daniel
Peter	David
Peter	Gabor
Peter	Tavneet

Disabling the optimizer rule: OptimizerType::COMPRESSED_MATERIALIZATION stops the error from arising

Some large query plans get chopped off with the default text mode. I think it would be possible to add a new mode to profiling output, can call it graph. Where the operators are nodes, and the edges go to their children. This way you could also combine it and create a visual graph building tool to further inspect the query plan.

See graphs here https://github.com/neo4j/neo4j/blob/5.1/community/community-it/algo-it/src/test/java/org/neo4j/kernel/impl/traversal/TestBidirectionalTraversal.java
(Also use the nice ascii art to avoid having to draw the graph a million times)

The query for path-finding should be something like:

WITH cte1 AS (
    SELECT  CREATE_CSR_EDGE(
            0,
            (SELECT count(a.id) FROM person a),
            CAST (
                (SELECT sum(CREATE_CSR_VERTEX(
                            0,
                            (SELECT count(a.id) FROM person a),
                            sub.dense_id,
                            sub.cnt)
                            )
                FROM (
                    SELECT a.rowid as dense_id, count(k.person1id) as cnt
                    FROM person a
                    LEFT JOIN person_knows_person k ON k.person1id = a.id
                    GROUP BY a.rowid) sub
                )
            AS BIGINT),
            a.rowid,
            c.rowid,
            k.rowid) as temp
    FROM person_knows_person k
    JOIN person a on a.id = k.person1id
    JOIN person c on c.id = k.person2id
)
SELECT distinct a.name AS a_name, b.name AS b_name,
FROM (SELECT count(temp) * 0 AS temp FROM cte1) x, (SELECT a.id, a.rowid FROM person a WHERE a.id = 332) a, person b
    where (x.temp + iterativelength(0, (SELECT count(c.id) FROM person c), a.rowid, b.rowid)) NOT NULL

Unsure how this should be handled. When updating a table that has been registered within a property graph, the following query won't work anymore, since the primary (or foreign key) which was used during registration no longer matches with the actual column value. Perhaps this is the way to handle it

# Data
CREATE TABLE Student(id BIGINT, name VARCHAR);
CREATE TABLE know(src BIGINT, dst BIGINT, createDate BIGINT);
CREATE TABLE School(name VARCHAR, Id BIGINT, Kind VARCHAR);
CREATE TABLE StudyAt(personId BIGINT, schoolId BIGINT);

INSERT INTO Student VALUES (0, 'Daniel'), (1, 'Tavneet'), (2, 'Gabor'), (3, 'Peter'), (4, 'David');
INSERT INTO know VALUES (0,1, 10), (0,2, 11), (0,3, 12), (3,0, 13), (1,2, 14), (1,3, 15), (2,3, 16), (4,3, 17);
INSERT INTO School VALUES ('VU', 0, 'University'), ('UVA', 1, 'University');
INSERT INTO StudyAt VALUES (0, 0), (1, 0), (2, 1), (3, 1), (4, 1);

-CREATE PROPERTY GRAPH pg
VERTEX TABLES (
    Student PROPERTIES ( id, name ) LABEL Person,
    School LABEL SCHOOL
    )
EDGE TABLES (
    know    SOURCE KEY ( src ) REFERENCES Student ( id )
            DESTINATION KEY ( dst ) REFERENCES Student ( id )
            LABEL Knows,
    studyAt SOURCE KEY ( personId ) REFERENCES Student ( id )
            DESTINATION KEY ( SchoolId ) REFERENCES School ( id )
            LABEL StudyAt
    );

ALTER TABLE student RENAME id TO jd;

-FROM GRAPH_TABLE (pg
    MATCH
    (a:Person)-[s:StudyAt]->(b:School)
    WHERE a.name = 'Daniel'
    COLUMNS (a.jd)
    ) study;

Binder Error: Table "a" does not have a column named "id"

Views provide a similar error:

create view v1 as select id from student; 
select * from v1; 
alter table student rename id to jd;
select * from v1; 
Error: Binder Error: Referenced column "id" not found in FROM clause!
Candidate bindings: "student.jd" 

We should write what the extension does, how the new syntax looks like, etc.
Perhaps also a logo

The following query is not allowed:

-FROM GRAPH_TABLE (snb
    MATCH (a:Person WHERE a.id = 17592186044461)-[k:knows]-> *(b:Person where b.id = 35184372088856)
    COLUMNS (a.id as a_id, b.id as b_id)
    ) tmp LIMIT 20

This query should be interpreted as an ALL path query, which would lead to infinite results if you follow the standard. A path prefix like ANY or ANY-k or a path mode such as TRAIL, ACYCLIC, or SIMPLE should be used to avoid infinite results.

In the current implementation, this is allowed. It could perhaps be detected in the transformer that we have an unbounded path query with an implied ALL path prefix and then an error should be thrown that ALL path is not implemented

Instead of throwing an error when a property graph doesn't exist, we could just ignore it and continue

Right now the translated query contains a LIMIT between lower and upper. However this is only enforced after the path-finding UDFs are finished. It would potentially save time if the limits are enforced in the UDF, to ensure the minimum required iterations. However, the added complexity might slow down the UDFs too much. To be investigated

Would require changes to the matchref_bind.cpp and the path-finding UDFs

The following query results in a seg fault:

-FROM GRAPH_TABLE (pg
    MATCH
    p = ANY SHORTEST 5 WALK (a:Person)-[k:knows]-> *(b:Person)
    WHERE a.name = 'Daniel'
    COLUMNS (p, a.name as name, b.name as school)
    ) study;

Should for now give a 'Not implemented Error: TopK has not been implemented yet.'

Seems to go wrong here: PGSubPath *p = (PGSubPath *) lfirst(list_head(l)); (https://github.com/cwida/duckdb-pgq/blob/fd44771959318ba55f4c19bfb6a9fe64e5434a73/third_party/libpg_query/grammar/statements/pgq.y#L402C2-L402C2)

This query will return a list of rowids alternating between the vertex rowid and the edge rowid between a source and destination
We will only support (ANY) SHORTEST path for now, there is also opportunity for ALL

The keyword DEFAULT LABEL is currently not supported.
Additionally, the list following LABEL discriminator (labelList) can currently contain duplicate labels. This should not be allowed since all labels should be unique.

What should be the result (or equivalent query of) the following query:

FROM GRAPH_TABLE (pg
MATCH SHORTEST 5 (a:Person)-[k:Knows]->*(b:Person), (b:Person)-[k2:Knows]->(c:Person)
COLUMNS (*)

SELECT * 
FROM pg
	(SELECT * 
	FROM person a, knows k, person b, knows k2, person c
	WHERE ...
	LIMIT 5
	)

I'm afraid that the LIMIT 5 will come too early and perhaps select the first 5 results of the entire join, while those might not be the 5 shortest who are then joined on the (c:Person)

Should throw a catalog/Binder exception

• #103
• Column of a table does not exist
• FK of a table does not exist
• Primary keys are not unique
• PK of referenced source table does not exist
• PK of referenced destination table does not exist
• FK of source of edge table does not exist
• Multiple PKs are referenced from source/destination table (How would this work?)
• Ensure everything is case insensitive

This issue gathers some syntax ideas to alter an existing property graph.

This is specified in the SQL/PGQ standard: 11.20 <alter property graph statement>
Please double-check that the proposed queries here adhere to the standard before implementing this.

ALTER PROPERTY GRAPH <property_graph> ADD VERTEX TABLES (CUSTOMER) 

ALTER PROPERTY GRAPH <property_graph> ADD EDGE TABLES (KNOWS, STUDIES_AT)

ALTER PROPERTY GRAPH <property_graph> ADD VERTEX TABLES (CUSTOMER) EDGE TABLES (KNOWS, STUDIES_AT)

ALTER PROPERTY GRAPH <property_graph> DROP VERTEX TABLES (CUSTOMER)

ALTER PROPERTY GRAPH <property_graph> <table_name (or label?)> ADD PROPERTIES (name)

ALTER PROPERTY GRAPH <property_graph> <table_name (or label?)> DROP PROPERTIES (name)

ALTER PROPERTY GRAPH <property_graph> <table_name (or label?)> RENAME LABEL <new_label>

Currently it is not possible to use both a basic pattern as well as a path-finding operation in the queries. We should be able to connect them (this will likely be one of the last things before we can formulate all SNB BI and interactive queries)

FROM GRAPH_TABLE (pg
MATCH (a:Person)-[k:Knows]->*(b:Person)-[s:StudyAt]->(u:University)
COLUMNS (*)

Do many terminate early and wait for a lower number of lanes to finish?

What happens?

see title

To Reproduce

FROM GRAPH_TABLE (pg
    MATCH
    ANY SHORTEST (a:Person)-[k:knows]->{0,0}(b:Person)
    WHERE a.name = 'Daniel'
    COLUMNS (a.name as name, b.name as school)
    ) study;

OS:

macOs 13 - Apple M1 Pro

DuckDB Version:

dev

DuckDB Client:

CLI

Full Name:

Daniel ten Wolde

Affiliation:

CWI

Have you tried this on the latest master branch?

• I agree

Have you tried the steps to reproduce? Do they include all relevant data and configuration? Does the issue you report still appear there?

• I agree

What happens?

see title

To Reproduce

Set pragma enable_verification and create a CSR

OS:

macOs 13 - Apple M1 Pro

DuckDB Version:

latest

DuckDB Client:

CLI

Full Name:

Daniel ten Wolde

Affiliation:

CWI

Have you tried this on the latest master branch?

• I agree

Have you tried the steps to reproduce? Do they include all relevant data and configuration? Does the issue you report still appear there?

• I agree

On MacOS, the BinderException is not being caught properly in planner.cpp, leading to an InvalidError exception thrown. On MacOS it leads to the std::exception case, while on Linux it goes to catch (const Exception &ex). Possibly related to duckdb/duckdb#6521

There are currently some test cases in test/sql/function/sql-pgq that are outdated and should be updated. This issue should go through these test cases and make sure to update them

Related to #30

Once a lane is finished it currently sits idle until all lanes have been completed. It could be an improvement to reuse lanes as soon as they are finished
Need to keep track of which iteration every lane is in. Can be done using a std::vector<int16_t> iteration(LANE_LIMIT, 0); that increments every iteration. Once a destination has been found, the iteration for that lane is reset to 0 and is refilled with the next source-destination pair.

-EXPLAIN SELECT study.name, study.school
FROM GRAPH_TABLE (pg
     MATCH
     (a:Person)-[s:StudyAt]->(b:School)
     WHERE a.name = 'Daniel'
     COLUMNS (a.name as name, b.name as school)
     ) study;

The following query leads to a segfault