You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@flink.apache.org by GitBox <gi...@apache.org> on 2020/12/21 16:20:00 UTC

[GitHub] [flink] leonardBang commented on a change in pull request #14280: [FLINK-20110][table-planner] Support 'merge' method for first_value a…

leonardBang commented on a change in pull request #14280:
URL: https://github.com/apache/flink/pull/14280#discussion_r546504664



##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstValueAggFunction.java
##########
@@ -107,6 +107,27 @@ public void accumulate(RowData rowData, StringData value, Long order) {
 		}
 	}
 
+	public void merge(RowData acc, Iterable<RowData> its) {

Review comment:
       `its ` => `it` ?

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/LastValueAggFunction.java
##########
@@ -106,6 +107,27 @@ public void accumulate(GenericRowData acc, StringData value, Long order) {
 		}
 	}
 
+	public void merge(RowData acc, Iterable<RowData> its) {

Review comment:
       `its` => `it`

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstValueAggFunction.java
##########
@@ -83,7 +83,7 @@ public void accumulate(RowData rowData, Object value) {
 		GenericRowData acc = (GenericRowData) rowData;
 		if (value != null && acc.getLong(1) == Long.MAX_VALUE) {
 			acc.setField(0, value);
-			acc.setField(1, System.currentTimeMillis());
+			acc.setField(1, System.nanoTime());

Review comment:
       I think we'd better use `System.currentTimeMillis()` which is matched with Flink PROC_TIME semantics, and the `System.nanoTime()` cannot represent current timestamp, it's just a relative time with higher precision.  

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/LastValueAggFunction.java
##########
@@ -106,6 +107,27 @@ public void accumulate(GenericRowData acc, StringData value, Long order) {
 		}
 	}
 
+	public void merge(RowData acc, Iterable<RowData> its) {
+		GenericRowData accRowData = (GenericRowData) acc;
+		long accOrder = accRowData.getLong(1);
+		GenericRowData firstAcc = accRowData;

Review comment:
       please rename the variable
   ```suggestion
   		GenericRowData lastAcc = accRowData;
   ```
   

##########
File path: flink-table/flink-table-planner-blink/src/test/java/org/apache/flink/table/planner/functions/aggfunctions/AggFunctionTestBase.java
##########
@@ -100,15 +100,15 @@ public void testAggregateWithMerge()
 				List<T> inputValues = inputValueSets.get(i);
 				T expected = expectedResults.get(i);
 				// equally split the vals sequence into two sequences
-				Tuple2<List<T>, List<T>> splitValues = splitValues(inputValues);
+				Tuple2<List, List> splitValues = splitValues(inputValues);
 				List<T> firstValues = splitValues.f0;
 				List<T> secondValues = splitValues.f1;
+
 				// 1. verify merge with accumulate
+				ACC acc = accumulateValues(firstValues);
 				List<ACC> accumulators = new ArrayList<>();
 				accumulators.add(accumulateValues(secondValues));
 
-				ACC acc = accumulateValues(firstValues);
-

Review comment:
       I think the `<T>` is meaningful, and we shouldn't update these code

##########
File path: flink-table/flink-table-planner-blink/src/test/java/org/apache/flink/table/planner/functions/aggfunctions/FirstLastValueAggFunctionWithOrderTestBase.java
##########
@@ -73,6 +76,112 @@ public void testAccumulateAndRetractWithoutMerge()
 		}
 	}
 
+	@Test
+	public void testAggregateWithMerge()
+		throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
+		AggregateFunction<T, ACC> aggregator = getAggregator();
+		if (UserDefinedFunctionUtils.ifMethodExistInFunction("merge", aggregator)) {
+			Method mergeFunc = aggregator.getClass().getMethod("merge", getAccClass(), Iterable.class);
+			List<List<T>> inputValueSets = getInputValueSets();
+			List<List<Long>> inputOrderSets = getInputOrderSets();
+			List<T> expectedResults = getExpectedResults();
+			Preconditions.checkArgument(inputValueSets.size() == expectedResults.size());
+			int size = getInputValueSets().size();
+			// iterate over input sets
+			for (int i = 0; i < size; ++i) {
+				List<T> inputValues = inputValueSets.get(i);
+				List<Long> inputOrders = inputOrderSets.get(i);
+				T expected = expectedResults.get(i);
+				// equally split the vals sequence into two sequences
+				Tuple2<List, List> splitValues = splitValues(inputValues);
+				Tuple2<List, List> splitOrders = splitValues(inputOrders);

Review comment:
       minor: Using `Tuple2<List<T>, List<T>>` to eliminate IDE compile warings

##########
File path: flink-table/flink-table-planner-blink/src/test/scala/org/apache/flink/table/planner/runtime/stream/sql/WindowAggregateITCase.scala
##########
@@ -77,7 +77,9 @@ class WindowAggregateITCase(mode: StateBackendMode)
         |  SUM(1),
         |  COUNT(`int`),
         |  COUNT(DISTINCT `float`),
-        |  concat_distinct_agg(name)
+        |  concat_distinct_agg(name),
+        |  first_value(`int`),

Review comment:
       Can we also add an IT test for first_value/last_value with retraction?

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstLastValueWithRetractAggFunctionBase.java
##########
@@ -0,0 +1,483 @@
+/*
+ * 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.flink.table.planner.functions.aggfunctions;
+
+import org.apache.flink.annotation.Internal;
+import org.apache.flink.table.api.DataTypes;
+import org.apache.flink.table.api.dataview.MapView;
+import org.apache.flink.table.data.StringData;
+import org.apache.flink.table.data.binary.BinaryStringData;
+import org.apache.flink.table.types.DataType;
+import org.apache.flink.table.types.logical.LogicalType;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.function.BiFunction;
+
+import static org.apache.flink.table.types.utils.DataTypeUtils.toInternalDataType;
+
+/**
+ * Base retraction aggregate function for FIRST_VALUE and LAST_VALUE.
+ */
+@Internal
+abstract class FirstLastValueWithRetractAggFunctionBase<T>
+		extends InternalAggregateFunction<T, FirstLastValueWithRetractAggFunctionBase.FirstLastValueWithRetractAccumulator<T>> {
+
+	private transient DataType valueDataType;
+
+	public FirstLastValueWithRetractAggFunctionBase(LogicalType valueType) {
+		this.valueDataType = toInternalDataType(valueType);
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Planning
+	// --------------------------------------------------------------------------------------------
+
+	@Override
+	public DataType[] getInputDataTypes() {
+		return new DataType[]{valueDataType};
+	}
+
+	@Override
+	public DataType getAccumulatorDataType() {
+		return DataTypes.STRUCTURED(
+			FirstLastValueWithRetractAccumulator.class,
+			DataTypes.FIELD(
+				"value",
+				valueDataType.nullable()),
+			DataTypes.FIELD(
+				"order",
+				DataTypes.BIGINT()),
+			DataTypes.FIELD(
+				"valueToOrderMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"valueToOrderRetractMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueRetractMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class)))
+		);
+	}
+
+	@Override
+	public DataType getOutputDataType() {
+		return valueDataType;
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Runtime
+	// --------------------------------------------------------------------------------------------
+
+	/** Accumulator for FIRST_VALUE or LAST_VALUE. */

Review comment:
       or -> and

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstLastValueWithRetractAggFunctionBase.java
##########
@@ -0,0 +1,483 @@
+/*
+ * 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.flink.table.planner.functions.aggfunctions;
+
+import org.apache.flink.annotation.Internal;
+import org.apache.flink.table.api.DataTypes;
+import org.apache.flink.table.api.dataview.MapView;
+import org.apache.flink.table.data.StringData;
+import org.apache.flink.table.data.binary.BinaryStringData;
+import org.apache.flink.table.types.DataType;
+import org.apache.flink.table.types.logical.LogicalType;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.function.BiFunction;
+
+import static org.apache.flink.table.types.utils.DataTypeUtils.toInternalDataType;
+
+/**
+ * Base retraction aggregate function for FIRST_VALUE and LAST_VALUE.
+ */
+@Internal
+abstract class FirstLastValueWithRetractAggFunctionBase<T>
+		extends InternalAggregateFunction<T, FirstLastValueWithRetractAggFunctionBase.FirstLastValueWithRetractAccumulator<T>> {
+
+	private transient DataType valueDataType;
+
+	public FirstLastValueWithRetractAggFunctionBase(LogicalType valueType) {
+		this.valueDataType = toInternalDataType(valueType);
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Planning
+	// --------------------------------------------------------------------------------------------
+
+	@Override
+	public DataType[] getInputDataTypes() {
+		return new DataType[]{valueDataType};
+	}
+
+	@Override
+	public DataType getAccumulatorDataType() {
+		return DataTypes.STRUCTURED(
+			FirstLastValueWithRetractAccumulator.class,
+			DataTypes.FIELD(
+				"value",
+				valueDataType.nullable()),
+			DataTypes.FIELD(
+				"order",
+				DataTypes.BIGINT()),
+			DataTypes.FIELD(
+				"valueToOrderMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"valueToOrderRetractMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueRetractMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class)))
+		);
+	}
+
+	@Override
+	public DataType getOutputDataType() {
+		return valueDataType;
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Runtime
+	// --------------------------------------------------------------------------------------------
+
+	/** Accumulator for FIRST_VALUE or LAST_VALUE. */
+	public static class FirstLastValueWithRetractAccumulator<T> {
+		public T value = null;
+		public Long order = null;
+		public MapView<T, List<Long>> valueToOrderMap = new MapView<>();
+		public MapView<T, List<Long>> valueToOrderRetractMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueRetractMap = new MapView<>();
+
+		@Override
+		public boolean equals(Object o) {
+			if (this == o) {
+				return true;
+			}
+			if (!(o instanceof FirstLastValueWithRetractAccumulator)) {
+				return false;
+			}
+			FirstLastValueWithRetractAccumulator<?> that = (FirstLastValueWithRetractAccumulator<?>) o;
+			return Objects.equals(value, that.value) &&
+				Objects.equals(order, that.order) &&
+				Objects.equals(valueToOrderMap, that.valueToOrderMap) &&
+				Objects.equals(valueToOrderRetractMap, that.valueToOrderRetractMap) &&
+				Objects.equals(orderToValueMap, that.orderToValueMap) &&
+				Objects.equals(orderToValueRetractMap, that.orderToValueRetractMap);
+		}
+
+		@Override
+		public int hashCode() {
+			return Objects.hash(
+				value,
+				order,
+				valueToOrderMap,
+				valueToOrderRetractMap,
+				orderToValueMap,
+				orderToValueRetractMap);
+		}
+	}
+
+	@Override
+	public FirstLastValueWithRetractAccumulator<T> createAccumulator() {
+		return new FirstLastValueWithRetractAccumulator<>();
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long order = System.nanoTime();
+			accumulate(acc, v, order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value, Long order,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long prevOrder = acc.order;
+			if (prevOrder == null || compare.apply(prevOrder, order)) {
+				acc.value = v;
+				acc.order = order;
+			}
+
+			// save order to orderToValueMap

Review comment:
       ```suggestion
   			// save order to valueToOrderMap
   ```

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstLastValueWithRetractAggFunctionBase.java
##########
@@ -0,0 +1,483 @@
+/*
+ * 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.flink.table.planner.functions.aggfunctions;
+
+import org.apache.flink.annotation.Internal;
+import org.apache.flink.table.api.DataTypes;
+import org.apache.flink.table.api.dataview.MapView;
+import org.apache.flink.table.data.StringData;
+import org.apache.flink.table.data.binary.BinaryStringData;
+import org.apache.flink.table.types.DataType;
+import org.apache.flink.table.types.logical.LogicalType;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.function.BiFunction;
+
+import static org.apache.flink.table.types.utils.DataTypeUtils.toInternalDataType;
+
+/**
+ * Base retraction aggregate function for FIRST_VALUE and LAST_VALUE.
+ */
+@Internal
+abstract class FirstLastValueWithRetractAggFunctionBase<T>
+		extends InternalAggregateFunction<T, FirstLastValueWithRetractAggFunctionBase.FirstLastValueWithRetractAccumulator<T>> {
+
+	private transient DataType valueDataType;
+
+	public FirstLastValueWithRetractAggFunctionBase(LogicalType valueType) {
+		this.valueDataType = toInternalDataType(valueType);
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Planning
+	// --------------------------------------------------------------------------------------------
+
+	@Override
+	public DataType[] getInputDataTypes() {
+		return new DataType[]{valueDataType};
+	}
+
+	@Override
+	public DataType getAccumulatorDataType() {
+		return DataTypes.STRUCTURED(
+			FirstLastValueWithRetractAccumulator.class,
+			DataTypes.FIELD(
+				"value",
+				valueDataType.nullable()),
+			DataTypes.FIELD(
+				"order",
+				DataTypes.BIGINT()),
+			DataTypes.FIELD(
+				"valueToOrderMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"valueToOrderRetractMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueRetractMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class)))
+		);
+	}
+
+	@Override
+	public DataType getOutputDataType() {
+		return valueDataType;
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Runtime
+	// --------------------------------------------------------------------------------------------
+
+	/** Accumulator for FIRST_VALUE or LAST_VALUE. */
+	public static class FirstLastValueWithRetractAccumulator<T> {
+		public T value = null;
+		public Long order = null;
+		public MapView<T, List<Long>> valueToOrderMap = new MapView<>();
+		public MapView<T, List<Long>> valueToOrderRetractMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueRetractMap = new MapView<>();
+
+		@Override
+		public boolean equals(Object o) {
+			if (this == o) {
+				return true;
+			}
+			if (!(o instanceof FirstLastValueWithRetractAccumulator)) {
+				return false;
+			}
+			FirstLastValueWithRetractAccumulator<?> that = (FirstLastValueWithRetractAccumulator<?>) o;
+			return Objects.equals(value, that.value) &&
+				Objects.equals(order, that.order) &&
+				Objects.equals(valueToOrderMap, that.valueToOrderMap) &&
+				Objects.equals(valueToOrderRetractMap, that.valueToOrderRetractMap) &&
+				Objects.equals(orderToValueMap, that.orderToValueMap) &&
+				Objects.equals(orderToValueRetractMap, that.orderToValueRetractMap);
+		}
+
+		@Override
+		public int hashCode() {
+			return Objects.hash(
+				value,
+				order,
+				valueToOrderMap,
+				valueToOrderRetractMap,
+				orderToValueMap,
+				orderToValueRetractMap);
+		}
+	}
+
+	@Override
+	public FirstLastValueWithRetractAccumulator<T> createAccumulator() {
+		return new FirstLastValueWithRetractAccumulator<>();
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long order = System.nanoTime();
+			accumulate(acc, v, order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value, Long order,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long prevOrder = acc.order;
+			if (prevOrder == null || compare.apply(prevOrder, order)) {
+				acc.value = v;
+				acc.order = order;
+			}
+
+			// save order to orderToValueMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList == null) {
+				orderList = new ArrayList<>();
+				orderList.add(order);
+			} else {
+				// use insertion sort,
+				// for the O(1) time complexity if order is asc, compare from back to front
+				int i = orderList.size();
+				boolean isInsert = false;
+				while (i > 0) {
+					Long tempOrder = orderList.get(i - 1);
+					if (tempOrder <= order) {
+						orderList.add(i, order);
+						isInsert = true;
+						break;
+					}
+					i--;
+				}
+				if (!isInsert) {
+					orderList.add(0, order);
+				}
+			}
+			// update valueToOrderMap
+			acc.valueToOrderMap.put(v, orderList);
+
+			// update orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			if (valueList == null) {
+				valueList = new ArrayList<>();
+			}
+			valueList.add(v);
+			acc.orderToValueMap.put(order, valueList);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), compare);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, Long order, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				Long order = orderList.get(0);
+				retract(acc, v, order);
+			}
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value, Long order) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			// remove from valueToOrderMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				orderList.remove(0);
+				if (orderList.isEmpty()) {
+					acc.valueToOrderMap.remove(v);
+				} else {
+					acc.valueToOrderMap.put(v, orderList);
+				}
+			} else {
+				// if not exist, save to valueToOrderRetractMap
+				List<Long> retractOrderList = acc.valueToOrderRetractMap.get(v);
+				if (retractOrderList == null) {
+					retractOrderList = new ArrayList<>();
+				}
+				retractOrderList.add(order);
+				acc.valueToOrderRetractMap.put(v, retractOrderList);
+			}
+			// remove from orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			int index = -1;
+			if (valueList != null &&  (index = valueList.indexOf(v)) >= 0) {
+				valueList.remove(index);
+				if (valueList.isEmpty()) {
+					acc.orderToValueMap.remove(order);
+				} else {
+					acc.orderToValueMap.put(order, valueList);
+				}
+			} else {
+				// if not exist, save to orderToValueRetractMap
+				List<T> retractValueList = acc.orderToValueRetractMap.get(order);
+				if (retractValueList == null) {
+					retractValueList = new ArrayList<>();
+				}
+				retractValueList.add(v);
+				acc.orderToValueRetractMap.put(order, retractValueList);
+			}
+			// if retract current first value

Review comment:
       ```suggestion
   			// update the acc value if the retracted value equals first/last value
   ```

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstLastValueWithRetractAggFunctionBase.java
##########
@@ -0,0 +1,483 @@
+/*
+ * 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.flink.table.planner.functions.aggfunctions;
+
+import org.apache.flink.annotation.Internal;
+import org.apache.flink.table.api.DataTypes;
+import org.apache.flink.table.api.dataview.MapView;
+import org.apache.flink.table.data.StringData;
+import org.apache.flink.table.data.binary.BinaryStringData;
+import org.apache.flink.table.types.DataType;
+import org.apache.flink.table.types.logical.LogicalType;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.function.BiFunction;
+
+import static org.apache.flink.table.types.utils.DataTypeUtils.toInternalDataType;
+
+/**
+ * Base retraction aggregate function for FIRST_VALUE and LAST_VALUE.
+ */
+@Internal
+abstract class FirstLastValueWithRetractAggFunctionBase<T>
+		extends InternalAggregateFunction<T, FirstLastValueWithRetractAggFunctionBase.FirstLastValueWithRetractAccumulator<T>> {
+
+	private transient DataType valueDataType;
+
+	public FirstLastValueWithRetractAggFunctionBase(LogicalType valueType) {
+		this.valueDataType = toInternalDataType(valueType);
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Planning
+	// --------------------------------------------------------------------------------------------
+
+	@Override
+	public DataType[] getInputDataTypes() {
+		return new DataType[]{valueDataType};
+	}
+
+	@Override
+	public DataType getAccumulatorDataType() {
+		return DataTypes.STRUCTURED(
+			FirstLastValueWithRetractAccumulator.class,
+			DataTypes.FIELD(
+				"value",
+				valueDataType.nullable()),
+			DataTypes.FIELD(
+				"order",
+				DataTypes.BIGINT()),
+			DataTypes.FIELD(
+				"valueToOrderMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"valueToOrderRetractMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueRetractMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class)))
+		);
+	}
+
+	@Override
+	public DataType getOutputDataType() {
+		return valueDataType;
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Runtime
+	// --------------------------------------------------------------------------------------------
+
+	/** Accumulator for FIRST_VALUE or LAST_VALUE. */
+	public static class FirstLastValueWithRetractAccumulator<T> {
+		public T value = null;
+		public Long order = null;
+		public MapView<T, List<Long>> valueToOrderMap = new MapView<>();
+		public MapView<T, List<Long>> valueToOrderRetractMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueRetractMap = new MapView<>();
+
+		@Override
+		public boolean equals(Object o) {
+			if (this == o) {
+				return true;
+			}
+			if (!(o instanceof FirstLastValueWithRetractAccumulator)) {
+				return false;
+			}
+			FirstLastValueWithRetractAccumulator<?> that = (FirstLastValueWithRetractAccumulator<?>) o;
+			return Objects.equals(value, that.value) &&
+				Objects.equals(order, that.order) &&
+				Objects.equals(valueToOrderMap, that.valueToOrderMap) &&
+				Objects.equals(valueToOrderRetractMap, that.valueToOrderRetractMap) &&
+				Objects.equals(orderToValueMap, that.orderToValueMap) &&
+				Objects.equals(orderToValueRetractMap, that.orderToValueRetractMap);
+		}
+
+		@Override
+		public int hashCode() {
+			return Objects.hash(
+				value,
+				order,
+				valueToOrderMap,
+				valueToOrderRetractMap,
+				orderToValueMap,
+				orderToValueRetractMap);
+		}
+	}
+
+	@Override
+	public FirstLastValueWithRetractAccumulator<T> createAccumulator() {
+		return new FirstLastValueWithRetractAccumulator<>();
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long order = System.nanoTime();
+			accumulate(acc, v, order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value, Long order,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long prevOrder = acc.order;
+			if (prevOrder == null || compare.apply(prevOrder, order)) {
+				acc.value = v;
+				acc.order = order;
+			}
+
+			// save order to orderToValueMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList == null) {
+				orderList = new ArrayList<>();
+				orderList.add(order);
+			} else {
+				// use insertion sort,
+				// for the O(1) time complexity if order is asc, compare from back to front
+				int i = orderList.size();
+				boolean isInsert = false;
+				while (i > 0) {
+					Long tempOrder = orderList.get(i - 1);
+					if (tempOrder <= order) {
+						orderList.add(i, order);
+						isInsert = true;
+						break;
+					}
+					i--;
+				}
+				if (!isInsert) {
+					orderList.add(0, order);
+				}
+			}
+			// update valueToOrderMap
+			acc.valueToOrderMap.put(v, orderList);
+
+			// update orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			if (valueList == null) {
+				valueList = new ArrayList<>();
+			}
+			valueList.add(v);
+			acc.orderToValueMap.put(order, valueList);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), compare);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, Long order, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				Long order = orderList.get(0);
+				retract(acc, v, order);
+			}
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value, Long order) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			// remove from valueToOrderMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				orderList.remove(0);
+				if (orderList.isEmpty()) {
+					acc.valueToOrderMap.remove(v);
+				} else {
+					acc.valueToOrderMap.put(v, orderList);
+				}
+			} else {
+				// if not exist, save to valueToOrderRetractMap
+				List<Long> retractOrderList = acc.valueToOrderRetractMap.get(v);
+				if (retractOrderList == null) {
+					retractOrderList = new ArrayList<>();
+				}
+				retractOrderList.add(order);
+				acc.valueToOrderRetractMap.put(v, retractOrderList);
+			}
+			// remove from orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			int index = -1;
+			if (valueList != null &&  (index = valueList.indexOf(v)) >= 0) {
+				valueList.remove(index);
+				if (valueList.isEmpty()) {
+					acc.orderToValueMap.remove(order);
+				} else {
+					acc.orderToValueMap.put(order, valueList);
+				}
+			} else {
+				// if not exist, save to orderToValueRetractMap
+				List<T> retractValueList = acc.orderToValueRetractMap.get(order);
+				if (retractValueList == null) {
+					retractValueList = new ArrayList<>();
+				}
+				retractValueList.add(v);
+				acc.orderToValueRetractMap.put(order, retractValueList);
+			}
+			// if retract current first value
+			if (v.equals(acc.value)) {
+				updateValue(acc);
+			}
+		}
+	}
+
+	public void merge(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Iterable<FirstLastValueWithRetractAccumulator<T>> its,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		for (FirstLastValueWithRetractAccumulator<T> it : its) {

Review comment:
       ```suggestion
   		for (FirstLastValueWithRetractAccumulator<T> otherAcc : accIt) {
   ```

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/LastValueAggFunction.java
##########
@@ -83,6 +83,7 @@ public void accumulate(RowData rowData, Object value) {
 		GenericRowData acc = (GenericRowData) rowData;
 		if (value != null) {
 			acc.setField(0, value);
+			acc.setField(1, System.nanoTime());

Review comment:
       ditto

##########
File path: flink-table/flink-table-planner-blink/src/test/java/org/apache/flink/table/planner/functions/aggfunctions/AggFunctionTestBase.java
##########
@@ -240,13 +240,13 @@ protected void retractValues(ACC accumulator, List<T> values)
 		}
 	}
 
-	protected Tuple2<List<T>, List<T>> splitValues(List<T> values) {
+	protected Tuple2<List, List> splitValues(List values) {
 		return splitValues(values, values.size() / 2);
 	}
 
-	protected Tuple2<List<T>, List<T>> splitValues(List<T> values, int index) {
-		List<T> firstValues = new ArrayList<>();
-		List<T> secondValues = new ArrayList<>();
+	protected Tuple2<List, List> splitValues(List values, int index) {
+		List firstValues = new ArrayList<>();
+		List secondValues = new ArrayList<>();

Review comment:
       Could we revert this change?

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/LastValueAggFunction.java
##########
@@ -106,6 +107,27 @@ public void accumulate(GenericRowData acc, StringData value, Long order) {
 		}
 	}
 
+	public void merge(RowData acc, Iterable<RowData> its) {
+		GenericRowData accRowData = (GenericRowData) acc;
+		long accOrder = accRowData.getLong(1);
+		GenericRowData firstAcc = accRowData;
+		boolean needUpdate = false;
+
+		for (RowData rowData : its) {
+			long order = rowData.getLong(1);
+			// if there is a upper order
+			if (accOrder < order) {

Review comment:
       Minor: We can exchange the operands order to make code more readable
   ```suggestion
   			if (order > accOrder) {
   ```

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstValueAggFunction.java
##########
@@ -107,6 +107,27 @@ public void accumulate(RowData rowData, StringData value, Long order) {
 		}
 	}
 
+	public void merge(RowData acc, Iterable<RowData> its) {
+		GenericRowData accRowData = (GenericRowData) acc;
+		long accOrder = accRowData.getLong(1);
+		GenericRowData firstAcc = accRowData;
+		boolean needUpdate = false;
+
+		for (RowData rowData : its) {
+			long order = rowData.getLong(1);
+			// if there is a lower order
+			if (accOrder > order) {

Review comment:
       minor: We can exchange the operands order to make code more readable
   ```suggestion
   			if (order < accOrder) {
   ```

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstValueAggFunction.java
##########
@@ -107,6 +107,27 @@ public void accumulate(RowData rowData, StringData value, Long order) {
 		}
 	}
 
+	public void merge(RowData acc, Iterable<RowData> its) {
+		GenericRowData accRowData = (GenericRowData) acc;
+		long accOrder = accRowData.getLong(1);
+		GenericRowData firstAcc = accRowData;
+		boolean needUpdate = false;
+
+		for (RowData rowData : its) {

Review comment:
       How about use Iterator ?
   ```	
   Iterator<RowData> iterator = it.iterator();
   while (iterator.hasNext()) {
   ```

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstLastValueWithRetractAggFunctionBase.java
##########
@@ -0,0 +1,483 @@
+/*
+ * 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.flink.table.planner.functions.aggfunctions;
+
+import org.apache.flink.annotation.Internal;
+import org.apache.flink.table.api.DataTypes;
+import org.apache.flink.table.api.dataview.MapView;
+import org.apache.flink.table.data.StringData;
+import org.apache.flink.table.data.binary.BinaryStringData;
+import org.apache.flink.table.types.DataType;
+import org.apache.flink.table.types.logical.LogicalType;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.function.BiFunction;
+
+import static org.apache.flink.table.types.utils.DataTypeUtils.toInternalDataType;
+
+/**
+ * Base retraction aggregate function for FIRST_VALUE and LAST_VALUE.

Review comment:
       minor: 
   ```suggestion
    * Base aggregate function with retraction for FIRST_VALUE and LAST_VALUE.
   ```

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstLastValueWithRetractAggFunctionBase.java
##########
@@ -0,0 +1,483 @@
+/*
+ * 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.flink.table.planner.functions.aggfunctions;
+
+import org.apache.flink.annotation.Internal;
+import org.apache.flink.table.api.DataTypes;
+import org.apache.flink.table.api.dataview.MapView;
+import org.apache.flink.table.data.StringData;
+import org.apache.flink.table.data.binary.BinaryStringData;
+import org.apache.flink.table.types.DataType;
+import org.apache.flink.table.types.logical.LogicalType;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.function.BiFunction;
+
+import static org.apache.flink.table.types.utils.DataTypeUtils.toInternalDataType;
+
+/**
+ * Base retraction aggregate function for FIRST_VALUE and LAST_VALUE.
+ */
+@Internal
+abstract class FirstLastValueWithRetractAggFunctionBase<T>
+		extends InternalAggregateFunction<T, FirstLastValueWithRetractAggFunctionBase.FirstLastValueWithRetractAccumulator<T>> {
+
+	private transient DataType valueDataType;
+
+	public FirstLastValueWithRetractAggFunctionBase(LogicalType valueType) {
+		this.valueDataType = toInternalDataType(valueType);
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Planning
+	// --------------------------------------------------------------------------------------------
+
+	@Override
+	public DataType[] getInputDataTypes() {
+		return new DataType[]{valueDataType};
+	}
+
+	@Override
+	public DataType getAccumulatorDataType() {
+		return DataTypes.STRUCTURED(
+			FirstLastValueWithRetractAccumulator.class,
+			DataTypes.FIELD(
+				"value",
+				valueDataType.nullable()),
+			DataTypes.FIELD(
+				"order",
+				DataTypes.BIGINT()),
+			DataTypes.FIELD(
+				"valueToOrderMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"valueToOrderRetractMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueRetractMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class)))
+		);
+	}
+
+	@Override
+	public DataType getOutputDataType() {
+		return valueDataType;
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Runtime
+	// --------------------------------------------------------------------------------------------
+
+	/** Accumulator for FIRST_VALUE or LAST_VALUE. */
+	public static class FirstLastValueWithRetractAccumulator<T> {
+		public T value = null;
+		public Long order = null;
+		public MapView<T, List<Long>> valueToOrderMap = new MapView<>();
+		public MapView<T, List<Long>> valueToOrderRetractMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueRetractMap = new MapView<>();
+
+		@Override
+		public boolean equals(Object o) {
+			if (this == o) {
+				return true;
+			}
+			if (!(o instanceof FirstLastValueWithRetractAccumulator)) {
+				return false;
+			}
+			FirstLastValueWithRetractAccumulator<?> that = (FirstLastValueWithRetractAccumulator<?>) o;
+			return Objects.equals(value, that.value) &&
+				Objects.equals(order, that.order) &&
+				Objects.equals(valueToOrderMap, that.valueToOrderMap) &&
+				Objects.equals(valueToOrderRetractMap, that.valueToOrderRetractMap) &&
+				Objects.equals(orderToValueMap, that.orderToValueMap) &&
+				Objects.equals(orderToValueRetractMap, that.orderToValueRetractMap);
+		}
+
+		@Override
+		public int hashCode() {
+			return Objects.hash(
+				value,
+				order,
+				valueToOrderMap,
+				valueToOrderRetractMap,
+				orderToValueMap,
+				orderToValueRetractMap);
+		}
+	}
+
+	@Override
+	public FirstLastValueWithRetractAccumulator<T> createAccumulator() {
+		return new FirstLastValueWithRetractAccumulator<>();
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long order = System.nanoTime();

Review comment:
       ```suggestion
   			Long order = System.currentTimeMillis();
   ```

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstLastValueWithRetractAggFunctionBase.java
##########
@@ -0,0 +1,483 @@
+/*
+ * 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.flink.table.planner.functions.aggfunctions;
+
+import org.apache.flink.annotation.Internal;
+import org.apache.flink.table.api.DataTypes;
+import org.apache.flink.table.api.dataview.MapView;
+import org.apache.flink.table.data.StringData;
+import org.apache.flink.table.data.binary.BinaryStringData;
+import org.apache.flink.table.types.DataType;
+import org.apache.flink.table.types.logical.LogicalType;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.function.BiFunction;
+
+import static org.apache.flink.table.types.utils.DataTypeUtils.toInternalDataType;
+
+/**
+ * Base retraction aggregate function for FIRST_VALUE and LAST_VALUE.
+ */
+@Internal
+abstract class FirstLastValueWithRetractAggFunctionBase<T>
+		extends InternalAggregateFunction<T, FirstLastValueWithRetractAggFunctionBase.FirstLastValueWithRetractAccumulator<T>> {
+
+	private transient DataType valueDataType;
+
+	public FirstLastValueWithRetractAggFunctionBase(LogicalType valueType) {
+		this.valueDataType = toInternalDataType(valueType);
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Planning
+	// --------------------------------------------------------------------------------------------
+
+	@Override
+	public DataType[] getInputDataTypes() {
+		return new DataType[]{valueDataType};
+	}
+
+	@Override
+	public DataType getAccumulatorDataType() {
+		return DataTypes.STRUCTURED(
+			FirstLastValueWithRetractAccumulator.class,
+			DataTypes.FIELD(
+				"value",
+				valueDataType.nullable()),
+			DataTypes.FIELD(
+				"order",
+				DataTypes.BIGINT()),
+			DataTypes.FIELD(
+				"valueToOrderMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"valueToOrderRetractMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueRetractMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class)))
+		);
+	}
+
+	@Override
+	public DataType getOutputDataType() {
+		return valueDataType;
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Runtime
+	// --------------------------------------------------------------------------------------------
+
+	/** Accumulator for FIRST_VALUE or LAST_VALUE. */
+	public static class FirstLastValueWithRetractAccumulator<T> {
+		public T value = null;
+		public Long order = null;
+		public MapView<T, List<Long>> valueToOrderMap = new MapView<>();
+		public MapView<T, List<Long>> valueToOrderRetractMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueRetractMap = new MapView<>();
+
+		@Override
+		public boolean equals(Object o) {
+			if (this == o) {
+				return true;
+			}
+			if (!(o instanceof FirstLastValueWithRetractAccumulator)) {
+				return false;
+			}
+			FirstLastValueWithRetractAccumulator<?> that = (FirstLastValueWithRetractAccumulator<?>) o;
+			return Objects.equals(value, that.value) &&
+				Objects.equals(order, that.order) &&
+				Objects.equals(valueToOrderMap, that.valueToOrderMap) &&
+				Objects.equals(valueToOrderRetractMap, that.valueToOrderRetractMap) &&
+				Objects.equals(orderToValueMap, that.orderToValueMap) &&
+				Objects.equals(orderToValueRetractMap, that.orderToValueRetractMap);
+		}
+
+		@Override
+		public int hashCode() {
+			return Objects.hash(
+				value,
+				order,
+				valueToOrderMap,
+				valueToOrderRetractMap,
+				orderToValueMap,
+				orderToValueRetractMap);
+		}
+	}
+
+	@Override
+	public FirstLastValueWithRetractAccumulator<T> createAccumulator() {
+		return new FirstLastValueWithRetractAccumulator<>();
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long order = System.nanoTime();
+			accumulate(acc, v, order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value, Long order,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long prevOrder = acc.order;
+			if (prevOrder == null || compare.apply(prevOrder, order)) {
+				acc.value = v;
+				acc.order = order;
+			}
+
+			// save order to orderToValueMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList == null) {
+				orderList = new ArrayList<>();
+				orderList.add(order);
+			} else {
+				// use insertion sort,
+				// for the O(1) time complexity if order is asc, compare from back to front
+				int i = orderList.size();
+				boolean isInsert = false;
+				while (i > 0) {
+					Long tempOrder = orderList.get(i - 1);
+					if (tempOrder <= order) {
+						orderList.add(i, order);
+						isInsert = true;
+						break;
+					}
+					i--;
+				}
+				if (!isInsert) {
+					orderList.add(0, order);
+				}
+			}
+			// update valueToOrderMap
+			acc.valueToOrderMap.put(v, orderList);
+
+			// update orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			if (valueList == null) {
+				valueList = new ArrayList<>();
+			}
+			valueList.add(v);
+			acc.orderToValueMap.put(order, valueList);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), compare);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, Long order, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				Long order = orderList.get(0);
+				retract(acc, v, order);
+			}
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value, Long order) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			// remove from valueToOrderMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				orderList.remove(0);
+				if (orderList.isEmpty()) {
+					acc.valueToOrderMap.remove(v);
+				} else {
+					acc.valueToOrderMap.put(v, orderList);
+				}
+			} else {
+				// if not exist, save to valueToOrderRetractMap
+				List<Long> retractOrderList = acc.valueToOrderRetractMap.get(v);
+				if (retractOrderList == null) {
+					retractOrderList = new ArrayList<>();
+				}
+				retractOrderList.add(order);
+				acc.valueToOrderRetractMap.put(v, retractOrderList);
+			}
+			// remove from orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			int index = -1;

Review comment:
       ```suggestion
   			int index;
   ```

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstLastValueWithRetractAggFunctionBase.java
##########
@@ -0,0 +1,483 @@
+/*
+ * 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.flink.table.planner.functions.aggfunctions;
+
+import org.apache.flink.annotation.Internal;
+import org.apache.flink.table.api.DataTypes;
+import org.apache.flink.table.api.dataview.MapView;
+import org.apache.flink.table.data.StringData;
+import org.apache.flink.table.data.binary.BinaryStringData;
+import org.apache.flink.table.types.DataType;
+import org.apache.flink.table.types.logical.LogicalType;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.function.BiFunction;
+
+import static org.apache.flink.table.types.utils.DataTypeUtils.toInternalDataType;
+
+/**
+ * Base retraction aggregate function for FIRST_VALUE and LAST_VALUE.
+ */
+@Internal
+abstract class FirstLastValueWithRetractAggFunctionBase<T>
+		extends InternalAggregateFunction<T, FirstLastValueWithRetractAggFunctionBase.FirstLastValueWithRetractAccumulator<T>> {
+
+	private transient DataType valueDataType;
+
+	public FirstLastValueWithRetractAggFunctionBase(LogicalType valueType) {
+		this.valueDataType = toInternalDataType(valueType);
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Planning
+	// --------------------------------------------------------------------------------------------
+
+	@Override
+	public DataType[] getInputDataTypes() {
+		return new DataType[]{valueDataType};
+	}
+
+	@Override
+	public DataType getAccumulatorDataType() {
+		return DataTypes.STRUCTURED(
+			FirstLastValueWithRetractAccumulator.class,
+			DataTypes.FIELD(
+				"value",
+				valueDataType.nullable()),
+			DataTypes.FIELD(
+				"order",
+				DataTypes.BIGINT()),
+			DataTypes.FIELD(
+				"valueToOrderMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"valueToOrderRetractMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueRetractMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class)))
+		);
+	}
+
+	@Override
+	public DataType getOutputDataType() {
+		return valueDataType;
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Runtime
+	// --------------------------------------------------------------------------------------------
+
+	/** Accumulator for FIRST_VALUE or LAST_VALUE. */
+	public static class FirstLastValueWithRetractAccumulator<T> {
+		public T value = null;
+		public Long order = null;
+		public MapView<T, List<Long>> valueToOrderMap = new MapView<>();
+		public MapView<T, List<Long>> valueToOrderRetractMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueRetractMap = new MapView<>();
+
+		@Override
+		public boolean equals(Object o) {
+			if (this == o) {
+				return true;
+			}
+			if (!(o instanceof FirstLastValueWithRetractAccumulator)) {
+				return false;
+			}
+			FirstLastValueWithRetractAccumulator<?> that = (FirstLastValueWithRetractAccumulator<?>) o;
+			return Objects.equals(value, that.value) &&
+				Objects.equals(order, that.order) &&
+				Objects.equals(valueToOrderMap, that.valueToOrderMap) &&
+				Objects.equals(valueToOrderRetractMap, that.valueToOrderRetractMap) &&
+				Objects.equals(orderToValueMap, that.orderToValueMap) &&
+				Objects.equals(orderToValueRetractMap, that.orderToValueRetractMap);
+		}
+
+		@Override
+		public int hashCode() {
+			return Objects.hash(
+				value,
+				order,
+				valueToOrderMap,
+				valueToOrderRetractMap,
+				orderToValueMap,
+				orderToValueRetractMap);
+		}
+	}
+
+	@Override
+	public FirstLastValueWithRetractAccumulator<T> createAccumulator() {
+		return new FirstLastValueWithRetractAccumulator<>();
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long order = System.nanoTime();
+			accumulate(acc, v, order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value, Long order,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long prevOrder = acc.order;
+			if (prevOrder == null || compare.apply(prevOrder, order)) {
+				acc.value = v;
+				acc.order = order;
+			}
+
+			// save order to orderToValueMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList == null) {
+				orderList = new ArrayList<>();
+				orderList.add(order);
+			} else {
+				// use insertion sort,
+				// for the O(1) time complexity if order is asc, compare from back to front
+				int i = orderList.size();
+				boolean isInsert = false;
+				while (i > 0) {
+					Long tempOrder = orderList.get(i - 1);
+					if (tempOrder <= order) {
+						orderList.add(i, order);
+						isInsert = true;
+						break;
+					}
+					i--;
+				}
+				if (!isInsert) {
+					orderList.add(0, order);
+				}
+			}
+			// update valueToOrderMap
+			acc.valueToOrderMap.put(v, orderList);
+
+			// update orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			if (valueList == null) {
+				valueList = new ArrayList<>();
+			}
+			valueList.add(v);
+			acc.orderToValueMap.put(order, valueList);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), compare);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, Long order, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				Long order = orderList.get(0);
+				retract(acc, v, order);
+			}
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value, Long order) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			// remove from valueToOrderMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				orderList.remove(0);
+				if (orderList.isEmpty()) {
+					acc.valueToOrderMap.remove(v);
+				} else {
+					acc.valueToOrderMap.put(v, orderList);
+				}
+			} else {
+				// if not exist, save to valueToOrderRetractMap

Review comment:
       exists

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstLastValueWithRetractAggFunctionBase.java
##########
@@ -0,0 +1,483 @@
+/*
+ * 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.flink.table.planner.functions.aggfunctions;
+
+import org.apache.flink.annotation.Internal;
+import org.apache.flink.table.api.DataTypes;
+import org.apache.flink.table.api.dataview.MapView;
+import org.apache.flink.table.data.StringData;
+import org.apache.flink.table.data.binary.BinaryStringData;
+import org.apache.flink.table.types.DataType;
+import org.apache.flink.table.types.logical.LogicalType;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.function.BiFunction;
+
+import static org.apache.flink.table.types.utils.DataTypeUtils.toInternalDataType;
+
+/**
+ * Base retraction aggregate function for FIRST_VALUE and LAST_VALUE.
+ */
+@Internal
+abstract class FirstLastValueWithRetractAggFunctionBase<T>
+		extends InternalAggregateFunction<T, FirstLastValueWithRetractAggFunctionBase.FirstLastValueWithRetractAccumulator<T>> {
+
+	private transient DataType valueDataType;
+
+	public FirstLastValueWithRetractAggFunctionBase(LogicalType valueType) {
+		this.valueDataType = toInternalDataType(valueType);
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Planning
+	// --------------------------------------------------------------------------------------------
+
+	@Override
+	public DataType[] getInputDataTypes() {
+		return new DataType[]{valueDataType};
+	}
+
+	@Override
+	public DataType getAccumulatorDataType() {
+		return DataTypes.STRUCTURED(
+			FirstLastValueWithRetractAccumulator.class,
+			DataTypes.FIELD(
+				"value",
+				valueDataType.nullable()),
+			DataTypes.FIELD(
+				"order",
+				DataTypes.BIGINT()),
+			DataTypes.FIELD(
+				"valueToOrderMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"valueToOrderRetractMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueRetractMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class)))
+		);
+	}
+
+	@Override
+	public DataType getOutputDataType() {
+		return valueDataType;
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Runtime
+	// --------------------------------------------------------------------------------------------
+
+	/** Accumulator for FIRST_VALUE or LAST_VALUE. */
+	public static class FirstLastValueWithRetractAccumulator<T> {
+		public T value = null;
+		public Long order = null;
+		public MapView<T, List<Long>> valueToOrderMap = new MapView<>();
+		public MapView<T, List<Long>> valueToOrderRetractMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueRetractMap = new MapView<>();
+
+		@Override
+		public boolean equals(Object o) {
+			if (this == o) {
+				return true;
+			}
+			if (!(o instanceof FirstLastValueWithRetractAccumulator)) {
+				return false;
+			}
+			FirstLastValueWithRetractAccumulator<?> that = (FirstLastValueWithRetractAccumulator<?>) o;
+			return Objects.equals(value, that.value) &&
+				Objects.equals(order, that.order) &&
+				Objects.equals(valueToOrderMap, that.valueToOrderMap) &&
+				Objects.equals(valueToOrderRetractMap, that.valueToOrderRetractMap) &&
+				Objects.equals(orderToValueMap, that.orderToValueMap) &&
+				Objects.equals(orderToValueRetractMap, that.orderToValueRetractMap);
+		}
+
+		@Override
+		public int hashCode() {
+			return Objects.hash(
+				value,
+				order,
+				valueToOrderMap,
+				valueToOrderRetractMap,
+				orderToValueMap,
+				orderToValueRetractMap);
+		}
+	}
+
+	@Override
+	public FirstLastValueWithRetractAccumulator<T> createAccumulator() {
+		return new FirstLastValueWithRetractAccumulator<>();
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long order = System.nanoTime();
+			accumulate(acc, v, order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value, Long order,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long prevOrder = acc.order;
+			if (prevOrder == null || compare.apply(prevOrder, order)) {
+				acc.value = v;
+				acc.order = order;
+			}
+
+			// save order to orderToValueMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList == null) {
+				orderList = new ArrayList<>();
+				orderList.add(order);
+			} else {
+				// use insertion sort,
+				// for the O(1) time complexity if order is asc, compare from back to front
+				int i = orderList.size();
+				boolean isInsert = false;
+				while (i > 0) {
+					Long tempOrder = orderList.get(i - 1);
+					if (tempOrder <= order) {
+						orderList.add(i, order);
+						isInsert = true;
+						break;
+					}
+					i--;
+				}
+				if (!isInsert) {
+					orderList.add(0, order);
+				}
+			}
+			// update valueToOrderMap
+			acc.valueToOrderMap.put(v, orderList);
+
+			// update orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			if (valueList == null) {
+				valueList = new ArrayList<>();
+			}
+			valueList.add(v);
+			acc.orderToValueMap.put(order, valueList);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), compare);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, Long order, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				Long order = orderList.get(0);
+				retract(acc, v, order);
+			}
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value, Long order) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			// remove from valueToOrderMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				orderList.remove(0);
+				if (orderList.isEmpty()) {
+					acc.valueToOrderMap.remove(v);
+				} else {
+					acc.valueToOrderMap.put(v, orderList);
+				}
+			} else {
+				// if not exist, save to valueToOrderRetractMap
+				List<Long> retractOrderList = acc.valueToOrderRetractMap.get(v);
+				if (retractOrderList == null) {
+					retractOrderList = new ArrayList<>();
+				}
+				retractOrderList.add(order);
+				acc.valueToOrderRetractMap.put(v, retractOrderList);
+			}
+			// remove from orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			int index = -1;
+			if (valueList != null &&  (index = valueList.indexOf(v)) >= 0) {
+				valueList.remove(index);
+				if (valueList.isEmpty()) {
+					acc.orderToValueMap.remove(order);
+				} else {
+					acc.orderToValueMap.put(order, valueList);
+				}
+			} else {
+				// if not exist, save to orderToValueRetractMap
+				List<T> retractValueList = acc.orderToValueRetractMap.get(order);
+				if (retractValueList == null) {
+					retractValueList = new ArrayList<>();
+				}
+				retractValueList.add(v);
+				acc.orderToValueRetractMap.put(order, retractValueList);
+			}
+			// if retract current first value
+			if (v.equals(acc.value)) {
+				updateValue(acc);
+			}
+		}
+	}
+
+	public void merge(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Iterable<FirstLastValueWithRetractAccumulator<T>> its,

Review comment:
       `its` => `accIt`

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/LastValueWithRetractAggFunction.java
##########
@@ -19,221 +19,74 @@
 package org.apache.flink.table.planner.functions.aggfunctions;
 
 import org.apache.flink.annotation.Internal;
-import org.apache.flink.table.api.DataTypes;
-import org.apache.flink.table.api.dataview.MapView;
 import org.apache.flink.table.data.StringData;
 import org.apache.flink.table.data.binary.BinaryStringData;
-import org.apache.flink.table.types.DataType;
 import org.apache.flink.table.types.logical.LogicalType;
 
-import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.List;
-import java.util.Objects;
-
-import static org.apache.flink.table.types.utils.DataTypeUtils.toInternalDataType;
+import java.util.function.BiFunction;
 
 /**
  * Built-in LAST_VALUE with retraction aggregate function.
  */
 @Internal
 public final class LastValueWithRetractAggFunction<T>
-		extends InternalAggregateFunction<T, LastValueWithRetractAggFunction.LastValueWithRetractAccumulator<T>> {
-
-	private transient DataType valueDataType;
+		extends FirstLastValueWithRetractAggFunctionBase<T> {
 
+	private static final BiFunction<Long, Long, Boolean> comparator = (x, y) -> (x - y) < 0;

Review comment:
       ```suggestion
   	private static final BiFunction<Long, Long, Boolean> comparator = (order1, order2) -> order1 < order2;
   ```

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstValueWithRetractAggFunction.java
##########
@@ -19,225 +19,72 @@
 package org.apache.flink.table.planner.functions.aggfunctions;
 
 import org.apache.flink.annotation.Internal;
-import org.apache.flink.table.api.DataTypes;
-import org.apache.flink.table.api.dataview.MapView;
 import org.apache.flink.table.data.StringData;
 import org.apache.flink.table.data.binary.BinaryStringData;
-import org.apache.flink.table.types.DataType;
 import org.apache.flink.table.types.logical.LogicalType;
 
-import java.util.ArrayList;
 import java.util.Iterator;
-import java.util.List;
-import java.util.Objects;
-
-import static org.apache.flink.table.types.utils.DataTypeUtils.toInternalDataType;
+import java.util.function.BiFunction;
 
 /**
  * Built-in FIRST_VALUE with retraction aggregate function.
  */
 @Internal
 public final class FirstValueWithRetractAggFunction<T>
-		extends InternalAggregateFunction<T, FirstValueWithRetractAggFunction.FirstValueWithRetractAccumulator<T>> {
-
-	private transient DataType valueDataType;
+		extends FirstLastValueWithRetractAggFunctionBase<T> {
 
+	private static final BiFunction<Long, Long, Boolean> comparator = (x, y) -> (x - y) > 0;
 	public FirstValueWithRetractAggFunction(LogicalType valueType) {
-		this.valueDataType = toInternalDataType(valueType);
-	}
-
-	// --------------------------------------------------------------------------------------------
-	// Planning
-	// --------------------------------------------------------------------------------------------
-
-	@Override
-	public DataType[] getInputDataTypes() {
-		return new DataType[]{valueDataType};
-	}
-
-	@Override
-	public DataType getAccumulatorDataType() {
-		return DataTypes.STRUCTURED(
-			FirstValueWithRetractAccumulator.class,
-			DataTypes.FIELD(
-				"firstValue",
-				valueDataType.nullable()),
-			DataTypes.FIELD(
-				"firstOrder",
-				DataTypes.BIGINT()),
-			DataTypes.FIELD(
-				"valueToOrderMap",
-				MapView.newMapViewDataType(
-					valueDataType.notNull(),
-					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
-			DataTypes.FIELD(
-				"orderToValueMap",
-				MapView.newMapViewDataType(
-					DataTypes.BIGINT(),
-					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class)))
-		);
-	}
-
-	@Override
-	public DataType getOutputDataType() {
-		return valueDataType;
-	}
-
-	// --------------------------------------------------------------------------------------------
-	// Runtime
-	// --------------------------------------------------------------------------------------------
-
-	/** Accumulator for FIRST_VALUE. */
-	public static class FirstValueWithRetractAccumulator<T> {
-		public T firstValue;
-		public Long firstOrder;
-		public MapView<T, List<Long>> valueToOrderMap;
-		public MapView<Long, List<T>> orderToValueMap;
-
-		@Override
-		public boolean equals(Object o) {
-			if (this == o) {
-				return true;
-			}
-			if (!(o instanceof FirstValueWithRetractAccumulator)) {
-				return false;
-			}
-			FirstValueWithRetractAccumulator<?> that = (FirstValueWithRetractAccumulator<?>) o;
-			return Objects.equals(firstValue, that.firstValue) &&
-				Objects.equals(firstOrder, that.firstOrder) &&
-				Objects.equals(valueToOrderMap, that.valueToOrderMap) &&
-				Objects.equals(orderToValueMap, that.orderToValueMap);
-		}
-
-		@Override
-		public int hashCode() {
-			return Objects.hash(firstValue, firstOrder, valueToOrderMap, orderToValueMap);
-		}
-	}
-
-	@Override
-	public FirstValueWithRetractAccumulator<T> createAccumulator() {
-		final FirstValueWithRetractAccumulator<T> acc = new FirstValueWithRetractAccumulator<>();
-		acc.firstValue = null;
-		acc.firstOrder = null;
-		acc.valueToOrderMap = new MapView<>();
-		acc.orderToValueMap = new MapView<>();
-		return acc;
+		super(valueType);
 	}
 
 	@SuppressWarnings("unchecked")
-	public void accumulate(FirstValueWithRetractAccumulator<T> acc, Object value) throws Exception {
-		if (value != null) {
-			T v = (T) value;
-			Long order = System.currentTimeMillis();
-			List<Long> orderList = acc.valueToOrderMap.get(v);
-			if (orderList == null) {
-				orderList = new ArrayList<>();
-			}
-			orderList.add(order);
-			acc.valueToOrderMap.put(v, orderList);
-			accumulate(acc, v, order);
-		}
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, Object value) throws Exception {
+		accumulate(acc, value, comparator);
 	}
 
 	@SuppressWarnings("unchecked")
-	public void accumulate(FirstValueWithRetractAccumulator<T> acc, Object value, Long order) throws Exception {
-		if (value != null) {
-			T v = (T) value;
-			Long prevOrder = acc.firstOrder;
-			if (prevOrder == null || prevOrder > order) {
-				acc.firstValue = v;
-				acc.firstOrder = order;
-			}
-
-			List<T> valueList = acc.orderToValueMap.get(order);
-			if (valueList == null) {
-				valueList = new ArrayList<>();
-			}
-			valueList.add(v);
-			acc.orderToValueMap.put(order, valueList);
-		}
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, Object value, Long order) throws Exception {
+		accumulate(acc, value, order, comparator);
 	}
 
-	public void accumulate(FirstValueWithRetractAccumulator<T> acc, StringData value) throws Exception {
-		if (value != null) {
-			accumulate(acc, (Object) ((BinaryStringData) value).copy());
-		}
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value) throws Exception {
+		accumulate(acc, (Object) ((BinaryStringData) value).copy(), comparator);
 	}
 
-	public void accumulate(FirstValueWithRetractAccumulator<T> acc, StringData value, Long order) throws Exception {
-		if (value != null) {
-			accumulate(acc, (Object) ((BinaryStringData) value).copy(), order);
-		}
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, Long order) throws Exception {
+		accumulate(acc, (Object) ((BinaryStringData) value).copy(), order, comparator);
 	}
 
-	@SuppressWarnings("unchecked")
-	public void retract(FirstValueWithRetractAccumulator<T> acc, Object value) throws Exception {
-		if (value != null) {
-			T v = (T) value;
-			List<Long> orderList = acc.valueToOrderMap.get(v);
-			if (orderList != null && orderList.size() > 0) {
-				Long order = orderList.get(0);
-				orderList.remove(0);
-				if (orderList.isEmpty()) {
-					acc.valueToOrderMap.remove(v);
-				} else {
-					acc.valueToOrderMap.put(v, orderList);
-				}
-				retract(acc, v, order);
-			}
-		}
+	public void merge(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Iterable<FirstLastValueWithRetractAccumulator<T>> its) throws Exception {

Review comment:
       `its` => `accIt`

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstLastValueWithRetractAggFunctionBase.java
##########
@@ -0,0 +1,483 @@
+/*
+ * 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.flink.table.planner.functions.aggfunctions;
+
+import org.apache.flink.annotation.Internal;
+import org.apache.flink.table.api.DataTypes;
+import org.apache.flink.table.api.dataview.MapView;
+import org.apache.flink.table.data.StringData;
+import org.apache.flink.table.data.binary.BinaryStringData;
+import org.apache.flink.table.types.DataType;
+import org.apache.flink.table.types.logical.LogicalType;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.function.BiFunction;
+
+import static org.apache.flink.table.types.utils.DataTypeUtils.toInternalDataType;
+
+/**
+ * Base retraction aggregate function for FIRST_VALUE and LAST_VALUE.
+ */
+@Internal
+abstract class FirstLastValueWithRetractAggFunctionBase<T>
+		extends InternalAggregateFunction<T, FirstLastValueWithRetractAggFunctionBase.FirstLastValueWithRetractAccumulator<T>> {
+
+	private transient DataType valueDataType;
+
+	public FirstLastValueWithRetractAggFunctionBase(LogicalType valueType) {
+		this.valueDataType = toInternalDataType(valueType);
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Planning
+	// --------------------------------------------------------------------------------------------
+
+	@Override
+	public DataType[] getInputDataTypes() {
+		return new DataType[]{valueDataType};
+	}
+
+	@Override
+	public DataType getAccumulatorDataType() {
+		return DataTypes.STRUCTURED(
+			FirstLastValueWithRetractAccumulator.class,
+			DataTypes.FIELD(
+				"value",
+				valueDataType.nullable()),
+			DataTypes.FIELD(
+				"order",
+				DataTypes.BIGINT()),
+			DataTypes.FIELD(
+				"valueToOrderMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"valueToOrderRetractMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueRetractMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class)))
+		);
+	}
+
+	@Override
+	public DataType getOutputDataType() {
+		return valueDataType;
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Runtime
+	// --------------------------------------------------------------------------------------------
+
+	/** Accumulator for FIRST_VALUE or LAST_VALUE. */
+	public static class FirstLastValueWithRetractAccumulator<T> {
+		public T value = null;
+		public Long order = null;
+		public MapView<T, List<Long>> valueToOrderMap = new MapView<>();
+		public MapView<T, List<Long>> valueToOrderRetractMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueRetractMap = new MapView<>();
+
+		@Override
+		public boolean equals(Object o) {
+			if (this == o) {
+				return true;
+			}
+			if (!(o instanceof FirstLastValueWithRetractAccumulator)) {
+				return false;
+			}
+			FirstLastValueWithRetractAccumulator<?> that = (FirstLastValueWithRetractAccumulator<?>) o;
+			return Objects.equals(value, that.value) &&
+				Objects.equals(order, that.order) &&
+				Objects.equals(valueToOrderMap, that.valueToOrderMap) &&
+				Objects.equals(valueToOrderRetractMap, that.valueToOrderRetractMap) &&
+				Objects.equals(orderToValueMap, that.orderToValueMap) &&
+				Objects.equals(orderToValueRetractMap, that.orderToValueRetractMap);
+		}
+
+		@Override
+		public int hashCode() {
+			return Objects.hash(
+				value,
+				order,
+				valueToOrderMap,
+				valueToOrderRetractMap,
+				orderToValueMap,
+				orderToValueRetractMap);
+		}
+	}
+
+	@Override
+	public FirstLastValueWithRetractAccumulator<T> createAccumulator() {
+		return new FirstLastValueWithRetractAccumulator<>();
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long order = System.nanoTime();
+			accumulate(acc, v, order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value, Long order,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long prevOrder = acc.order;
+			if (prevOrder == null || compare.apply(prevOrder, order)) {
+				acc.value = v;
+				acc.order = order;
+			}
+
+			// save order to orderToValueMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList == null) {
+				orderList = new ArrayList<>();
+				orderList.add(order);
+			} else {
+				// use insertion sort,
+				// for the O(1) time complexity if order is asc, compare from back to front
+				int i = orderList.size();
+				boolean isInsert = false;
+				while (i > 0) {
+					Long tempOrder = orderList.get(i - 1);
+					if (tempOrder <= order) {
+						orderList.add(i, order);
+						isInsert = true;
+						break;
+					}
+					i--;
+				}
+				if (!isInsert) {
+					orderList.add(0, order);
+				}
+			}
+			// update valueToOrderMap
+			acc.valueToOrderMap.put(v, orderList);
+
+			// update orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			if (valueList == null) {
+				valueList = new ArrayList<>();
+			}
+			valueList.add(v);
+			acc.orderToValueMap.put(order, valueList);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), compare);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, Long order, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				Long order = orderList.get(0);
+				retract(acc, v, order);
+			}
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value, Long order) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			// remove from valueToOrderMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				orderList.remove(0);
+				if (orderList.isEmpty()) {
+					acc.valueToOrderMap.remove(v);
+				} else {
+					acc.valueToOrderMap.put(v, orderList);
+				}
+			} else {
+				// if not exist, save to valueToOrderRetractMap
+				List<Long> retractOrderList = acc.valueToOrderRetractMap.get(v);
+				if (retractOrderList == null) {
+					retractOrderList = new ArrayList<>();
+				}
+				retractOrderList.add(order);
+				acc.valueToOrderRetractMap.put(v, retractOrderList);
+			}
+			// remove from orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			int index = -1;
+			if (valueList != null &&  (index = valueList.indexOf(v)) >= 0) {
+				valueList.remove(index);
+				if (valueList.isEmpty()) {
+					acc.orderToValueMap.remove(order);
+				} else {
+					acc.orderToValueMap.put(order, valueList);
+				}
+			} else {
+				// if not exist, save to orderToValueRetractMap

Review comment:
       exists

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstValueWithRetractAggFunction.java
##########
@@ -19,225 +19,72 @@
 package org.apache.flink.table.planner.functions.aggfunctions;
 
 import org.apache.flink.annotation.Internal;
-import org.apache.flink.table.api.DataTypes;
-import org.apache.flink.table.api.dataview.MapView;
 import org.apache.flink.table.data.StringData;
 import org.apache.flink.table.data.binary.BinaryStringData;
-import org.apache.flink.table.types.DataType;
 import org.apache.flink.table.types.logical.LogicalType;
 
-import java.util.ArrayList;
 import java.util.Iterator;
-import java.util.List;
-import java.util.Objects;
-
-import static org.apache.flink.table.types.utils.DataTypeUtils.toInternalDataType;
+import java.util.function.BiFunction;
 
 /**
  * Built-in FIRST_VALUE with retraction aggregate function.
  */
 @Internal
 public final class FirstValueWithRetractAggFunction<T>
-		extends InternalAggregateFunction<T, FirstValueWithRetractAggFunction.FirstValueWithRetractAccumulator<T>> {
-
-	private transient DataType valueDataType;
+		extends FirstLastValueWithRetractAggFunctionBase<T> {
 
+	private static final BiFunction<Long, Long, Boolean> comparator = (x, y) -> (x - y) > 0;

Review comment:
       ```suggestion
   	private static final BiFunction<Long, Long, Boolean> comparator = (order1, order2) -> order1 > order2;
   ```

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstLastValueWithRetractAggFunctionBase.java
##########
@@ -0,0 +1,483 @@
+/*
+ * 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.flink.table.planner.functions.aggfunctions;
+
+import org.apache.flink.annotation.Internal;
+import org.apache.flink.table.api.DataTypes;
+import org.apache.flink.table.api.dataview.MapView;
+import org.apache.flink.table.data.StringData;
+import org.apache.flink.table.data.binary.BinaryStringData;
+import org.apache.flink.table.types.DataType;
+import org.apache.flink.table.types.logical.LogicalType;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.function.BiFunction;
+
+import static org.apache.flink.table.types.utils.DataTypeUtils.toInternalDataType;
+
+/**
+ * Base retraction aggregate function for FIRST_VALUE and LAST_VALUE.
+ */
+@Internal
+abstract class FirstLastValueWithRetractAggFunctionBase<T>
+		extends InternalAggregateFunction<T, FirstLastValueWithRetractAggFunctionBase.FirstLastValueWithRetractAccumulator<T>> {
+
+	private transient DataType valueDataType;
+
+	public FirstLastValueWithRetractAggFunctionBase(LogicalType valueType) {
+		this.valueDataType = toInternalDataType(valueType);
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Planning
+	// --------------------------------------------------------------------------------------------
+
+	@Override
+	public DataType[] getInputDataTypes() {
+		return new DataType[]{valueDataType};
+	}
+
+	@Override
+	public DataType getAccumulatorDataType() {
+		return DataTypes.STRUCTURED(
+			FirstLastValueWithRetractAccumulator.class,
+			DataTypes.FIELD(
+				"value",
+				valueDataType.nullable()),
+			DataTypes.FIELD(
+				"order",
+				DataTypes.BIGINT()),
+			DataTypes.FIELD(
+				"valueToOrderMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"valueToOrderRetractMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueRetractMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class)))
+		);
+	}
+
+	@Override
+	public DataType getOutputDataType() {
+		return valueDataType;
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Runtime
+	// --------------------------------------------------------------------------------------------
+
+	/** Accumulator for FIRST_VALUE or LAST_VALUE. */
+	public static class FirstLastValueWithRetractAccumulator<T> {
+		public T value = null;
+		public Long order = null;
+		public MapView<T, List<Long>> valueToOrderMap = new MapView<>();
+		public MapView<T, List<Long>> valueToOrderRetractMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueRetractMap = new MapView<>();
+
+		@Override
+		public boolean equals(Object o) {
+			if (this == o) {
+				return true;
+			}
+			if (!(o instanceof FirstLastValueWithRetractAccumulator)) {
+				return false;
+			}
+			FirstLastValueWithRetractAccumulator<?> that = (FirstLastValueWithRetractAccumulator<?>) o;
+			return Objects.equals(value, that.value) &&
+				Objects.equals(order, that.order) &&
+				Objects.equals(valueToOrderMap, that.valueToOrderMap) &&
+				Objects.equals(valueToOrderRetractMap, that.valueToOrderRetractMap) &&
+				Objects.equals(orderToValueMap, that.orderToValueMap) &&
+				Objects.equals(orderToValueRetractMap, that.orderToValueRetractMap);
+		}
+
+		@Override
+		public int hashCode() {
+			return Objects.hash(
+				value,
+				order,
+				valueToOrderMap,
+				valueToOrderRetractMap,
+				orderToValueMap,
+				orderToValueRetractMap);
+		}
+	}
+
+	@Override
+	public FirstLastValueWithRetractAccumulator<T> createAccumulator() {
+		return new FirstLastValueWithRetractAccumulator<>();
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long order = System.nanoTime();
+			accumulate(acc, v, order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value, Long order,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long prevOrder = acc.order;
+			if (prevOrder == null || compare.apply(prevOrder, order)) {
+				acc.value = v;
+				acc.order = order;
+			}
+
+			// save order to orderToValueMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList == null) {
+				orderList = new ArrayList<>();
+				orderList.add(order);
+			} else {
+				// use insertion sort,
+				// for the O(1) time complexity if order is asc, compare from back to front
+				int i = orderList.size();
+				boolean isInsert = false;
+				while (i > 0) {
+					Long tempOrder = orderList.get(i - 1);
+					if (tempOrder <= order) {
+						orderList.add(i, order);
+						isInsert = true;
+						break;
+					}
+					i--;
+				}
+				if (!isInsert) {
+					orderList.add(0, order);
+				}
+			}
+			// update valueToOrderMap
+			acc.valueToOrderMap.put(v, orderList);
+
+			// update orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			if (valueList == null) {
+				valueList = new ArrayList<>();
+			}
+			valueList.add(v);
+			acc.orderToValueMap.put(order, valueList);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), compare);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, Long order, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				Long order = orderList.get(0);
+				retract(acc, v, order);
+			}
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value, Long order) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			// remove from valueToOrderMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				orderList.remove(0);
+				if (orderList.isEmpty()) {
+					acc.valueToOrderMap.remove(v);
+				} else {
+					acc.valueToOrderMap.put(v, orderList);
+				}
+			} else {
+				// if not exist, save to valueToOrderRetractMap
+				List<Long> retractOrderList = acc.valueToOrderRetractMap.get(v);
+				if (retractOrderList == null) {
+					retractOrderList = new ArrayList<>();
+				}
+				retractOrderList.add(order);
+				acc.valueToOrderRetractMap.put(v, retractOrderList);
+			}
+			// remove from orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			int index = -1;
+			if (valueList != null &&  (index = valueList.indexOf(v)) >= 0) {
+				valueList.remove(index);
+				if (valueList.isEmpty()) {
+					acc.orderToValueMap.remove(order);
+				} else {
+					acc.orderToValueMap.put(order, valueList);
+				}
+			} else {
+				// if not exist, save to orderToValueRetractMap
+				List<T> retractValueList = acc.orderToValueRetractMap.get(order);
+				if (retractValueList == null) {
+					retractValueList = new ArrayList<>();
+				}
+				retractValueList.add(v);
+				acc.orderToValueRetractMap.put(order, retractValueList);
+			}
+			// if retract current first value
+			if (v.equals(acc.value)) {
+				updateValue(acc);
+			}
+		}
+	}
+
+	public void merge(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Iterable<FirstLastValueWithRetractAccumulator<T>> its,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		for (FirstLastValueWithRetractAccumulator<T> it : its) {
+			if (acc.order == null || (it.order != null && compare.apply(acc.order, it.order))) {
+				acc.value = it.value;
+				acc.order = it.order;
+			}
+			mergeValueToOrderMap(acc, it);
+			mergeOrderToValueMap(acc, it);
+			// if current first value is retract

Review comment:
       ```suggestion
   			// update the acc value if the first/last value has been retracted after merge
   ```

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstLastValueWithRetractAggFunctionBase.java
##########
@@ -0,0 +1,483 @@
+/*
+ * 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.flink.table.planner.functions.aggfunctions;
+
+import org.apache.flink.annotation.Internal;
+import org.apache.flink.table.api.DataTypes;
+import org.apache.flink.table.api.dataview.MapView;
+import org.apache.flink.table.data.StringData;
+import org.apache.flink.table.data.binary.BinaryStringData;
+import org.apache.flink.table.types.DataType;
+import org.apache.flink.table.types.logical.LogicalType;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.function.BiFunction;
+
+import static org.apache.flink.table.types.utils.DataTypeUtils.toInternalDataType;
+
+/**
+ * Base retraction aggregate function for FIRST_VALUE and LAST_VALUE.
+ */
+@Internal
+abstract class FirstLastValueWithRetractAggFunctionBase<T>
+		extends InternalAggregateFunction<T, FirstLastValueWithRetractAggFunctionBase.FirstLastValueWithRetractAccumulator<T>> {
+
+	private transient DataType valueDataType;
+
+	public FirstLastValueWithRetractAggFunctionBase(LogicalType valueType) {
+		this.valueDataType = toInternalDataType(valueType);
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Planning
+	// --------------------------------------------------------------------------------------------
+
+	@Override
+	public DataType[] getInputDataTypes() {
+		return new DataType[]{valueDataType};
+	}
+
+	@Override
+	public DataType getAccumulatorDataType() {
+		return DataTypes.STRUCTURED(
+			FirstLastValueWithRetractAccumulator.class,
+			DataTypes.FIELD(
+				"value",
+				valueDataType.nullable()),
+			DataTypes.FIELD(
+				"order",
+				DataTypes.BIGINT()),
+			DataTypes.FIELD(
+				"valueToOrderMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"valueToOrderRetractMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueRetractMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class)))
+		);
+	}
+
+	@Override
+	public DataType getOutputDataType() {
+		return valueDataType;
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Runtime
+	// --------------------------------------------------------------------------------------------
+
+	/** Accumulator for FIRST_VALUE or LAST_VALUE. */
+	public static class FirstLastValueWithRetractAccumulator<T> {
+		public T value = null;
+		public Long order = null;
+		public MapView<T, List<Long>> valueToOrderMap = new MapView<>();
+		public MapView<T, List<Long>> valueToOrderRetractMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueRetractMap = new MapView<>();
+
+		@Override
+		public boolean equals(Object o) {
+			if (this == o) {
+				return true;
+			}
+			if (!(o instanceof FirstLastValueWithRetractAccumulator)) {
+				return false;
+			}
+			FirstLastValueWithRetractAccumulator<?> that = (FirstLastValueWithRetractAccumulator<?>) o;
+			return Objects.equals(value, that.value) &&
+				Objects.equals(order, that.order) &&
+				Objects.equals(valueToOrderMap, that.valueToOrderMap) &&
+				Objects.equals(valueToOrderRetractMap, that.valueToOrderRetractMap) &&
+				Objects.equals(orderToValueMap, that.orderToValueMap) &&
+				Objects.equals(orderToValueRetractMap, that.orderToValueRetractMap);
+		}
+
+		@Override
+		public int hashCode() {
+			return Objects.hash(
+				value,
+				order,
+				valueToOrderMap,
+				valueToOrderRetractMap,
+				orderToValueMap,
+				orderToValueRetractMap);
+		}
+	}
+
+	@Override
+	public FirstLastValueWithRetractAccumulator<T> createAccumulator() {
+		return new FirstLastValueWithRetractAccumulator<>();
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long order = System.nanoTime();
+			accumulate(acc, v, order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value, Long order,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long prevOrder = acc.order;
+			if (prevOrder == null || compare.apply(prevOrder, order)) {
+				acc.value = v;
+				acc.order = order;
+			}
+
+			// save order to orderToValueMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList == null) {
+				orderList = new ArrayList<>();
+				orderList.add(order);
+			} else {
+				// use insertion sort,
+				// for the O(1) time complexity if order is asc, compare from back to front
+				int i = orderList.size();
+				boolean isInsert = false;
+				while (i > 0) {
+					Long tempOrder = orderList.get(i - 1);
+					if (tempOrder <= order) {
+						orderList.add(i, order);
+						isInsert = true;
+						break;
+					}
+					i--;
+				}
+				if (!isInsert) {
+					orderList.add(0, order);
+				}
+			}
+			// update valueToOrderMap
+			acc.valueToOrderMap.put(v, orderList);
+
+			// update orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			if (valueList == null) {
+				valueList = new ArrayList<>();
+			}
+			valueList.add(v);
+			acc.orderToValueMap.put(order, valueList);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), compare);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, Long order, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				Long order = orderList.get(0);
+				retract(acc, v, order);
+			}
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value, Long order) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			// remove from valueToOrderMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				orderList.remove(0);
+				if (orderList.isEmpty()) {
+					acc.valueToOrderMap.remove(v);
+				} else {
+					acc.valueToOrderMap.put(v, orderList);
+				}
+			} else {
+				// if not exist, save to valueToOrderRetractMap
+				List<Long> retractOrderList = acc.valueToOrderRetractMap.get(v);
+				if (retractOrderList == null) {
+					retractOrderList = new ArrayList<>();
+				}
+				retractOrderList.add(order);
+				acc.valueToOrderRetractMap.put(v, retractOrderList);
+			}
+			// remove from orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			int index = -1;
+			if (valueList != null &&  (index = valueList.indexOf(v)) >= 0) {
+				valueList.remove(index);
+				if (valueList.isEmpty()) {
+					acc.orderToValueMap.remove(order);
+				} else {
+					acc.orderToValueMap.put(order, valueList);
+				}
+			} else {
+				// if not exist, save to orderToValueRetractMap
+				List<T> retractValueList = acc.orderToValueRetractMap.get(order);
+				if (retractValueList == null) {
+					retractValueList = new ArrayList<>();
+				}
+				retractValueList.add(v);
+				acc.orderToValueRetractMap.put(order, retractValueList);
+			}
+			// if retract current first value
+			if (v.equals(acc.value)) {
+				updateValue(acc);
+			}
+		}
+	}
+
+	public void merge(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Iterable<FirstLastValueWithRetractAccumulator<T>> its,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		for (FirstLastValueWithRetractAccumulator<T> it : its) {
+			if (acc.order == null || (it.order != null && compare.apply(acc.order, it.order))) {
+				acc.value = it.value;
+				acc.order = it.order;
+			}
+			mergeValueToOrderMap(acc, it);
+			mergeOrderToValueMap(acc, it);
+			// if current first value is retract
+			if (!acc.valueToOrderMap.contains(acc.value)) {
+				updateValue(acc);
+			}
+		}
+	}
+
+	public void resetAccumulator(FirstLastValueWithRetractAccumulator<T> acc) {
+		acc.value = null;
+		acc.order = null;
+		acc.valueToOrderMap.clear();
+		acc.valueToOrderRetractMap.clear();
+		acc.orderToValueMap.clear();
+		acc.orderToValueRetractMap.clear();
+	}
+
+	@Override
+	public T getValue(FirstLastValueWithRetractAccumulator<T> acc) {
+		return acc.value;
+	}
+
+	private void mergeOrderToValueMap(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			FirstLastValueWithRetractAccumulator<T> it) throws Exception {

Review comment:
       `it ` -> `otherAcc`

##########
File path: flink-table/flink-table-planner-blink/src/main/java/org/apache/flink/table/planner/functions/aggfunctions/FirstLastValueWithRetractAggFunctionBase.java
##########
@@ -0,0 +1,483 @@
+/*
+ * 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.flink.table.planner.functions.aggfunctions;
+
+import org.apache.flink.annotation.Internal;
+import org.apache.flink.table.api.DataTypes;
+import org.apache.flink.table.api.dataview.MapView;
+import org.apache.flink.table.data.StringData;
+import org.apache.flink.table.data.binary.BinaryStringData;
+import org.apache.flink.table.types.DataType;
+import org.apache.flink.table.types.logical.LogicalType;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.function.BiFunction;
+
+import static org.apache.flink.table.types.utils.DataTypeUtils.toInternalDataType;
+
+/**
+ * Base retraction aggregate function for FIRST_VALUE and LAST_VALUE.
+ */
+@Internal
+abstract class FirstLastValueWithRetractAggFunctionBase<T>
+		extends InternalAggregateFunction<T, FirstLastValueWithRetractAggFunctionBase.FirstLastValueWithRetractAccumulator<T>> {
+
+	private transient DataType valueDataType;
+
+	public FirstLastValueWithRetractAggFunctionBase(LogicalType valueType) {
+		this.valueDataType = toInternalDataType(valueType);
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Planning
+	// --------------------------------------------------------------------------------------------
+
+	@Override
+	public DataType[] getInputDataTypes() {
+		return new DataType[]{valueDataType};
+	}
+
+	@Override
+	public DataType getAccumulatorDataType() {
+		return DataTypes.STRUCTURED(
+			FirstLastValueWithRetractAccumulator.class,
+			DataTypes.FIELD(
+				"value",
+				valueDataType.nullable()),
+			DataTypes.FIELD(
+				"order",
+				DataTypes.BIGINT()),
+			DataTypes.FIELD(
+				"valueToOrderMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"valueToOrderRetractMap",
+				MapView.newMapViewDataType(
+					valueDataType.notNull(),
+					DataTypes.ARRAY(DataTypes.BIGINT()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class))),
+			DataTypes.FIELD(
+				"orderToValueRetractMap",
+				MapView.newMapViewDataType(
+					DataTypes.BIGINT(),
+					DataTypes.ARRAY(valueDataType.notNull()).bridgedTo(List.class)))
+		);
+	}
+
+	@Override
+	public DataType getOutputDataType() {
+		return valueDataType;
+	}
+
+	// --------------------------------------------------------------------------------------------
+	// Runtime
+	// --------------------------------------------------------------------------------------------
+
+	/** Accumulator for FIRST_VALUE or LAST_VALUE. */
+	public static class FirstLastValueWithRetractAccumulator<T> {
+		public T value = null;
+		public Long order = null;
+		public MapView<T, List<Long>> valueToOrderMap = new MapView<>();
+		public MapView<T, List<Long>> valueToOrderRetractMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueMap = new MapView<>();
+		public MapView<Long, List<T>> orderToValueRetractMap = new MapView<>();
+
+		@Override
+		public boolean equals(Object o) {
+			if (this == o) {
+				return true;
+			}
+			if (!(o instanceof FirstLastValueWithRetractAccumulator)) {
+				return false;
+			}
+			FirstLastValueWithRetractAccumulator<?> that = (FirstLastValueWithRetractAccumulator<?>) o;
+			return Objects.equals(value, that.value) &&
+				Objects.equals(order, that.order) &&
+				Objects.equals(valueToOrderMap, that.valueToOrderMap) &&
+				Objects.equals(valueToOrderRetractMap, that.valueToOrderRetractMap) &&
+				Objects.equals(orderToValueMap, that.orderToValueMap) &&
+				Objects.equals(orderToValueRetractMap, that.orderToValueRetractMap);
+		}
+
+		@Override
+		public int hashCode() {
+			return Objects.hash(
+				value,
+				order,
+				valueToOrderMap,
+				valueToOrderRetractMap,
+				orderToValueMap,
+				orderToValueRetractMap);
+		}
+	}
+
+	@Override
+	public FirstLastValueWithRetractAccumulator<T> createAccumulator() {
+		return new FirstLastValueWithRetractAccumulator<>();
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long order = System.nanoTime();
+			accumulate(acc, v, order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void accumulate(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Object value, Long order,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			Long prevOrder = acc.order;
+			if (prevOrder == null || compare.apply(prevOrder, order)) {
+				acc.value = v;
+				acc.order = order;
+			}
+
+			// save order to orderToValueMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList == null) {
+				orderList = new ArrayList<>();
+				orderList.add(order);
+			} else {
+				// use insertion sort,
+				// for the O(1) time complexity if order is asc, compare from back to front
+				int i = orderList.size();
+				boolean isInsert = false;
+				while (i > 0) {
+					Long tempOrder = orderList.get(i - 1);
+					if (tempOrder <= order) {
+						orderList.add(i, order);
+						isInsert = true;
+						break;
+					}
+					i--;
+				}
+				if (!isInsert) {
+					orderList.add(0, order);
+				}
+			}
+			// update valueToOrderMap
+			acc.valueToOrderMap.put(v, orderList);
+
+			// update orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			if (valueList == null) {
+				valueList = new ArrayList<>();
+			}
+			valueList.add(v);
+			acc.orderToValueMap.put(order, valueList);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), compare);
+		}
+	}
+
+	public void accumulate(FirstLastValueWithRetractAccumulator<T> acc, StringData value, Long order, BiFunction<Long, Long, Boolean> compare) throws Exception {
+		if (value != null) {
+			accumulate(acc, (Object) ((BinaryStringData) value).copy(), order, compare);
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				Long order = orderList.get(0);
+				retract(acc, v, order);
+			}
+		}
+	}
+
+	@SuppressWarnings("unchecked")
+	public void retract(FirstLastValueWithRetractAccumulator<T> acc, Object value, Long order) throws Exception {
+		if (value != null) {
+			T v = (T) value;
+			// remove from valueToOrderMap
+			List<Long> orderList = acc.valueToOrderMap.get(v);
+			if (orderList != null && orderList.size() > 0) {
+				orderList.remove(0);
+				if (orderList.isEmpty()) {
+					acc.valueToOrderMap.remove(v);
+				} else {
+					acc.valueToOrderMap.put(v, orderList);
+				}
+			} else {
+				// if not exist, save to valueToOrderRetractMap
+				List<Long> retractOrderList = acc.valueToOrderRetractMap.get(v);
+				if (retractOrderList == null) {
+					retractOrderList = new ArrayList<>();
+				}
+				retractOrderList.add(order);
+				acc.valueToOrderRetractMap.put(v, retractOrderList);
+			}
+			// remove from orderToValueMap
+			List<T> valueList = acc.orderToValueMap.get(order);
+			int index = -1;
+			if (valueList != null &&  (index = valueList.indexOf(v)) >= 0) {
+				valueList.remove(index);
+				if (valueList.isEmpty()) {
+					acc.orderToValueMap.remove(order);
+				} else {
+					acc.orderToValueMap.put(order, valueList);
+				}
+			} else {
+				// if not exist, save to orderToValueRetractMap
+				List<T> retractValueList = acc.orderToValueRetractMap.get(order);
+				if (retractValueList == null) {
+					retractValueList = new ArrayList<>();
+				}
+				retractValueList.add(v);
+				acc.orderToValueRetractMap.put(order, retractValueList);
+			}
+			// if retract current first value
+			if (v.equals(acc.value)) {
+				updateValue(acc);
+			}
+		}
+	}
+
+	public void merge(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			Iterable<FirstLastValueWithRetractAccumulator<T>> its,
+			BiFunction<Long, Long, Boolean> compare) throws Exception {
+		for (FirstLastValueWithRetractAccumulator<T> it : its) {
+			if (acc.order == null || (it.order != null && compare.apply(acc.order, it.order))) {
+				acc.value = it.value;
+				acc.order = it.order;
+			}
+			mergeValueToOrderMap(acc, it);
+			mergeOrderToValueMap(acc, it);
+			// if current first value is retract
+			if (!acc.valueToOrderMap.contains(acc.value)) {
+				updateValue(acc);
+			}
+		}
+	}
+
+	public void resetAccumulator(FirstLastValueWithRetractAccumulator<T> acc) {
+		acc.value = null;
+		acc.order = null;
+		acc.valueToOrderMap.clear();
+		acc.valueToOrderRetractMap.clear();
+		acc.orderToValueMap.clear();
+		acc.orderToValueRetractMap.clear();
+	}
+
+	@Override
+	public T getValue(FirstLastValueWithRetractAccumulator<T> acc) {
+		return acc.value;
+	}
+
+	private void mergeOrderToValueMap(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			FirstLastValueWithRetractAccumulator<T> it) throws Exception {
+		// merge orderToValueMap
+		for (Map.Entry<Long, List<T>> entry : it.orderToValueMap.entries()) {
+			Long key = entry.getKey();
+			if (acc.orderToValueMap.contains(key)) {
+				List<T> itList = entry.getValue();
+				List<T> accList = acc.orderToValueMap.get(key);
+				// merge
+				List<T> mergedList = mergeOrderedList(itList, accList, new Comparator<T>() {
+					@Override
+					public int compare(T o1, T o2) {
+						try {
+							Long o1MinOrder = acc.valueToOrderMap.get(o1).get(0);
+							Long o2MinOrder = acc.valueToOrderMap.get(o2).get(0);
+							return (int) (o1MinOrder - o2MinOrder);
+						} catch (Exception e) {
+							throw new RuntimeException(e);
+						}
+					}
+				});
+				acc.orderToValueMap.put(key, mergedList);
+			} else {
+				// if order doesn't exist, put to orderToValueMap
+				acc.orderToValueMap.put(key, entry.getValue());
+			}
+		}
+
+		// merge orderToValueRetractMap
+		for (Map.Entry<Long, List<T>> entry : it.orderToValueRetractMap.entries()) {
+			Long key = entry.getKey();
+			if (acc.orderToValueRetractMap.contains(key)) {
+				List<T> valueList = acc.orderToValueRetractMap.get(key);
+				valueList.addAll(entry.getValue());
+				acc.orderToValueRetractMap.put(key, valueList);
+			} else {
+				acc.orderToValueRetractMap.put(key, entry.getValue());
+			}
+		}
+
+		// retract from orderToValueRetractMap
+		Iterator<Map.Entry<Long, List<T>>> orderToValueRetractMapIt =
+			acc.orderToValueRetractMap.entries().iterator();
+		while (orderToValueRetractMapIt.hasNext()) {
+			Map.Entry<Long, List<T>> entry = orderToValueRetractMapIt.next();
+			Long key = entry.getKey();
+			if (acc.orderToValueMap.contains(key)) {
+				List<T> valueList = acc.orderToValueMap.get(key);
+				List<T> retractValueList = entry.getValue();
+				List<T> newRetractValueList = new ArrayList<>();
+				for (int i = 0; i < retractValueList.size(); i++) {
+					if (!valueList.remove(retractValueList.get(i))) {
+						newRetractValueList.add(retractValueList.get(i));
+					}
+				}
+				if (valueList.size() > 0) {
+					acc.orderToValueMap.put(key, valueList);
+				} else {
+					acc.orderToValueMap.remove(key);
+				}
+				if (newRetractValueList.size() > 0) {
+					acc.orderToValueRetractMap.put(key, newRetractValueList);
+				} else {
+					orderToValueRetractMapIt.remove();
+				}
+			}
+		}
+	}
+
+	private void mergeValueToOrderMap(
+			FirstLastValueWithRetractAccumulator<T> acc,
+			FirstLastValueWithRetractAccumulator<T> it) throws Exception {

Review comment:
       `it` -> `otherAcc`




----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org