risingwave_stream/executor/dedup/
append_only_dedup.rs1use 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
27pub struct AppendOnlyDedupExecutor<S: StateStore> {
33 ctx: ActorContextRef,
34
35 input: Option<Executor>,
36 dedup_cols: Vec<usize>,
38 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 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 let barrier = expect_first_barrier(&mut input).await?;
81 let first_epoch = barrier.epoch;
82 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 debug_assert!(chunk.ops().iter().all(|&op| op == Op::Insert));
94
95 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 self.populate_cache(dedup_keys.iter().flatten()).await?;
107
108 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 vis_builder.append(true);
119 } else {
120 vis_builder.append(false);
122 }
123 }
124 None => {
125 vis_builder.append(false);
127 }
128 }
129 }
130
131 let vis = vis_builder.finish();
132 if vis.count_ones() > 0 {
133 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 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 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 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 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 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}