首页 注册 登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
› MySQL 5.5 Community Server
› MySQL 5.6 Community Server
› Percona Configuration Wizard
› XtraBackup 搭建主从复制
Great Sites on MySQL
› Percona
› MySQL Performance Blog
› Severalnines
推荐管理工具
› Sequel Pro
› phpMyAdmin
推荐书目
› MySQL Cookbook
MySQL 相关项目
› MariaDB
› Drizzle
参考文档
› http://mysql-python.sourceforge.net/MySQLdb.html
广告
hyd8323268
V2EX  ›  MySQL

问题表有 50w，回答表 900w，需求是查出指定用户没有回答过的问题，怎么能快一点，有大佬支个招不。

  •   
  •   hyd8323268 · 2020-12-08 11:08:59 +08:00 · 7377 次点击
    这是一个创建于 1457 天前的主题，其中的信息可能已经有所发展或是发生改变。
    现在是子查询，但是如果用户回答超过 10w 并且问题表进行分页的话会更慢。需要考虑到分页和跳转指定页的实现。
  • 分页
  • 回答
  • 指定
  • 查出
    66 条回复  •  2020-12-10 10:09:06 +08:00
    zjttfs
        1
    zjttfs  
       2020-12-08 11:26:04 +08:00
    问题表加统计 回答数, 回答数做索引 如何?
    zpfhbyx
        2
    zpfhbyx  
       2020-12-08 11:28:50 +08:00
    问题表冗余一个字段 用 bitmap 的方式标记回答的用户，查询的时候 字段>>uid & 0 =0(应该是这样) 标记为未回答，后面的就好搞了
    hyd8323268
        3
    hyd8323268  
    OP
       2020-12-08 11:35:30 +08:00
    @zjttfs 需求是查询出该顾问未回答过的问题，而不是未被人回答过的问题哦 orz
    xuanbg
        4
    xuanbg  
       2020-12-08 11:44:33 +08:00
    select q.* from question q left join answer a on a. question_id = q.id where a.id is null;
    xuanbg
        5
    xuanbg  
       2020-12-08 11:49:21 +08:00
    具体到顾问，on 后面加上 and a. adviser_id = 顾问 id 就行
    taogen
        6
    taogen  
       2020-12-08 11:49:23 +08:00 via Android
    表结构，查询 SQL 和 explain 贴一下。
    xuanbg
        7
    xuanbg  
       2020-12-08 11:50:56 +08:00   ❤️ 1
    你这个需求无法优化数据结构，肯定快不起来的……
    aeli
        8
    aeli  
       2020-12-08 11:53:51 +08:00
    @zpfhbyx 这个 bitmap 就行了，不过最好放到 redis 里面
    zpfhbyx
        9
    zpfhbyx  
       2020-12-08 11:59:39 +08:00
    @aeli 放 redis 做检索分页不好搞吧
    treblex
        10
    treblex  
       2020-12-08 12:45:07 +08:00
    给问题按难度 类型 分级，像多邻国那种形式会不会好一点，
    必须查出用户没有答过的问题 感觉不是个强需求，就算随机也不见得用户会发现
    whileFalse
        11
    whileFalse  
       2020-12-08 13:44:32 +08:00
    把问题 ID 先缓存到内存里。然后查该用户的所有回答即可。
    opengps
        12
    opengps  
       2020-12-08 13:51:59 +08:00 via Android
    问题表下增加统计字段，小批量分时段维护
    laminux29
        13
    laminux29  
       2020-12-08 13:56:52 +08:00
    你就缺那点硬盘空间嘛？这题显然是空间换时间的思路啊，给每个用户建个 2 分表，分别存储已回答与未回答的不就完事了。
    Nillouise
        14
    Nillouise  
       2020-12-08 14:01:41 +08:00
    每个用户储存回答过的问题，查询的时候在应用里跟全部问题过滤一下即可。
    sunziren
        15
    sunziren  
       2020-12-08 14:03:52 +08:00
    先整一个 2TB 的内存，然后数据库放到内存里
    sunziren
        16
    sunziren  
       2020-12-08 14:04:50 +08:00
    然后双路 CPU+集群，然后咱们再进一步探讨
    I52Hertz
        17
    I52Hertz  
       2020-12-08 16:11:20 +08:00
    先查出已回答的问题，然后从全集里去掉
    pkupyx
        18
    pkupyx  
       2020-12-08 16:30:29 +08:00
    详细描述需求场景吧，都打了什么标签，推荐没做过的的题目应该也不是 50W 道题里面没做过的随机推吧。
    vance123
        19
    vance123  
       2020-12-08 17:20:30 +08:00
    转化成算法题的话就是:
    对于序列 s = 00001010101..., 已知所有`1`的下标, 求第 k 个`0`的下标大小
    解法应该是 O(1)吧, 当然问题 ID 要连续
    stevenbipt
        20
    stevenbipt  
       2020-12-08 17:39:41 +08:00
    sql 的话像 4 楼那样直接一个 left join 就能出来
    BigLion
        21
    BigLion  
       2020-12-08 18:42:00 +08:00
    直接 left join
    CRVV
        22
    CRVV  
       2020-12-08 20:20:43 +08:00
    只有一种确定的顺序还是可以随意指定顺序？


    1. 只有一种顺序
    如果只有一种顺序，按这个顺序建一个索引，然后 Index Scan 就好了，一个用户回答过的问题通常不会很多吧。
    跳转到第 x 页这种需求不可能快，不用考虑了。

    如果在这种排序下，每个用户回答过的问题都没有聚集在一起，这个方法应该就够快了。
    如果有聚集在一起，用 vance123 的方法

    2. 顺序可以任意指定
    2.1 给每一种顺序建一个索引，然后回到 1，这个通常不现实
    2.2 如果不能给每种顺序建索引，就没有通用的 O(n) 以内的算法了。基本上都要 Sequential Scan 。当然有各种优化的方法，但这种事情依赖于非常具体的需求。
    richard1122
        23
    richard1122  
       2020-12-08 20:22:57 +08:00
    你把表结构、索引和 sql 贴出来，再跑一下 explain 也贴出来。
    900w 这个量对这个需求索引设计正常点不会慢的
    debuggerx
        24
    debuggerx  
       2020-12-08 20:46:31 +08:00   ❤️ 8
    说下我几年前的一个需求情况和解决思路，看看能不能有所启发吧
    当时公司做一套答题，题库大约 5k 条，每轮答题给 10 条数据，同一个用户只要显示过的题目后面就不再出现。
    我是先把题库入库，然后写了个算法，核心是利用用户的 uid 作为 seed 丢给 java 的 random 函数，从而给每个用户生成一个独一无二的随机序列，再利用这个随机序列对题库做映射，这样每个用户都能实际确定一个答题顺序，然后每次答题，只用记录答题的轮数，访问答题接口时只要传 uid 和轮数就能先快速在程序中算出需要的题目 id，然后数据库 select in [ids] 就可以了
    ben1024
        25
    ben1024  
       2020-12-08 20:50:38 +08:00
    直接左连接取值查询后，进行子查询限制 limit
    leeg810312
        26
    leeg810312  
       2020-12-08 21:11:26 +08:00 via Android
    数据库查询需求中，所有不包含的需求都要转化为包含，性能才能提升
    makdon
        27
    makdon  
       2020-12-08 21:33:36 +08:00
    用布隆过滤器应该可以搞得比较快。
    新增一个用户-布隆的 bitmap 表，主键用户 id，另一列一个大 bitmap
    然后
    select *
    from 问题表
    where
    !( 取布隆 bit 结果(问题 id) & 用户 bitmap)
    # 假定 id 连续单调递增
    order by 问题 id
    offset 页数*页大小

    没有具体 benchmark，不过我想这大概能用，线性遍历问题表够了就可以返回的算法

    不过其实算一下，9,000,000 条问题，一条算 1KB，内存占用也就 9GB 这个数量级，如果业务允许（例如增删改不不频繁），我会搞两台内存大的服务器，直接在内存里面玩上面的解法；
    如果“用户回答超过 10w”指的是一个用户的话，那就改成随机从问题库里面挑然后位与康康有没有回答过，分页按钮改成“换一批问题”（不然每次都要遍历 10w 个问题）
    一定要分页的话，可以给用户记录一个“上一次回答的最后一个问题的 id”，下次找的时候从那个 id 开始找。
    ofooo
        28
    ofooo  
       2020-12-08 21:42:02 +08:00
    把问题表缓存到内存里感觉不错。50 万也不多
    liuzhaowei55
        29
    liuzhaowei55  
       2020-12-08 21:42:21 +08:00
    首先，优化需求，去掉跳转指定页的这个需求，然后
    1. 回答表排序
    2. 拿出 1000 条数据，去答案表里边过滤掉一下，大概率留下的数据就可以返回前端使用了
    3. 下次加载带上上次的最后一条有效数据标志作为条件
    4. 想了下，这个只适合手机这种上拉刷新的方式加载数据
    CoderGeek
        30
    CoderGeek  
       2020-12-08 21:55:57 +08:00
    1.将用户回答过的问题 id 存在 redis 中
    2.选取需要用户回答的问题，都是为回答过的全部返回
    3.有回答过的继续取

    当然问题列表也可以做缓存也是存 id
    CoderGeek
        31
    CoderGeek  
       2020-12-08 21:57:01 +08:00
    @CoderGeek 未回答过的全部返回
    CoderGeek
        32
    CoderGeek  
       2020-12-08 21:58:18 +08:00
    没仔细看 有的用户回答过 10W ？ 不允许重复 那你这个效率不会很快前端可以控制的话 从前端解决
    ElmerZhang
        33
    ElmerZhang  
       2020-12-08 23:07:23 +08:00
    如果我来做的话，这个场景我应该会直接上 ElasticSearch
    szuwl
        34
    szuwl  
       2020-12-08 23:50:42 +08:00 via iPhone
    数据量都上千万了，直接分表就完事了
    optional
        35
    optional  
       2020-12-09 00:16:04 +08:00 via iPhone
    用户回答过的相对问题总数基本可以忽略，可以不用考虑索引了，直接走主键索引就好。
    c6h6benzene
        36
    c6h6benzene  
       2020-12-09 01:25:24 +08:00
    直接 left join 的话可能没有办法拿到“没有回答”的问题。可能得先用户 ID 跟问题 ID 乘一下。
    gyf304
        37
    gyf304  
       2020-12-09 06:05:29 +08:00
    可以考虑用一个 materialized view 实现一个 用户->问题 ID 的 adjacency list 。
    justNoBody
        38
    justNoBody  
       2020-12-09 09:52:13 +08:00
    @taogen 6# 说的对 说不定光看执行计划就可以优化了😂
    nano91
        39
    nano91  
       2020-12-09 10:12:13 +08:00
    我还是觉得应该反过来做，既然你要找特定人的未回答问题，那就直接找特定人回答过的问题，然后取反就行了，这一点应该要重新做设计，也就是说得有一个地方记录下来每个人回答了那些问题 person.id => anwser.question_id，因为每个人回答的问题数量相对于问题总数一定是很少的，这个方法相比直接按原始的 人-回答-问题 这样查询要更好
    v2Geeker
        40
    v2Geeker  
       2020-12-09 10:47:49 +08:00
    上面很多方案都没算过成本。这个需求没有钱还是挺难快起来的。
    zpfhbyx
        41
    zpfhbyx  
       2020-12-09 12:30:10 +08:00
    @v2Geeker 我很好奇。问题表冗余一个字段。。有啥成本。。
    v2Geeker
        42
    v2Geeker  
       2020-12-09 14:25:01 +08:00
    @zpfhbyx 哥哥，你自己先算算嘛。我来跟你先算一个吧，你的方案，50w 的 bitmap，即每条数据会多出 0.0596M 的大小。900w 条数据，一共多出 518.55G 的数据。。。这还没算用户增长和问题增长的情况。
    v2Geeker
        43
    v2Geeker  
       2020-12-09 14:25:36 +08:00
    @zpfhbyx 空间换时间。还是我全都要。
    zpfhbyx
        44
    zpfhbyx  
       2020-12-09 14:38:09 +08:00
    @v2Geeker bitmap 转十进制落库啊，这么算的话只会出一个 int 或者 bigint 啊，然后按位操作就行了
    todd7zhang
        45
    todd7zhang  
       2020-12-09 14:43:39 +08:00
    @zpfhbyx 不对吧，按你 "bitmap 字段>>uid & 0 =0" 的逻辑， 一个 int32 的 bitmap，uid 取值范围[0, 31]啊？用户数几十个才
    zpfhbyx
        46
    zpfhbyx  
       2020-12-09 14:56:49 +08:00
    @v2Geeker 老哥，我错了。光想着行了。。没想列。
    zpfhbyx
        47
    zpfhbyx  
       2020-12-09 14:57:23 +08:00
    @todd7zhang 嗯， 的确是
    wellsc
        48
    wellsc  
       2020-12-09 15:00:52 +08:00
    bitmap 的话要考虑数据一致性问题的，要引入中间件同步数据
    JimmyChange
        49
    JimmyChange  
       2020-12-09 16:55:20 +08:00
    感觉所有问题 id 放内存，从问题表查出所有已回答问题 id 后求个补集就可以吧
    final7genesis
        50
    final7genesis  
       2020-12-09 17:02:29 +08:00
    redis 用户为 key, 问题序号 setbit 存储， 每天重新计算可行不？
    mazhan465
        51
    mazhan465  
       2020-12-09 18:20:30 +08:00
    先查该用户回答的问题列表，一般来说一个用户也不会回答几千几万个问题。即便真的有这么多问题，无非也就是将问题表再全表拉下来，减去已回答问题。
    这样直接在程序里做减法运算，比 db 做 join 或者 exists 快多了
    keepeye
        52
    keepeye  
       2020-12-09 18:27:02 +08:00
    先查出该用户回答过的问题，然后再 not in 一下?
    lishen226
        53
    lishen226  
       2020-12-09 18:45:02 +08:00
    10W 条查主键应该不慢吧，关键是要多快的速度啊？
    skaly
        54
    skaly  
       2020-12-09 18:51:10 +08:00
    在问题表里面加一个字段,标识是否有用户回答,这样就行了嘛,不要考虑实时聚合的查,没有意义的
    byou
        55
    byou  
       2020-12-09 19:29:52 +08:00
    可以换一种思路，分页显示所有问题，在当前用户回答过的问题前边做个标记，表示此问题已回答。就像 leetcode 题库那样的。
    感觉没有必要只显示未回答问题，试试说服产品？
    nuk
        56
    nuk  
       2020-12-09 20:20:34 +08:00
    如果不是取全部数据的话，完全可以每个用户存分页的 index
    50w 回答，假如一页 100，那么最多最多就是 5000 个 index
    用户每次回答后更新 index，然后在 index 的范围内找没回答的问题
    问题就是修改每页数量。。会很麻烦。。
    faceRollingKB
        57
    faceRollingKB  
       2020-12-09 20:37:05 +08:00
    50w 个问题再怎么检索都得每个人匹配 50w 次才能得出结果，量在这里我觉得快不到哪去，不如跑一个定时任务每天刷一遍数据存起来
    faceRollingKB
        58
    faceRollingKB  
       2020-12-09 20:41:45 +08:00
    每天刷有点浪费资源，就谁查给谁刷一遍做缓存吧
    kinXdle
        59
    kinXdle  
       2020-12-09 23:00:06 +08:00 via iPhone
    用户表加个标示列，回答了就更新
    hyd8323268
        60
    hyd8323268  
    OP
       2020-12-10 09:58:29 +08:00
    @faceRollingKB 最终方案是如此
    hyd8323268
        61
    hyd8323268  
    OP
       2020-12-10 09:59:30 +08:00
    @kinXdle 标识列存什么呢，已回答 id ？十几万 id 集？...
    hyd8323268
        62
    hyd8323268  
    OP
       2020-12-10 10:03:24 +08:00
    @byou 如果用户回答过多，就会导致翻很多页都是已回答，并且排序是时间，所有页码也不固定，最后 pass 了
    hyd8323268
        63
    hyd8323268  
    OP
       2020-12-10 10:04:37 +08:00
    @keepeye 先查后 not in 效率还不如 not in 子查询
    faceRollingKB
        64
    faceRollingKB  
       2020-12-10 10:04:41 +08:00
    @hyd8323268 只能看看业务上能不能做一些优化，比如其他人提到的给问题编组，组与组之间有一定规律，然后只记录用户答题所在的组，业务上就可以不匹配直接得出问题答了没有
    hyd8323268
        65
    hyd8323268  
    OP
       2020-12-10 10:05:06 +08:00
    @szuwl 这个好像和分表没有关系吧
    hyd8323268
        66
    hyd8323268  
    OP
       2020-12-10 10:09:06 +08:00
    @faceRollingKB 现在的方案是不显示的全部问答，每天凌晨跑脚本，给活跃用户并且回答数超过 5 万级批量生成 1000 个问题 id，放到临时表中，未答条件的直接查库。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3500 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 11:12 · PVG 19:12 · LAX 03:12 · JFK 06:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.