diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/column/assembly/ASTERIXDB-3539/ASTERIXDB-3539.001.ddl.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/column/assembly/ASTERIXDB-3539/ASTERIXDB-3539.001.ddl.sqlpp
new file mode 100644
index 0000000..d151eb1
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/column/assembly/ASTERIXDB-3539/ASTERIXDB-3539.001.ddl.sqlpp
@@ -0,0 +1,28 @@
+/*
+ * 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.
+ */
+
+ DROP DATAVERSE test IF EXISTS;
+ CREATE DATAVERSE test;
+
+ USE test;
+
+ CREATE DATASET ColumnDataset
+ PRIMARY KEY (uid:int) WITH {
+     "storage-format": {"format": "column"}
+ };
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/column/assembly/ASTERIXDB-3539/ASTERIXDB-3539.002.update.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/column/assembly/ASTERIXDB-3539/ASTERIXDB-3539.002.update.sqlpp
new file mode 100644
index 0000000..7828d12
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/column/assembly/ASTERIXDB-3539/ASTERIXDB-3539.002.update.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.
+ */
+
+
+USE test;
+UPSERT INTO ColumnDataset(
+    {"uid": 1, "a": [{"x": "aaaaaaaaaazzzz"}, {"x": "aaaaaaaaaaabzzzz"}, {"x": "aaaaaaaaaaaaabzzzzzzzz"}]},
+    {"uid": 2, "a": [{"x": "aaaaaaaaaazzzzextra"}, {"x": "aaaaaaaaaaabzzzzextra"}, {"x": "aaaaaaaaaaaaabzzzzzzzzextra"}]},
+    {"uid": 3, "a": [{"x": "aaaaaaaaaazzzzextra"}, {"x": "aaaaaaaaaaabzzzzextra"}, {"x": "aaaaaaaaaaaaabzzzzzzzzextra"}]},
+    {"uid": 4, "a": [{"x": "aaaaaaaaaazzzzextra"}, {"x": "aaaaaaaaaaabzzzzextra"}, {"x": "aaaaaaaaaaaaabzzzzzzzzextra"}]},
+    {"uid": 5, "a": [{"x": "aaaaaaaaaazzzzextra"}, {"x": "aaaaaaaaaaabzzzzextra"}, {"x": "aaaaaaaaaaaaabzzzzzzzzextra"}]},
+    {"uid": 6, "a": [{"x": "aaaaaaaaaazzzzextra"}, {"x": "aaaaaaaaaaabzzzzextra"}, {"x": "aaaaaaaaaaaaabzzzzzzzzextra"}]},
+    {"uid": 7, "a": [{"x": "aaaaaaaaaazzzzextra"}, {"x": "aaaaaaaaaaabzzzzextra"}, {"x": "aaaaaaaaaaaaabzzzzzzzz"}]}
+);
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/column/assembly/ASTERIXDB-3539/ASTERIXDB-3539.003.update.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/column/assembly/ASTERIXDB-3539/ASTERIXDB-3539.003.update.sqlpp
new file mode 100644
index 0000000..5337d9b
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/column/assembly/ASTERIXDB-3539/ASTERIXDB-3539.003.update.sqlpp
@@ -0,0 +1,22 @@
+/*
+ * 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.
+ */
+
+USE test;
+DELETE FROM ColumnDataset
+WHERE uid >= 2 AND uid <= 6;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/column/assembly/ASTERIXDB-3539/ASTERIXDB-3539.004.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/column/assembly/ASTERIXDB-3539/ASTERIXDB-3539.004.query.sqlpp
new file mode 100644
index 0000000..b7fac3c
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/column/assembly/ASTERIXDB-3539/ASTERIXDB-3539.004.query.sqlpp
@@ -0,0 +1,23 @@
+/*
+ * 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.
+ */
+
+ USE test;
+ SELECT VALUE a.x
+ FROM ColumnDataset c, c.a a
+ WHERE a.x = "aaaaaaaaaazzzzextra";
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/column/assembly/ASTERIXDB-3539/ASTERIXDB-3539.003.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/column/assembly/ASTERIXDB-3539/ASTERIXDB-3539.003.adm
new file mode 100644
index 0000000..7328549
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/column/assembly/ASTERIXDB-3539/ASTERIXDB-3539.003.adm
@@ -0,0 +1 @@
+"aaaaaaaaaazzzzextra"
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/sqlpp_queries.xml b/asterixdb/asterix-app/src/test/resources/runtimets/sqlpp_queries.xml
index 422d913..5476877 100644
--- a/asterixdb/asterix-app/src/test/resources/runtimets/sqlpp_queries.xml
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/sqlpp_queries.xml
@@ -16369,6 +16369,11 @@
       </compilation-unit>
     </test-case>
     <test-case FilePath="column">
+      <compilation-unit name="assembly/ASTERIXDB-3539">
+        <output-dir compare="Text">assembly/ASTERIXDB-3539</output-dir>
+      </compilation-unit>
+    </test-case>
+    <test-case FilePath="column">
       <compilation-unit name="filter/ASTERIXDB-3499">
         <output-dir compare="Text">filter/ASTERIXDB-3499</output-dir>
       </compilation-unit>
diff --git a/asterixdb/asterix-column/src/main/java/org/apache/asterix/column/tuple/QueryColumnTupleReference.java b/asterixdb/asterix-column/src/main/java/org/apache/asterix/column/tuple/QueryColumnTupleReference.java
index e1dddf1..64ac0a2 100644
--- a/asterixdb/asterix-column/src/main/java/org/apache/asterix/column/tuple/QueryColumnTupleReference.java
+++ b/asterixdb/asterix-column/src/main/java/org/apache/asterix/column/tuple/QueryColumnTupleReference.java
@@ -162,11 +162,14 @@
         // index == -1 if the normalized filter indicated that a mega leaf node
         // is filtered
         if (index == tupleIndex) {
+            antimatterGap = 0;
             // setAt in the assembler expect the value index (i.e., tupleCount - antiMatterCount)
             assembler.setAt(columnFilterEvaluator.getValueIndex());
             // set the next tuple index that satisfies the filter
             columnFilterEvaluator.evaluate();
             return assembler.nextValue();
+        } else {
+            antimatterGap++;
         }
         return MissingValueGetter.MISSING;
     }
diff --git a/asterixdb/asterix-column/src/main/java/org/apache/asterix/column/tuple/QueryColumnWithMetaTupleReference.java b/asterixdb/asterix-column/src/main/java/org/apache/asterix/column/tuple/QueryColumnWithMetaTupleReference.java
index e7402c3..4202f47 100644
--- a/asterixdb/asterix-column/src/main/java/org/apache/asterix/column/tuple/QueryColumnWithMetaTupleReference.java
+++ b/asterixdb/asterix-column/src/main/java/org/apache/asterix/column/tuple/QueryColumnWithMetaTupleReference.java
@@ -186,12 +186,15 @@
         // index == -1 if the normalized filter indicated that a mega leaf node is filtered
         if (index == tupleIndex) {
             // setAt in the assembler expect the value index (i.e., tupleCount - antiMatterCount)
+            antimatterGap = 0;
             int valueIndex = columnFilterEvaluator.getValueIndex();
             assembler.setAt(valueIndex);
             metaAssembler.setAt(valueIndex);
             // set the next tuple index that satisfies the filter
             columnFilterEvaluator.evaluate();
             return assembler.nextValue();
+        } else {
+            antimatterGap++;
         }
 
         return MissingValueGetter.MISSING;
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/api/IColumnTupleIterator.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/api/IColumnTupleIterator.java
index 4034906..4b9cc99 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/api/IColumnTupleIterator.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/api/IColumnTupleIterator.java
@@ -108,4 +108,11 @@
     void unpinColumnsPages() throws HyracksDataException;
 
     void close();
+
+    /**
+     * @return the gap between the lastAssembledTuple index and the current antimatter tuple index
+     */
+    int getAntimatterGap();
+
+    void resetAntimatterGap();
 }
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/impls/lsm/LSMColumnBTreeRangeSearchCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/impls/lsm/LSMColumnBTreeRangeSearchCursor.java
index 41126e2..cee77edd 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/impls/lsm/LSMColumnBTreeRangeSearchCursor.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/impls/lsm/LSMColumnBTreeRangeSearchCursor.java
@@ -86,7 +86,9 @@
         IColumnTupleIterator columnTuple = (IColumnTupleIterator) e.getTuple();
         if (!columnTuple.isAntimatter()) {
             // Skip non-key columns
-            columnTuple.skip(1);
+            int antiMatterGap = columnTuple.getAntimatterGap();
+            columnTuple.skip(antiMatterGap + 1);
+            columnTuple.resetAntimatterGap();
         }
     }
 
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/impls/lsm/tuples/AbstractColumnTupleReference.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/impls/lsm/tuples/AbstractColumnTupleReference.java
index f30007d..1937ffc 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/impls/lsm/tuples/AbstractColumnTupleReference.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree-column/src/main/java/org/apache/hyracks/storage/am/lsm/btree/column/impls/lsm/tuples/AbstractColumnTupleReference.java
@@ -46,6 +46,7 @@
     private final int numberOfPrimaryKeys;
     private int endIndex;
     protected int tupleIndex;
+    protected int antimatterGap;
 
     // For logging
     private final LongSet pinnedPages;
@@ -102,6 +103,7 @@
     @Override
     public final void newPage() throws HyracksDataException {
         tupleIndex = 0;
+        antimatterGap = 0;
         ByteBuffer pageZero = frame.getBuffer();
         pageZero.clear();
         pageZero.position(HEADER_SIZE);
@@ -119,6 +121,7 @@
     @Override
     public final void reset(int startIndex, int endIndex) throws HyracksDataException {
         tupleIndex = startIndex;
+        antimatterGap = 0;
         this.endIndex = endIndex;
         ByteBuffer pageZero = frame.getBuffer();
         int numberOfTuples = frame.getTupleCount();
@@ -293,4 +296,14 @@
     public final void resetByTupleIndex(ITreeIndexFrame frame, int tupleIndex) {
         throw new UnsupportedOperationException(UNSUPPORTED_OPERATION_MSG);
     }
+
+    @Override
+    public int getAntimatterGap() {
+        return antimatterGap;
+    }
+
+    @Override
+    public void resetAntimatterGap() {
+        antimatterGap = 0;
+    }
 }