Pith. sign in

REVIEW 4 major objections 5 minor 24 references

Towards Cross-Model Efficiency in SQL/PGQ

T0 review · 4 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Pith's one-line read SQL and SQL/PGQ are not yet "fully decoupled": query latency still depends on how the query is expressed.

desk verdict The paper's central comparison is undermined by SQL rewrites that don't match the PGQ queries, so the numbers don't support the headline claim, but the research direction is worth watching. read the letter →

arxiv 2505.07595 v1 pith:H75CBLPO submitted 2025-05-12 cs.DB

classification cs.DB
keywords SQL/PGQpropertygraphsqueryoptimizationcross-modelefficiencyGQLgraphpatternmatchingperformanceevaluationrewriting
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that the SQL/PGQ standard's promise of free switching between relational and graph querying is not yet met, because measured latency depends on which formalism the user chooses. The authors run six query pairs — bounded friend-triangle patterns and unbounded transfer cycles — written in both plain SQL and SQL/PGQ across DuckDB, Google Cloud Spanner, and Neo4j. They find that DuckDB often runs SQL/PGQ faster than the equivalent SQL, while Spanner runs SQL faster than SQL/PGQ, and Neo4j shows mixed results. From these gaps they conclude that current systems optimize each formalism separately, and that a holistic optimizer choosing the best internal algorithm regardless of syntax would shrink the gap. A sympathetic reader would care because the commercial value of SQL/PGQ depends on the user's choice of formalism being a matter of clarity, not performance.

What carries the argument

The central mechanism is the paired SQL/SQL/PGQ rewriting of six queries, split into bounded patterns that reduce to ordinary joins and unbounded patterns that need recursive SQL or graph traversal. Running both versions on the same engine and taking the ratio of SQL latency to SQL/PGQ latency isolates the effect of formalism on each system's optimizer. The bounded/unbounded split matters because it distinguishes cases where relational join techniques should suffice from cases where graph-specific algorithms like multi-source BFS and Bellman-Ford are needed, which lets the paper pinpoint where each engine's optimization effort actually goes.

What would settle it

Re-run the six queries on a single controlled machine with the same dataset sizes plus larger ones (thousands to millions of rows), repeating each measurement several times. If DuckDB no longer favors SQL/PGQ, Spanner no longer favors SQL, or the gaps shrink below the noise level, the conclusion that the models are not yet decoupled loses its experimental support.

Watch

Extended reading notes

Core claim

The paper's central claim is that performance is often tied to how a query is expressed, so the SQL and SQL/PGQ execution paths are not yet fully decoupled. Evidence comes from a small benchmark where the same logical queries are encoded twice, once in SQL and once in SQL/PGQ, and run on DuckDB and Spanner, with Neo4j covering only the graph side. Results show the advantage flips by system: DuckDB's SQL/PGQ executions are generally faster than its SQL ones, including on unbounded traversals, while Spanner's SQL executions beat its SQL/PGQ ones on bounded patterns, which are the only ones Spanner supports. The paper argues that these differences are signs of separate optimizations for each formalism, and that systems should instead translate internally between the two models so the user's choice of language does not dictate performance.

Load-bearing premise

The load-bearing premise is that the measured latencies capture real engine behavior, even though each query ran once, on only 50–150 synthetic rows, and on environments that mix a local PC with cloud machines of unknown hardware.

Editorial extensions

If this is right

  • If the decoupling claim is right, engines should automatically rewrite SQL/PGQ patterns into joins when the pattern is bounded and relational plans are cheaper.
  • Unbounded Kleene-star queries should be executed with graph traversal algorithms (CSR-based BFS, shortest path) rather than recursive SQL where the engine supports them, because DuckDB's SQL/PGQ shows the speedup such structures can provide.
  • Systems like Spanner that only optimize the SQL path will need native pattern-matching acceleration before they can honor SQL/PGQ's promise.
  • Internal rewriting must be partial: since recursive SQL is strictly more expressive than SQL/PGQ, the optimizer can always rewrite patterns into SQL but can only sometimes rewrite SQL into patterns.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One extension not tested in the paper: if the same paired queries are run on an engine that compiles both formalisms to a common intermediate representation, the SQL/SQL/PGQ latency ratio should approach 1, a direct way to confirm the decoupling diagnosis.
  • The paper's graph-creation numbers suggest that virtual graph views (compiled to relational plans) are viable in DuckDB but costly in Spanner and Neo4j; a system designer might therefore choose to keep views virtual only when the compilation path is present, and materialize them elsewhere.
  • If the observed gaps persist with larger datasets and repeated trials, cloud providers would face both an optimization opportunity and a standards-compliance risk, since SQL/PGQ adoption depends on the formalism not being a performance liability.
  • The one-run-per-cell methodology implies the true effect sizes are likely smaller than the reported ratios, so any future fix should be validated statistically, not with single latency samples.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper studies the SQL/PGQ standard, which lets users query property graphs through either SQL-style joins or graph-pattern matching. It reports an experimental comparison of six queries (three bounded friend-triangle-style patterns and three unbounded transfer-cycle patterns) on synthetic datasets of 50, 100, and 150 rows, using DuckDB with DuckPGQ, Google Cloud Spanner, and Neo4j. The main empirical claim, stated in the abstract and Section 4, is that performance is often tied to how a query is expressed, which suggests that current systems are not yet fully decoupling SQL and SQL/PGQ optimization. The paper also proposes two future directions: applying and combining relational and graph algorithms, and internal query rewriting between the two formalisms. The authors acknowledge their results should be read qualitatively because of heterogeneous execution environments.

Significance. If the central claim were established, the paper would provide a useful data point for the SQL/PGQ and GQL community: it would indicate that users cannot currently choose between SQL and graph patterns based purely on convenience without performance consequences, and it would motivate holistic, cross-formalism optimizers. The paper is honest about several limitations and makes its experimental scripts available, which is commendable. However, the empirical evidence as presented does not support the central claim, because the SQL rewrites in Section 3 are not faithful translations of the SQL/PGQ queries, and because the experimental protocol (single unreplicated runs, tiny synthetic datasets, uncontrolled cloud environments) is too weak to separate query-formalism effects from noise. The paper also contains an internal inconsistency between Table 1 and Table 4 for DuckDB Q5 at size 150. With corrected query translations and a more rigorous experimental design, the underlying question is worth investigating.

major comments (4)
  1. [Section 3, Query 1] The SQL rewrite of Query 1 is not equivalent to the PGQ triangle query. The PGQ query matches a directed triangle (x->y, y->z, z->x) and returns (x.name, y.name, z.name). The SQL version returns only distinct pairs (f.pid1, f.pid2) that have a common friend through FriendPairs, and it does not require the closing edge z->x or return the third vertex. The two queries therefore compute different results, and the latency ratio in Table 1 for Q1 measures different workloads rather than the effect of SQL versus SQL/PGQ expression. This undermines the bounded-query comparison.
  2. [Section 3, Query 2 vs. Query 3] Query 3 is not a faithful translation of Query 2. Query 2 uses ANY SHORTEST to find a shortest directed cycle matching the transfer pattern, whereas Query 3 recursively enumerates all directed walks up to depth 2000 and returns every account that appears in a cycle of length at least 2. These are different computations: Query 3 can return cycles that are not shortest, and the depth limit of 2000 is an ad hoc free parameter that is not shown to approximate ANY SHORTEST on the experimental datasets. Consequently, the unbounded-query ratio comparisons in Table 1 and the associated figures do not isolate the query formalism.
  3. [Tables 1 and 4] There is an internal inconsistency in the reported DuckDB results. Table 1 reports the DuckDB Q5 ratio at dataset size 150 as 250.00, but Table 4 gives SQL latency 12,420 ms and SQL/PGQ latency 55.5 ms, whose ratio is approximately 223.8, not 250. Smaller discrepancies also appear for other cells (e.g., Q2 at size 100 and Q4 at size 150). Since Table 1 is the main quantitative evidence for the paper's central claim, these discrepancies need to be resolved and the tables audited.
  4. [Section 4, Experimental Setting] The experimental protocol is too weak to support the paper's qualitative conclusions. Each query appears to have been run once per cell, on datasets of only 50, 100, and 150 rows, and the cloud-based runs for Spanner and Neo4j were executed on hardware and configurations outside the authors' control, as the paper itself acknowledges. With no repetitions, no confidence intervals, and no statistical test, the latency differences in Figures 1 and 2 and Table 1 are indistinguishable from environment noise. This is particularly important because the entire central claim rests on these measurements.
minor comments (5)
  1. [Section 3] Query 3's title contains a typo ('Recusive'), and the identifiers 'accoun_in_cycl e' and 'accou nt_in_cy cle' are broken by spaces. Please fix these formatting errors.
  2. [Section 4] The query definitions in the appendix and the paper would benefit from a precise statement of the six queries Q1-Q6; currently the reader must infer which figure corresponds to which query and how the bounded and unbounded variants relate. In particular, Query 2's 'RETURN ;' and the undefined variables px and pz in its WHERE clause should be corrected or explained.
  3. [Table 4] The entry '36.3m' for SQL Q5 at size 100 appears to be a typo; it should likely be '36.3', and the units should be stated consistently.
  4. [Section 1] There is a typo in the Introduction: 'feasable translations' should be 'feasible translations'.
  5. [Section 5] The statements about the expressiveness asymmetry between recursive SQL and SQL/PGQ rely on references [3] and [6], which are the authors' own prior work. A brief independent explanation of the separating query class would help readers assess this claim without consulting the cited papers.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the experimental comparison is self-contained and the cited theoretical results are independent of the measured latency claims.

full rationale

The paper's central claim, that SQL and SQL/PGQ queries exhibit performance gaps that depend on the execution engine, is supported by direct experiments comparing externally specified queries on synthetic datasets. There are no fitted parameters that are later renamed as predictions, and no quantity is defined in terms of the outcome it is supposed to explain. The latency ratios in Table 1 are computed from raw measurements and do not reduce by construction to any input assumption. The self-citations to [3] and [6] are used only for theoretical expressiveness statements (e.g., that core SQL/PGQ translates to first-order logic with transitive closure, and that SQL/PGQ cannot express certain linear recursive queries); these are not the source of the experimental numbers, and they are not invoked to forbid alternative interpretations of the benchmark data. The paper also explicitly acknowledges that its cross-system comparisons are qualitative because of heterogeneous cloud environments, which is a limitation rather than a circular step. Concerns about whether the SQL rewrites in Section 3 are faithfully equivalent to the PGQ queries (e.g., Query 1 returning only two endpoints versus the triangle's three vertices, and Query 3 approximating ANY SHORTEST with a depth bound) are validity and correctness issues, not circularity: the comparison could be wrong without being circular. Since no derivation step is equivalent to its own input by construction, the appropriate score is 0.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central claim depends on the SQL/PGQ standard semantics and prior expressiveness results, plus the hand-chosen recursion depth bound in the SQL translation. No new theoretical entities or fitted parameters appear; the only hand-set value is the recursion limit 2000.

free parameters (1)
  • Recursion depth limit = 2000
    Query 3 caps recursive SQL paths at depth 2000 to approximate the ANY SHORTEST cycle semantics of Query 2; this bound is chosen by hand and not justified for arbitrary graphs, so it is an ad hoc constant in the translation.
assumptions (5)
  • domain assumption Property graphs are modeled as tuples (N, E, lab, src, tgt, prop) per [6].
    Appendix A.1 defines the graph model used by all queries; this is standard in the SQL/PGQ literature.
  • domain assumption SQL/PGQ pattern-matching semantics follow the formalizations in [4,5] (GPC and GQL digest).
    Section 2 relies on these references for syntax and semantics of GRAPH_TABLE and Kleene-star patterns.
  • standard math Core SQL/PGQ can be translated to first-order logic with transitive closure, and recursive SQL is strictly more expressive, per [3,6].
    Section 3 uses this to argue translations from SQL/PGQ to (recursive) SQL exist and the reverse does not.
  • ad hoc to paper The depth-limited recursive SQL in Query 3 faithfully approximates ANY SHORTEST for the experimental datasets.
    Section 3 states the bound 'mirroring the termination condition of ANY SHORTEST' but offers no proof of semantic equivalence.
  • domain assumption Uniformly random Mockaroo data of 50 to 150 rows is a meaningful testbed for query engine behavior.
    Section 4 describes dataset generation; the representativeness of this narrow, synthetic regime is assumed when drawing conclusions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Towards Cross-Model Efficiency in SQL/PGQ." pith.science (2026). https://pith.science/paper/H75CBLPO

@misc{pith2026250507595,
  author       = {Pith},
  title        = {Pith review of: Towards Cross-Model Efficiency in SQL/PGQ},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/H75CBLPO}},
  note         = {Machine review of arXiv:2505.07595}
}
read the original abstract

SQL/PGQ is a new standard that integrates graph querying into relational systems, allowing users to freely switch between graph patterns and SQL. Our experiments show performance gaps between these models, as queries written in both formalisms can exhibit varying performance depending on the formalism used, suggesting that current approaches handle each query type separately, applying distinct optimizations to each formalism. We argue that a holistic optimization is necessary, where the system internally decides on the best algorithms regardless of whether queries are written in SQL or as graph patterns. We propose possible future research direction to unify these optimizations and mitigate performance gaps.

Figures

Figures reproduced from arXiv: 2505.07595 by the authors.

Figure 1
Figure 1. Execution time (ms) as a function of dataset size [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 3
Figure 3. Relational tables dataset with account, own, person, friends, and transfer. [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Comparison of execution time (ms) as a function of dataset size (#rows) for SQL/PGQ queries for DuckDB (1-3 bounded [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figures from the paper (3 more)
Figure 5
Figure 5. Figure 5: Comparison of execution time (ms) as a function of dataset size (#rows) for SQL/PGQ queries for DuckDB (4-6 [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 6
Figure 6. Figure 6: Comparison of graph creation times (ms) as a function of dataset size (# rows) [PITH_FULL_IMAGE:figures/full_fig_p009_6.png]
Figure 7
Figure 7. Figure 7: Comparison of execution time (ms) as a function of dataset size (#rows) for Cypher queries for Neo4j (1-3 bounded [PITH_FULL_IMAGE:figures/full_fig_p009_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 16 canonical work pages

  1. [1]

    Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan Reutter, and Domagoj Vrgoč. 2017. Foundations of Modern Query Languages for Graph Databases. ACM Comput. Surv. 50, 5, Article 68 (Sep 2017). 40 pages

  2. [2]

    Fei Bi, Lijun Chang, Xuemin Lin, Lu Qin, and Wenjie Zhang. 2016. Efficient Subgraph Matching by Postponing Cartesian Products. In Proceedings of the 2016 International Conference on Management of Data . 1199–1214

  3. [3]

    Lin, and Liat Peterfreund

    Diego Figueira, Anthony W. Lin, and Liat Peterfreund. 2024. Relational Perspec- tive on Graph Query Languages. arXiv:2407.06766 [cs.DB] https://arxiv.org/abs/ 2407.06766

  4. [4]

    Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoc. 2023. GPC: A Pattern Calculus for Property Graphs. In Pro- ceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2023, Seattle, W A, USA, June 18-23,...

  5. [5]

    Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoc. 2023. A Researcher’s Digest of GQL. In 26th International Conference on Database Theory, ICDT 2023, March 28-31, 2023, Ioannina, Greece (LIPIcs, Vol. 255), Floris Geerts and Brecht Vandevoor...

  6. [6]

    Amélie Gheerbrant, Leonid Libkin, Liat Peterfreund, and Alexandra Rogova

  7. [7]

    Google. n.d.. Google Cloud Spanner Implementation. https://cloud.google.com/ spanner/docs/reference/standard-sql/graph-intro

  8. [8]

    GQL Standards Committee. 2025. GQL Standards. https://www.gqlstandards.org/

Show all 24 references
  1. [9]

    Wook-Shin Han, Jinsoo Lee, and Jeong-Hoon Lee. 2013. Turboiso: Towards Ultrafast and Robust Subgraph Isomorphism Search in Large Graph Databases. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD ’13), Association for Computing Machin...

  2. [10]

    Toshihide Ibaraki and Tiko Kameda. 1984. On the optimal nesting order for computing N-relational joins. ACM Trans. Database Syst. 9, 3 (sep 1984), 482–502

  3. [11]

    Jan Kossmann, Thorsten Papenbrock, and Felix Naumann. 2022. Data de- pendencies for query optimization: a survey. VLDB J. 31, 1 (2022), 1–22. https://doi.org/10.1007/s00778-021-00676-3

  4. [12]

    Ravi Krishnamurthy, Haran Boral, and Carlo Zaniolo. 1986. Optimization of Nonrecursive Queries. In VLDB’86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings, Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, and Yahiko Kamba...

  5. [13]

    Yunkai Lou, Longbin Lai, Bingqing Lyu, Yufan Yang, Xiaoli Zhou, Wenyuan Yu, Ying Zhang, and Jingren Zhou. 2024. Towards a Converged Relational-Graph Optimization Framework. Proc. ACM on Management of Data (SIGMOD)

  6. [14]

    Mockaroo. n.d.. Mockaroo. https://www.mockaroo.com/

  7. [15]

    Neo4j. n.d.. Neo4j documentation. https://neo4j.com/docs/

  8. [16]

    Ngo, Ely Porat, Christopher Ré, and Atri Rudra

    Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. 2018. Worst-case Optimal Join Algorithms. J. ACM 65, 3 (2018), 16:1–16:40. https://doi.org/10.1145/3180143

  9. [17]

    Hung Q Ngo, Christopher Ré, and Atri Rudra. 2014. Skew strikes back: new developments in the theory of join algorithms. Acm Sigmod Record 42, 4 (2014), 5–16

  10. [18]

    openCypher. 2017. Cypher Query Language Reference, Version 9. https: //github.com/opencypher/openCypher/blob/master/docs/openCypher9.pdf

  11. [19]

    Hadar Rotschield. 2025. Towards Cross-Model Efficiency in SQL/PGQ: Exper- imental Query Scripts. Open source at https://github.com/hadarrot/Towards- Cross-Model-Efficiency-in-SQL-PGQ

  12. [20]

    Haichuan Shang, Ying Zhang, Xuemin Lin, and Jeffrey Xu Yu. 2008. Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism. Proc. VLDB Endow. 1, 1 (Aug 2008), 364–375. https://doi.org/10.14778/1453856. 1453899

  13. [21]

    Daniel ten Wolde, Gábor Szárnyas, and Peter A. Boncz. 2023. DuckPGQ: Bringing SQL/PGQ to DuckDB. Proc. VLDB Endow. 16, 12 (2023), 4034–4037. https://doi. org/10.14778/3611540.3611614

  14. [22]

    Julian R. Ullmann. 1976. An algorithm for subgraph isomorphism. Journal of the ACM (JACM) 23, 1 (1976), 31–42

  15. [23]

    Daniel ten Wolde, Gábor Szárnyas, and Peter Boncz. 2023. Duckpgq: Bringing sql/pgq´ to duckdb. Proceedings of the VLDB Endowment 16, 12 (2023), 4034–4037. GRADES-NDA ’25, June 22–27, 2025, Berlin, Germany Hadar Rotschield and Liat Peterfreund A APPENDIX A.1 Property Graph defi...

  16. [2024]

    CoRR abs/2409.01102 (2024)

    GQL and SQL/PGQ: Theoretical Models and Expressive Power. CoRR abs/2409.01102 (2024). Accepted for publication in VLDB 2025 (proceedings not yet online)

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.