Tracking: implement PrefixBloomFilter

[Li0k]

• [x] feat(utils): Support get prefix_len from pk by Table Schema

  • deserialize with data_type and order_type
  • deserialize without memory copy

• [x] #3874

  let prefix_column_index_in_storage_pk = vec![0..read_pattern_prefix_column];
  let prefix_len = deserialize_prefix_len_by_column (data_type_vec, prefix_column_index_in_storage_pk;
  let prefix_slice = &storage_pk[0..prefix_len];

• ~[ ] feat(frontend): Frontend infer the read_pattern_prefix_column and store it in TableCatalog~

• [x] #3927

• [x] #4027

• [x] feat(hummock): Build sst_table with SliceTransform

  • L0 sst build by Compute Node
  • sst build by Compactor Node

• [x] feat(storage): use dist_key as read_pattern_column for bloom_filter

[chenzl25]

Type Timestampz is encoded as i64 which is different from Timestamp, so we need to fix it.

[Li0k]

SSTBuilder will hold the SliceTransform and add key to bloom_filter, we need to compare prefix to avoid adding the same key repeatedly. Duplicate keys may inflate bloom filter size

[Li0k]

As default we use FullKeySliceTransform to ensure the same behavior as before. (for normal compaction)

using the exisiting table_id from compaction_group to filter the slice_transform. but In some cases existing_tableids does not exist (shared buffer compaction/ all table_id in sst has ben deleted). Some thoughts on this

1. use FullKeySliceTransform for this case to ensure the same behavior as before
2. use DummySliceTransform for this case to reduce cost of bloom_filter and rebuild it when normal compaction happend
3. Adding TableId to WriteBatch ensures that we can get table_id that exists in shared_buffer. And get slice_transform by table_id (prefer this option )

[Li0k]

some bench result

• with TPCH-q12 bench (scale 12 query 12 partition 12)
• use prefix_bloom_filter on the left , try to boost qps from 12w to 40w (14:00 - 15:00)
• no use prefix_bloom_filter on the right qps 40w (15:00 - )

• Summary for Q12
  • Compactor:
    • more 10~20% compactor cpu cost
    • compact duration is same in most cases, occasionally the max value is higher
  • Compute:
    • Source Throughput from 8w to 12w
    • Read Iter duration from 40ms to 25ms
    • Read Merged SSTs from 25 to 8
    • BloomFilter filter rate 96%

[Li0k]

• with TPCH-q20 bench (scale 20 query 20 partition 12)
• no use prefix_bloom_filter on 40w qps backpressure 100 (17:00 - 17:10)
• use prefix_bloom_filter on 40w qps backpressure 35 (17:10 - 17:15)
• • use prefix_bloom_filter on 80w qps backpressure 100 (17:20 - )

• Summary for Q20
  • Compactor:
    • cpu stable
    • compact duration is same in most cases, occasionally the max value is higher
  • Compute:
    • Source Throughput from 13w to 14w (qps 40w), and 20w (qps 80w)
    • Read Iter duration from 90ms to 50ms
    • Read Merged SSTs from 50 to 10
    • BloomFilter filter rate 97%