Skip to content

Commit 87eb1fa

Browse files
glasstigerglasstiger
authored
Merge branch 'master' into nw_quotes
2 parents 0aa54ce + 42483f0 commit 87eb1fa

File tree

13 files changed

+482
-97
lines changed

13 files changed

+482
-97
lines changed

‎core/src/main/java/io/questdb/griffin/ExpressionTreeBuilder.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -30,7 +30,7 @@
3030
import java.util.ArrayDeque;
3131
import java.util.Deque;
3232

33-
final class ExpressionTreeBuilder implements ExpressionParserListener {
33+
public final class ExpressionTreeBuilder implements ExpressionParserListener {
3434

3535
private final Deque<ExpressionNode> argStack = new ArrayDeque<>();
3636
private final Deque<QueryModel> modelStack = new ArrayDeque<>();
@@ -70,7 +70,7 @@ public void onNode(ExpressionNode node) throws SqlException {
7070
argStack.push(node);
7171
}
7272

73-
ExpressionNode poll() {
73+
public ExpressionNode poll() {
7474
return argStack.poll();
7575
}
7676

‎core/src/main/java/io/questdb/griffin/FunctionParser.java‎

Lines changed: 22 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -312,6 +312,9 @@ public Function parseFunction(
312312
}
313313
try {
314314
this.metadata = metadata;
315+
if (node != null) {
316+
node.reassociateConstants(configuration.getCairoSqlLegacyOperatorPrecedence());
317+
}
315318
try {
316319
traverseAlgo.traverse(node, this);
317320
} catch (Exception e) {
@@ -374,9 +377,19 @@ public void visit(ExpressionNode node) throws SqlException {
374377
mutableArgPositions.clear();
375378
mutableArgPositions.setPos(argCount);
376379
for (int n = 0; n < argCount; n++) {
377-
final Function arg = functionStack.poll();
380+
Function arg = functionStack.poll();
378381
final int pos = positionStack.pop();
379382

383+
try {
384+
if (arg != null && arg.isConstant() && arg.extendedOps() == null && !(arg instanceof TypeConstant)) {
385+
arg = functionToConstant(arg);
386+
}
387+
} catch (Throwable th) {
388+
// these args were already popped from functionStack
389+
Misc.freeObjList(mutableArgs);
390+
throw th;
391+
}
392+
380393
mutableArgs.setQuick(n, arg);
381394
mutableArgPositions.setQuick(n, pos);
382395

@@ -1307,7 +1320,14 @@ private int extractYearFromTimestamp(CharSequence timestampStr) {
13071320
}
13081321

13091322
private Function functionToConstant(Function function) {
1310-
Function newFunction = functionToConstant0(function);
1323+
Function newFunction;
1324+
try {
1325+
newFunction = functionToConstant0(function);
1326+
} catch (Throwable th) {
1327+
function.close();
1328+
throw th;
1329+
}
1330+
13111331
// Sometimes functionToConstant0 returns same instance as passed in parameter
13121332
if (newFunction != function) {
13131333
// and we want to close underlying function only in case it's different form returned newFunction

‎core/src/main/java/io/questdb/griffin/OperatorExpression.java‎

Lines changed: 36 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -38,23 +38,23 @@ public final class OperatorExpression {
3838
add(new OperatorExpression(Operator.Dot, 1, false, BINARY));
3939
add(new OperatorExpression(Operator.DoubleColon, 2, true, BINARY));
4040
// arithmetic operators, UnaryMinus and UnaryComplement defined above are strongest from this block
41-
add(new OperatorExpression(Operator.Multiplication, 3, true, BINARY));
41+
add(new OperatorExpression(Operator.Multiplication, 3, true, BINARY, true, true, true));
4242
add(new OperatorExpression(Operator.Division, 3, true, BINARY));
4343
add(new OperatorExpression(Operator.Modulo, 3, true, BINARY));
4444

45-
add(new OperatorExpression(Operator.Plus, 4, true, BINARY));
45+
add(new OperatorExpression(Operator.Plus, 4, true, BINARY, true, true, true));
4646
add(new OperatorExpression(Operator.Minus, 4, true, BINARY));
4747
// IP operators
4848
add(new OperatorExpression(Operator.IpContainsStrictLeft, 4, true, BINARY));
4949
add(new OperatorExpression(Operator.IpContainsStrictRight, 4, true, BINARY));
5050
add(new OperatorExpression(Operator.IpContainsLeft, 4, true, BINARY));
5151
add(new OperatorExpression(Operator.IpContainsRight, 4, true, BINARY));
5252
// concatenation
53-
add(new OperatorExpression(Operator.Concatenation, 5, true, BINARY));
53+
add(new OperatorExpression(Operator.Concatenation, 5, true, BINARY, true, true, false));
5454
// bitwise operators
55-
add(new OperatorExpression(Operator.BitAnd, 8, true, BINARY));
56-
add(new OperatorExpression(Operator.BitXor, 9, true, BINARY));
57-
add(new OperatorExpression(Operator.BitOr, 10, true, BINARY));
55+
add(new OperatorExpression(Operator.BitAnd, 8, true, BINARY, true, true, true));
56+
add(new OperatorExpression(Operator.BitXor, 9, true, BINARY, true, true, true));
57+
add(new OperatorExpression(Operator.BitOr, 10, true, BINARY, true, true, true));
5858
// set operators
5959
add(new OperatorExpression(Operator.In, 7, true, SET, false));
6060
add(new OperatorExpression(Operator.Between, 7, true, SET, false)); // ternary operator
@@ -73,8 +73,8 @@ public final class OperatorExpression {
7373
add(new OperatorExpression(Operator.ILikeSqlStyle, 7, true, BINARY, false));
7474
// logical operators
7575
add(new OperatorExpression(Operator.BinaryNot, 11, true, UNARY, false));
76-
add(new OperatorExpression(Operator.BinaryAnd, 11, true, BINARY, false));
77-
add(new OperatorExpression(Operator.BinaryOr, 11, true, BINARY, false));
76+
add(new OperatorExpression(Operator.BinaryAnd, 11, true, BINARY, false, true, true));
77+
add(new OperatorExpression(Operator.BinaryOr, 11, true, BINARY, false, true, true));
7878
}});
7979
private static final OperatorRegistry registry = new OperatorRegistry(
8080
new ObjList<>() {{
@@ -85,22 +85,22 @@ public final class OperatorExpression {
8585
add(new OperatorExpression(Operator.Dot, 1, false, BINARY));
8686
add(new OperatorExpression(Operator.DoubleColon, 2, true, BINARY));
8787
// arithmetic operators, UnaryMinus and UnaryComplement defined above are strongest from this block
88-
add(new OperatorExpression(Operator.Multiplication, 4, true, BINARY));
88+
add(new OperatorExpression(Operator.Multiplication, 4, true, BINARY, true, true, true));
8989
add(new OperatorExpression(Operator.Division, 4, true, BINARY));
9090
add(new OperatorExpression(Operator.Modulo, 4, true, BINARY));
91-
add(new OperatorExpression(Operator.Plus, 5, true, BINARY));
91+
add(new OperatorExpression(Operator.Plus, 5, true, BINARY, true, true, true));
9292
add(new OperatorExpression(Operator.Minus, 5, true, BINARY));
9393
// IP operators
9494
add(new OperatorExpression(Operator.IpContainsStrictLeft, 6, true, BINARY));
9595
add(new OperatorExpression(Operator.IpContainsStrictRight, 6, true, BINARY));
9696
add(new OperatorExpression(Operator.IpContainsLeft, 6, true, BINARY));
9797
add(new OperatorExpression(Operator.IpContainsRight, 6, true, BINARY));
9898
// concatenation
99-
add(new OperatorExpression(Operator.Concatenation, 7, true, BINARY));
99+
add(new OperatorExpression(Operator.Concatenation, 7, true, BINARY, true, true, false));
100100
// bitwise operators
101-
add(new OperatorExpression(Operator.BitAnd, 8, true, BINARY));
102-
add(new OperatorExpression(Operator.BitXor, 9, true, BINARY));
103-
add(new OperatorExpression(Operator.BitOr, 10, true, BINARY));
101+
add(new OperatorExpression(Operator.BitAnd, 8, true, BINARY, true, true, true));
102+
add(new OperatorExpression(Operator.BitXor, 9, true, BINARY, true, true, true));
103+
add(new OperatorExpression(Operator.BitOr, 10, true, BINARY, true, true, true));
104104
// set operators
105105
add(new OperatorExpression(Operator.In, 11, false, SET, false));
106106
add(new OperatorExpression(Operator.Between, 11, false, SET, false)); // ternary operator
@@ -119,30 +119,34 @@ public final class OperatorExpression {
119119
add(new OperatorExpression(Operator.ILikeSqlStyle, 13, true, BINARY, false));
120120
// logical operators
121121
add(new OperatorExpression(Operator.BinaryNot, 14, false, UNARY, false));
122-
add(new OperatorExpression(Operator.BinaryAnd, 15, true, BINARY, false));
123-
add(new OperatorExpression(Operator.BinaryOr, 16, true, BINARY, false));
122+
add(new OperatorExpression(Operator.BinaryAnd, 15, true, BINARY, false, true, true));
123+
add(new OperatorExpression(Operator.BinaryOr, 16, true, BINARY, false, true, true));
124124
add(new OperatorExpression(Operator.Colon, 17, false, BINARY));
125125
}});
126+
final boolean associative;
127+
final boolean commutative;
126128
final boolean leftAssociative;
127129
final OperatorExpression.Operator operator;
128130
final int precedence;
129131
final boolean symbol;
130132
final int type;
131133

132134
private OperatorExpression(OperatorExpression.Operator operator, int precedence, boolean leftAssociative, int type, boolean symbol) {
133-
this.operator = operator;
134-
this.precedence = precedence;
135-
this.leftAssociative = leftAssociative;
136-
this.type = type;
137-
this.symbol = symbol;
135+
this(operator, precedence, leftAssociative, type, symbol, false, false);
138136
}
139137

140138
private OperatorExpression(OperatorExpression.Operator operator, int precedence, boolean leftAssociative, int type) {
139+
this(operator, precedence, leftAssociative, type, true, false, false);
140+
}
141+
142+
private OperatorExpression(OperatorExpression.Operator operator, int precedence, boolean leftAssociative, int type, boolean symbol, boolean associative, boolean commutative) {
141143
this.operator = operator;
142144
this.precedence = precedence;
143145
this.leftAssociative = leftAssociative;
144146
this.type = type;
145-
this.symbol = true;
147+
this.symbol = symbol;
148+
this.associative = associative;
149+
this.commutative = commutative;
146150
}
147151

148152
public static OperatorRegistry chooseRegistry(boolean cairoSqlLegacyOperatorPrecedence) {
@@ -157,12 +161,20 @@ public static OperatorRegistry getRegistry() {
157161
return registry;
158162
}
159163

164+
public String getToken() {
165+
return operator.token;
166+
}
167+
160168
public int getType() {
161169
return type;
162170
}
163171

164-
public String getToken() {
165-
return operator.token;
172+
public boolean isAssociative() {
173+
return associative;
174+
}
175+
176+
public boolean isCommutative() {
177+
return commutative;
166178
}
167179

168180
public boolean greaterPrecedence(int otherPrecedence) {

‎core/src/main/java/io/questdb/griffin/model/ExpressionNode.java‎

Lines changed: 138 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -58,7 +58,13 @@ public class ExpressionNode implements Mutable, Sinkable {
5858
public boolean implemented;
5959
public boolean innerPredicate = false;
6060
public int intrinsicValue = IntrinsicModel.UNDEFINED;
61+
public boolean isConstantExpression;
6162
public ExpressionNode lhs;
63+
// The expression parser (ExpressionParser.onNode) guarantees:
64+
// - paramCount == 1: rhs is non-null, lhs is null.
65+
// - paramCount == 2: both lhs and rhs are non-null.
66+
// - paramCount > 2: children are stored in args; each entry is non-null.
67+
// No later transformation violates these invariants.
6268
public int paramCount;
6369
public int position;
6470
public int precedence;
@@ -258,6 +264,7 @@ public static ExpressionNode deepClone(final ObjectPool<ExpressionNode> pool, fi
258264
copy.type = node.type;
259265
copy.paramCount = node.paramCount;
260266
copy.intrinsicValue = node.intrinsicValue;
267+
copy.isConstantExpression = node.isConstantExpression;
261268
copy.innerPredicate = node.innerPredicate;
262269
copy.implemented = node.implemented;
263270
copy.windowExpression = node.windowExpression; // shallow copy - WindowColumn is pooled
@@ -275,6 +282,7 @@ public void clear() {
275282
type = UNKNOWN;
276283
paramCount = 0;
277284
intrinsicValue = IntrinsicModel.UNDEFINED;
285+
isConstantExpression = false;
278286
queryModel = null;
279287
innerPredicate = false;
280288
implemented = false;
@@ -295,6 +303,7 @@ public ExpressionNode copyFrom(final ExpressionNode other) {
295303
this.type = other.type;
296304
this.paramCount = other.paramCount;
297305
this.intrinsicValue = other.intrinsicValue;
306+
this.isConstantExpression = other.isConstantExpression;
298307
this.innerPredicate = other.innerPredicate;
299308
this.windowExpression = other.windowExpression;
300309
return this;
@@ -327,6 +336,135 @@ public ExpressionNode of(int type, CharSequence token, int precedence, int posit
327336
return this;
328337
}
329338

339+
/**
340+
* Walks this expression tree bottom-up and regroups adjacent constant
341+
* operands of associative (and, where needed, commutative) binary operators
342+
* so that constant folding can collapse them into a single constant.
343+
*
344+
* <p>For example, {@code (col + 1) + 4} is rewritten to {@code col + (1 + 4)},
345+
* which the function parser then folds to {@code col + 5}.</p>
346+
*
347+
* <p>The method handles four structural patterns. In each pattern, {@code A}
348+
* is a non-constant subtree, {@code C1} and {@code C2} are constant subtrees,
349+
* and {@code op} is the same binary operator at both levels:</p>
350+
*
351+
* <ul>
352+
* <li><b>Pattern A</b> — {@code (A op C1) op C2 → A op (C1 op C2)}.
353+
* Requires only associativity (natural left-associative chain).</li>
354+
* <li><b>Pattern B</b> — {@code (C1 op A) op C2 → A op (C1 op C2)}.
355+
* Also requires commutativity to move {@code A} to the outer position.</li>
356+
* <li><b>Mirror A</b> — {@code C2 op (A op C1) → A op (C2 op C1)}.
357+
* Also requires commutativity to swap the outer operands.</li>
358+
* <li><b>Mirror B</b> — {@code C2 op (C1 op A) → (C2 op C1) op A}.
359+
* Requires only associativity (pure regrouping).</li>
360+
* </ul>
361+
*
362+
* <p>The rewrite is purely structural: it relinks existing {@link ExpressionNode}
363+
* instances without allocating new nodes.</p>
364+
*
365+
* @return {@code true} if this subtree is entirely constant (every leaf is a
366+
* constant and every interior node is a binary operation on constants),
367+
* {@code false} otherwise
368+
*/
369+
public boolean reassociateConstants(boolean cairoSqlLegacyOperatorPrecedence) {
370+
if (type == CONSTANT) {
371+
isConstantExpression = true;
372+
return true;
373+
}
374+
375+
if (paramCount > 2) {
376+
// For n-ary operators, we reassociate inner arguments without changing the tree structure.
377+
for (int i = 0; i < paramCount; i++) {
378+
// Every args child is guaranteed non-null by the expression parser (ExpressionParser.onNode)
379+
// and no later transformation violates this invariant.
380+
args.getQuick(i).reassociateConstants(cairoSqlLegacyOperatorPrecedence);
381+
}
382+
return false;
383+
}
384+
385+
// Recurse bottom-up. Each child caches its result in isConstantExpression,
386+
// so grandchild constancy checks below are O(1) field reads.
387+
boolean lhsConst = lhs != null && lhs.reassociateConstants(cairoSqlLegacyOperatorPrecedence);
388+
boolean rhsConst = rhs != null && rhs.reassociateConstants(cairoSqlLegacyOperatorPrecedence);
389+
390+
if (type != OPERATION || paramCount != 2) {
391+
return false;
392+
}
393+
394+
if (lhsConst && rhsConst) {
395+
isConstantExpression = true;
396+
return true;
397+
}
398+
399+
// op is never null: every OPERATION node with paramCount == 2 gets its token
400+
// from the operator registry during parsing or optimization, and the same
401+
// registry is selected here via cairoSqlLegacyOperatorPrecedence.
402+
OperatorExpression op = OperatorExpression.chooseRegistry(cairoSqlLegacyOperatorPrecedence).getOperatorDefinition(token);
403+
if (!op.isAssociative()) {
404+
return false;
405+
}
406+
407+
// In every pattern below, !lhsConst (or !rhsConst) guarantees that the
408+
// inner OPERATION node has at most one constant child. So when we confirm
409+
// which grandchild IS constant, the other one is implicitly NOT constant
410+
// — no need to check it.
411+
412+
if (rhsConst && lhs.type == OPERATION
413+
&& lhs.paramCount == 2
414+
&& lhs.token.equals(token)) {
415+
if (lhs.rhs.isConstantExpression) {
416+
// Pattern A: (A op C1) op C2 → A op (C1 op C2)
417+
ExpressionNode inner = lhs;
418+
ExpressionNode a = inner.lhs;
419+
ExpressionNode c1 = inner.rhs;
420+
ExpressionNode c2 = rhs;
421+
this.lhs = a;
422+
this.rhs = inner;
423+
inner.lhs = c1;
424+
inner.rhs = c2;
425+
inner.isConstantExpression = true;
426+
} else if (op.isCommutative() && lhs.lhs.isConstantExpression) {
427+
// Pattern B: (C1 op A) op C2 → A op (C1 op C2)
428+
ExpressionNode inner = lhs;
429+
ExpressionNode c1 = inner.lhs;
430+
ExpressionNode a = inner.rhs;
431+
ExpressionNode c2 = rhs;
432+
this.lhs = a;
433+
this.rhs = inner;
434+
inner.lhs = c1;
435+
inner.rhs = c2;
436+
inner.isConstantExpression = true;
437+
}
438+
439+
return false;
440+
}
441+
442+
if (lhsConst && rhs.type == OPERATION
443+
&& rhs.paramCount == 2
444+
&& rhs.token.equals(token)) {
445+
if (op.isCommutative() && rhs.rhs.isConstantExpression) {
446+
// Mirror A: C2 op (A op C1) → A op (C2 op C1)
447+
ExpressionNode inner = rhs;
448+
ExpressionNode c2 = lhs;
449+
this.lhs = inner.lhs;
450+
inner.lhs = c2;
451+
inner.isConstantExpression = true;
452+
} else if (rhs.lhs.isConstantExpression) {
453+
// Mirror B: C2 op (C1 op A) → (C2 op C1) op A
454+
ExpressionNode inner = rhs;
455+
ExpressionNode c2 = lhs;
456+
ExpressionNode c1 = inner.lhs;
457+
this.rhs = inner.rhs;
458+
this.lhs = inner;
459+
inner.lhs = c2;
460+
inner.rhs = c1;
461+
inner.isConstantExpression = true;
462+
}
463+
}
464+
465+
return false;
466+
}
467+
330468
@Override
331469
public void toSink(@NotNull CharSink<?> sink) {
332470
// note: it's safe to take any registry (new or old) because we don't use precedence here

‎core/src/test/java/io/questdb/test/cairo/ArrayTest.java‎

Lines changed: 4 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -2351,11 +2351,9 @@ public void testProjection() throws Exception {
23512351

23522352
@Test
23532353
public void testRndArrayBadTypes() throws Exception {
2354-
assertMemoryLeak(() -> {
2355-
assertExceptionNoLeakCheck("select rnd_double_array(1, 100.0, 10), rnd_varchar() from long_sequence(5);",
2356-
27, "nanRate must be an integer"
2357-
);
2358-
});
2354+
assertMemoryLeak(() -> assertExceptionNoLeakCheck("select rnd_double_array(1, 100.0, 10), rnd_varchar() from long_sequence(5);",
2355+
27, "nanRate must be an integer"
2356+
));
23592357
}
23602358

23612359
@Test
@@ -2864,7 +2862,7 @@ public void testSubArray3d() throws Exception {
28642862
"SELECT arr[2,3-1:,2:] x FROM tango",
28652863
"""
28662864
VirtualRecord
2867-
functions: [arr[2,3-1:,2:]]
2865+
functions: [arr[2,2:,2:]]
28682866
PageFrame
28692867
Row forward scan
28702868
Frame forward scan on: tango

0 commit comments

Comments
 (0)