Uplifting the Superpowers of Worst-Case-Optimal Join Algorithms

Uplifting the Superpowers of Worst-Case-Optimal Join Algorithms⋆ Adrián Gómez-Brandón1,3 , Aidan Hogan2,3 , and Gonzalo Navarro2,3 1

arXiv:2608.03840v1 [cs.DB] 4 Aug 2026

Universidade da Coruña, CITIC, Facultade de Informática, Spain 2 Deptartment of Computer Science, University of Chile, Chile 3 IMFD — Millennium Institute for Foundational Research on Data, Chile

Abstract. Worst-case-optimal (wco) join algorithms have demonstrated their power – in both theory and practice – to efficiently solve complex Basic Graph Patterns (BGPs). Modern graph query languages, such as SPARQL and GQL, have BGPs at their core, but also have a wide range of other features, including filters (aka. selections). Such conditions are typically handled via pre- or post-filtering, before or after processing the BGPs. In this paper we show how to uplift wco join algorithms so as to incorporate such filtering natively, improving efficiency. We demonstrate the superiority of this approach by extending the Ring – a compact index that provides wco resolution of BGPs within almost no extra space on top of the graph – so as to handle property graphs using our new techniques while retaining compactness. We implement this extension and experimentally show that it outperforms various baseline systems.

1

Introduction

There is an ever-growing demand for increasingly-efficient systems for querying knowledge graphs. In the context of open knowledge graphs, RDF and SPARQL dominate [32]. In the context of enterprise knowledge graphs, property graphs, query languages such as Cypher [23] and GQL [17], and commercial engines such as Neo4j [52], are a popular alternative. Despite these seemingly disparate graph models and query languages, the same key primitives – in particular, graph patterns [2] – underlie both RDF/SPARQL and property graph query engines. Techniques for querying one form of knowledge graph model can often be applied for the other, with various systems [12, 48, 51] natively supporting both. A promising recent line of research for efficiency evaluating graph queries is to combine compact data structures and worst-case optimal joins [6, 7, 13, 30, 4]. Such works have focused on evaluating BGPs over triple-based models such as RDF. We extend these works in two ways. First, we show how techniques originally proposed for RDF-like models – specifically the Ring [6] – can be adapted ⋆

Funded by ANID – Millennium Science Initiative Program – Code ICN17 002, and Fondecyt Grant 1260080, ANID, Chile. Adrián Gómez-Brandón is funded by MCIN/AEI/10.13039/501100011033 and EU/ERDF “A way of making Europe” PID2022-141027NB-C21 (EARTHDL). CITIC is funded by the Xunta de Galicia and co-financed by the EU through FEDER Galicia: grant ED431G 2023/01.

to the property graph model. Second, we further add support for selections, aka. filters, which are among the most widely-used query operators in practice: Bonifati et al. [14] find, for example, that 40% of SPARQL queries in real-world logs use FILTER, second only to SELECT. While filters can be evaluated over the results of a BGP, one of the most fundamental query optimizations is to “push down” filters, using them to eliminate intermediate results as soon as possible. We propose techniques to enable the push-down of filters by translating them into efficient operations directly over a custom compact data structure. Paper structure: Section 2 discusses related works on compact data structures and wco joins for graphs. Section 3 presents preliminaries. Section 4 introduces the core technical abstraction of “leaptors”: iterators enabling wco execution for graph queries with filters. Section 5 proposes the PG-Ring for the concrete setting of property graphs and GQL-like queries, describing the implementation of a static, in-memory database engine using leaptors. Section 6 presents experimental results for two benchmarks comparing PG-Ring with internal and external baselines. Section 7 wraps up our contributions and presents future work.

2

Related Work

In the context of efficiently evaluating graph patterns, recent years have seen two promising lines of research emerge. The first line of research refers to worst-case optimal (wco) joins [43], which provide – in the context of querying graphs – theoretical and practical guarantees on the maximum cost of enumerating all solutions for a basic graph pattern (BGP). Such algorithms have been shown empirically to provide notable speedups over traditional join algorithms, upholding their theoretical underpinnings for RDF/SPARQL [28, 13, 51] and similar triple-based graph models [36]. However, the benefits of wco joins in terms of time often come at the cost of space [28, 36, 51] as they often require storing additional index orders. The second line of research explores compressed data structures for indexing and querying graphs. In the RDF/SPARQL world, formats such as HDT [21], COTTAS [3], etc., propose compressed RDF file formats that can evaluate triple patterns, which can be used to build more complex query engines [47]. More recent works have combined both lines of research by investigating succinct data structures that support wco joins. These in-memory structures include the Ring (based on wavelet trees) [6], QDags (based on quadtrees) [7], Hypertries (based on bit tensors) [13], RDF-TDAA (based on Directly Addressable Arrays) [30], and RDFCSA (based on compressed suffix arrays) [4]. These works support wco queries while addressing their key limitation: space. However, to the best of our knowledge, no work has investigated succinct data structures that support wco joins and filters (beyond equality). Furthermore, we are not aware of works applying wco joins over property graphs.

3

Graph Databases and Worst-Case-Optimal Algorithms

3.1

RDF and Basic Graph Patterns

In the RDF model [16], graph databases are directed labeled multigraphs; edges p s → o are also regarded as triples (s, p, o) and thus the database is seen as the set of those triples. Node s is called the subject, label p the predicate, and node o the object of the triple. Basic Graph Patterns (BGPs) are the core feature of most graph query languages [2], consisting of a set of triple patterns (x, y, z), where any component can be a constant or a variable symbol. A solution to a BGP is a function that assigns a (node or label) value to each variable of the BGP so that, replacing variables by their values, all the triple patterns become graph triples in the database. Solving a BGP consists of enumerating all the solutions. Let a graph G have N triples and Q be a BGP. We call Q(G) the solution of Q over G, and Q∗ ≥ |Q(G)| the maximum possible size of a solution of Q over any graph of N triples. An algorithm that solves Q is said to be worst-caseoptimal (wco) [8, 28] if it works in time Õ(Q∗ ), where Õ hides factors that are polylogarithmic on N , or independent of it (such as |Q|). The wco concept and the development of practical wco algorithms have had an enormous impact on the resolution of complex and cyclic BGPs. In particular, wco algorithms outperform every algorithm based on enforcing the triple pattern conditions consecutively (as classic database join plans do); they enforce all the conditions simultaneously. The classical example is the triangle query R(a, b) ▷◁ S(b, c) ▷◁ T (c, a), which if the tables have N pairs takes Ω(N 2 ) worst-case time with any consecutiveenforcing algorithm, whereas wco algorithms solve it in time Õ(N 3/2 ). 3.2

Leapfrog TrieJoin

Leapfrog Triejoin (LTJ) [49] is a seminal wco join algorithm. It precalculates six tries where the graph triples are inserted as strings of length 3 in all different orders, T = {SPO, SOP, POS, PSO, OSP, OPS}. It chooses an order to handle the variables, which is called a variable elimination order (VEO), and then assigns each triple pattern t ∈ Q to a trie τt ∈ T , such that (i) the constants of t appear first in the order of τt , and (ii) the variables of t appear in τt in the same order of the VEO. For each triple pattern t ∈ Q, LTJ first descends by its constants on τt , and the node vt ∈ τt arrived at is the locus of t. Next, LTJ takes one variable x after the other in the VEO. Let Tx = {t ∈ Q, x appears in t}. For each t ∈ Tx , the possible values of x are the children of vt . LTJ then intersects the children of all the loci {vt , t ∈ Tx }. For each value c in the intersection, it branches with the binding x := c and descends by value c from all the involved loci, vt ← child(vt , c) for all vt ∈ Tx . By the time all the variables are bound in this way, the set of bindings in that branch form a new solution to report. Fig. 1 shows a toy graph and its trie POS (ignore property age of nodes for now). A way to implement LTJ intersections is to take the smallest child value c of one locus vt ∈ Tx , and search the children of the next locus vt′ ∈ Tx for the smallest child value c′ ≥ c; this operation is called leap, that is, c′ ← leap(c).

age:

Alice works

Finance

lives age: 55

Bob works

lives

Europe

works

lives

lives

age: 45 works

Carla

Finance

Europe

CS

America

age: 60

Diego Emily

Diego

Bob

Carla

Alice

America

Diego

lives

Bob

Emily

Carla

lives age: 25

Alice

CS

Emily

works works

Fig. 1: On the left, a graph database of where people live and area they work in; person nodes have also property age. On the right, the trie POS for the graph.

We then assign c ← c′ and go on with the third locus vt′′ ∈ Tx , and so on. We continue cycling over the loci until a whole pass over Tx retains the same c value, giving the next element in the intersection. After branching on x := c, we restart the process with the next child value in some loci. This algorithm is optimal in the sense that its cost is Õ(alt), where alt is the alternation complexity [11] of the sets to intersect. This is the least number of switches from one sorted sequence of values to another needed to cover them all; for example intersecting {2i, 1 ≤ i ≤ n} ∩ {2i − 1, 1 ≤ i ≤ n} = ∅ is hard because we must switch at every new value (alt = 2n−1), whereas intersecting {i, 1 ≤ i ≤ n}∩{i, n < i ≤ 2n} = ∅ is easy (alt = 1; it suffices to compare two elements to certify the output). Other intersection techniques used in some LTJ implementations, like probing the elements of the smallest set in the others, do not yield this guarantee. 3.3

Beyond RDF: Filtering by properties and labels

Most graph query languages, like SPARQL [27], GQL [22], and SQL/PGQ [17], have BGPs at their core, but also include filters. GQL and SQL/PGQ assume property graphs [1], which extend triples to allow nodes and edges to have properties with values: one may specify that some variable x, when assigned to a node or edge in the triple pattern, contains a property π and that its corresponding value x.π is within a range, say a ≤ x.π ≤ b. It is also customary to assign labels to nodes and edges, requiring that variable x is assigned to an element having a label ℓ; let us denote this as x.ℓ. While SPARQL filters are applied directly on nodes and predicates in triples, we allow zero-to-many values per property and zero-to-many labels, and hence our scheme is also flexible enough to capture features of RDF, as we will discuss in Section 4.3. While the BGP core of the query can be solved efficiently with a wco algorithm, conditions on properties and labels have been typically handled outside of this wco algorithm by pre- or post-filtering: we can either filter all nodes and edge values v to leave for consideration only those holding a ≤ v.π ≤ b (or where label v.ℓ exists), or first solve the BGP and filter every output, removing bindings of v that do not satisfy the conditions. If we use LTJ, a better solution

is to adapt it so as to post-filter the values v as soon as they come out of the intersection of loci children, thereby pruning branches earlier. However, as with non-wco algorithms, these approaches may force us to examine many more solutions than necessary. Consider, for the graph of Fig. 1, the BGP {(x, lives, Europe), (x, works, CS)} complemented with the condition x.age ≥ 50, aimed at finding senior people working in CS in Europe. LTJ will choose two loci, say in POS (it could also be OPS), by descending through (lives, Europe) and (works, CS), respectively. The intersection of the loci children yields all people x working in CS in Europe. If we pre-filter by age on a large real graph of this form, we will generate a lot of senior people, very few of which will end up passing the BGP filter. If we post-filter, we will generate a lot of people working in CS in Europe, very few of which will pass the seniority filter. None of those methods meet the alternation complexity bound, which is never asymptotically larger than the minimum of both sets, and can be much smaller.

4

Leaptors: Incorporating Filters into LTJ

We generalize the logic of LTJ so as to handle not only triple patterns mapped to trie loci, but in general leaptors (these extend “iterators”, which can only deliver the elements sequentially). A leaptor represents a set S with a total order and supports operation leap(c) = min{c′ ∈ S ∪ {+∞}, c′ ≥ c}, in time polylogarithmic on |S|. An example leaptor is the algorithm that finds the child of a trie node (the locus) with the smallest value c′ ≥ c; this can be implemented, say, via exponential search on the increasing sequence of child values. 4.1

Properties and ranges of values

We now define a new leaptor to incorporate filters on property values. Let U be the set of node/edge identifiers in the graph, and Aπ be the set of values a property π takes in the graph. Assume that both sets are integers; if not, we map them to integer ranges [1, |U|] and [1, |Aπ |] while preserving order. For example, by storing an array of all the node/edge values, and another of all the values of Aπ , we can map from actual values to integer ranges with an O(log N )-time binary search, and can map back any result in constant time. We now define a discrete grid Mπ of [1, |U|] × [1, |Aπ |], and set a point at (v, a) in Mπ for every node/edge v having property π with value a. This supports v having zero-to-many values for a property π. Query leap(c) on the leaptor for a ≤ x.π ≤ b is implemented on Mπ via the orthogonal range query leftmost([c, +∞], [a+ , b− ]), which finds a point with minimum x-value c′ ≥ c whose y-value is within [a+ , b− ] (leap(c) returns +∞ if this range is empty). Here, a+ is the smallest value a+ ≥ a in Aπ and b− is the largest value b− ≤ b in Aπ ; both are found in O(log |Aπ |) ⊆ O(log N ) time via binary searches (done only once per query). The geometric query itself is called an orthogonal range successor query, and can be solved in time O(logϵ N ) for any constant ϵ > 0, using space linear in the number of points in Mπ [40]. This space is proportional

60

60

55

Age

45

40 25

20 0

Alice

Bob

Carla Diego Emily Nodes

Fig. 2: The grid Mage for the graph of Fig. 1 (only showing person nodes). The shadowed area corresponds to the query leftmost([Carla, +∞] × [50, +∞]).

to the database size, which includes one unit of space per value each property has for each node/edge. The leaptor time is then always in O(log N ). See Fig. 2. Let us return to our example of Section 3.3 to illustrate the power of our method. Apart from the two leaptors implemented on tries for the triple patterns, we have the one implemented with grids for the condition x.age ≥ 50. Once a candidate c passes the filters of the two loci, we find the leftmost point (c′ , a) in [c, +∞] × [a+ , b− ]. This will yield the next senior person c′ ≥ c, and then the next person working in CS in Europe will be sought after c′ , not after c. In the example, the first candidate coming out of the intersection of children of trie loci (lives, Europe) and (works, CS) is Bob. The grid leaptor also returns Bob for the query leap(Bob) = leftmost([Bob, +∞] × [50, +∞]), and thus Bob is an output of the query. If we now start from the grid to get the next candidate, its leaptor returns Diego (see the shaded area in Fig. 2), which lets us discard Carla already. This process achieves the alternation complexity, visiting fewer candidates than pre- or post-filtering, and potentially not fully traversing either set (those passing the BGP and those passing the age filter). For example, if the person ids happen to be clustered by country, occupation, or age, the alternation complexity can be much lower than the number of candidates processed by standard filtering. 4.2

Labels

Property graphs may also permit labels on nodes/edges, and queries may filter for elements having some label ℓ. While labels can be handled as a special property (giving them value 0 when the label exists, and asking for leftmost([c, +∞]× [0, 0]) on their grid), a faster leaptor is possible. Let Dℓ index the node or edge ids with label ℓ. Dℓ supports successor queries [45], which find the smallest integer ≥ c in a set of size N (or +∞ if there is none) in time O(log log N ), using O(N ) space. The leaptor for label ℓ then simply implements leap(c) = successor (Dℓ , c). It is also generally possible to ask for elements having a property π, independently of its value. The corresponding leaptor can, again, be simulated with query leftmost([c, +∞] × [−∞, +∞]) on Mπ , but within linear space we can also

SPO order Alice Alice Bob Bob Carla Carla Diego Diego Emily Emily

lives works lives works lives works lives works lives works

OSP order

LSPO

Europe Finance Europe CS Europe CS America CS America Finance

America America CS CS CS Europe Europe Europe Finance Finance

Diego Emily Bob Carla Diego Alice Bob Carla Alice Emily

POS order

LOSP

lives lives works works works lives lives lives works works

lives lives lives lives lives works works works works works

America America Europe Europe Europe CS CS CS Finance Finance

LPOS

Diego Emily Alice Bob Carla Bob Carla Diego Alice Emily

Fig. 3: A Ring structure on the graph of Fig. 1, assuming the node id order is the lexicographic order of the strings. The Ring only stores the three shaded sequences. The arrows show how the triple (Alice, lives, Europe) is tracked across the three orders. The rectangle on POS, corresponding to the child of the trie root by works, descends by Carla to the rectangle on SPO.

store a successor data structure Dπ with the node or edge ids having some value for property π, and run leap(c) in time O(log log N ). 4.3

Extending the Ring Index

The Ring [6] is a succinct index that handles BGPs in wco time on RDF graphs. An index is said to be succinct if, including the data, it uses S + o(S) space, where S is the size of a plain representation of the data. The Ring represents the set of triples (s, p, o) with three sequences, LSPO , LOSP , and LPOS . Sequence LSPO stores the objects of the N triples sorted by the order SPO, that is, triples (s, p, o) are sorted lexicographically and LSPO collects the sequence of their o components. Analogously, sequence LOSP collects the N predicates p in the order OSP and sequence LPOS collects the N subjects s in the order POS. Overall, letting U be the universe of nodes and predicates, the Ring uses 3N log2 |U|(1 + o(1)) bits, which is the space needed to store the N triples (s, p, o) in plain form, plus a sublinear redundant space. See Fig. 3. The sequences L∗ [1, N ] are represented with a data structure called a wavelet tree [26, 38], which uses N log2 |U|(1 + o(1)) bits and in particular implements the operation rankc (L∗ , i), the number of times c occurs in L∗ [1, i], in time O(log |U |). We also represent arrays AO , AP , and AS , where A∗ [1, |U|] holds in A∗ [e] the number of positions in L∗ with values less than e. Those arrays can be represented with sparse bitvectors B∗ [1, N ] where B∗ [A∗ [e]] = 1 for all e and 0 otherwise, so A∗ [e] = select1 (B∗ , e), where selectb (B∗ , e) is the position of the eth bit b in B∗ . Sparse bitvectors [44, 18, 20] use |U| log2 (N/|U |) + 2|U| ∈ O(N ) bits, which fits within the sublinear extra space of the Ring, and answer select1 queries in constant time. With those structures we can track triples across the arrays L∗ : the triple at LSPO [i] has object o = LSPO [i], and it corresponds to LOSP [i′ ], where i′ = AO [o] +

ranko (LSPO , i). The triple then has predicate p = LOSP [i′ ], and it corresponds to LPOS [i′′ ], where i′′ = AP [p] + rankp (LOSP , i′ ). The subject of the triple is then s = LPOS [i′′ ] and if we compute AS [s] + ranks (LPOS , i′′ ) we return to LSPO [i]. Trie nodes correspond to ranges in some sequence L∗ . A locus in SOP or SPO, reached by descending by s, corresponds to the range LSPO [i, j] = LSPO [AS [s] + 1, AS [s + 1]] of the triples (s, ∗, ∗). If we now descend by o in SOP, the resulting locus corresponds to range (s, o, ∗) in the order SOP, which we do not represent, but also to range (o, s, ∗) in the order OSP, which we do represent in LOSP . This is LOSP [i′ , j ′ ], where i′ = AO [o]+ranko (LSPO , i−1)+1 and j ′ = AO [o]+ranko (LSPO , j). If, instead, we descend by p after s in SPO, we stay in the same sequence LSPO , which represents that trie, now restricting the range to the triples (s, p, ∗). The new range is computed by descending from the root of POS with p, and from the resulting range LPOS [i′′ , j ′′ ] descending by s to LSPO [i′′′ , j ′′′ ], with i′′′ = AS [s] + ranks (LPOS , i′′ − 1) + 1 and j ′′′ = AS [s] + ranks (LPOS , j ′′ ). We will still call those operations “descending” by a value, even if they are mapped to ranges in L∗ . See again Fig. 3 for examples of tracking and descending. Descending operations allow the Ring to simulate the LTJ algorithm by mapping loci to ranges in L∗ . The Ring leaptor is implemented as follows. Say we are again in LSPO [i, j] after descending by s in trie SOP. To implement leap(c) on the values of o, we must find the smallest value in LSPO [i, j] that is ≥ c. This operation, called range next value, is supported in O(log |U|) time by the wavelet tree [24]. If, instead, we are in trie SPO and want to find the smallest value of p that is ≥ c, we start at range LPOS [AP [c] + 1, N ] (the range of all predicates ≥ p in order POS), and compute LSPO [i′ ] = AS [s] + ranks (LPOS , AP [c]) + 1. Tracking LSPO [i′ ] to LOSP yields the desired value of p. The Ring then implements the leaptors in time O(log |U |), yielding a total query time complexity of O(Q∗ · |Q| log |U|) ⊆ Õ(Q∗ ). Incorporating properties and labels. We add to the Ring succinct representations of grids Mπ that use Nπ log2 |Aπ |(1 + o(1)) bits, where Nπ is the sum of the number of values property π has over all nodes. This is again the size of the data plus a sublinear term. Such a succinct representation is the wavelet tree of the sequence Sπ of values property π takes, sorted by increasing identifiers of the nodes. We also represent a bitvector Bπ [|U| + Nπ ] where, for each node identifier v, we append a 1 and then as many 0s as values v has for property π; note that positions in Sπ align with 0s in Bπ . The grid of Fig. 2, for example, would be represented with the sequence Sage = ⟨55, 45, 60, 25⟩ and the bitvector Bage = 110101010 (considering only the node ids that appear in the figure). For Bπ we use a dense bitvector representation, which uses (|U| + Nπ )(1 + o(1)) bits of space (thus fitting within the sublinear extra space of the index) and supports queries selectb in constant time [15, 37]. We thus compute with c′ ← select1 (Bπ , c) − c + 1 the first position in Sπ of node identifiers ≥ c. The wavelet tree then solves the orthogonal range successor query from Sπ [c′ ..], in time O(log |U|) [10]. The answer c′′ is finally converted back to an identifier with select0 (Bπ , c′′ )−c′′ . In our example, to compute leftmost([Carla, +∞]×[50, +∞]) on Mage , where Carla = 3, we start with c′ ← select1 (Bage , 3) − 3 + 1 = 2, so we

find the first value ≥ 50 on Sage [2..]. This is at Sage [3] = 60. We finally convert that position, c′′ = 3, back to the identifier select0 (Bage , 3) − 3 = 4 = Diego. Queries on labels are handled with generic successor data structures in Section 4.2. While using linear space, such a representation is not succinct: If a label ℓ is assigned to m elements out of n, a succinct representation uses space close to the bits required to specify which are those m elements, that is,
n n + O(m) bits. We thus use instead a sparse bitvector Bℓ for log2 m = m log m each label ℓ, with one bit per node, marking with a 1 the elements having label ℓ. A sparse bitvector [44, 18, 20] represents n bits, m of which are 1, using at most n + 2m bits, and provides operations rankb and select0 in time O(log m) m log m and (as already mentioned) select1 in constant time. Operation leap(c) for the condition x.ℓ is then implemented as select1 (Bℓ , rank1 (Bℓ , c − 1) + 1) with this leaptor, in time O(log m) ⊆ O(log N ). This representation also provides a leaptor for the next element not having a label ℓ, with leap(c) = select0 (Bℓ , rank0 (Bℓ , c− 1) + 1), also in time O(log m). Section 5.2 describes a similar mechanism for edge properties and labels. This extended Ring is succinct on the triples, properties and labels it represents. It implements LTJ and supports leaptors for filtering. If we count the filters on property values and Boolean expressions on labels as part of the query size |Q|, the overhead for query time stays O(|Q| log |U |) ⊆ Õ(1). RDF model. Node properties π can be expressed in RDF by creating nodes with all the literal values a that property π can yield, and represent v.π = a with a triple (v, π, a). Labels can be given a reserved property lab. Conditions like x.π = a can then be expressed as a triple pattern (x, π, a), whereas range conditions like a ≤ x.π ≤ b can be translated into {(x, π, y), a ≤ y ≤ b} with variables x and y. The second clause is a range condition on (literal) node identifiers, which can be implemented by ensuring that node identifiers respect the order of the literals and using a leaptor for y that defines leap(c) = max(a, c) if c ≤ b and p +∞ otherwise. Properties of edges u → v can be modeled by reification: create a node e representing the edge, with properties e.from = u, e.to = v, e.label = p, set further properties e.π = a on the edge, and express them all as RDF triples. While correct, a wco solution to those translated range conditions is less efficient than the one we described, because they filter the variables in sequence, not simultaneously. Consider the clauses {(x, π, y), a ≤ y ≤ b}. If x is eliminated before y, LTJ will produce all the possible values of x, and only later, when y is eliminated, it will filter those values of x for which a ≤ x.π ≤ b, one by one. If y is eliminated before x, LTJ will bound it to every literal node within [a, b], and only later, when x is eliminated, connect the y values, one by one, to actual values of x by label π. Both strategies correspond to what we have exemplified as pre- or post-filtering; our strategy using grids Mπ performs the filtering simultaneously for the range values and the other conditions on x. Rather than represent properties and labels in RDF, a dual idea is to represent RDF triples with properties and labels in order to support more efficient simultaneous filtering using grids in the RDF setting. For example, RDF triples of the type (x, p, y), where p is a datatype-property and y is a literal, could be

represented as properties on x (x.p = y), while triples of the form (x, type, y) could be represented as labels on x (x.lab = y). This is feasible since our model supports zero-or-more labels and property values per node. However, our model would require some amendments to cover hybrid object/datatype properties (RDF properties with a mix of datatype and node values), joins on the predicate position, and other such details, as allowed in the base RDF/SPARQL case.

5

Property Graphs

In the previous section we described techniques for efficiently handling filters on properties and labels. We now apply these techniques for a concrete data model and query language, namely property graphs and a fragment of GQL. Some details of this concrete setting (e.g., edge identifiers, Boolean label expressions) require additional care, while others (e.g., one edge label, at most one value for a property on a given node or edge) provide opportunities to optimize further. 5.1

Data model and query language

A property graph is a directed labeled multigraph where any node or edge may feature a set of property-value pairs; properties have a unique value per node/edge. In addition, an edge is annotated with one label, and a node with zero or more labels. Unlike in RDF, edges have an identity beyond their label (e.g., there can be two edges with the same label connecting the same nodes). Let G(N , E) be a property graph, with N ∩ E = ∅. Let P be the set of properties associated with any node or edge, and let properties have atomic values in A (e.g., integers, dates, strings). The nodes have zero or more labels in LN and the edges have exactly one label in LE , with LN ∩ LE = ∅. Our graph of Fig. 1 is a property graph, with node property age and edge labels lives and works. Possible edge properties could be, for example, a date since (for edges with label lives) or an integer salary (for edges with label works). Possible labels for nodes (representing persons) could be person and has-phd. Two main standards exist to query property graphs: SQL/PGQ and GQL [22]; their common graph pattern matching language is called GPML [17]. A GPML query is of the form MATCH pattern, where pattern specifies the subgraph to match as a set of edge patterns, optionally augmented with a WHERE clause to filter the results. We now describe the fragment we support [17, 1, 22]. The most basic edge patterns are of the form (s) → (o), where s and o can be constants in N or node variables from a set VN . Those are analogous to triple patterns but do not specify any label. Conditions on labels are associated with node variables, for example we can add a clause (x:person) to specify that x ∈ VN can match only nodes having the label person ∈ LN . We can include these clauses in edge patterns, for example in (x:person) → (y). Label conditions may consist of expressions including conjunctions (&), disjunctions (|), negations (!), and groups of labels. For example, a clause (x:person&has-phd) admits the nodes with labels person and has-phd.

Label conditions can also be given on edge patterns, as in (s) − [:works] → (o), which allows matching only edges whose label is works ∈ LE ; expressions on labels can also be used. It is also possible to give variable names, from a set VE disjoint from VN , to edges: (s) − [e] → (o) gives variable name e ∈ VE to the edge; we can also incorporate expressions as in (s) − [e : works] → (o). The WHERE clause filters the results by restricting the existence or the values of some of their properties or by comparing the identifiers of edges/nodes (yet we cannot compare edge variables with node variables). Conditions can be combined with AND, OR, and NOT. Comparisons are of the form (A op B), where A and B are constants or variable property values x.π of the same type, and op ∈ {=, ̸= , <, ≤, ≥, >}. We can directly compare node or edge identifiers as if they were properties, as in (x<=y) AND (y<=z), which avoids reporting the same tuples (x, y, z) in every possible order. One can also state that a variable must have, or not have, some property using (x.since IS NOT NULL) or (x.since IS NULL). A final RETURN clause indicates which variable values, or their property values, to return from each solution. This implies a projection of the tuples returned in the standard BGPs. Under bag semantics repetitions resulting from projections are not removed and the query algorithms can still be wco. The following query, for example, looks for names and ages of senior people working in CS in Europe that started in their job before 2010 or have no phd: MATCH (x:person)-[:lives]->(Europe), (x)-[e:works]->(CS) WHERE (x.age >= 50) AND ((e.since < 01/01/2010) OR (!x.has-phd)) RETURN x.name, x.age

5.2

PG-Ring: A succinct index for property graphs

We build on the Ring extensions described in Section 4.3 to define PG-Ring, which indexes property graphs within succinct space. Since the edges of property graphs have exactly one label in LN , we treat edges e = s → o as triples (s, λ(e), o) in order to create the sequences L∗ . The symbols of LPOS and LSPO then range over N and those of LOSP range over LE . Storing the additional edge identifiers of property graphs would exceed the data size budget, so we rather exploit the fact that such identifiers are internal by defining the identifier of an edge as its index in the order POS. We choose this index order since all edge identifiers with some label ℓ are precisely in the range [AP [ℓ] + 1, AP [ℓ + 1]], and edge patterns of the form (s) − [: ℓ] → (o) are treated as a constant predicate in a triple pattern, instead of using a leaptor. Boolean expressions L on labels, (s)−[: L] → (o), are converted into a set of O(L) disjoint ranges: the complement of ℓ becomes {[1, AP [ℓ]], [AP [ℓ + 1] + 1, N ]}, disjunction becomes union of ranges, and conjunction becomes intersection. Though we process a set of disjoint ranges during query processing, for simplicity we assume a single range in what follows. Leaptors for edge variables. Variables in VE can be assigned to edge identifiers. Those will be handled like any other variable in LTJ, with the particularity that

AND

(x)-[e:works]->(CS)

POS trie

(x.age >= 50)

OR

Mage grid

POS trie lives

works

Europe

CS

age

(x)-[:lives]->(Europe)

50

(e.since < 01/01/2010) Msince grid

node ids x

since

x

2010

(!x.hasPhD) B hasPhD bitvector 0011010100010101011 node ids

edge ids

Fig. 4: The syntax tree of our example of Section 5.1. Each internal node implements a Boolean leaptor; leaf nodes implement trie, grid, and bitvector leaptors.

their identifiers are not explicit in any sequence L∗ , but implicit as indices in LPOS (i.e., on order POS). The leaptor for a variable z ∈ VE – which is mentioned on an edge pattern t represented by a trie τt ∈ Tz – will thus implement leap(c) differently depending on which sequence L∗ holds the range that represents the locus vt . See Appendix A for details [9]. Leaptors for node properties and labels. Since now each property π defined for a node v has exactly one value v.π, we can slightly simplify the scheme of Section 4.3, storing bitvectors Bπ [1, |N |] telling at Bπ [v] whether node v has property π (in the example of Fig. 2, Bage = 01111). If so, the wavelet tree sequence Sπ that represents Mπ has value Sπ [rank1 (Bπ , v)] = v.π, and the first position of Sπ with node identifier ≥ c is rank1 (Bπ , c−1)+1. See Appendix A for details [9]. The general case: Boolean leaptors. The WHERE clause features a general Boolean expression, not just a conjunction. We use the same syntax tree mechanism to define a Boolean leaptor for the whole expression. The use of a syntax tree generalizes the set intersections discussed so far by also allowing disjunction nodes, which leap by taking the least of the leap values of both children. Negations must be removed by pushing them to the leaves and applying them to the atomic condition, both for properties (e.g., NOT (x < y) becomes (x >= y)) and for labels (e.g. NOT (x.person) becomes (!x.person)). We further integrate into the syntax tree the edge patterns of the MATCH clause as a conjunction with those of the WHERE clause. See Fig. 4, and Appendix A for more details [9].

6

Experiments

We implement PG-Ring in C++11 on top of the succinct data structures library, SDSL, as described in more detail in Appendix B [9]. We compare it with various state-of-the-art alternatives that support property graphs and GQL-like languages for two different benchmarks: LSQB and Wikidata. We run a set of queries with a time limit of 600 seconds. Following the LSQB benchmark [35], for each query, we report the average runtime over 5 runs. That measurement is

106

106

105 Kùzu

104

Memgraph

103

DuckDB Umbra Neo4j

102

PG-Ring

101 100

101 Space (GB)

104

Neo4j

Memgraph

Kùzu DuckDB

103

PG-Ring

Umbra MillDB

102 101

MillDB

100

Avg Time (msec.)

Avg Time (msec.)

105

102

100

100

101 Space (GB)

102

Fig. 5: The space-time trade-off of the evaluated systems on the six queries of LSQB. The first plot is limited to 10 results, and the second to 1,000. computed after a first warm-up to mitigate the advantage of in-memory systems. Disk activity was monitored using iostat at one-second intervals. In LSQB, a single pass over the queries was enough to avoid disk reads, whereas in Wikidata, additional warm-up queries (e.g., reporting all the nodes) were required beforehand. For both benchmarks, the effect on time performance of a cold cache scenario is reported in Appendix F [9]. All experiments were conducted on an AMD Ryzen 9 9900X at 4.4GHz, with 24 cores, 32 MB cache, and 249 GB RAM. 6.1

Labelled Subgraph Query Benchmark

We used the Labelled Subgraph Query Benchmark (LSQB) [35] to generate a graph with 35.5 million nodes and 219.4 million edges. Each node can be given one of 14 possible labels, whereas each edge can be given one of 15 possible labels. In this benchmark, nodes and edges do not have properties. We also choose six queries to evaluate from the benchmark. See Appendix C [9] for further details. We compare systems supporting GQL (details in Appendix D [9]): Umbra [42], DuckDB [46], Kùzu [29], Neo4j [41], Memgraph [34], MillDB [51], and our PG-Ring. We run the six queries on all the systems, limiting results to 10 and 1,000. Appendix C shows detailed results [9]; Fig. 5 summarizes them. The left plot shows the space and average time of each system with the number of results limited to 10. We can see that PG-Ring achieves a good balance between space and time. In space, PG-Ring is dominated only by DuckDB, which is 1.6 times smaller due to its columnar compression, but its average times are 12−2,700 times slower (see Appendix C [9]). The next competitor in space is Umbra, which uses 1.8 times more space than PG-Ring. In time performance, the PG-Ring wins in three cyclic queries (Q2, Q3, and Q6, see Appendix C [9]), showing the effect of using the LTJ algorithm to solve these queries. In the other queries, the clear winner is MillDB. In fact, MillDB is very competitive in all queries, but it requires around 5.4 times more space than PG-Ring. The right plot shows the same evaluation when restricting the results to 1,000. In this scenario, PG-Ring performs competitively on cyclic queries, with

102

250 0.679

Pre-filter

101 Neo4j

100 0

20

40

MillDB

60 80 100 120 140 Space (GB)

0.766

150

0.295

100 50

Post-filter PG-Ring

Time (msec.)

Avg Time (sec.)

200

0.186 0.182

0 PG-Ring Post-fil. Pre-fil. MillDB

Neo4j

System

Fig. 6: On the left, the space-time trade-off of the evaluated systems. On the right, boxplots represent the distribution of query execution times. The numbers on top indicate the median time for each system.

the exception of Q2, where Neo4j performs best. In contrast, Neo4j shows weaker performance in Q3, where it exceeds the time limit, and Q6, where it is 11 times slower. In Q1, Memgraph stands out by being 1.8 times faster than MillDB, but it is the most space demanding structure and times out in Q3. For all remaining queries, MillDB is the top performer, taking less than 4 milliseconds per query. The plot shows that DuckDB and Umbra fare better for obtaining many results. In conclusion, PG-Ring offers a good space-time trade-off, it is highly competitive for cyclic queries, highlighting the impact of the wco join algorithm; and ranks second in space usage thanks to the use of compact data structures. 6.2

Wikidata Benchmark

We use the Wikidata knowledge graph [50] to evaluate our performance in a large scale graph with properties (via qualifiers). The Wikidata graph is represented using the RDF model; therefore, we transformed it into a property graph. The resulting graph consists of 109 million nodes, which can take 103 thousand distinct labels and have 10,569 different properties. In total, there are 719.5 million edges, with 1,640 possible edge labels and 603 distinct properties. From the Wikidata SPARQL query logs, we extracted a set of 19.6 thousand queries and converted them to GQL syntax. See Appendix E for details [9]. We exclude Umbra [42], DuckDB [46], and Kùzu [29] because Wikidata nodes can have multiple labels (classes), but these systems assume a single type/table per entity. Memgraph [34] was also excluded due to its high memory usage and the impracticality of loading the Wikidata graph. In Neo4j [41], we create indexes on the entity identifiers and on the properties used in the queries. To study the effect of incorporating the filters directly to the LTJ algorithm, we include two variants of PG-Ring: The pre-filter baseline first applies the property and label filters, and only then evaluates the edge patterns. The postfilter baseline evaluates the edge patterns first and subsequently applies filters.

Fig. 6 shows the performance in space and time of different systems on the selected queries, limiting the output to 1,000,000 results. PG-Ring achieves the most favorable space-time trade-off: it requires only 32% of the storage used by MillDB, which is on average just 32% faster than PG-Ring. MillDB shows, however, more stability across all queries, with its third quartile being at around 5 milliseconds, while the other systems exceed 10 milliseconds. Conversely, Neo4j is slower than PG-Ring and consumes significantly more space, exceeding 100 GB: in a real-world scenario Neo4j will consume much more space because we are restricting the indexes to just those properties involved in the queries. The experiment also shows that pushing the filters directly into the LTJ algorithm leads to superior performance. On average, PG-Ring achieves a 16% improvement over the post-filter baseline and is 15 times faster than pre-filter. The boxplots show a more marked difference in distributions, for example PGRing is almost 60% faster than post-filter in the median, and much more stable in general. As an example to explain this difference, consider one of the queries: MATCH (v:Q5)-[e:P21]->(u) WHERE (v.P569 >= 1554-01-01) AND (v.P569 < 1555-01-01) RETURN v, e, u

which gets the gender (P21) of humans (Q5) born in (P569) 1554, for which PGRing achieves a speedup over 5,000 times compared to the post-filter baseline, which needs to check for every human if they were born in 1554. Conversely, the pre-filter is twice as slow as PG-Ring because it first retrieves all entities born in 1554 and only then verifies whether they are humans. Note that Wikidata can also store birth dates for non-human entities (e.g., fictional characters, animals).

7

Conclusions

We proposed succinct data structures that support wco joins and filters. We show the advantages of pushing the filtering within the wco processing of the joins, thereby uplifting the superpowers of those join processing algorithms, and outperforming the classic pre- and post-filtration methods that handle the wco joins as a black box. We adapt and optimize these structures for the concrete setting of evaluating the corresponding fragment of GQL queries over property graphs, giving rise to PG-Ring. Experiments on two property graphs show that although existing systems sometimes outperform PG-Ring in terms of time (MillDB), or space (DuckDB), PG-Ring provides a strong time–space trade-off in this setting. For future work, we plan to implement PG-Ring for RDF/SPARQL, optimize it specifically for this setting, and compare it with leading systems. Though the Ring supports this setting, an interesting question arises from when it is preferable to represent (e.g.) datatype values as property values versus graph nodes. We also wish to explore pushing further query operators from GQL, SPARQL, etc., into low-level operations on the succinct data structures. A limitation of PG-Ring is that it is currently read-only, but it can be adapted to support updates. The original Ring article [6, Sec. 8 & App. E] discusses

in detail how to handle changes on nodes and edges. The PG-Ring represents property values and labels via wavelet trees and bitvectors, for which dynamic versions exist [31] while retaining succinctness and enabling updates in time O(log2 N ), but at the cost of an O(log N ) time penalty factor on queries. This can be alleviated with adaptive dynamic bitvectors [39], a recent development that supports dynamism with a much smaller penalty when the update-to-query ratio is very low, something proven to work well for Wikidata-style workloads [5]. Supplemental Material Statement: Source code and query sets are available from Github at https://anonymous.4open.science/r/PG-Ring-B1F8. The datasets are available from Zenodo at https://zenodo.org/records/19818050. Appendices are submitted as an extended version on EasyChair, and will be published on arXiv. Declaration of use of Generative AI: Generative AI was used only as a support tool for code completion, for assisting with the parsing and preprocessing of some data, and to produce Figs. 1–3 in tikz from textual descriptions. All suggestions were reviewed, tested, and adapted before being included in the final work.

References 1. R. Angles. The Property Graph Database Model. In Proc. Alberto Mendelzon Workshop (AMW), 2018. 2. R. Angles, M. Arenas, P. Barceló, A. Hogan, J. L. Reutter, and D. Vrgoc. Foundations of modern query languages for graph databases. ACM Computing Surveys, 50(5):68:1–68:40, 2017. 3. J. Arenas-Guerrero and S. Ferrada. COTTAS: columnar triple table storage for efficient and compressed RDF management. In Proc. 24th International Semantic Web Conference (ISWC), part II, pages 313–331, 2025. 4. D. Arroyuelo, F. Barisione, A. Fariña, A. Gómez-Brandón, and G. Navarro. New compressed indices for multijoins on graph databases. Information Systems, 137:article 102647, 2026. 5. D. Arroyuelo, D. Campos, A. Gómez-Brandón, Y. Linker, G. Navarro, C. Rojas, and D. Vrgoc. CompactLTJ: Space & time efficient Leapfrog Triejoin on graph databases. The Very Large Databases Journal, 34:article 67, 2025. 6. D. Arroyuelo, A. Gómez-Brandón, A. Hogan, G. Navarro, J. Reutter, J. RojasLedesma, and A. Soto. The Ring: Worst-case optimal joins in graph databases using (almost) no extra space. ACM Transactions on Database Systems, 49(2):1– 45, 2024. 7. D. Arroyuelo, G. Navarro, J. L. Reutter, and J. Rojas-Ledesma. Optimal joins using compressed quadtrees. ACM Transactions on Database Systems, 47(2):8:1– 8:53, 2022. 8. A. Atserias, M. Grohe, and D. Marx. Size bounds and query plans for relational joins. SIAM Journal on Computing, 42(4):1737–1767, 2013. 9. Anonymous Authors. Extended Version (with Appendices A–F), Uplifting the Superpowers of Worst-Case-Optimal Join Algorithms. Uploaded to EasyChair for review, to be published on arXiv, 2026. 10. J. Barbay, F. Claude, and G. Navarro. Compact binary relation representations with rich functionality. Information and Computation, 232:19–37, 2013.

11. J. Barbay and C. Kenyon. Deterministic algorithm for the t-threshold set problem. In Proc. 14th ISAAC, pages 575–584, 2003. 12. B. R. Bebee, D. Choi, A. Gupta, A. Gutmans, A. Khandelwal, Y. Kiran, S. Mallidi, B. McGaughy, M. Personick, K. Rajan, S. Rondelli, A. Ryazanov, M. Schmidt, K. Sengupta, B. B. Thompson, D. Vaidya, and S. Wang. Amazon Neptune: Graph Data Management in the Cloud. In Proc. ISWC 2018 Posters & Demonstrations, Industry and Blue Sky Ideas Tracks, 2018. 13. A. Bigerl, F. Conrads, C. Behning, M. Ahmed Sherif, M. Saleem, and A.-C. Ngonga Ngomo. Tentris - a tensor-based triple store. In Proc. 19th International Semantic Web Conference (ISWC), part I, pages 56–73, 2020. 14. A. Bonifati, W. Martens, and T. Timm. An analytical study of large SPARQL query logs. The VLDB Journal, 29(2-3):655–679, 2020. 15. D. R. Clark. Compact PAT Trees. PhD thesis, University of Waterloo, Canada, 1996. 16. R. Cyganiak, D. Wood, and M. Lanthaler. RDF 1.1 Concepts and Abstract Syntax. W3C Recommendation, February 2014. https://www.w3.org/TR/rdf11-concepts/. 17. A. Deutsch, N. Francis, A. Green, K. W. Hare, B. Li, L. Libkin, T. Lindaaker, V. Marsault, W. Martens, J. Michels, F. Murlak, S. Plantikow, P. Selmer, O. van Rest, H. Voigt, D. Vrgoc, M. Wu, and F. Zemke. Graph pattern matching in GQL and SQL/PGQ. In Proc. International Conference on Management of Data (SIGMOD), pages 2246–2258, 2022. 18. P. Elias. Efficient storage and retrieval by content and address of static files. Journal of the ACM, 21:246–260, 1974. 19. O. Erling, A. Averbuch, J. Larriba-Pey, H. Chafi, A. Gubichev, A. Prat, M.-D. Pham, and P. Boncz. The LDBC social network benchmark: Interactive workload. In Proc. ACM International Conference on Management of Data (SIGMOD), pages 619–630, 2015. 20. R. Fano. On the number of bits required to implement an associative memory. Memo 61, Computer Structures Group, Project MAC, Massachusetts, 1971. 21. Javier D. Fernández, Miguel A. Martı́nez-Prieto, Claudio Gutierrez, Axel Polleres, and Mario Arias. Binary RDF representation for publication and exchange (HDT). Journal of Web Semantics, 19:22–41, 2013. 22. N. Francis, A. Gheerbrant, P. Guagliardo, L. Libkin, V. Marsault, W. Martens, F. Murlak, L. Peterfreund, A. Rogova, and D. Vrgoc. A Researcher’s Digest of GQL. In Proc. 26th International Conference on Database Theory (ICDT), pages 1:1–1:22, 2023. 23. N. Francis, A. Green, P. Guagliardo, L. Libkin, T. Lindaaker, V. Marsault, S. Plantikow, M. Rydberg, P. Selmer, and A. Taylor. Cypher: An evolving query language for property graphs. In Proc. International Conference on Management of Data (SIGMOD), pages 1433–1445, 2018. 24. T. Gagie, G. Navarro, and S.J. Puglisi. New algorithms on wavelet trees and applications to information retrieval. Theoretical Computer Science, 426-427:25– 41, 2012. 25. S. Gog, T. Beller, A. Moffat, and M. Petri. From theory to practice: Plug and play with succinct data structures. In Proc. 13th International Symposium on Experimental Algorithms (SEA), pages 326–337, 2014. 26. R. Grossi, A. Gupta, and J. S. Vitter. High-order entropy-compressed text indexes. In Proc. 14th Symposium on Discrete Algorithms (SODA), pages 841–850, 2003. 27. S. Harris, A. Seaborne, and E. Prud’hommeaux. SPARQL 1.1 Query Language. W3C Recommendation, March 2013. https://www.w3.org/TR/sparql11-query/.

28. A. Hogan, C. Riveros, C. Rojas, and A. Soto. A worst-case optimal join algorithm for SPARQL. In Proc. 18th International Semantic Web Conference (ISWC), pages 258–275, 2019. 29. G. Jin, X. Feng, Z. Chen, C. Liu, and S. Salihoglu. Kùzu graph database management system. In Proc. 13th Conference on Innovative Data Systems Research (CIDR), 2023. 30. Y. Liu, Y. Lin, X. Peng, Y. Li, and J. Zhang. RDF-TDAA: Optimizing RDF indexing and querying with a trie based on directly addressable arrays and a pathbased strategy. Expert Systems and Applications, 279:article 127384, 2025. 31. V. Mäkinen and G. Navarro. Dynamic entropy-compressed sequences and full-text indexes. ACM Transactions on Algorithms, 4(3):article 32, 2008. 32. S. Malyshev, M. Krötzsch, L. González, J. Gonsior, and A. Bielefeldt. Getting the most out of Wikidata: Semantic technology usage in Wikipedia’s Knowledge Graph. In Proc. 17th International Semantic Web Conference (ISWC), part II, pages 376–394, 2018. 33. M. A. Martı́nez-Prieto, N. Brisaboa, R. Cánovas, F. Claude, and G. Navarro. Practical compressed string dictionaries. Information Systems, 56:73–108, 2016. 34. Memgraph Ltd. Memgraph: An in-memory graph database, 2024. 35. A. Mhedhbi, M. Lissandrini, L. Kuiper, J. Waudby, and G. Szárnyas. LSQB: A large-scale subgraph query benchmark. In Proc. 4th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA), pages 1–11, 2021. 36. A. Mhedhbi and S. Salihoglu. Optimizing subgraph queries by combining binary and worst-case optimal joins. Proc. VLDB Endowment, 12(11):1692–1704, 2019. 37. J. I. Munro. Tables. In Proc. 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 37–42, 1996. 38. G. Navarro. Wavelet trees for all. Journal of Discrete Algorithms, 25:2–20, 2014. 39. G. Navarro. Practical adaptive dynamic bitvectors. Software Practice and Experience, 55(9):1539–1559, 2025. 40. Y. Nekrich and G. Navarro. Sorted range reporting. In Proc. 13th Scandinavian Symposium on Algorithmic Theory (SWAT), LNCS 7357, pages 271–282, 2012. 41. Neo4j, Inc. Neo4j graph database management system, 2024. 42. T. Neumann and M. J. Freitag. Umbra: A disk-based system with in-memory performance. In Proc. 10th Conference on Innovative Data Systems Research, (CIDR), 2020. 43. H. Q. Ngo, E. Porat, C. Ré, and A. Rudra. Worst-case optimal join algorithms. Journal of the ACM, 65(3):16:1–16:40, 2018. 44. D. Okanohara and K. Sadakane. Practical entropy-compressed rank/select dictionary. In Proc. 9th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 60–70, 2007. 45. M. Pătraşcu and M. Thorup. Time-space trade-offs for predecessor search. In Proc. 38th Annual ACM Symposium on Theory of Computing (STOC), pages 232–240, 2006. 46. M. Raasveldt and H. Mühleisen. DuckDB: An embeddable analytical database. In Proc. ACM International Conference on Management of Data (SIGMOD), pages 1981–1984, 2019. 47. R. Taelman, J. Van Herwegen, M. Vander Sande, and R. Verborgh. Comunica: A modular SPARQL query engine for the web. In Proc. 17th International Semantic Web Conference (ISWC), part II, pages 239–255, 2018. 48. W. van Leeuwen, T. Mulder, B. Van De Wall, G. Fletcher, and N. Yakovets. Avantgraph query processing engine. Proc. VLDB Endowment, 15(12):3698–3701, 2022.

49. T. L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In Proc. 17th International Conference on Database Theory (ICDT), pages 96–106, 2014. 50. D. Vrandecic and M. Krötzsch. Wikidata: A free collaborative knowledgebase. Communications of the ACM, 57(10):78–85, 2014. 51. D. Vrgoc, C. Rojas, R. Angles, M. Arenas, D. Arroyuelo, C. Buil-Aranda, A. Hogan, G. Navarro, C. Riveros, and J. Romero. MillenniumDB: An open-source graph database system. Data Intelligence, 5(3):560–610, 2023. 52. J. Webber. A programmatic introduction to Neo4j. In Proc. ACM Conference on Systems, Programming, and Applications: Software for Humanity (SPLASH), pages 217–218. ACM, 2012.

A

PG-Ring: Additional Details

A.1

Leaptors for edge variables

We implement leap(c) differently depending on which sequence L∗ holds the range that represents the locus vt : – LPOS [i, j]: this is the easiest case because the order POS coincides with that of the edge identifiers. We simply return the first element of [i, j] ∩ [c, ∞], that is, max(i, c) if it is ≤ j, or else +∞. – LSPO [i, j]: this case occurs when a value s was previously used to descend from a range LPOS [i′ , j ′ ]. We then restrict the range in LSPO by starting from range [i′ , j ′ ] ∩ [c, N ] in LPOS and descending by s towards LSPO [i′′ , j ′′ ], as described in Section 4.3 when binding p after s. If i′′ > j ′′ (i.e., the range is empty) we return +∞, otherwise we track LSPO [i′′ ] to LOSP as also described in Section 4.3 and return the resulting position. – LOSP [i, j]: there are two subcases. • If both s and o were bound, we had been in a range LPOS [i′ , j ′ ], descended by s to LSPO [i′′ , j ′′ ], and finally descended by o to LOSP [i, j]. Generalizing the previous case, we retraverse the path starting from interval [i′ , j ′ ] ∩ [c, N ] in LPOS , and upon obtaining the final range LOSP [i′′′ , j ′′′ ], return i′′′ if i′′′ ≤ j ′′′ , or else +∞. • If s was not bound, then p was not bound either (or we would be in order POS). In this case we first find p such that AP [p] < c ≤ AP [p + 1], which covers position c in order POS. We then find the smallest value p′ ≥ p in LOSP [AO [o] + 1, AO [o + 1]] (using operation range next value on the wavelet tree of LOSP ). Next, we descend by p′ towards LPOS [i′ , j ′ ]. Finally, we return i′ if i′ ≤ j ′ , or else +∞. When it comes to binding the value of an edge variable z := e, the resulting range will contain only one entry. We can start from LPOS [e] and track it to the sequence that contains the current range, as explained in Section 4.3. A.2

Leaptors for node properties and labels

A leaptor for leap(c) with ranges a+ ≤ x.π ≤ b− , for constants a+ and b− , is implemented as follows. We first compute c′ = rank1 (Bπ , c − 1) + 1. Second, we compute c′′ ← leftmost([c′ , +∞], [a′ , b′ ]) with the wavelet tree of Sπ . Finally, if there is no answer we return +∞ and otherwise we return select1 (Bπ , c′′ ). For range comparisons between properties of two variables, say x.π ≤ y.π ′ , we proceed as follows for leap(c) on variable x: if y is not yet bound, we compute c′ as in the previous paragraph and return select1 (Bπ , c′ ), the first node ≥ c having property π. Otherwise, we proceed as in the previous paragraph, treating y.π ′ as a constant (which is found at Sπ′ [rank1 (Bπ′ , y)]). We similarly handle comparisons between node identifiers, like x < y, treating them in the same way as property comparisons x.id < y.id for a special property

id, with x.id = x (the numeric identifier of x ∈ N ). That is, when processing x, we return leap(c) = +∞ if y is bound and c ≥ y, and leap(c) = c otherwise. Node labels are handled as in Section 4.3. For Boolean conditions on labels, we can handle the complement of a single label ℓ with the leaptor for not having a label we described in there. A leaptor for a general Boolean expression L on labels can push negations down to the leaves of the syntax tree and implement leap(c) by recursively solving the queries on both children of internal nodes, taking the minimum returned value c′ on disjunctions. For conjunctions, we create multiary nodes containing all the subexpressions that descend by conjunction nodes, and intersect all children as a set, just as for an intersection algorithm. Overall, this matches the alternation complexity of the problem with an extra penalty factor of O(|L| log N ) ⊆ Õ(1). Bitvectors Bπ of properties can be used in the same way as bitvectors Bℓ of labels, to filter by nodes having or not having property π. A.3

The general case: Boolean leaptors

Unlike for labels, some leaves of the syntax tree may not apply for the current variable x being eliminated, either because x is not mentioned in the condition or because x is mentioned but there are other unbound variables. Similarly, leaves representing edge patterns do not apply if they do not contain the variable x to be eliminated. When eliminating x, those leaves become trivial leaptors leap(c) = c. For each new variable x to eliminate, we first simplify the syntax tree for x, with the rules trivial AND X = X and trivial OR X = trivial. This, in particular, removes edge patterns that do not participate in the elimination of x. In Fig. 4, for example, the OR node disappears when eliminating x. Similarly, bound variables may render conditions directly true or false (such as !x.hasPhD in our example once we eliminate x) and those are simplified in the syntax tree for the elimination of further variables: when eliminating variable e, the syntax tree is either just the trie for the edge variable e (if x.hasPhD holds for the bound value of x) or that node ANDed with the leaf for e.since < 01/01/2010 (if not). We say that the reduced syntax tree is reduced for x.

B

Implementation

We implement PG-Ring in C++11 on top of the succinct data structures library, SDSL (https://github.com/simongog/sdsl-lite) [25]. The grids of properties Mπ are implemented with wavelet matrices (wm int) and Bπ as plain bitvectors (bit vector). Regarding the labels, the bitvector Bℓ is represented using the sparse bitvector (sd vector). Generally, datasets contain node, edge, and label identifiers as strings, but PG-Ring needs to deal with them as integers. As they are static identifiers, for each of them, we store a dictionary that allows the mapping between strings and integers. We use a dictionary based on Plain-Front Coding from the compressed string dictionaries library, libCSD (https://github.com/migumar2/libCSD) [33]. Similarly, the PG-Ring represents each property value as an integer, so we need

to map the original values to an integer depending on the property type (e.g. integers, floats, dates). To this end, we transform each value with a function that associates the original value with an integer identifier. This function is type-dependent and ensures that (i) the original value can be recovered from its identifier, and (ii) the identifier can be compared with other identifiers of the same type in exactly the same way as the original values are compared. Our system works under the bag semantics and supports homomorphic pattern matching, allowing repetitions in nodes and relationships. When the system receives a query, we use the dictionaries and functions to get the integer identifiers. Once the query is solved, the identifiers are mapped to the original data. We describe next how we choose appropriate variable elimination orders in the presence of clauses on properties and labels. In this prototype, disjunctions on WHERE clause are not implemented. B.1

Variable elimination orders

The order in which variables are eliminated can have an important impact on practical efficiency [49]. Good practices for LTJ on graph databases [28] are (i) leave lonely variables (those appearing only once in the BGP) to the end, (ii) eliminate first the variables that will produce fewer bindings, and (iii) avoid if possible to bind variables not connected to anyone already bound. For the Ring, it was shown [6] that taking the minimum length of the L∗ ranges of all the loci in Tx was a good predictor to choose the variable with fewest bindings. They also showed that adaptive VEOs, which choose the next variable to eliminate only after eliminating the current one, and considering the range lengths after previous bindings (which differ in each branch) outperforms static VEOs, which define a fixed variable ordering from the beginning. To choose a good VEO for the PG-Ring, we classify the variables as follows: 1. Non-lonely node variables: variables in VN that appear in two or more edge patterns. 2. Non-lonely edge variables: variables in VE that appear in two or more edge patterns. 3. Lonely variables: node or edge variables that occur in just one edge pattern. The non-lonely node variables are better choices to eliminate first: binding one of them fixes a node across multiple branches, while fixing an edge constrains only one branch. Accordingly, we first bind the non-lonely node variables, then the non-lonely edge variables, and finally the lonely variables. Within each set, we follow policies (ii) and (iii). For (ii), we estimate the selectivity of the bindings, both for the edge patterns and for the WHERE clauses, to bind first variables with lower selectivity. Selectivity will be the expected fraction of matches for a given variable x and a node of the reduced syntax tree for x, assuming uniformity and independence. The selectivity of AND nodes is then the product of the selectivities of their children, and that of an OR node with children selectivities s1 and s2 is 1 − (1 − s1 )(1 − s2 ). For edge pattern leaves, selectivity is estimated as the length

of the range in the corresponding L∗ sequence divided by N (i.e., the fraction of edges x can match). For the conditions, we proceed as follows. Comparisons of property values. Consider a clause comparing x.π with y.π ′ . We know from the data the ranges [minπ , maxπ ] for x.π and [minπ′ , maxπ′ ] for y.π ′ . Selectivity is estimated as the probability that a point from the two-dimensional rectangle [minπ , maxπ ] × [minπ′ , maxπ′ ] satisfies the comparison. For example, x.π > y.π ′ corresponds to the probability that a point lies above the diagonal line (x = y), assuming uniformity. Further, assuming independence, we multiply this probability by the fraction of 1s in Bπ and by the fraction of 1s in Bπ′ , which are the fractions of node pairs having properties π and π ′ , respectively. In case one of the values is fixed (e.g., x.π > v for a constant v, or y is bound and y.π ′ = v in x.π > y.π ′ ), the selectivity estimation can be refined to the fraction of the range [minπ , maxπ ] that satisfies that condition, (maxπ −v)/(maxπ − minπ +1), times the fraction of 1s in Bπ . A more refined option is to explicitly count the number of points in Mπ within the range defined by the comparison (in our case, [1, +∞] × [v + 1, ∞]) and divide it by n (where n = |N | if x ∈ VN and n = N if x ∈ VE ). This counting takes O(log |Aπ |) time with wavelet trees, which is significant if we have to apply it on every branch. This option is thus applied only on the static VEO. Comparisons of identifiers For comparisons involving the identifiers of two variables, the estimation is analogous but easier. As the values of both variables are in the same range [1, n], equality comparisons are assigned a selectivity of 1/n, inequality comparisons a selectivity of 1 − 1/n, and all other types of comparisons a default selectivity of 0.5. In case one of the identifiers is fixed (e.g., x > v for a constant v, or y is bound to v in x > y), we estimate it by the fraction of range [1, n] that satisfies the condition. Expressions on labels. We similarly use the fraction fℓ of 1s in Bℓ to estimate the selectivity of a query x.ℓ. In case of negations, the correct estimation is 1 − fℓ . For more complex Boolean formulas, we do as with general Boolean expressions. Internal query optimization. Beyond choosing VEOs, we can optimize the Boolean syntax tree that results for each variable x to eliminate: The children of AND nodes are probed left to right, restarting with the leftmost one after each value c in the intersection is found; therefore AND children should be sorted by most selective conditions first (edge patterns and filters can be mixed in this order). Further, range conditions on the same variable x or a property x.π should be combined into one (like x.π ≥ a AND x.π ≤ b into a ≤ x.π ≤ b), because the grid query is more efficient than the alternation complexity.

C

The LSQB Benchmark

The Labelled Subgraph Query Benchmark (LSQB) [35] is a subgraph matching benchmark designed to evaluate the performance of database management systems in graphs with labels in nodes and edges. The benchmark uses the LDBC

hasMember

Forum

Person

isLocatedIn

City

isPartOf

Country

p1: Person

containerOf

knows

p2: Person

hasCreator replyOf

hasTag

Post

Tag

Comment

hasType

hasCreator replyOf

TagClass

Comment

Q1 Country isPartOf

Tag

isPartOf

c1: City

isPartOf

li: Person

likes

Message

isLocatedIn

isLocatedIn

knows

p1: Person knows

hasTag

c3: City

c2: City

isLocatedIn

Post

Q2

p2: Person

hasCreator

cr: Person

replyOf

p3: Person Comment

knows

Q3

Q4 p1: Person knows

t2: Tag

t1: Tag

̸= t1

hasTag

Message

hasTag replyOf

Comment

Q5

p2: Person knows

p3: Person hasInterest ̸= p1

Tag

Q6

Fig. 7: The first six queries from the Labelled Subgraph Queries Benchmark.

social network generator [19] to create the dataset. In our case, we set the scalability factor to 10, obtaining 35,496,603 nodes and 219,425,671 edges. Each node can be given one of 14 possible labels, whereas each edge can be given one of 15 possible labels. In this benchmark, nodes and edges do not have properties. The LSQB benchmark consists of nine queries, where the last three contain optional edges and negations of relationships. The PG-Ring does not support this kind of operators, thus we limit the benchmark to the first six queries. Fig. 7 shows the chosen queries and Fig. 8 the average query times obtained.

D

Systems Compared

In the evaluation, we use these systems with the following settings: – Umbra [42]: A system based on relational tables whose query plans use binary joins but may introduce wco plans for some sub-queries. – DuckDB [46]: A non-wco relational database that stores data in columnar format. It uses vectorized and pipelined models to produce optimized binary join plans. – Kùzu [29]: A graph query engine that stores property graphs using unsorted adjacency lists. It employs cost-based dynamic programming to generate execution plans that combine wco and pairwise joins.

System

Limit

Q1

Q2

Q3

Q4

Q5

Q6

Umbra

10 1,000

1,912.38 1,913.06

465.54 474.24

162.26 5,038.58 2,432.72 162.04 5,028.82 2,437.34

45.28 46.62

DuckDB

10 1,000

3,071.52 3,109.04

446.38 451.96

299.24 5,138.54 3,199.64 137.22 301.62 5,196.26 3,202.10 138.52

Kuzu

10 1,000

11,207.38 1,394.62 115,999.14 2,260.88 2,772.04 11,440.90 1,406.14 116,053.84 2,279.18 2,784.96

Neo4j

10 1,000

8.92 56.22

3.66 32.08

4,439.06 TO

3.76 35.88

5.82 33.96

2.26 27.28

Memgraph

10 1,000

4.38 17.26

37.88 192.38

65,980.02 TO

36.84 50.88

8.00 9.46

1.72 4.50

MillDB

10 1,000

5.79 31.34

2.25 77.91

15.80 1,368.47

2.70 3.44

1.47 3.14

1.84 1.93

PG-Ring

10 1,000

259.25 8,810.63

1.45 173.70

0.66 24.17

3.24 114.01 150.87 1,135.47

0.05 2.48

61.06 65.10

Fig. 8: Average times (in msec) of queries, with limit of 10 and 1,000 results.

– Neo4j [41]: A widely used graph database that implements the property graph model. Its execution plans are based on index lookups, expand operators, and pairwise joins. – Memgraph [34]: An in-memory graph database that stores the property graph model using adjacency structures. Query plans rely on traversal-based operators combined with pairwise joins. – MillDB [51]: A graph database that supports the property graph model using a quad-based storage. The query plans combine wco joins and pairwise joins. – PG-Ring: the system presented in this work. We ensure that all systems run in a single-threaded execution. All the systems use non-repeated edge semantics, except MillDB and PG-Ring. For this reason, for those two systems the queries of LSQB are modified adding in the WHERE clause additional expressions to avoid repeated edges. As Kùzu, PG-Ring does not support undirected edges in the query pattern. To support all LSQB queries, we handle undirected edges by storing them in both directions.

E

The Wikidata Benchmark

We convert a Wikidata knowledge graph [50] into a property graph as follows. Each Wikidata entity is modeled as a node, with the exception of those referenced

by the instance-of property, which are converted into node labels. Those literals (e.g. strings, numbers, coordinates, dates) linked to a node are represented as properties of the node. The remaining RDF properties are modeled as relationships whose label is the RDF property itself. The edges store the temporal, numeric, and geospatial properties obtained from their qualifiers. In addition, we verify that the added values match the corresponding property type. The resulting graph consists of 108,882,974 nodes, which can take on 102,718 distinct labels and have 10,569 different properties. In total, there are 719,656,925 edges, featuring 1,640 possible edge labels and 603 distinct properties. We obtained 19,605 queries from the Wikidata SPARQL query log by extracting BGPs with filters and applying a similar transformation to the BGPs (and filters) in order to match the transformed knowledge graph. Queries that are syntactically similar (e.g., same graph pattern, same filter types) are grouped together, regardless of constants and operands. After grouping them, we choose a representative sample of 1,000 queries, with a minimum of one per group and distributing the rest in proportion to the number of elements in each group.

F

Cold Cache Scenario

For fairness to disk-based systems, we reported the averaged time in a warm cache scenario. We have also evaluated the systems in a cold cache setup: before the execution of each set of queries for each system, we clean the cache with the command echo 3 | sudo tee /proc/sys/vm/drop caches. Then, we measure the running times of a single execution of each query. Fig. 9 details the results on both benchmarks in the cold cache scenario. We can observe how the performance of disk-based systems degrades with respect to the warm cache scenario. This time, the outstanding systems in the LSQB benchmark are PG-Ring (mostly when limiting to 10 output tuples) and Memgraph (mostly when limiting to 1000 outputs). On the Wikidata benchmark, the cold cache setup affects sharply the performance of both MillDB and Neo4j, as they are disk-based.

System

Limit

Q1

Q2

Q3

Umbra

10 37,806.90 1,000 37,875.42

2,235.14 2,233.34

188.86 14,835.52 195.78 14,842.23

2,547.69 426.12 2,537.86 423.26

DuckDB

10 12,321.13 1,000 11,929.72

884.21 867.36

297.54 11,795.84 301.84 11,665.70

4,263.62 182.53 4,289.34 166.20

Kuzu

10 16,416.00 1,000 16,404.10

Neo4j

10 1,000

Memgraph

10 1,000

MillDB

PG-Ring

3,140.02 118,911.93 3,174.60 118,559.12

2,316.14 760.80 170,786.27 6,115.30 23,148.54 TO

Q4

3,314.12 3,358.14

Q5

Q6

3,875.07 140.09 3,798.43 152.60

407.12 14,725.46 113.13 4,135.32 24,139.87 442.88

36.92 113.78

41,272.58 TO

24.26 27.68

6.42 6.64

10 1,000

1,751.43 995.05 6,687.00 33,693.54

687.08 2,287.22

273.11 465.04

7.86 157.41 71.40 165.09

10 1,000

262.09 8,804.49

1.22 28.82

1.46 157.19

21.08 28.14

3.04 180.28

102

117.94 1,136.67

1.64 4.10

0.13 4.37

600

Pre-filter Neo4j

101 MillDB

Time (msec.)

Avg Time (sec.)

0.694

400

200

Post-filter PG-Ring

100 0

20

40

32.18

0.758

177.1

0.470

0 60 80 100 120 140 Space (GB)

PG-Ring Post-fil. Pre-fil. MillDB

Neo4j

System

Fig. 9: Results in the cold cache scenario. On top the detailed execution times (in msec) for the six queries of LSQB. On the bottom, the space-time trade-off and times distribution on the Wikidata benchmark. The numbers of the boxplots indicates the median of execution times.

Related documents

• SORT: A Systematically Optimized Ranking Transformer for Industrial-scale Recommenders#798788
• SORT: A Systematically Optimized Ranking Transformer for Industrial-scale Recommenders#797374
• Measuring Progress in Reasoning Toward Mathematical Discovery with Automatic Verification#999211
• Query-Aware Token Budgeting for Efficient Late-Interaction Visual Document Retrieval#975313
• Length Generalization for Transformers via Compression#986478