diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeAccessMethod.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeAccessMethod.java
index 099f769..b45e1c6 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeAccessMethod.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeAccessMethod.java
@@ -329,8 +329,10 @@
         LimitType[] highKeyLimits = new LimitType[numSecondaryKeys];
         boolean[] lowKeyInclusive = new boolean[numSecondaryKeys];
         boolean[] highKeyInclusive = new boolean[numSecondaryKeys];
-        ILogicalExpression[] constantAtRuntimeExpressions = new ILogicalExpression[numSecondaryKeys];
-        LogicalVariable[] constAtRuntimeExprVars = new LogicalVariable[numSecondaryKeys];
+        ILogicalExpression[] lowKeyConstAtRuntimeExpressions = new ILogicalExpression[numSecondaryKeys];
+        ILogicalExpression[] highKeyConstantAtRuntimeExpressions = new ILogicalExpression[numSecondaryKeys];
+        LogicalVariable[] lowKeyConstAtRuntimeExprVars = new LogicalVariable[numSecondaryKeys];
+        LogicalVariable[] highKeyConstAtRuntimeExprVars = new LogicalVariable[numSecondaryKeys];
 
         /* TODO: For now we don't do any sophisticated analysis of the func exprs to come up with "the best" range
          * predicate. If we can't figure out how to integrate a certain funcExpr into the current predicate,
@@ -367,13 +369,6 @@
             ILogicalExpression searchKeyExpr = returnedSearchKeyExpr.first;
             ILogicalExpression searchKeyEQExpr = null;
             boolean realTypeConvertedToIntegerType = returnedSearchKeyExpr.third;
-            if (searchKeyExpr.getExpressionTag() == LogicalExpressionTag.FUNCTION_CALL) {
-                constantAtRuntimeExpressions[keyPos] = searchKeyExpr;
-                constAtRuntimeExprVars[keyPos] = context.newVar();
-                VariableReferenceExpression varRef = new VariableReferenceExpression(constAtRuntimeExprVars[keyPos]);
-                varRef.setSourceLocation(searchKeyExpr.getSourceLocation());
-                searchKeyExpr = varRef;
-            }
 
             LimitType limit = getLimitType(optFuncExpr, probeSubTree);
             if (limit == null) {
@@ -395,6 +390,24 @@
                 }
             }
 
+            if (searchKeyExpr.getExpressionTag() == LogicalExpressionTag.FUNCTION_CALL) {
+                LogicalVariable constAtRuntimeExprVar = context.newVar();
+                VariableReferenceExpression constAtRuntimeExprVarRef =
+                        new VariableReferenceExpression(constAtRuntimeExprVar);
+                constAtRuntimeExprVarRef.setSourceLocation(searchKeyExpr.getSourceLocation());
+
+                if (limit == LimitType.LOW_INCLUSIVE || limit == LimitType.LOW_EXCLUSIVE || limit == LimitType.EQUAL) {
+                    lowKeyConstAtRuntimeExpressions[keyPos] = searchKeyExpr;
+                    lowKeyConstAtRuntimeExprVars[keyPos] = constAtRuntimeExprVar;
+                }
+                if (limit == LimitType.HIGH_INCLUSIVE || limit == LimitType.HIGH_EXCLUSIVE
+                        || limit == LimitType.EQUAL) {
+                    highKeyConstantAtRuntimeExpressions[keyPos] = searchKeyExpr;
+                    highKeyConstAtRuntimeExprVars[keyPos] = constAtRuntimeExprVar;
+                }
+                searchKeyExpr = constAtRuntimeExprVarRef;
+            }
+
             switch (limit) {
                 case EQUAL: {
                     if (lowKeyLimits[keyPos] == null && highKeyLimits[keyPos] == null) {
@@ -562,9 +575,10 @@
         ArrayList<LogicalVariable> assignKeyVarList = new ArrayList<>();
         ArrayList<Mutable<ILogicalExpression>> assignKeyExprList = new ArrayList<>();
         int numLowKeys = createKeyVarsAndExprs(numSecondaryKeys, lowKeyLimits, lowKeyExprs, assignKeyVarList,
-                assignKeyExprList, keyVarList, context, constantAtRuntimeExpressions, constAtRuntimeExprVars);
+                assignKeyExprList, keyVarList, context, lowKeyConstAtRuntimeExpressions, lowKeyConstAtRuntimeExprVars);
         int numHighKeys = createKeyVarsAndExprs(numSecondaryKeys, highKeyLimits, highKeyExprs, assignKeyVarList,
-                assignKeyExprList, keyVarList, context, constantAtRuntimeExpressions, constAtRuntimeExprVars);
+                assignKeyExprList, keyVarList, context, highKeyConstantAtRuntimeExpressions,
+                highKeyConstAtRuntimeExprVars);
 
         BTreeJobGenParams jobGenParams = new BTreeJobGenParams(chosenIndex.getIndexName(), IndexType.BTREE,
                 dataset.getDataverseName(), dataset.getDatasetName(), retainInput, requiresBroadcast);
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/index-selection/range-search-open/range-search-open.5.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/index-selection/range-search-open/range-search-open.5.query.sqlpp
new file mode 100644
index 0000000..c37d241
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/index-selection/range-search-open/range-search-open.5.query.sqlpp
@@ -0,0 +1,30 @@
+/*
+ * 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 range search with non-constant search expressions
+ */
+
+use test;
+
+select value count(*)
+from LineItem as c
+where
+  ((c.l_suppkey < 100 + tobigint(random()/2) /* = 0 */) and
+  (c.l_suppkey > 5 + tobigint(random()/2) /* = 0 */));
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/index-selection/range-search/range-search.5.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/index-selection/range-search/range-search.5.query.sqlpp
new file mode 100644
index 0000000..c37d241
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/index-selection/range-search/range-search.5.query.sqlpp
@@ -0,0 +1,30 @@
+/*
+ * 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 range search with non-constant search expressions
+ */
+
+use test;
+
+select value count(*)
+from LineItem as c
+where
+  ((c.l_suppkey < 100 + tobigint(random()/2) /* = 0 */) and
+  (c.l_suppkey > 5 + tobigint(random()/2) /* = 0 */));
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/index-selection/range-search-open/range-search-open.2.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/index-selection/range-search-open/range-search-open.2.adm
new file mode 100644
index 0000000..2aba3a1
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/index-selection/range-search-open/range-search-open.2.adm
@@ -0,0 +1 @@
+2978
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/index-selection/range-search/range-search.2.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/index-selection/range-search/range-search.2.adm
new file mode 100644
index 0000000..2aba3a1
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/index-selection/range-search/range-search.2.adm
@@ -0,0 +1 @@
+2978
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results_parser_sqlpp/index-selection/range-search-open/range-search-open.5.ast b/asterixdb/asterix-app/src/test/resources/runtimets/results_parser_sqlpp/index-selection/range-search-open/range-search-open.5.ast
new file mode 100644
index 0000000..ecfb9f3
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results_parser_sqlpp/index-selection/range-search-open/range-search-open.5.ast
@@ -0,0 +1,67 @@
+DataverseUse test
+Query:
+SELECT ELEMENT [
+FunctionCall asterix.sql-count@1[
+  (
+    SELECT ELEMENT [
+    LiteralExpr [LONG] [1]
+    ]
+    FROM [      Variable [ Name=#1 ]
+      AS Variable [ Name=#2 ]
+    ]
+  )
+]
+]
+FROM [  FunctionCall asterix.dataset@1[
+    LiteralExpr [STRING] [test.LineItem]
+  ]
+  AS Variable [ Name=$c ]
+]
+Where
+  OperatorExpr [
+    OperatorExpr [
+      FieldAccessor [
+        Variable [ Name=$c ]
+        Field=l_suppkey
+      ]
+      <
+      OperatorExpr [
+        LiteralExpr [LONG] [100]
+        +
+        FunctionCall test.to-bigint@1[
+          OperatorExpr [
+            FunctionCall test.random@0[
+            ]
+            /
+            LiteralExpr [LONG] [2]
+          ]
+        ]
+      ]
+    ]
+    and
+    OperatorExpr [
+      FieldAccessor [
+        Variable [ Name=$c ]
+        Field=l_suppkey
+      ]
+      >
+      OperatorExpr [
+        LiteralExpr [LONG] [5]
+        +
+        FunctionCall test.to-bigint@1[
+          OperatorExpr [
+            FunctionCall test.random@0[
+            ]
+            /
+            LiteralExpr [LONG] [2]
+          ]
+        ]
+      ]
+    ]
+  ]
+Group All
+  GROUP AS Variable [ Name=#1 ]
+  (
+    c:=Variable [ Name=$c ]
+  )
+
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results_parser_sqlpp/index-selection/range-search/range-search.5.ast b/asterixdb/asterix-app/src/test/resources/runtimets/results_parser_sqlpp/index-selection/range-search/range-search.5.ast
new file mode 100644
index 0000000..ecfb9f3
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results_parser_sqlpp/index-selection/range-search/range-search.5.ast
@@ -0,0 +1,67 @@
+DataverseUse test
+Query:
+SELECT ELEMENT [
+FunctionCall asterix.sql-count@1[
+  (
+    SELECT ELEMENT [
+    LiteralExpr [LONG] [1]
+    ]
+    FROM [      Variable [ Name=#1 ]
+      AS Variable [ Name=#2 ]
+    ]
+  )
+]
+]
+FROM [  FunctionCall asterix.dataset@1[
+    LiteralExpr [STRING] [test.LineItem]
+  ]
+  AS Variable [ Name=$c ]
+]
+Where
+  OperatorExpr [
+    OperatorExpr [
+      FieldAccessor [
+        Variable [ Name=$c ]
+        Field=l_suppkey
+      ]
+      <
+      OperatorExpr [
+        LiteralExpr [LONG] [100]
+        +
+        FunctionCall test.to-bigint@1[
+          OperatorExpr [
+            FunctionCall test.random@0[
+            ]
+            /
+            LiteralExpr [LONG] [2]
+          ]
+        ]
+      ]
+    ]
+    and
+    OperatorExpr [
+      FieldAccessor [
+        Variable [ Name=$c ]
+        Field=l_suppkey
+      ]
+      >
+      OperatorExpr [
+        LiteralExpr [LONG] [5]
+        +
+        FunctionCall test.to-bigint@1[
+          OperatorExpr [
+            FunctionCall test.random@0[
+            ]
+            /
+            LiteralExpr [LONG] [2]
+          ]
+        ]
+      ]
+    ]
+  ]
+Group All
+  GROUP AS Variable [ Name=#1 ]
+  (
+    c:=Variable [ Name=$c ]
+  )
+