This is an automated email from the ASF dual-hosted git repository.
afs pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/jena.git
The following commit(s) were added to refs/heads/main by this push:
new 5425c9713b Limit path flatten max length
5425c9713b is described below
commit 5425c9713b7e183d498f134aa92b1ac668006a62
Author: Rob Vesse <[email protected]>
AuthorDate: Fri Sep 25 10:50:25 2026 +0100
Limit path flatten max length
When TransformPathFlatten/TransformPathFlattenAlgebra run they expand
some paths of the form :x :p{N,M} ?y into multiple triple patterns
within a BGP e.g. :x :p ?q0 . ?q0 :p ?y etc. This is safe for short
values of M but can result in extremely large expansions if M is a large
value. The large expansion is unlikely to make the query run any faster
and a sufficiently large value can cause the query optimiser to fail with
memory/stack issues. This commit introduces a new static control for
the maximum expansion length capped at 5 by default and does not apply
full expansion to anything longer than that.
---
.../optimize/TransformPathFlattenAlgebra.java | 15 +-
.../org/apache/jena/sparql/path/PathCompiler.java | 75 +++++++---
.../algebra/optimize/TestTransformPathFlatten.java | 155 ++++++++++++++++++++-
3 files changed, 224 insertions(+), 21 deletions(-)
diff --git
a/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformPathFlattenAlgebra.java
b/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformPathFlattenAlgebra.java
index c84545f5dc..7ca46df3a5 100644
---
a/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformPathFlattenAlgebra.java
+++
b/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformPathFlattenAlgebra.java
@@ -175,7 +175,7 @@ public class TransformPathFlattenAlgebra extends
TransformCopy {
@Override
public void visit(P_Mod pathMod) {
if (pathMod.isFixedLength()) {
- if (pathMod.getFixedLength() > 0) {
+ if (PathCompiler.isReducibleLength(pathMod.getFixedLength())) {
// Treat as a fixed length path and convert that way
instead
Path p = PathFactory.pathFixedLength(pathMod.getSubPath(),
pathMod.getFixedLength());
Op op = transformPath(null, subject, p, object);
@@ -221,6 +221,13 @@ public class TransformPathFlattenAlgebra extends
TransformCopy {
if ( pathMod.getMin() > pathMod.getMax() )
throw new ARQException("Bad path: " + pathMod);
+ // If the max length is very large the reduction is unlikely to
benefit performance and just generates an
+ // unnecessarily large algebra tree
+ if (!PathCompiler.isReducibleLength(pathMod.getMax())) {
+ result = null;
+ return;
+ }
+
Op op = null;
for ( long i = pathMod.getMin() ; i <= pathMod.getMax() ; i++ ) {
Path p = PathFactory.pathFixedLength(pathMod.getSubPath(), i);
@@ -232,6 +239,12 @@ public class TransformPathFlattenAlgebra extends
TransformCopy {
@Override
public void visit(P_FixedLength pFixedLength) {
+ if (!PathCompiler.isReducibleLength(pFixedLength.getCount())) {
+ // Don't transform zero length or too long paths
+ result = null;
+ return;
+ }
+
Op op = null;
Var v1 = null;
for ( int i = 0 ; i < pFixedLength.getCount() ; i++ ) {
diff --git
a/jena-arq/src/main/java/org/apache/jena/sparql/path/PathCompiler.java
b/jena-arq/src/main/java/org/apache/jena/sparql/path/PathCompiler.java
index fdeab79443..4d2e31318a 100644
--- a/jena-arq/src/main/java/org/apache/jena/sparql/path/PathCompiler.java
+++ b/jena-arq/src/main/java/org/apache/jena/sparql/path/PathCompiler.java
@@ -33,6 +33,21 @@ import org.apache.jena.sparql.core.Var;
import org.apache.jena.sparql.core.VarAlloc;
public class PathCompiler {
+ /**
+ * Default maximum length value used for the {@link
#MAX_LENGTH_PATH_FOR_REDUCTION} control
+ */
+ public static final int DEFAULT_MAX_LENGTH = 5;
+ /**
+ * Specifies the maximum length (inclusive) of a path that will be reduced
by expanding it into individual
+ * invocations of the path expression linked by intermediate variables.
Defaults to {@value #DEFAULT_MAX_LENGTH}.
+ * <p>
+ * This control prevents a query using a path like {@code :x :p{N} :y}
with a large value of {@code N} being
+ * expanded into a massive algebra tree that yields no performance
benefits.
+ * </p>
+ * @see #isReducibleLength(long)
+ */
+ public static int MAX_LENGTH_PATH_FOR_REDUCTION = DEFAULT_MAX_LENGTH;
+
// Convert to work on OpPath.
// Need pre (and post) BGPs.
@@ -126,16 +141,10 @@ public class PathCompiler {
if ( path instanceof P_FixedLength pFixedLen ) {
long N = pFixedLen.getCount();
- if ( N > 0 ) {
+ if (isReducibleLength(N)) {
// Don't do {0}
- Node stepStart = startNode;
-
- for ( long i = 0 ; i < N - 1 ; i++ ) {
- Node v = varAlloc.allocVar();
- reduce(x, varAlloc, stepStart, pFixedLen.getSubPath(), v);
- stepStart = v;
- }
- reduce(x, varAlloc, stepStart, pFixedLen.getSubPath(),
endNode);
+ // Also if the path is too long the reduction won't generate
any performance benefits
+ reduceFixedLength(x, varAlloc, startNode, endNode, N,
pFixedLen.getSubPath());
return;
}
}
@@ -143,15 +152,8 @@ public class PathCompiler {
if ( path instanceof P_Mod pMod ) {
if ( pMod.isFixedLength() && pMod.getFixedLength() > 0 ) {
long N = pMod.getFixedLength();
- if ( N > 0 ) {
- Node stepStart = startNode;
-
- for ( long i = 0 ; i < N - 1 ; i++ ) {
- Node v = varAlloc.allocVar();
- reduce(x, varAlloc, stepStart, pMod.getSubPath(), v);
- stepStart = v;
- }
- reduce(x, varAlloc, stepStart, pMod.getSubPath(), endNode);
+ if (isReducibleLength(N)) {
+ reduceFixedLength(x, varAlloc, startNode, endNode, N,
pMod.getSubPath());
return;
}
}
@@ -199,4 +201,41 @@ public class PathCompiler {
// Nothing can be done.
x.add(new TriplePath(startNode, path, endNode));
}
+
+ /**
+ * Checks whether a given length of path is considered reducible
+ * <p>
+ * Only paths that are non-zero length and less than, or equal to, the
configured
+ * {@link #MAX_LENGTH_PATH_FOR_REDUCTION} (default {@value
#DEFAULT_MAX_LENGTH}) are considered reducible. Anything
+ * else is left as-is as either reduction would change semantics (for
zero-length paths), or could lead to very
+ * large algebra tree which would negatively impact performance.
+ * </p>
+ * @param N Path length
+ * @return True if reducible, false otherwise
+ */
+ public static boolean isReducibleLength(long N) {
+ return N > 0 && N <= MAX_LENGTH_PATH_FOR_REDUCTION;
+ }
+
+ /**
+ * Reduces a fixed length path by expanding the {@code n} steps into
individual path invocations with intermediate
+ * variables.
+ * @param x Path block to append into
+ * @param varAlloc Variable allocator
+ * @param startNode Start node
+ * @param endNode End node
+ * @param n Fixed path length
+ * @param subPath Sub path to use in each expanded step
+ */
+ private static void reduceFixedLength(PathBlock x, VarAlloc varAlloc, Node
startNode, Node endNode, long n,
+ Path subPath) {
+ Node stepStart = startNode;
+
+ for (long i = 0; i < n - 1 ; i++ ) {
+ Node v = varAlloc.allocVar();
+ reduce(x, varAlloc, stepStart, subPath, v);
+ stepStart = v;
+ }
+ reduce(x, varAlloc, stepStart, subPath, endNode);
+ }
}
diff --git
a/jena-arq/src/test/java/org/apache/jena/sparql/algebra/optimize/TestTransformPathFlatten.java
b/jena-arq/src/test/java/org/apache/jena/sparql/algebra/optimize/TestTransformPathFlatten.java
index 67ec934f81..daa0fe29d8 100644
---
a/jena-arq/src/test/java/org/apache/jena/sparql/algebra/optimize/TestTransformPathFlatten.java
+++
b/jena-arq/src/test/java/org/apache/jena/sparql/algebra/optimize/TestTransformPathFlatten.java
@@ -455,6 +455,157 @@ public class TestTransformPathFlatten {
assertThrowsExactly(ARQException.class, ()->testAlgebraTransform(op1,
null));
}
+ @Test public void pathFlatten_n_to_m_10() {
+ Op op1 = path("?x", ":p{5}", ":T1");
+ Op expected = op("""
+ (bgp
+ (triple ?x <http://example/p> ??P0)
+ (triple ??P0 <http://example/p> ??P1)
+ (triple ??P1 <http://example/p> ??P2)
+ (triple ??P2 <http://example/p> ??P3)
+ (triple ??P3 <http://example/p>
<http://example/T1>)
+ )
+ """
+ );
+ testDefaultTransform(op1, expected);
+ }
+
+ @Test public void pathFlatten_n_to_m_10_algebra() {
+ Op op1 = path("?x", ":p{5}", ":T1");
+ Op expected = op("""
+ (join
+ (join
+ (join
+ (join
+ (triple ?x <http://example/p> ??Q0)
+ (triple ??Q0 <http://example/p> ??Q1))
+ (triple ??Q1 <http://example/p> ??Q2))
+ (triple ??Q2 <http://example/p> ??Q3))
+ (triple ??Q3 <http://example/p>
<http://example/T1>))
+ """
+ );
+ testAlgebraTransform(op1, expected);
+ }
+
+ @Test public void pathFlatten_n_to_m_11() {
+ Op op1 = path("?x", ":p{11}", ":T1");
+ testDefaultTransform(op1, null);
+ }
+
+ @Test public void pathFlatten_n_to_m_11_algebra() {
+ Op op1 = path("?x", ":p{11}", ":T1");
+ testAlgebraTransform(op1, null);
+ }
+
+ @Test public void pathFlatten_n_to_m_12() {
+ try {
+ // Reconfiguring the maximum permitted path length for reduction
should prevent this query from being
+ // optimised
+ PathCompiler.MAX_LENGTH_PATH_FOR_REDUCTION = 3;
+ Op op1 = path("?x", ":p{5}", ":T1");
+ testDefaultTransform(op1, null);
+ } finally {
+ PathCompiler.MAX_LENGTH_PATH_FOR_REDUCTION =
PathCompiler.DEFAULT_MAX_LENGTH;
+ }
+ }
+
+ @Test public void pathFlatten_n_to_m_12_algebra() {
+ try {
+ // Reconfiguring the maximum permitted path length for reduction
should prevent this query from being
+ // optimised
+ PathCompiler.MAX_LENGTH_PATH_FOR_REDUCTION = 3;
+ Op op1 = path("?x", ":p{5}", ":T1");
+ testAlgebraTransform(op1, null);
+ } finally {
+ PathCompiler.MAX_LENGTH_PATH_FOR_REDUCTION =
PathCompiler.DEFAULT_MAX_LENGTH;
+ }
+ }
+
+ @Test
+ public void pathFlatten_n_to_m_huge_01() {
+ Op op1 = path(":T1", ":p{1000000}", "?x");
+ testDefaultTransform(op1, null);
+ }
+
+ @Test
+ public void pathFlatten_n_to_m_huge_02() {
+ Op op1 = path(":T1", ":p{1, 1000000}", "?x");
+ Op expected = op("""
+ (sequence
+ (bgp (triple <http://example/T1>
<http://example/p> ??P0))
+ (path ??P0 (mod 0 999999
<http://example/p>) ?x))
+ """);
+ testDefaultTransform(op1, expected);
+ }
+
+ @Test
+ public void pathFlatten_n_to_m_huge_03() {
+ Op op1 = path(":T1", ":p{100,1000000}", "?x");
+ Op expected = op("""
+ (sequence
+ (path <http://example/T1> (pathN 100
<http://example/p>) ??P0)
+ (path ??P0 (mod 0 999900
<http://example/p>) ?x))
+ """);
+ testDefaultTransform(op1, expected);
+ }
+
+ @Test
+ public void pathFlatten_n_to_m_huge_04() {
+ Op op1 = path(":T1", ":p{1000000,}", "?x");
+ Op expected = op("""
+ (sequence
+ (path <http://example/T1> (pathN 1000000
<http://example/p>) ??P0)
+ (path ??P0 (pathN* <http://example/p>) ?x))
+ """);
+ testDefaultTransform(op1, expected);
+ }
+
+ @Test
+ public void pathFlatten_n_to_m_huge_05() {
+ Op op1 = path(":T1", ":p{999999, 1000000}", "?x");
+ Op expected = op("""
+ (sequence
+ (path <http://example/T1> (pathN 999999
<http://example/p>) ??P0)
+ (path ??P0 (mod 0 1 <http://example/p>) ?x))
+ """);
+ testDefaultTransform(op1, expected);
+ }
+
+ @Test
+ public void pathFlatten_n_to_m_huge_01_algebra() {
+ Op op1 = path(":T1", ":p{1000000}", "?x");
+ testAlgebraTransform(op1, null);
+ }
+
+ @Test
+ public void pathFlatten_n_to_m_huge_02_algebra() {
+ Op op1 = path(":T1", ":p{1, 1000000}", "?x");
+ testAlgebraTransform(op1, null);
+ }
+
+ @Test
+ public void pathFlatten_n_to_m_huge_03_algebra() {
+ Op op1 = path(":T1", ":p{100,1000000}", "?x");
+ testAlgebraTransform(op1, null);
+ }
+
+ @Test
+ public void pathFlatten_n_to_m_huge_04_algebra() {
+ Op op1 = path(":T1", ":p{1000000,}", "?x");
+ Op expected = op("""
+ (sequence
+ (path <http://example/T1> (pathN 1000000
<http://example/p>) ??Q0)
+ (path ??Q0 (pathN* <http://example/p>) ?x))
+ """);
+ testAlgebraTransform(op1, expected);
+ }
+
+ @Test
+ public void pathFlatten_n_to_m_huge_05_algebra() {
+ Op op1 = path(":T1", ":p{999999, 1000000}", "?x");
+ testAlgebraTransform(op1, null);
+ }
+
private static Op path(String s, String pathStr, String o) {
Path path = PathParser.parse(pathStr, prologue);
TriplePath tp = new TriplePath(SSE.parseNode(s), path,
SSE.parseNode(o));
@@ -495,10 +646,10 @@ public class TestTransformPathFlatten {
}
if ( opExpected == null ) {
// Expect no transformation to be applied so input should be same
as transformation output
- assertEquals(opInput, opTransformed);
+ assertEquals(opInput, opTransformed, "No transform expected but
one occurred");
} else {
// Expect transformation to have been applied
- assertEquals(opExpected, opTransformed);
+ assertEquals(opExpected, opTransformed, "Transform not as
expected");
}
}
