Skip to main content

risingwave_stream/executor/dedup/
append_only_dedup.rs

1// Copyright 2023 RisingWave Labs
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use futures::stream;
16use itertools::Itertools;
17use risingwave_common::array::Op;
18use risingwave_common::bitmap::BitmapBuilder;
19use risingwave_common::row::RowExt;
20
21use crate::cache::ManagedLruCache;
22use crate::common::metrics::MetricsInfo;
23use crate::executor::prelude::*;
24
25type Cache = ManagedLruCache<OwnedRow, ()>;
26
27/// [`AppendOnlyDedupExecutor`] drops any message that has duplicate pk columns with previous
28/// messages. It only accepts append-only input, and its output will be append-only as well.
29///
30/// Keys below the watermark on the state table's clean watermark column are removed from the
31/// state, as the watermark guarantees that they never arrive again.
32pub struct AppendOnlyDedupExecutor<S: StateStore> {
33    ctx: ActorContextRef,
34
35    input: Option<Executor>,
36    /// Input column indices of the dedup key, in the pk order of the state table.
37    dedup_cols: Vec<usize>,
38    /// The input column whose watermark cleans the state.
39    clean_watermark_col: Option<usize>,
40    state_table: StateTable<S>,
41    cache: Cache,
42}
43
44impl<S: StateStore> AppendOnlyDedupExecutor<S> {
45    pub fn new(
46        ctx: ActorContextRef,
47        input: Executor,
48        dedup_cols: Vec<usize>,
49        state_table: StateTable<S>,
50        watermark_epoch: AtomicU64Ref,
51        metrics: Arc<StreamingMetrics>,
52    ) -> Self {
53        let metrics_info =
54            MetricsInfo::new(metrics, state_table.table_id(), ctx.id, "AppendOnly Dedup");
55        // The pk of the state table is the dedup columns, so the clean watermark column maps to
56        // the input by its position in the pk.
57        let clean_watermark_col = state_table.clean_watermark_index.map(|idx| {
58            let pk_pos = state_table
59                .pk_indices()
60                .iter()
61                .position(|&i| i == idx)
62                .expect("clean watermark column should be a dedup column");
63            dedup_cols[pk_pos]
64        });
65        Self {
66            ctx,
67            input: Some(input),
68            dedup_cols,
69            clean_watermark_col,
70            state_table,
71            cache: Cache::unbounded(watermark_epoch, metrics_info),
72        }
73    }
74
75    #[try_stream(ok = Message, error = StreamExecutorError)]
76    async fn executor_inner(mut self) {
77        let mut input = self.input.take().unwrap().execute();
78
79        // Consume the first barrier message and initialize state table.
80        let barrier = expect_first_barrier(&mut input).await?;
81        let first_epoch = barrier.epoch;
82        // The first barrier message should be propagated.
83        yield Message::Barrier(barrier);
84        self.state_table.init_epoch(first_epoch).await?;
85
86        #[for_await]
87        for msg in input {
88            self.cache.evict();
89
90            match msg? {
91                Message::Chunk(chunk) => {
92                    // Append-only dedup executor only receives INSERT messages.
93                    debug_assert!(chunk.ops().iter().all(|&op| op == Op::Insert));
94
95                    // Extract dedup keys for all rows (regardless of visibility) in the chunk.
96                    let dedup_keys = chunk
97                        .data_chunk()
98                        .rows_with_holes()
99                        .map(|row_ref| {
100                            row_ref.map(|row| row.project(&self.dedup_cols).to_owned_row())
101                        })
102                        .collect_vec();
103
104                    // Ensure that if a key for a visible row exists before, then it is in the
105                    // cache, by querying the storage.
106                    self.populate_cache(dedup_keys.iter().flatten()).await?;
107
108                    // Now check for duplication and insert new keys into the cache.
109                    let mut vis_builder = BitmapBuilder::with_capacity(chunk.capacity());
110                    for key in dedup_keys {
111                        match key {
112                            Some(key) => {
113                                if self.cache.put(key, ()).is_none() {
114                                    // The key doesn't exist before. The row should be visible.
115                                    // Note that we can do deduplication in such a simple way because
116                                    // this executor only accepts append-only input. Otherwise, we can
117                                    // only do this if dedup columns contain all the input columns.
118                                    vis_builder.append(true);
119                                } else {
120                                    // The key exists before. The row shouldn't be visible.
121                                    vis_builder.append(false);
122                                }
123                            }
124                            None => {
125                                // The row is originally invisible.
126                                vis_builder.append(false);
127                            }
128                        }
129                    }
130
131                    let vis = vis_builder.finish();
132                    if vis.count_ones() > 0 {
133                        // Construct the new chunk and write the data to state table.
134                        let (ops, columns, _) = chunk.into_inner();
135                        let chunk = StreamChunk::with_visibility(ops, columns, vis);
136                        self.state_table.write_chunk(chunk.clone());
137                        self.state_table.try_flush().await?;
138
139                        yield Message::Chunk(chunk);
140                    }
141                }
142
143                Message::Barrier(barrier) => {
144                    let post_commit = self.state_table.commit(barrier.epoch).await?;
145
146                    let update_vnode_bitmap = barrier.as_update_vnode_bitmap(self.ctx.id);
147                    yield Message::Barrier(barrier);
148
149                    if let Some((_, cache_may_stale)) =
150                        post_commit.post_yield_barrier(update_vnode_bitmap).await?
151                        && cache_may_stale
152                    {
153                        self.cache.clear();
154                    }
155                }
156
157                Message::Watermark(watermark) => {
158                    if self.clean_watermark_col == Some(watermark.col_idx) {
159                        self.state_table.update_watermark(watermark.val.clone());
160                    }
161                    yield Message::Watermark(watermark);
162                }
163            }
164        }
165    }
166
167    /// Populate the cache with keys that exist in storage before.
168    pub async fn populate_cache<'a>(
169        &mut self,
170        keys: impl Iterator<Item = &'a OwnedRow>,
171    ) -> StreamExecutorResult<()> {
172        let mut futures = vec![];
173        for key in keys {
174            if self.cache.contains(key) {
175                continue;
176            }
177
178            let table = &self.state_table;
179            futures.push(async move { (key, table.exists(key).await) });
180        }
181
182        if !futures.is_empty() {
183            let mut buffered = stream::iter(futures).buffer_unordered(10).fuse();
184            while let Some(result) = buffered.next().await {
185                let (key, exists) = result;
186                if exists? {
187                    // Only insert into the cache when we have this key in storage.
188                    self.cache.put(key.to_owned(), ());
189                }
190            }
191        }
192
193        Ok(())
194    }
195}
196
197impl<S: StateStore> Execute for AppendOnlyDedupExecutor<S> {
198    fn execute(self: Box<Self>) -> BoxedMessageStream {
199        self.executor_inner().boxed()
200    }
201}
202
203#[cfg(test)]
204mod tests {
205    use std::sync::atomic::AtomicU64;
206
207    use risingwave_common::catalog::{ColumnDesc, ColumnId, Field, TableId};
208    use risingwave_common::test_prelude::StreamChunkTestExt;
209    use risingwave_common::util::epoch::test_epoch;
210    use risingwave_common::util::sort_util::OrderType;
211    use risingwave_hummock_sdk::HummockReadEpoch;
212    use risingwave_storage::memory::MemoryStateStore;
213    use risingwave_storage::table::batch_table::BatchTable;
214
215    use super::*;
216    use crate::common::table::test_utils::gen_pbtable;
217    use crate::executor::test_utils::{MessageSender, MockSource, StreamExecutorTestExt};
218
219    const TABLE_ID: TableId = TableId::new(1);
220
221    fn column_descs() -> Vec<ColumnDesc> {
222        vec![
223            ColumnDesc::unnamed(ColumnId::new(0), DataType::Int64),
224            ColumnDesc::unnamed(ColumnId::new(1), DataType::Int64),
225        ]
226    }
227
228    /// A dedup executor on the first column of `(I, I)` rows, with its state in `store`.
229    async fn create_executor(store: MemoryStateStore) -> (MessageSender, BoxedMessageStream) {
230        let schema = Schema::new(vec![
231            Field::unnamed(DataType::Int64),
232            Field::unnamed(DataType::Int64),
233        ]);
234        let state_table = StateTable::from_table_catalog(
235            &gen_pbtable(
236                TABLE_ID,
237                column_descs(),
238                vec![OrderType::ascending()],
239                vec![0],
240                0,
241            ),
242            store,
243            None,
244        )
245        .await;
246        let (tx, source) = MockSource::channel();
247        let executor = AppendOnlyDedupExecutor::new(
248            ActorContext::for_test(123),
249            source.into_executor(schema, vec![0]),
250            vec![0],
251            state_table,
252            Arc::new(AtomicU64::new(0)),
253            Arc::new(StreamingMetrics::unused()),
254        );
255        (tx, executor.boxed().execute())
256    }
257
258    #[tokio::test]
259    async fn test_dedup_executor() {
260        let (mut tx, mut dedup_executor) = create_executor(MemoryStateStore::new()).await;
261
262        tx.push_barrier(test_epoch(1), false);
263        dedup_executor.next().await.unwrap().unwrap();
264
265        let chunk = StreamChunk::from_pretty(
266            " I I
267            + 1 1
268            + 2 2 D
269            + 1 7",
270        );
271        tx.push_chunk(chunk);
272        let msg = dedup_executor.next().await.unwrap().unwrap();
273        assert_eq!(
274            msg.into_chunk().unwrap(),
275            StreamChunk::from_pretty(
276                " I I
277                + 1 1
278                + 2 2 D
279                + 1 7 D",
280            )
281        );
282
283        tx.push_barrier(test_epoch(2), false);
284        dedup_executor.next().await.unwrap().unwrap();
285
286        let chunk = StreamChunk::from_pretty(
287            " I I
288            + 3 9
289            + 2 5
290            + 1 20",
291        );
292        tx.push_chunk(chunk);
293        let msg = dedup_executor.next().await.unwrap().unwrap();
294        assert_eq!(
295            msg.into_chunk().unwrap(),
296            StreamChunk::from_pretty(
297                " I I
298                + 3 9
299                + 2 5
300                + 1 20 D",
301            )
302        );
303    }
304
305    #[tokio::test]
306    async fn test_dedup_executor_clean_state_by_watermark() {
307        let state_store = MemoryStateStore::new();
308        // No clean watermark column is set in the catalog, so the first dedup column is used.
309        let (mut tx, mut dedup_executor) = create_executor(state_store.clone()).await;
310        let table = BatchTable::for_test(
311            state_store,
312            TABLE_ID,
313            column_descs(),
314            vec![OrderType::ascending()],
315            vec![0],
316            vec![0, 1],
317        );
318        let stored_keys = async || {
319            let mut keys = vec![];
320            for key in 1..=4_i64 {
321                let row = table
322                    .get_row(
323                        &OwnedRow::new(vec![Some(key.into())]),
324                        HummockReadEpoch::NoWait(u64::MAX),
325                    )
326                    .await
327                    .unwrap();
328                if row.is_some() {
329                    keys.push(key);
330                }
331            }
332            keys
333        };
334
335        tx.push_barrier(test_epoch(1), false);
336        dedup_executor.expect_barrier().await;
337
338        tx.push_chunk(StreamChunk::from_pretty(
339            " I I
340            + 1 1
341            + 2 2
342            + 3 3
343            + 4 4",
344        ));
345        dedup_executor.expect_chunk().await;
346
347        // A watermark on a non-dedup column is forwarded without cleaning the state.
348        tx.push_int64_watermark(1, 10);
349        assert_eq!(
350            dedup_executor.expect_watermark().await,
351            Watermark::new(1, DataType::Int64, ScalarImpl::Int64(10))
352        );
353        tx.push_barrier(test_epoch(2), false);
354        dedup_executor.expect_barrier().await;
355        assert_eq!(stored_keys().await, vec![1, 2, 3, 4]);
356
357        tx.push_int64_watermark(0, 3);
358        assert_eq!(
359            dedup_executor.expect_watermark().await,
360            Watermark::new(0, DataType::Int64, ScalarImpl::Int64(3))
361        );
362        tx.push_barrier(test_epoch(3), false);
363        dedup_executor.expect_barrier().await;
364        assert_eq!(stored_keys().await, vec![3, 4]);
365    }
366}