文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布

Apache Doris 内部数据裁剪与过滤机制的实现原理

，如 Join 时用 Build 侧数据生成谓词过滤 Probe 侧； 二级索引辅助：用 Bloom Filter、Cuckoo Filter等轻量级索引快速判断数据是否存在，避免全文件扫描。...v2, ..., vn)谓词，Probe 侧用该谓词过滤，仅保留 Join 列在In列表中的行，过滤率 100%（无误判）； 当 Build 侧数据量 > 阈值：生成 Bloom Filter（布隆过滤器...），Probe 侧用 Bloom Filter 判断 Join 列是否 “可能存在” 于 Build 侧： 若 Bloom Filter 判断 “不存在”，直接跳过该行； 若判断 “可能存在”，继续后续...为什么用 Bloom Filter：当 Build 侧数据量极大（如 100 万行），生成 In 谓词的开销（存储、传输、解析）过高，而 Bloom Filter 体积小（如 100 万行仅需几 MB）...例：Build 侧构建 Bloom Filter 需 2 秒，Probe 侧前 1 秒读取的数据未过滤，但 1 秒后启用 Bloom Filter，过滤后续 80% 的数据，整体仍能大幅减少 Join

28210
    • 您找到你想要的搜索结果了吗？
    是的
    没有找到

    高并发订单去重：布隆过滤器过滤已存在订单号的实战方案

    但当订单量突破亿级时，传统方案（查数据库、查 Redis Set）会因 “内存占用大”“查询慢” 失效，而布隆过滤器（Bloom Filter）凭借 “低内存、高吞吐、O (1) 查询” 的特性，成为这类场景的最优解...结论：用 “360MB 位数组 + 10 个哈希函数”，可存储 2 亿个订单号，误判率控制在 0.1% 以下 —— 完全满足订单场景需求，且内存成本极低。3....，error_rate=0.001（误判率），capacity=200000000（预计2亿订单）BF.RESERVE order_bloom_filter 0.001 200000000EXPANSION...= "order:bloom:filter"; // 误判率（与Redis初始化时一致） private static final double ERROR_RATE = 0.001;...，查询 “当天 + 近 30 天” 的所有过滤器，只要有一个过滤器判断 “可能存在”，就进行数据库校验；过期过滤器清理：每天凌晨删除 “30 天前” 的过滤器（如DEL order:bloom:filter

    42910

    大数据量下的集合过滤—Bloom Filter

    Bloom Filter就是一种解决方案。 Bloom Filter 概念 布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。...Bloom Filter跟单哈希函数Bit-Map不同之处在于：Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概率。 ?...如果bloom filter中存储的是黑名单，那么可以通过建立一个白名单来存储可能会误判的元素。 删除困难。...可以采用Counting Bloom Filter Bloom Filter 实现 布隆过滤器有许多实现与优化，Guava中就提供了一种Bloom Filter的实现。...如果用哈希表，每存储一亿个 email地址，就需要 1.6GB的内存（用哈希表实现的具体办法是将每一个 email地址对应成一个八字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有

    2K50

    大数据量下的集合过滤—Bloom Filter

    Bloom Filter就是一种解决方案。 Bloom Filter 概念 布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。...Bloom Filter跟单哈希函数Bit-Map不同之处在于：Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概率。 ?...如果bloom filter中存储的是黑名单，那么可以通过建立一个白名单来存储可能会误判的元素。 删除困难。...可以采用Counting Bloom Filter Bloom Filter 实现 布隆过滤器有许多实现与优化，Guava中就提供了一种Bloom Filter的实现。...如果用哈希表，每存储一亿个 email地址，就需要 1.6GB的内存（用哈希表实现的具体办法是将每一个 email地址对应成一个八字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有

    1.6K10

    Scrapy爬虫去重效率优化之Bloom Filter的算法的对接

    我们计算一下用这种方式耗费的存储空间。每个十六进制数占用4 b，1个指纹用40个十六进制数表示，占用空间为20 B，1万个指纹即占用空间200 KB，1亿个指纹占用2 GB。...了解Bloom Filter Bloom Filter，中文名称叫作布隆过滤器，是1970年由Bloom提出的，它可以被用来检测一个元素是否在一个集合中。...Bloom Filter的空间利用效率很高，使用它可以大大节省存储空间。Bloom Filter使用位数组表示一个待检测集合，并可以快速地通过概率算法判断一个元素是否存在于这个集合中。...本节我们来了解Bloom Filter的基本算法，以及Scrapy-Redis中对接Bloom Filter的方法。 2....Bloom Filter的实现就已经完成了，我们可以用一个实例来测试一下，代码如下： conn = StrictRedis(host='localhost', port=6379, password='

    4.2K72

    海量数据处理算法—Bloom Filter

    所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。 此外，Bloom Filter的hash函数选择会影响算法的效果。...将元素全部添加入Bloom Filter后，我们能得到真实的空间使用率，用这个值代入公式计算出一个比m小的值，重新构造Bloom Filter，对原先的哈希值进行求余处理，在误判率不变的情况下，使得其内存大小更合适...一般key-value存储系统的values存在硬盘，查询就是件费时的事。将Storage的数据都插入Filter，在Filter中查询都不存在时，那就不需要去Storage查询了。...Proxy-Cache 在Internet Cache Protocol中的Proxy-Cache很多都是使用Bloom Filter存储URLs，除了高效的查询外，还能很方便得传输交换Cache...如果用哈希表，每存储一亿个 email地址，就需要 1.6GB的内存（用哈希表实现的具体办法是将每一个 email地址对应成一个八字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有

    2.3K10

    Counting Bloom Filter 的原理和实现

    在所要表达的集合是静态集合的时候，标准 Bloom Filter 可以很好地工作，但是如果要表达的集合经常变动，标准Bloom Filter的弊端就显现出来了，因为它不支持删除操作。...二、什么是 Counting Bloom Filter Counting Bloom Filter 的出现，解决了上述问题，它将标准 Bloom Filter 位数组的每一位扩展为一个小的计数器（Counter...Counting Bloom Filter 通过多占用几倍的存储空间的代价， 给 Bloom Filter 增加了删除操作。基本原理是不是很简单？...看下图就能明白它和 Bloom Filter 的区别在哪。 ?...Bloom Filter）利用 d-left hashing 的方法存储 fingerprint，解决哈希表的负载平衡问题；ACBF（Accurate Counting Bloom Filter）通过

    18.1K1611

    BloomFilter 简介及在 Hadoop reduce side join 中的应用

    因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。...检测广播消息包的环路，将Bloom Filter保存在包里，每个节点将自己添加入Bloom Filter。 　　信息队列管理，使用Counter Bloom Filter管理信息流量。...如果用哈希表，每存储一亿个 email 地址，就需要1.6GB 的内存（用哈希表实现的具体办法是将每一个email 地址对应成一个八字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有...而Bloom Filter只需要哈希表1/8 到1/4 的大小就能解决同样的问题。Bloom Filter决不会漏掉任何一个在黑名单中的可疑地址。...注意：hbase的bloom filter是惰性加载的，在写压力比较大的情况下，会有不停的compact并产生storefile，那么新的storefile是不会马上将bloom filter加载到内存的

    1.4K80

    百万级并发下的去重挑战：Bloom Filter 与 Redis 的组合方案

    三、不同方案的实验报告于是我开始系统地比较各种方案：方案原理优点缺点Bloom Filter用多个哈希函数映射到位数组占内存小、速度快有误判（少量URL被错判为已存在）Redis HyperLogLog...四、最终方案：Bloom Filter + Redis + 持久化备份最后定下的架构是这样的：Bloom Filter 负责实时查重，超快；Redis HyperLogLog 负责全局唯一统计（看总共抓了多少个不同...URL）；文件持久化 定时保存Bloom Filter状态，防止重启丢失。...bloom.bit_array.tofile(f) print("Bloom Filter 持久化完成。")...七、总结：没有完美方案，只有合理组合层级工具作用内存层Bloom Filter高速查重分布式层Redis HyperLogLog唯一数统计存储层文件 / SQLite宕机恢复做采集久了你会发现： “去重

    30010

    快速学习-HBase实战解密

    一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。...如果用哈希表，每存储一亿个 email 地址， 就需要 1.6GB 的内存（用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹googlechinablog.com/2006/...因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。...下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0，如图9-5所示。 ?...为了add一个元素，用k个hash function将它hash得到bloom filter中k个bit位，将这k个bit位置1。

    53920

    布隆过滤器redis缓存 顶

    Bloom Filter就是一种解决方案。 Bloom Filter 概念 布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。...Bloom Filter有可能会出现错误判断，但不会漏掉判断。也就是Bloom Filter判断元 素不再集合，那肯定不在。如果判断元素存在集合中，有一定的概率判断错误。...Bloom Filter跟单哈希函数Bit-Map不同之处在于：Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概 率。 ?...如果bloom filter中存储的是黑名单， 那么可以通过建立一个白名单来存储可能会误判的元素。 删除困难。...可以采用Counting Bloom Filter Bloom Filter 实现 布隆过滤器有许多实现与优化，Guava中就提供了一种Bloom Filter的实现。

    1.1K20

    Bloom Filter布隆过滤器

    由此可见，Bloom filter也不是完美的，它的高效也是有一定代价的，它通过容忍一定的错误率发生换取了存储空间的极大节省。...三、优缺点 与其它数据结构相比较，Bloom filter的最大优点是空间效率和查找时间复杂性，它的存储空间和插入/查询时间都是常数。Hash函数之间没有相关性，可以方便地由硬件并行实现。...Bloom filter不需要存储元素本身，在某些对保密要求非常严格的场合有优势。另外，Bloom filter一般都可以表示大数据集的全集，而其它任何数据结构都难以做到。...这使得要求“零错误”的场合无法应用Bloom filter。其次，一般情况下不能从Bloom filter中删除元素。...这两方面也是目前Bloom filter的重点研究方向，有不少工作，使得出现了很多Bloom filter的变种。

    89220

    布隆过滤器Bloom Filter简介

    因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。...（3）现在，把这个n个元素依次用第1步选取的k个哈希函数映射到bit数组的位置上，bit数组被映射到的位置的元素变为1。显然，一个元素能被映射到k个位置上。...具体做法就是：将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url...5、如何解决布隆过滤器不支持删除的问题： （1）counting bloom filter： Counting Bloom Filter将标准 Bloom Filter位数组的每一位扩展为一个小的计数器...Counting Bloom Filter通过多占用几倍的存储空间的代价，给Bloom Filter增加了删除操作。

    69520

    Twitter推荐引擎架构设计分析

    整体物料存储用Concurrent HashMap结构，更新速度可达数万/s，满足物料数量要求。...推特推荐系统原已读是基于 bloom filter 实现。...如图为推特原 30 天已读方案实例：共四个 filter，每十天存储一个 filter，每次读取覆盖最近 30 天的四个 filter，取回 bloom filter 后通过或运算将其合并成一个 bloom...该方案： 结构不合理，面对所有用户 bloom filter 大小均不变，因此：高消费的用户使用推特频率高，填充率高，则误判高；低消费用户阅读量小，空间利用率低，浪费资源 直接读取存储的 Redis，存储一旦出错服务也难免受牵连...bloom filter 完成已读记录 稳定性，一方面建立独立的短期（如几个小时）已读存储，在主要资源不可用时提供降级服务；另一方面，优化 Redis 资源访问方式，Meta 信息及最新一个 bloom

    74300
    点击加载更多

    相关资讯

    热门标签

    更多标签

    活动推荐

      运营活动

      活动名称
      广告关闭

      腾讯云开发者

      扫码关注腾讯云开发者

      扫码关注腾讯云开发者

      领取腾讯云代金券

      热门产品

      热门推荐

      更多推荐

      Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有

      深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

      腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号

      领券