diff --git a/asterixdb/asterix-app/src/test/resources/optimizerts/results/query-issue562_ps.plan b/asterixdb/asterix-app/src/test/resources/optimizerts/results/query-issue562_ps.plan
index d2bfaf0..9499b08 100644
--- a/asterixdb/asterix-app/src/test/resources/optimizerts/results/query-issue562_ps.plan
+++ b/asterixdb/asterix-app/src/test/resources/optimizerts/results/query-issue562_ps.plan
@@ -9,12 +9,12 @@
                 -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                   -- REPLICATE  |PARTITIONED|
                     -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                      -- SORT_GROUP_BY[$$152]  |PARTITIONED|
+                      -- SORT_GROUP_BY[$$156]  |PARTITIONED|
                               {
                                 -- AGGREGATE  |LOCAL|
                                   -- NESTED_TUPLE_SOURCE  |LOCAL|
                               }
-                        -- HASH_PARTITION_EXCHANGE [$$152]  |PARTITIONED|
+                        -- HASH_PARTITION_EXCHANGE [$$156]  |PARTITIONED|
                           -- SORT_GROUP_BY[$$phone_substr]  |PARTITIONED|
                                   {
                                     -- AGGREGATE  |LOCAL|
@@ -27,29 +27,29 @@
                                     -- STREAM_SELECT  |PARTITIONED|
                                       -- STREAM_PROJECT  |PARTITIONED|
                                         -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                          -- SORT_GROUP_BY[$$149]  |PARTITIONED|
+                                          -- SORT_GROUP_BY[$$153]  |PARTITIONED|
                                                   {
                                                     -- AGGREGATE  |LOCAL|
                                                       -- NESTED_TUPLE_SOURCE  |LOCAL|
                                                   }
-                                            -- HASH_PARTITION_EXCHANGE [$$149]  |PARTITIONED|
-                                              -- PRE_CLUSTERED_GROUP_BY[$$145]  |PARTITIONED|
+                                            -- HASH_PARTITION_EXCHANGE [$$153]  |PARTITIONED|
+                                              -- PRE_CLUSTERED_GROUP_BY[$$149]  |PARTITIONED|
                                                       {
                                                         -- AGGREGATE  |LOCAL|
                                                           -- STREAM_SELECT  |LOCAL|
                                                             -- NESTED_TUPLE_SOURCE  |LOCAL|
                                                       }
                                                 -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                                  -- STABLE_SORT [$$145(ASC)]  |PARTITIONED|
+                                                  -- STABLE_SORT [$$149(ASC)]  |PARTITIONED|
                                                     -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                                                       -- STREAM_PROJECT  |PARTITIONED|
                                                         -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                                          -- HYBRID_HASH_JOIN [$$132][$$139]  |PARTITIONED|
+                                                          -- HYBRID_HASH_JOIN [$$136][$$143]  |PARTITIONED|
                                                             -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                                                               -- ASSIGN  |PARTITIONED|
                                                                 -- STREAM_PROJECT  |PARTITIONED|
                                                                   -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                                                    -- HYBRID_HASH_JOIN [$$phone_substr][$$134]  |PARTITIONED|
+                                                                    -- HYBRID_HASH_JOIN [$$phone_substr][$$138]  |PARTITIONED|
                                                                       -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                                                                         -- STREAM_PROJECT  |PARTITIONED|
                                                                           -- ASSIGN  |PARTITIONED|
@@ -60,7 +60,7 @@
                                                                       -- BROADCAST_EXCHANGE  |PARTITIONED|
                                                                         -- UNNEST  |UNPARTITIONED|
                                                                           -- EMPTY_TUPLE_SOURCE  |UNPARTITIONED|
-                                                            -- HASH_PARTITION_EXCHANGE [$$139]  |PARTITIONED|
+                                                            -- HASH_PARTITION_EXCHANGE [$$143]  |PARTITIONED|
                                                               -- ASSIGN  |PARTITIONED|
                                                                 -- STREAM_PROJECT  |PARTITIONED|
                                                                   -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
@@ -75,12 +75,12 @@
                           -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                             -- REPLICATE  |PARTITIONED|
                               -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                -- SORT_GROUP_BY[$$152]  |PARTITIONED|
+                                -- SORT_GROUP_BY[$$156]  |PARTITIONED|
                                         {
                                           -- AGGREGATE  |LOCAL|
                                             -- NESTED_TUPLE_SOURCE  |LOCAL|
                                         }
-                                  -- HASH_PARTITION_EXCHANGE [$$152]  |PARTITIONED|
+                                  -- HASH_PARTITION_EXCHANGE [$$156]  |PARTITIONED|
                                     -- SORT_GROUP_BY[$$phone_substr]  |PARTITIONED|
                                             {
                                               -- AGGREGATE  |LOCAL|
@@ -93,29 +93,29 @@
                                               -- STREAM_SELECT  |PARTITIONED|
                                                 -- STREAM_PROJECT  |PARTITIONED|
                                                   -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                                    -- SORT_GROUP_BY[$$149]  |PARTITIONED|
+                                                    -- SORT_GROUP_BY[$$153]  |PARTITIONED|
                                                             {
                                                               -- AGGREGATE  |LOCAL|
                                                                 -- NESTED_TUPLE_SOURCE  |LOCAL|
                                                             }
-                                                      -- HASH_PARTITION_EXCHANGE [$$149]  |PARTITIONED|
-                                                        -- PRE_CLUSTERED_GROUP_BY[$$145]  |PARTITIONED|
+                                                      -- HASH_PARTITION_EXCHANGE [$$153]  |PARTITIONED|
+                                                        -- PRE_CLUSTERED_GROUP_BY[$$149]  |PARTITIONED|
                                                                 {
                                                                   -- AGGREGATE  |LOCAL|
                                                                     -- STREAM_SELECT  |LOCAL|
                                                                       -- NESTED_TUPLE_SOURCE  |LOCAL|
                                                                 }
                                                           -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                                            -- STABLE_SORT [$$145(ASC)]  |PARTITIONED|
+                                                            -- STABLE_SORT [$$149(ASC)]  |PARTITIONED|
                                                               -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                                                                 -- STREAM_PROJECT  |PARTITIONED|
                                                                   -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                                                    -- HYBRID_HASH_JOIN [$$132][$$139]  |PARTITIONED|
+                                                                    -- HYBRID_HASH_JOIN [$$136][$$143]  |PARTITIONED|
                                                                       -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                                                                         -- ASSIGN  |PARTITIONED|
                                                                           -- STREAM_PROJECT  |PARTITIONED|
                                                                             -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                                                              -- HYBRID_HASH_JOIN [$$phone_substr][$$134]  |PARTITIONED|
+                                                                              -- HYBRID_HASH_JOIN [$$phone_substr][$$138]  |PARTITIONED|
                                                                                 -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                                                                                   -- STREAM_PROJECT  |PARTITIONED|
                                                                                     -- ASSIGN  |PARTITIONED|
@@ -126,7 +126,7 @@
                                                                                 -- BROADCAST_EXCHANGE  |PARTITIONED|
                                                                                   -- UNNEST  |UNPARTITIONED|
                                                                                     -- EMPTY_TUPLE_SOURCE  |UNPARTITIONED|
-                                                                      -- HASH_PARTITION_EXCHANGE [$$139]  |PARTITIONED|
+                                                                      -- HASH_PARTITION_EXCHANGE [$$143]  |PARTITIONED|
                                                                         -- ASSIGN  |PARTITIONED|
                                                                           -- STREAM_PROJECT  |PARTITIONED|
                                                                             -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/random/random.2.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/random/random.2.query.sqlpp
new file mode 100644
index 0000000..c23f43b
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/random/random.2.query.sqlpp
@@ -0,0 +1,27 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/*
+ * Description    : Test that a LET clause containing random() is not inlined
+ * Success        : Yes
+ */
+
+LET x = random(), y = tostring(x)
+FROM range(1, 1) r
+SELECT VALUE string(x) = y
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/misc/random/random.2.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/misc/random/random.2.adm
new file mode 100644
index 0000000..f32a580
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/misc/random/random.2.adm
@@ -0,0 +1 @@
+true
\ No newline at end of file
diff --git a/asterixdb/asterix-lang-common/src/main/java/org/apache/asterix/lang/common/util/FunctionUtil.java b/asterixdb/asterix-lang-common/src/main/java/org/apache/asterix/lang/common/util/FunctionUtil.java
index 6752f77..24384f2 100644
--- a/asterixdb/asterix-lang-common/src/main/java/org/apache/asterix/lang/common/util/FunctionUtil.java
+++ b/asterixdb/asterix-lang-common/src/main/java/org/apache/asterix/lang/common/util/FunctionUtil.java
@@ -58,6 +58,15 @@
         return getFunctionInfo(new FunctionIdentifier(fs.getNamespace(), fs.getName(), fs.getArity()));
     }
 
+    public static IFunctionInfo getBuiltinFunctionInfo(String functionName, int arity) {
+        IFunctionInfo fi =
+                getFunctionInfo(new FunctionIdentifier(AlgebricksBuiltinFunctions.ALGEBRICKS_NS, functionName, arity));
+        if (fi == null) {
+            fi = getFunctionInfo(new FunctionIdentifier(FunctionConstants.ASTERIX_NS, functionName, arity));
+        }
+        return fi;
+    }
+
     @FunctionalInterface
     public interface IFunctionCollector {
         Set<CallExpr> getFunctionCalls(Expression expression) throws CompilationException;
diff --git a/asterixdb/asterix-lang-common/src/main/java/org/apache/asterix/lang/common/visitor/base/AbstractQueryExpressionVisitor.java b/asterixdb/asterix-lang-common/src/main/java/org/apache/asterix/lang/common/visitor/base/AbstractQueryExpressionVisitor.java
index 117fa77..28533e1 100644
--- a/asterixdb/asterix-lang-common/src/main/java/org/apache/asterix/lang/common/visitor/base/AbstractQueryExpressionVisitor.java
+++ b/asterixdb/asterix-lang-common/src/main/java/org/apache/asterix/lang/common/visitor/base/AbstractQueryExpressionVisitor.java
@@ -39,12 +39,14 @@
 import org.apache.asterix.lang.common.statement.DropDatasetStatement;
 import org.apache.asterix.lang.common.statement.FeedDropStatement;
 import org.apache.asterix.lang.common.statement.FeedPolicyDropStatement;
+import org.apache.asterix.lang.common.statement.FunctionDecl;
 import org.apache.asterix.lang.common.statement.FunctionDropStatement;
 import org.apache.asterix.lang.common.statement.IndexDropStatement;
 import org.apache.asterix.lang.common.statement.InsertStatement;
 import org.apache.asterix.lang.common.statement.LoadStatement;
 import org.apache.asterix.lang.common.statement.NodeGroupDropStatement;
 import org.apache.asterix.lang.common.statement.NodegroupDecl;
+import org.apache.asterix.lang.common.statement.Query;
 import org.apache.asterix.lang.common.statement.SetStatement;
 import org.apache.asterix.lang.common.statement.StartFeedStatement;
 import org.apache.asterix.lang.common.statement.StopFeedStatement;
@@ -56,6 +58,16 @@
 public abstract class AbstractQueryExpressionVisitor<R, T> implements ILangVisitor<R, T> {
 
     @Override
+    public R visit(Query q, T arg) throws CompilationException {
+        return null;
+    }
+
+    @Override
+    public R visit(FunctionDecl fd, T arg) throws CompilationException {
+        return null;
+    }
+
+    @Override
     public R visit(CreateIndexStatement cis, T arg) throws CompilationException {
         return null;
     }
diff --git a/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/SqlppQueryRewriter.java b/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/SqlppQueryRewriter.java
index 28851fd..8bc319f 100644
--- a/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/SqlppQueryRewriter.java
+++ b/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/SqlppQueryRewriter.java
@@ -150,10 +150,6 @@
         // Rewrites like/not-like expressions.
         rewriteOperatorExpression();
 
-        // Inlines WITH expressions after variableCheckAndRewrite(...) so that the variable scoping for WITH
-        // expression is correct.
-        inlineWithExpressions();
-
         // Rewrites several variable-arg functions into their corresponding internal list-input functions.
         rewriteListInputFunctions();
 
@@ -165,6 +161,10 @@
         // names could be case sensitive.
         rewriteFunctionNames();
 
+        // Inlines WITH expressions after variableCheckAndRewrite(...) so that the variable scoping for WITH
+        // expression is correct.
+        inlineWithExpressions();
+
         // Sets the var counter of the query.
         topStatement.setVarCounter(context.getVarCounter().get());
     }
diff --git a/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/InlineWithExpressionVisitor.java b/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/InlineWithExpressionVisitor.java
index ebb7b10..9865bdf 100644
--- a/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/InlineWithExpressionVisitor.java
+++ b/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/rewrites/visitor/InlineWithExpressionVisitor.java
@@ -32,10 +32,14 @@
 import org.apache.asterix.lang.common.rewrites.LangRewritingContext;
 import org.apache.asterix.lang.sqlpp.expression.SelectExpression;
 import org.apache.asterix.lang.sqlpp.util.SqlppRewriteUtil;
+import org.apache.asterix.lang.sqlpp.visitor.CheckNonFunctionalExpressionVisitor;
 import org.apache.asterix.lang.sqlpp.visitor.base.AbstractSqlppExpressionScopingVisitor;
 
 public class InlineWithExpressionVisitor extends AbstractSqlppExpressionScopingVisitor {
 
+    private final CheckNonFunctionalExpressionVisitor checkNonFunctionalExpressionVisitor =
+            new CheckNonFunctionalExpressionVisitor();
+
     public InlineWithExpressionVisitor(LangRewritingContext context) {
         super(context);
     }
@@ -57,11 +61,14 @@
                 // Performs the rewriting recursively in the newBindingExpr itself.
                 super.visit(newBindingExpr, arg);
 
+                Expression bindingExpr = letClause.getBindingExpr();
+                Boolean isNonFunctional = bindingExpr.accept(checkNonFunctionalExpressionVisitor, null);
+                if (isNonFunctional != null && isNonFunctional) {
+                    continue;
+                }
+
                 // Removes the WITH entry and adds variable-expr mapping into the varExprMap.
                 with.remove();
-                Expression bindingExpr = letClause.getBindingExpr();
-                // Wraps the binding expression with IndependentSubquery, so that free identifier references
-                // in the binding expression will not be resolved use outer-scope variables.
                 varExprMap.put(letClause.getVarExpr(), bindingExpr);
             }
 
diff --git a/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/visitor/CheckNonFunctionalExpressionVisitor.java b/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/visitor/CheckNonFunctionalExpressionVisitor.java
new file mode 100644
index 0000000..167660a
--- /dev/null
+++ b/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/visitor/CheckNonFunctionalExpressionVisitor.java
@@ -0,0 +1,44 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.asterix.lang.sqlpp.visitor;
+
+import org.apache.asterix.common.exceptions.CompilationException;
+import org.apache.asterix.common.functions.FunctionSignature;
+import org.apache.asterix.lang.common.expression.CallExpr;
+import org.apache.asterix.lang.common.util.FunctionUtil;
+import org.apache.asterix.lang.sqlpp.visitor.base.AbstractSqlppContainsExpressionVisitor;
+import org.apache.hyracks.algebricks.core.algebra.functions.IFunctionInfo;
+
+/**
+ * Checks whether given expression is non-functional (i.e. whether it calls a non-functional function)
+ */
+public final class CheckNonFunctionalExpressionVisitor extends AbstractSqlppContainsExpressionVisitor<Void> {
+    @Override
+    public Boolean visit(CallExpr callExpr, Void arg) throws CompilationException {
+        FunctionSignature fs = callExpr.getFunctionSignature();
+        IFunctionInfo fi = FunctionUtil.getBuiltinFunctionInfo(fs.getName(), fs.getArity());
+        // TODO: all external functions are considered functional for now.
+        // we'll need to revisit this code once we enable non-functional in ExternalFunctionInfo
+        if (fi != null && !fi.isFunctional()) {
+            return true;
+        }
+        return super.visit(callExpr, arg);
+    }
+}
diff --git a/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/visitor/base/AbstractSqlppContainsExpressionVisitor.java b/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/visitor/base/AbstractSqlppContainsExpressionVisitor.java
new file mode 100644
index 0000000..e3f65e6
--- /dev/null
+++ b/asterixdb/asterix-lang-sqlpp/src/main/java/org/apache/asterix/lang/sqlpp/visitor/base/AbstractSqlppContainsExpressionVisitor.java
@@ -0,0 +1,328 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.asterix.lang.sqlpp.visitor.base;
+
+import java.util.Collection;
+
+import org.apache.asterix.common.exceptions.CompilationException;
+import org.apache.asterix.lang.common.base.ILangExpression;
+import org.apache.asterix.lang.common.clause.GroupbyClause;
+import org.apache.asterix.lang.common.clause.LetClause;
+import org.apache.asterix.lang.common.clause.LimitClause;
+import org.apache.asterix.lang.common.clause.OrderbyClause;
+import org.apache.asterix.lang.common.clause.WhereClause;
+import org.apache.asterix.lang.common.expression.CallExpr;
+import org.apache.asterix.lang.common.expression.FieldAccessor;
+import org.apache.asterix.lang.common.expression.FieldBinding;
+import org.apache.asterix.lang.common.expression.GbyVariableExpressionPair;
+import org.apache.asterix.lang.common.expression.IfExpr;
+import org.apache.asterix.lang.common.expression.IndexAccessor;
+import org.apache.asterix.lang.common.expression.ListConstructor;
+import org.apache.asterix.lang.common.expression.ListSliceExpression;
+import org.apache.asterix.lang.common.expression.LiteralExpr;
+import org.apache.asterix.lang.common.expression.OperatorExpr;
+import org.apache.asterix.lang.common.expression.QuantifiedExpression;
+import org.apache.asterix.lang.common.expression.RecordConstructor;
+import org.apache.asterix.lang.common.expression.UnaryExpr;
+import org.apache.asterix.lang.common.expression.VariableExpr;
+import org.apache.asterix.lang.common.struct.Identifier;
+import org.apache.asterix.lang.common.struct.QuantifiedPair;
+import org.apache.asterix.lang.sqlpp.clause.AbstractBinaryCorrelateClause;
+import org.apache.asterix.lang.sqlpp.clause.FromClause;
+import org.apache.asterix.lang.sqlpp.clause.FromTerm;
+import org.apache.asterix.lang.sqlpp.clause.HavingClause;
+import org.apache.asterix.lang.sqlpp.clause.JoinClause;
+import org.apache.asterix.lang.sqlpp.clause.NestClause;
+import org.apache.asterix.lang.sqlpp.clause.Projection;
+import org.apache.asterix.lang.sqlpp.clause.SelectBlock;
+import org.apache.asterix.lang.sqlpp.clause.SelectClause;
+import org.apache.asterix.lang.sqlpp.clause.SelectElement;
+import org.apache.asterix.lang.sqlpp.clause.SelectRegular;
+import org.apache.asterix.lang.sqlpp.clause.SelectSetOperation;
+import org.apache.asterix.lang.sqlpp.clause.UnnestClause;
+import org.apache.asterix.lang.sqlpp.expression.CaseExpression;
+import org.apache.asterix.lang.sqlpp.expression.SelectExpression;
+import org.apache.asterix.lang.sqlpp.expression.WindowExpression;
+import org.apache.asterix.lang.sqlpp.struct.SetOperationRight;
+import org.apache.hyracks.algebricks.common.utils.Pair;
+
+/**
+ * Base class for visitors that search for expressions having certain properties and return a boolean value
+ * indicating whether such expressions were found or not, or {@code null} if search could not be performed.
+ */
+public abstract class AbstractSqlppContainsExpressionVisitor<T>
+        extends AbstractSqlppQueryExpressionVisitor<Boolean, T> {
+
+    @Override
+    public Boolean visit(FromClause fromClause, T arg) throws CompilationException {
+        for (FromTerm fromTerm : fromClause.getFromTerms()) {
+            if (fromTerm.accept(this, arg)) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    @Override
+    public Boolean visit(FromTerm fromTerm, T arg) throws CompilationException {
+        if (visit(fromTerm.getLeftExpression(), arg)) {
+            return true;
+        }
+        if (fromTerm.hasCorrelateClauses()) {
+            for (AbstractBinaryCorrelateClause correlateClause : fromTerm.getCorrelateClauses()) {
+                if (correlateClause.accept(this, arg)) {
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
+
+    @Override
+    public Boolean visit(JoinClause joinClause, T arg) throws CompilationException {
+        return visit(joinClause.getRightExpression(), arg) || visit(joinClause.getConditionExpression(), arg);
+    }
+
+    @Override
+    public Boolean visit(NestClause nestClause, T arg) throws CompilationException {
+        return nestClause.accept(this, arg);
+    }
+
+    @Override
+    public Boolean visit(Projection projection, T arg) throws CompilationException {
+        return visit(projection.getExpression(), arg);
+    }
+
+    @Override
+    public Boolean visit(SelectBlock selectBlock, T arg) throws CompilationException {
+        return (selectBlock.hasFromClause() && visit(selectBlock.getFromClause(), arg))
+                || (selectBlock.hasLetWhereClauses() && visitExprList(selectBlock.getLetWhereList(), arg))
+                || (selectBlock.hasGroupbyClause() && visit(selectBlock.getGroupbyClause(), arg))
+                || (selectBlock.hasLetHavingClausesAfterGroupby()
+                        && visitExprList(selectBlock.getLetHavingListAfterGroupby(), arg))
+                || visit(selectBlock.getSelectClause(), arg);
+    }
+
+    @Override
+    public Boolean visit(SelectClause selectClause, T arg) throws CompilationException {
+        return (selectClause.selectElement() && visit(selectClause.getSelectElement(), arg))
+                || (selectClause.selectRegular() && visit(selectClause.getSelectRegular(), arg));
+    }
+
+    @Override
+    public Boolean visit(SelectElement selectElement, T arg) throws CompilationException {
+        return visit(selectElement.getExpression(), arg);
+    }
+
+    @Override
+    public Boolean visit(SelectRegular selectRegular, T arg) throws CompilationException {
+        return visitExprList(selectRegular.getProjections(), arg);
+    }
+
+    @Override
+    public Boolean visit(SelectSetOperation selectSetOperation, T arg) throws CompilationException {
+        if (selectSetOperation.getLeftInput().accept(this, arg)) {
+            return true;
+        }
+        if (selectSetOperation.hasRightInputs()) {
+            for (SetOperationRight right : selectSetOperation.getRightInputs()) {
+                if (right.getSetOperationRightInput().accept(this, arg)) {
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
+
+    @Override
+    public Boolean visit(SelectExpression selectStatement, T arg) throws CompilationException {
+        return (selectStatement.hasLetClauses() && visitExprList(selectStatement.getLetList(), arg))
+                || visit(selectStatement.getSelectSetOperation(), arg)
+                || (selectStatement.hasOrderby() && visit(selectStatement.getOrderbyClause(), arg))
+                || (selectStatement.hasLimit() && visit(selectStatement.getLimitClause(), arg));
+    }
+
+    @Override
+    public Boolean visit(UnnestClause unnestClause, T arg) throws CompilationException {
+        return visit(unnestClause.getRightExpression(), arg);
+    }
+
+    @Override
+    public Boolean visit(HavingClause havingClause, T arg) throws CompilationException {
+        return visit(havingClause.getFilterExpression(), arg);
+    }
+
+    @Override
+    public Boolean visit(CaseExpression caseExpression, T arg) throws CompilationException {
+        return visit(caseExpression.getConditionExpr(), arg) || visitExprList(caseExpression.getWhenExprs(), arg)
+                || visitExprList(caseExpression.getThenExprs(), arg) || visit(caseExpression.getElseExpr(), arg);
+    }
+
+    @Override
+    public Boolean visit(LiteralExpr l, T arg) throws CompilationException {
+        return false;
+    }
+
+    @Override
+    public Boolean visit(VariableExpr v, T arg) throws CompilationException {
+        return false;
+    }
+
+    @Override
+    public Boolean visit(ListConstructor lc, T arg) throws CompilationException {
+        return visitExprList(lc.getExprList(), arg);
+    }
+
+    @Override
+    public Boolean visit(RecordConstructor rc, T arg) throws CompilationException {
+        for (FieldBinding fb : rc.getFbList()) {
+            if (visit(fb.getLeftExpr(), arg)) {
+                return true;
+            }
+            if (visit(fb.getRightExpr(), arg)) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    @Override
+    public Boolean visit(OperatorExpr operatorExpr, T arg) throws CompilationException {
+        return visitExprList(operatorExpr.getExprList(), arg);
+    }
+
+    @Override
+    public Boolean visit(FieldAccessor fa, T arg) throws CompilationException {
+        return visit(fa.getExpr(), arg);
+    }
+
+    @Override
+    public Boolean visit(IndexAccessor ia, T arg) throws CompilationException {
+        return visit(ia.getExpr(), arg) || visit(ia.getIndexExpr(), arg);
+    }
+
+    @Override
+    public Boolean visit(ListSliceExpression expression, T arg) throws CompilationException {
+        return visit(expression.getExpr(), arg) || visit(expression.getStartIndexExpression(), arg)
+                || visit(expression.getEndIndexExpression(), arg);
+    }
+
+    @Override
+    public Boolean visit(IfExpr ifexpr, T arg) throws CompilationException {
+        return visit(ifexpr.getCondExpr(), arg) || visit(ifexpr.getThenExpr(), arg) || visit(ifexpr.getElseExpr(), arg);
+    }
+
+    @Override
+    public Boolean visit(QuantifiedExpression qe, T arg) throws CompilationException {
+        for (QuantifiedPair qf : qe.getQuantifiedList()) {
+            if (visit(qf.getExpr(), arg)) {
+                return true;
+            }
+        }
+        return visit(qe.getSatisfiesExpr(), arg);
+    }
+
+    @Override
+    public Boolean visit(LetClause lc, T arg) throws CompilationException {
+        return visit(lc.getBindingExpr(), arg);
+    }
+
+    @Override
+    public Boolean visit(WhereClause wc, T arg) throws CompilationException {
+        return visit(wc.getWhereExpr(), arg);
+    }
+
+    @Override
+    public Boolean visit(OrderbyClause oc, T arg) throws CompilationException {
+        return visitExprList(oc.getOrderbyList(), arg);
+    }
+
+    @Override
+    public Boolean visit(GroupbyClause gc, T arg) throws CompilationException {
+        for (GbyVariableExpressionPair key : gc.getGbyPairList()) {
+            if (visit(key.getExpr(), arg)) {
+                return true;
+            }
+        }
+        if (gc.hasDecorList()) {
+            for (GbyVariableExpressionPair key : gc.getDecorPairList()) {
+                if (visit(key.getExpr(), arg)) {
+                    return true;
+                }
+            }
+        }
+        if (gc.hasGroupFieldList() && visitFieldList(gc.getGroupFieldList(), arg)) {
+            return true;
+        }
+        if (gc.hasWithMap() && visitExprList(gc.getWithVarMap().keySet(), arg)) {
+            return true;
+        }
+        return false;
+    }
+
+    @Override
+    public Boolean visit(LimitClause lc, T arg) throws CompilationException {
+        return visit(lc.getLimitExpr(), arg) || visit(lc.getOffset(), arg);
+    }
+
+    @Override
+    public Boolean visit(UnaryExpr u, T arg) throws CompilationException {
+        return visit(u.getExpr(), arg);
+    }
+
+    @Override
+    public Boolean visit(WindowExpression winExpr, T arg) throws CompilationException {
+        return (winExpr.hasPartitionList() && visitExprList(winExpr.getPartitionList(), arg))
+                || (winExpr.hasOrderByList() && visitExprList(winExpr.getOrderbyList(), arg))
+                || (winExpr.hasFrameStartExpr() && visit(winExpr.getFrameStartExpr(), arg))
+                || (winExpr.hasFrameEndExpr() && visit(winExpr.getFrameEndExpr(), arg))
+                || (winExpr.hasWindowFieldList() && visitFieldList(winExpr.getWindowFieldList(), arg))
+                || visitExprList(winExpr.getExprList(), arg);
+    }
+
+    @Override
+    public Boolean visit(CallExpr callExpr, T arg) throws CompilationException {
+        return visitExprList(callExpr.getExprList(), arg);
+    }
+
+    private boolean visit(ILangExpression expr, T arg) throws CompilationException {
+        return expr != null && expr.accept(this, arg);
+    }
+
+    private <E extends ILangExpression> boolean visitExprList(Collection<E> exprList, T arg)
+            throws CompilationException {
+        for (E langExpr : exprList) {
+            if (visit(langExpr, arg)) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    private <E extends ILangExpression> boolean visitFieldList(Collection<Pair<E, Identifier>> fieldList, T arg)
+            throws CompilationException {
+        for (Pair<E, Identifier> p : fieldList) {
+            if (visit(p.first, arg)) {
+                return true;
+            }
+        }
+        return false;
+    }
+}
diff --git a/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/functions/ExternalFunctionInfo.java b/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/functions/ExternalFunctionInfo.java
index 2c80470..c1ad794 100644
--- a/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/functions/ExternalFunctionInfo.java
+++ b/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/functions/ExternalFunctionInfo.java
@@ -37,6 +37,7 @@
 
     public ExternalFunctionInfo(String namespace, String name, int arity, FunctionKind kind, List<IAType> argumentTypes,
             IAType returnType, IResultTypeComputer rtc, String body, String language) {
+        // TODO: fix CheckNonFunctionalExpressionVisitor once we have non-functional external functions
         super(namespace, name, arity, true);
         this.rtc = rtc;
         this.argumentTypes = argumentTypes;