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 · 7096 次点击
    这是一个创建于 1206 天前的主题,其中的信息可能已经有所发展或是发生改变。
    现在是子查询,但是如果用户回答超过 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   ·   我们的愿景   ·   实用小工具   ·   3130 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 12:59 · PVG 20:59 · LAX 05:59 · JFK 08:59
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.