简单生活

  • 这是第二次 SQL 编程大赛[1],我依旧是评委之一,所以自己也尝试了独立完成该问题的挑战。这次大赛分为“普通挑战”和“进阶挑战”。其中普通挑战较为简单,本文主要讨论自己完成进阶挑战过程中的想法与思路。

    问题描述

    原始的问题,可以参考:NineData 第二届数据库编程大赛 用一条SQL秒杀火车票,本文仅考虑其中的“进阶挑战”。这里该“进阶挑战问题”复述如下。

    有如下两张表存放着乘客信息和列车信息,使用一条SQL给每个乘客分配一趟列车以及对应的座位号,需要注意,需要考虑进阶挑战的一些要求,比如,每趟列车可以发售10%的无座车票;车票需要有限发售有座车票,然后才开始发售无座车票。

    mysql> desc passenger;
    +-------------------+-------------+------+-----+
    | Field             | Type        | Null | Key |
    +-------------------+-------------+------+-----+
    | passenger_id      | varchar(16) | NO   | PRI |
    | departure_station | varchar(32) | NO   |     |
    | arrival_station   | varchar(32) | NO   |     |
    +-------------------+-------------+------+-----+
    mysql> desc train;
    +-------------------+-------------+------+-----+
    | Field             | Type        | Null | Key |
    +-------------------+-------------+------+-----+
    | train_id          | varchar(8)  | NO   | PRI |
    | departure_station | varchar(32) | NO   |     |
    | arrival_station   | varchar(32) | NO   |     |
    | seat_count        | int         | NO   |     |
    +-------------------+-------------+------+-----+

    示例数据如下:

    mysql> select * from passenger limit 3;
    +--------------+-------------------+-----------------+
    | passenger_id | departure_station | arrival_station |
    +--------------+-------------------+-----------------+
    | P00000001    | 上海              | 福州            |
    | P00000002    | 成都              | 成都            |
    | P00000003    | 乌鲁木齐          | 太原            |
    +--------------+-------------------+-----------------+
    mysql> select * from train limit 3;
    +----------+-------------------+-----------------+------------+
    | train_id | departure_station | arrival_station | seat_count |
    +----------+-------------------+-----------------+------------+
    | G1006    | 重庆              | 北京            |       1600 |
    | G1007    | 杭州              | 福州            |        600 |
    | G1008    | 济南              | 合肥            |        800 |
    +----------+-------------------+-----------------+------------+

    解题思路

    对乘客进行编号

    首先利用数据库的Windows Function功能对所有的乘客先分组再编号,具体的,按照“出发站”和“到达站”分组,然后在组内进行编号。次编号则为后续乘客车票分配的编号。例如,从 A 到 B 地,一共有 2420 个乘客。那么乘客的编号则是1…2420;再有乘客从 C 到 D 地,共有1800个乘客,则编号则为 1 … 1800。大概可以使用类似如下的 SQL 代码实现:

    ROW_NUMBER() over(PARTITION BY departure_station,arrival_station) as seq

    对列车进行排序和计算

    与乘客类似的,先按照出发和到达站点进行分组,并计算每个列车能够容纳的乘客数量,即座位数量的 1.1 倍。然后,在分组内进行“累加”计算,该累加计算,需算出每个列车能够运载乘客的起始序号和结束序号。例如,从 A 到 B地,共有列车 G01 和 G07 ,并分别有 600 和 1600 个座位。那么,经过上述的累加计算,列车 G01 能够运载的乘客编号应该是 1 到 660,而 G01 能够运载的乘客编号则为 661 到 2420 (即为 660 + 1600*110%)。

    上述计算也可以使用 Window Function来实现,参考实现如下:

            sum(seat_count*1.1)
              over (
                     PARTITION BY departure_station,arrival_station
                     ORDER BY train_id
                   ) as p_seat_to ,

    合并计算结果

    然后,将上述经过计算的乘客表和列车表进行 JOIN ,条件是 起始站和到达站相同,且乘客编号在列车编号之间。如果,乘客无法关联出列车,则表示无法分配列车。

    该方案的最终 SQL

    SELECT
      p_01.p_id,
      p_01.d_s,
      p_01.a_s,
      t_01.train_id as t_id,
      p_01.seq, -- passager seq from d_s to a_s
      t_01.seat_count,
      @p_seat_from := (t_01.p_seat_to-t_01.seat_count*1.1 + 1) as seat_from, -- train seat from(start index)
      t_01.p_seat_to as seat_to, -- train seat from(start index)
    
      if(p_01.seq >= p_seat_to-seat_count*0.1 + 1, "ti_no_seat","...") as ti_no_seat,
                    
      
      @seq_in_train := p_01.seq - @p_seat_from + 1  as seq_in_train, -- seq in the train
    
      @carriage_id := ceil(@seq_in_train/100) as t_carr_id, -- for carriage id 
    
      @row_id := ceil((@seq_in_train%100)/5) as row_id, -- row_id
    
      @seat_id := ceil((@seq_in_train%100)%5) seat_id  -- 0,1,2,3,4  A B C E F
    
    
    FROM
         (
           select
               ROW_NUMBER() over(PARTITION BY departure_station,arrival_station) as seq ,
               passenger_id as p_id,
               departure_station as d_s,
               arrival_station as a_s
           from
           passenger
         ) as p_01
    
         LEFT JOIN
    
        (
          select
            seat_count,
            sum(seat_count*1.1)
              over (
                     PARTITION BY departure_station,arrival_station
                     ORDER BY train_id
                   ) as p_seat_to ,
            train_id,
            departure_station as d_s ,
            arrival_station as a_s
          from
          train
        ) t_01
    
        ON
                p_01.seq >= p_seat_to-seat_count*1.1 + 1
            and p_01.seq <= p_seat_to
            and p_01.d_s =  t_01.d_s
            and p_01.a_s =  t_01.a_s

    上述实现的问题

    这样的实现,是可以完成相关的座位分配。但是,却会出现一个不合理的情况,即可能有车次的座位没有分配完,但是有一部分乘客却被分配到了无座的车次。比如,从A到B的车次,有两班,第一班车600个座位,第二版1600个座位,一共有 800 个乘客的话,那么这里分配自由度就比较高,比如这种情况依旧分配了 220 个无座的座位,是否是满足要求的。

    在最初,该赛题还未对外发布时,是没有该限制的。而后,发现该漏洞后,新增了一个规则,即需要先把有座的票优先分配,再分配无座的车票。

    考虑优先分配有座

    考虑优先分配有座的车票,再对上述实现进行一定程度的修改。

    重新考虑对列车的编号和计算

    对于每一趟列车X,构造一个虚拟列车X',该虚拟列车X'虚拟的负责所有的X列车的座票。而在给列车中计算起始和结束乘客编号时,则优先计算原列车的编号范围,在所有的原列车编号计算完成后,再计算X'的乘客编号范围。

    这里使用 CTEs 实现该表达如下:

    WITH 
      t_no_seat_virtual AS (
            select train_id as t_id,departure_station as d_s,arrival_station as a_s,seat_count, seat_count*0.1 as seat_count_no_seat 
            from train ),
      t_include_no_seat AS (
            select t_id,d_s ,a_s ,seat_count, "with_seat" as if_seat
            from t_no_seat_virtual
            union 
            select t_id,d_s ,a_s ,seat_count_no_seat, "no_seat" as if_seat
            from t_no_seat_virtual)
    SELECT * from t_include_no_seat ORDER BY t_id

    包含虚拟列车的表 t_include_no_seat

    然后把上面的实现中,表train替换成这里的 t_include_no_seat ,包含了额外的“虚拟列车”,完整的 SQL 如下:

    WITH
      t_no_seat_virtual AS (
            select train_id as t_id,departure_station as d_s,arrival_station as a_s,seat_count, seat_count*0.1 as seat_count_no_seat
            from train ),
      t_include_no_seat AS (
            select t_id,d_s ,a_s ,seat_count, 0 as if_no_seat
            from t_no_seat_virtual
            union
            select t_id,d_s ,a_s ,seat_count_no_seat, 1 as if_no_seat
            from t_no_seat_virtual)
    select
      seat_count,
      sum(seat_count)
        over (
               PARTITION BY d_s,a_s
               ORDER BY t_id,if_no_seat
             ) as p_seat_to ,
      t_id,
      d_s ,
      a_s,
      if_no_seat
    from
    t_include_no_seat

    返回的结果如下:

    +------------+-----------+------+--------+--------+------------+
    | seat_count | p_seat_to | t_id | d_s    | a_s    | if_no_seat |
    +------------+-----------+------+--------+--------+------------+
    |      600.0 |     600.0 | G109 | 上海   | 北京   |          0 |
    |       60.0 |     660.0 | G109 | 上海   | 北京   |          1 |
    |     1600.0 |    2260.0 | G40  | 上海   | 北京   |          0 |
    |      160.0 |    2420.0 | G40  | 上海   | 北京   |          1 |
    |     1600.0 |    4020.0 | G70  | 上海   | 北京   |          0 |
    |      160.0 |    4180.0 | G70  | 上海   | 北京   |          1 |
    |     1600.0 |    1600.0 | G113 | 上海   | 广州   |          0 |
    |      160.0 |    1760.0 | G113 | 上海   | 广州   |          1 |
    |     1600.0 |    3360.0 | G26  | 上海   | 广州   |          0 |
    |      160.0 |    3520.0 | G26  | 上海   | 广州   |          1 |
    |     1600.0 |    5120.0 | G48  | 上海   | 广州   |          0 |
    |      160.0 |    5280.0 | G48  | 上海   | 广州   |          1 |
    |     1600.0 |    1600.0 | G52  | 上海   | 成都   |          0 |
    |      160.0 |    1760.0 | G52  | 上海   | 成都   |          1 |
    |     1600.0 |    3360.0 | G8   | 上海   | 成都   |          0 |
    |      160.0 |    3520.0 | G8   | 上海   | 成都   |          1 |
    |     1600.0 |    1600.0 | G107 | 上海   | 武汉   |          0 |
    |      160.0 |    1760.0 | G107 | 上海   | 武汉   |          1 |
    |     1600.0 |    3360.0 | G17  | 上海   | 武汉   |          0 |
    |      160.0 |    3520.0 | G17  | 上海   | 武汉   |          1 |

    这里需要注意的是,编号的 ORDER BY 需要按照 if_no_seat,t_id 进行排序,这样就可以保障,优先分配有座位的位置。

    WITH
      t_no_seat_virtual AS (
            select train_id as t_id,departure_station as d_s,arrival_station as a_s,seat_count, seat_count*0.1 as seat_count_no_seat
            from train ),
      t_include_no_seat AS (
            select t_id,d_s ,a_s ,seat_count, 0 as if_no_seat
            from t_no_seat_virtual
            union
            select t_id,d_s ,a_s ,seat_count_no_seat, 1 as if_no_seat
            from t_no_seat_virtual)
    select
      sum(seat_count)
        over (
               PARTITION BY d_s,a_s
               ORDER BY     if_no_seat,t_id
             ) as p_seat_to ,
      seat_count,
      t_id,
      d_s ,
      a_s,
      if_no_seat
    from
    t_include_no_seat

    按照乘客序号分配座位

    与前述的实现相同,首先按照始发和到达站点将旅客表与“虚拟列车”表关联。如果自己序列落在某个列车的区间中就表示有座位。

    关于 row 的分配异常问题

    按照上述的分配,会将编号为 100 背书的人,分配为 0F,而正确的应该是 20 F。所以,需要额外处理该数值。具体的:

    ceil((( p_01.seq-t_01.p_seat_to + t_01.seat_count )%100)/5) 

    修改如下:

    IF( (p_01.seq-t_01.p_seat_to + t_01.seat_count)%100 = 0, "20" ,ceil((( p_01.seq-t_01.p_seat_to + t_01.seat_count )%100)/5))  

    这部分代码实现较为冗长,更好的方法是先计算偏倚值,然后使用字符串截取函数截取,而无需写这么多的CASE ... WHEN

    完整的SQL

    WITH 
      t_no_seat_virtual AS (
            select train_id as t_id,departure_station as d_s,arrival_station as a_s,seat_count, seat_count*0.1 as seat_count_no_seat 
            from train ),
      t_include_no_seat AS (
            select t_id,d_s ,a_s ,seat_count, 0 as if_no_seat
            from t_no_seat_virtual
            union 
            select t_id,d_s ,a_s ,seat_count_no_seat, 1 as if_no_seat
            from t_no_seat_virtual)
    
    SELECT
      p_01.p_id,
      p_01.d_s,
      p_01.a_s,
      t_01.t_id as t_id,
      p_01.seq, -- passager seq from d_s to a_s
      t_01.seat_count,
      t_01.if_no_seat,
      @p_seat_from := (t_01.p_seat_to-t_01.seat_count + 1) as seat_from, -- train seat from(start index)
      t_01.p_seat_to as seat_to, -- train seat from(start index)
      
      @seq_in_train := p_01.seq - @p_seat_from + 1  as seq_in_train, -- seq in the train
    
      @carriage_id := ceil(@seq_in_train/100) as t_carr_id, -- for carriage id 
    
      @row_id := ceil((@seq_in_train%100)/5) as row_id, -- row_id
    
      @seat_id := ceil((@seq_in_train%100)%5) seat_id,  -- 0,1,2,3,4  A B C E F
    
      CASE
        WHEN @seat_id = 1 THEN CONCAT(@row_id,"A")
        WHEN @seat_id = 2 THEN CONCAT(@row_id,"B")
        WHEN @seat_id = 3 THEN CONCAT(@row_id,"C")
        WHEN @seat_id = 4 THEN CONCAT(@row_id,"E")
        WHEN @seat_id = 0 THEN CONCAT(@row_id,"F")
        ELSE "ERROR"
      END as seat_index
    
    FROM
         (
           select
               ROW_NUMBER() over(PARTITION BY departure_station,arrival_station) as seq ,
               passenger_id as p_id,
               departure_station as d_s,
               arrival_station as a_s
           from
           passenger
         ) as p_01
    
         LEFT JOIN
    
        (
          select
            seat_count,
            sum(seat_count)
              over (
                     PARTITION BY d_s,a_s
                     ORDER BY     if_no_seat,t_id
                   ) as p_seat_to ,
            t_id,
            d_s ,
            a_s ,
            if_no_seat
          from
          t_include_no_seat
        ) t_01
    
        ON
                p_01.seq >= p_seat_to-seat_count + 1
            and p_01.seq <= p_seat_to
            and p_01.d_s =  t_01.d_s
            and p_01.a_s =  t_01.a_s

    修正SQL

    最后按照题目要求,对输出结果做一些修正。具体的:

    • 按要求,如果分配座位为无座的,则在车厢号展示为””,座位号显示”无座”。
    • 删除中间计算结果,为了保证性能,就不在外面再套一层了,事实上,套一层可读性会更好
    WITH 
      t_no_seat_virtual AS (
            select train_id as t_id,
                   departure_station as d_s,
                   arrival_station as a_s,
                   seat_count, seat_count*0.1 as seat_count_no_seat 
            from train ),
      t_include_no_seat AS (
            select t_id,d_s ,a_s ,seat_count, 0 as if_no_seat
            from t_no_seat_virtual
            union 
            select t_id,d_s ,a_s ,seat_count_no_seat, 1 as if_no_seat
            from t_no_seat_virtual)
    
    SELECT
      p_01.p_id,
      p_01.d_s,
      p_01.a_s,
      t_01.t_id as t_id,
      p_01.seq, -- passager seq from d_s to a_s
      t_01.seat_count,
      t_01.if_no_seat,
      @p_seat_from := (t_01.p_seat_to-t_01.seat_count + 1) as seat_from, -- train seat from(start index)
      t_01.p_seat_to as seat_to, -- train seat from(start index)
      
      @seq_in_train := p_01.seq - @p_seat_from + 1  as seq_in_train, -- seq in the train
    
      -- @carriage_id := ceil(@seq_in_train/100) as t_carr_id, -- for carriage id 
    
      IF(if_no_seat, "" , @carriage_id := ceil(@seq_in_train/100) ) as t_carr_id,
    
      @row_id := ceil((@seq_in_train%100)/5) as row_id, -- row_id
    
      @seat_id := IF( !isnull(t_01.t_id) and if_no_seat,-1,ceil((@seq_in_train%100)%5)) as seat_id,  -- 0,1,2,3,4  A B C E F
    
      CASE
        WHEN @seat_id = 1  THEN CONCAT(@row_id,"A")
        WHEN @seat_id = 2  THEN CONCAT(@row_id,"B")
        WHEN @seat_id = 3  THEN CONCAT(@row_id,"C")
        WHEN @seat_id = 4  THEN CONCAT(@row_id,"E")
        WHEN @seat_id = 0  THEN CONCAT(@row_id,"F")
        WHEN @seat_id = -1 THEN "无座"
        ELSE NULL
      END as seat_index
    
    FROM
         (
           select
               ROW_NUMBER() over(PARTITION BY departure_station,arrival_station) as seq ,
               passenger_id as p_id,
               departure_station as d_s,
               arrival_station as a_s
           from
           passenger
         ) as p_01
    
         LEFT JOIN
    
        (
          select
            seat_count,
            sum(seat_count)
              over (
                     PARTITION BY d_s,a_s
                     ORDER BY     if_no_seat,t_id
                   ) as p_seat_to ,
            t_id,
            d_s ,
            a_s ,
            if_no_seat
          from
          t_include_no_seat
        ) t_01
    
        ON
                p_01.seq >= p_seat_to-seat_count + 1
            and p_01.seq <= p_seat_to
            and p_01.d_s =  t_01.d_s
            and p_01.a_s =  t_01.a_s

    正确性验证

    这个 SQL 的正确性并不好验证。而事实上,只要能够正确的完成这条SQL,基本上就已经打败了80%的选手了。如果性能再有一些优化,基本上已经是前10%的选手。

    这里从以下几个方面对SQL正确性做初步验证:

    • 对于每一个系列(始发站和到达站相同)的车次进行统计,统计座位数量和旅客数量,然后看实际分配情况是否符合
    • 手动检车车厢、座位号分配的情况
    • 检查某个系列,无座和有座的乘客数量

    座位供需统计

    座位的供需情况有如下三种:(a) 座票供应充值 (b) 加上无座后供应充值 (c) 供应不足。完整的供需计算如下:

    
    case #1
    ti_supply |__________________________|___________|
    ti_needed |<------------------->|
    
    case #2
    ti_supply |__________________________|___________|
    ti_needed |<------------------------------>|
    
    case #3
    ti_supply |__________________________|___________|
    ti_needed |<-------------------------------------------->|
    
    -- ti_ always short for tickets
    -- p_  always short for passager
    -- t_  always short for train
    select
        p_needed.d_s,
        p_needed.a_s,
        ti_needed,
        ti_supply,
        if( ti_needed > ti_supply, ti_needed - ti_supply , 0 )  as p_without_ti,
        if( ti_needed > ti_supply/1.1 ,  round(ti_supply/1.1,0) , ti_needed ) as p_with_ti_with_seat,
        if( ti_needed <= ti_supply/1.1 ,   -- case #1
            0,
            if( ti_needed <= ti_supply,    -- case #2
                round(ti_needed - ti_supply/1.1,0) ,
                ti_supply/11               -- case #3
              )
          ) as p_with_ti_without_seat
    from
      (
        select
          -- passenger_id as p_id,
          departure_station as d_s,
          arrival_station as a_s,
          count(1) as ti_needed
        from
          passenger
        group by
          departure_station,arrival_station
      ) p_needed
      ,
      (
        select
          -- train_id t_id,
          departure_station as d_s ,
          arrival_station as a_s,
          1.1*sum(seat_count) as ti_supply
        from
          train
        group by
          departure_station,arrival_station
      ) t_supply
    WHERE
            p_needed.d_s = t_supply.d_s
        and p_needed.a_s = t_supply.a_s

    返回的供需表如下:

    +--------+--------+-----------+-----------+--------------+---------------------+------------------------+
    | d_s    | a_s    | ti_needed | ti_supply | p_without_ti | p_with_ti_with_seat | p_with_ti_without_seat |
    +--------+--------+-----------+-----------+--------------+---------------------+------------------------+
    | 上海   | 北京   |      2460 |    4180.0 |            0 |                2460 |                      0 |
    | 上海   | 广州   |      2406 |    5280.0 |            0 |                2406 |                      0 |
    | 上海   | 成都   |      2421 |    3520.0 |            0 |                2421 |                      0 |
    | 上海   | 武汉   |      2454 |    7700.0 |            0 |                2454 |                      0 |
    | 上海   | 深圳   |      2388 |    7040.0 |            0 |                2388 |                      0 |
    | 北京   | 上海   |      2381 |    1760.0 |        621.0 |                1600 |              160.00000 |
    | 北京   | 广州   |      2448 |    3520.0 |            0 |                2448 |                      0 |
    | 北京   | 成都   |      2384 |    3520.0 |            0 |                2384 |                      0 |
    | 北京   | 杭州   |      2478 |    3520.0 |            0 |                2478 |                      0 |
    | 北京   | 武汉   |      2404 |    5940.0 |            0 |                2404 |                      0 |
    | 北京   | 深圳   |      2342 |    3520.0 |            0 |                2342 |                      0 |
    | 广州   | 上海   |      2339 |    4180.0 |            0 |                2339 |                      0 |
    | 广州   | 北京   |      2368 |    1760.0 |        608.0 |                1600 |              160.00000 |
    | 广州   | 成都   |      2332 |    3520.0 |            0 |                2332 |                      0 |
    | 广州   | 杭州   |      2407 |    5280.0 |            0 |                2407 |                      0 |
    | 广州   | 武汉   |      2320 |    3520.0 |            0 |                2320 |                      0 |
    | 广州   | 深圳   |      2352 |    1760.0 |        592.0 |                1600 |              160.00000 |
    | 成都   | 上海   |      2422 |    4180.0 |            0 |                2422 |                      0 |
    | 成都   | 北京   |      2318 |    5940.0 |            0 |                2318 |                      0 |
    | 成都   | 广州   |      2450 |    1760.0 |        690.0 |                1600 |              160.00000 |
    | 成都   | 杭州   |      2343 |    5280.0 |            0 |                2343 |                      0 |
    | 成都   | 武汉   |      2415 |    5280.0 |            0 |                2415 |                      0 |
    | 成都   | 深圳   |      2364 |    2420.0 |            0 |                2200 |                    164 |
    | 杭州   | 北京   |      2389 |    1760.0 |        629.0 |                1600 |              160.00000 |
    | 杭州   | 成都   |      2370 |    1760.0 |        610.0 |                1600 |              160.00000 |
    | 杭州   | 深圳   |      2387 |   10560.0 |            0 |                2387 |                      0 |
    | 武汉   | 上海   |      2323 |    5280.0 |            0 |                2323 |                      0 |
    | 武汉   | 北京   |      2453 |    5280.0 |            0 |                2453 |                      0 |
    | 武汉   | 广州   |      2395 |   10560.0 |            0 |                2395 |                      0 |
    | 武汉   | 成都   |      2337 |    1760.0 |        577.0 |                1600 |              160.00000 |
    | 武汉   | 杭州   |      2428 |    3520.0 |            0 |                2428 |                      0 |
    | 武汉   | 深圳   |      2390 |    5280.0 |            0 |                2390 |                      0 |
    | 深圳   | 上海   |      2251 |    3520.0 |            0 |                2251 |                      0 |
    | 深圳   | 北京   |      2309 |    7040.0 |            0 |                2309 |                      0 |
    | 深圳   | 成都   |      2341 |    3520.0 |            0 |                2341 |                      0 |
    | 深圳   | 杭州   |      2412 |     660.0 |       1752.0 |                 600 |               60.00000 |
    | 深圳   | 武汉   |      2329 |   10120.0 |            0 |                2329 |                      0 |
    +--------+--------+-----------+-----------+--------------+---------------------+------------------------+

    SQL 计算返回结果统计

    先使用 CREATE TABLE t_ret ...将结果集存储一个中间的临时表。

    然后,再计算 SQL返回结果表中的统计数据:

    SELECT 
      d_s,a_s,
      CASE
        WHEN ISNULL(seat_index)  THEN "p_without_ti"
        WHEN seat_index = "无座"  THEN "p_with_ti_without_seat"
        ELSE "p_with_ti_with_seat"
      END as p_status,
      COUNT(1)
    FROM t_ret
    GROUP BY d_s,a_s , p_status

    返回:

    +--------+--------+------------------------+----------+
    | d_s    | a_s    | p_status               | COUNT(1) |
    +--------+--------+------------------------+----------+
    | 上海   | 北京   | p_with_ti_with_seat    |     2460 |
    | 上海   | 广州   | p_with_ti_with_seat    |     2406 |
    | 上海   | 成都   | p_with_ti_with_seat    |     2421 |
    | 上海   | 杭州   | p_without_ti           |     2373 |
    | 上海   | 武汉   | p_with_ti_with_seat    |     2454 |
    | 上海   | 深圳   | p_with_ti_with_seat    |     2388 |
    | 北京   | 上海   | p_with_ti_with_seat    |     1600 |
    | 北京   | 上海   | p_with_ti_without_seat |      160 |
    | 北京   | 上海   | p_without_ti           |      621 |
    | 北京   | 广州   | p_with_ti_with_seat    |     2448 |
    | 北京   | 成都   | p_with_ti_with_seat    |     2384 |
    | 北京   | 杭州   | p_with_ti_with_seat    |     2478 |
    | 北京   | 武汉   | p_with_ti_with_seat    |     2404 |
    | 北京   | 深圳   | p_with_ti_with_seat    |     2342 |
    | 广州   | 上海   | p_with_ti_with_seat    |     2339 |
    | 广州   | 北京   | p_with_ti_with_seat    |     1600 |
    | 广州   | 北京   | p_with_ti_without_seat |      160 |
    | 广州   | 北京   | p_without_ti           |      608 |
    | 广州   | 成都   | p_with_ti_with_seat    |     2332 |
    | 广州   | 杭州   | p_with_ti_with_seat    |     2407 |
    | 广州   | 武汉   | p_with_ti_with_seat    |     2320 |
    | 广州   | 深圳   | p_with_ti_with_seat    |     1600 |
    | 广州   | 深圳   | p_with_ti_without_seat |      160 |
    | 广州   | 深圳   | p_without_ti           |      592 |
    | 成都   | 上海   | p_with_ti_with_seat    |     2422 |
    | 成都   | 北京   | p_with_ti_with_seat    |     2318 |
    | 成都   | 广州   | p_with_ti_with_seat    |     1600 |
    | 成都   | 广州   | p_with_ti_without_seat |      160 |
    | 成都   | 广州   | p_without_ti           |      690 |
    | 成都   | 杭州   | p_with_ti_with_seat    |     2343 |
    | 成都   | 武汉   | p_with_ti_with_seat    |     2415 |
    | 成都   | 深圳   | p_with_ti_with_seat    |     2200 |
    | 成都   | 深圳   | p_with_ti_without_seat |      164 |
    | 杭州   | 上海   | p_without_ti           |     2376 |
    | 杭州   | 北京   | p_with_ti_with_seat    |     1600 |
    | 杭州   | 北京   | p_with_ti_without_seat |      160 |
    | 杭州   | 北京   | p_without_ti           |      629 |
    | 杭州   | 广州   | p_without_ti           |     2401 |
    | 杭州   | 成都   | p_with_ti_with_seat    |     1600 |
    | 杭州   | 成都   | p_with_ti_without_seat |      160 |
    | 杭州   | 成都   | p_without_ti           |      610 |
    | 杭州   | 武汉   | p_without_ti           |     2353 |
    | 杭州   | 深圳   | p_with_ti_with_seat    |     2387 |
    | 武汉   | 上海   | p_with_ti_with_seat    |     2323 |
    | 武汉   | 北京   | p_with_ti_with_seat    |     2453 |
    | 武汉   | 广州   | p_with_ti_with_seat    |     2395 |
    | 武汉   | 成都   | p_with_ti_with_seat    |     1600 |
    | 武汉   | 成都   | p_with_ti_without_seat |      160 |
    | 武汉   | 成都   | p_without_ti           |      577 |
    | 武汉   | 杭州   | p_with_ti_with_seat    |     2428 |
    | 武汉   | 深圳   | p_with_ti_with_seat    |     2390 |
    | 深圳   | 上海   | p_with_ti_with_seat    |     2251 |
    | 深圳   | 北京   | p_with_ti_with_seat    |     2309 |
    | 深圳   | 广州   | p_without_ti           |     2387 |
    | 深圳   | 成都   | p_with_ti_with_seat    |     2341 |
    | 深圳   | 杭州   | p_with_ti_with_seat    |      600 |
    | 深圳   | 杭州   | p_with_ti_without_seat |       60 |
    | 深圳   | 杭州   | p_without_ti           |     1752 |
    | 深圳   | 武汉   | p_with_ti_with_seat    |     2329 |
    +--------+--------+------------------------+----------+

    从上述的两个结果对比来看,挑选了几个来看,数据是一致的。比如,“深圳->杭州”,上面表格计算得

    | 深圳   | 杭州   |      2412 |     660.0 |       1752.0 |                 600 |               60.00000 |

    对比:

    | 深圳   | 杭州   | p_with_ti_with_seat    |      600 |
    | 深圳   | 杭州   | p_with_ti_without_seat |       60 |
    | 深圳   | 杭州   | p_without_ti           |     1752 |

    这里的 600、60、1752也是一致的。

    最后按照输出进行调整

    WITH
      t_no_seat_virtual AS (
        select
          train_id as t_id,
          departure_station as d_s,
          arrival_station as a_s,
          seat_count,
          seat_count*0.1 as seat_count_no_seat
        from train
      ),
      t_include_no_seat AS (
        select t_id,d_s ,a_s ,seat_count, 0 as if_no_seat
        from t_no_seat_virtual
        union
        select t_id,d_s ,a_s ,seat_count_no_seat, 1 as if_no_seat
        from t_no_seat_virtual
      )
    SELECT
      p_01.p_id,         -- output 01
      p_01.d_s,          -- output 02
      p_01.a_s,          -- output 03
      t_01.t_id as t_id, -- output 04
      IF(
          if_no_seat,
          "" ,
          ceil((p_01.seq-t_01.p_seat_to + t_01.seat_count)/100)
      ) as t_carr_id, -- output 05
    
      CASE IF( !isnull(t_01.t_id) and if_no_seat,-1,ceil((( p_01.seq-t_01.p_seat_to + t_01.seat_count )%100)%5))
        WHEN 1  THEN CONCAT( ceil((( p_01.seq-t_01.p_seat_to + t_01.seat_count )%100)/5) ,"A")
        WHEN 2  THEN CONCAT( ceil((( p_01.seq-t_01.p_seat_to + t_01.seat_count )%100)/5) ,"B")
        WHEN 3  THEN CONCAT( ceil((( p_01.seq-t_01.p_seat_to + t_01.seat_count )%100)/5) ,"C")
        WHEN 4  THEN CONCAT( ceil((( p_01.seq-t_01.p_seat_to + t_01.seat_count )%100)/5) ,"E")
        WHEN 0  THEN CONCAT( IF( (p_01.seq-t_01.p_seat_to + t_01.seat_count)%100 = 0, "20" ,ceil((( p_01.seq-t_01.p_seat_to + t_01.seat_count )%100)/5)) ,"F")
        WHEN -1 THEN "无座"
        ELSE NULL
      END as seat_index   -- output 06
    FROM
      (
        select
          ROW_NUMBER() over(PARTITION BY departure_station,arrival_station) as seq ,
          passenger_id as p_id,
          departure_station as d_s,
          arrival_station as a_s
        from
        passenger
      ) as p_01
    
      LEFT JOIN
    
      (
        select
          seat_count,
          sum(seat_count)
            over (
                   PARTITION BY d_s,a_s
                   ORDER BY     if_no_seat,t_id
                 ) as p_seat_to ,
          t_id,
          d_s ,
          a_s ,
          if_no_seat
        from
        t_include_no_seat
      ) t_01
    
      ON
            p_01.seq >= p_seat_to-seat_count + 1
        and p_01.seq <= p_seat_to
        and p_01.d_s =  t_01.d_s
        and p_01.a_s =  t_01.a_s
    ORDER BY p_01.p_id

    赛题与数据

    原始的比赛题目参考:https://www.ninedata.cloud/sql_train2024 这里仅讨论其中的“进阶挑战”。

    表定义(MySQL)

    CREATE DATABASE `game_ticket`;
    
    use game_ticket;
    
    CREATE TABLE `passenger` (
      `passenger_id` varchar(16) NOT NULL,
      `departure_station` varchar(32) NOT NULL,
      `arrival_station` varchar(32) NOT NULL,
      PRIMARY KEY (`passenger_id`)
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
    
    CREATE TABLE `train` (
      `train_id` varchar(8) NOT NULL,
      `departure_station` varchar(32) NOT NULL,
      `arrival_station` varchar(32) NOT NULL,
      `seat_count` int NOT NULL,
      PRIMARY KEY (`train_id`)
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

    赛题数据

    为了方便调试,这里保持了一份CSV的输入如下,供测试使用:

    相关阅读

  • 2024 数据库年度总结

    ·

    在上周五完成最后一个每周行业动态[49]之后,才发现距离春节只剩一个月了,2024也即将过去,要不就整体回顾一下这一整年所看到的数据库领域现状与变化吧。

    当红辣子鸡:向量数据库与AI

    AI(或者说LLM)所展现的能力,似乎还没有看到上限。而基于此的,面相各行业的应用,也在蓬勃发展。数据库和这个领域最大的结合点,就是向量存储与搜索了。在这一年里,几乎所有的主流数据库,都推出或增强了相关功能。Forrester 也率先发布了独立的 Vector Database Wave ,对各个数据库的向量处理能力做了评估。

    Forrester 的 Vector Database Wave

    在今年的Q3,Forrester 发布了独立的 Vector Database Wave,其中 Zilliz(对应开源产品名:milvus)凭借完整、高效的向量数据处理能力处于绝对领先的位置。后续厂商分别有:DataStax、Microsoft、Amazon、Oracle、Pinecone 等[30]

    现在,几乎所有的数据库或云厂商也都在投入“向量”技术,这类 AI 技术与应用也都在快速演进,向量存储与应用的竞争还远没有结束。

    各个数据库或云厂商发布的 Vector 功能

    再过去的2024年,各个数据库厂商都争相发布了自己在向量方向的支持。具体的:

    • 百度云发布了独立向量数据库产品: VectorDB[14]
    • TiDB 发布了 Vector Search (Beta),将向量能力与 TiDB 做了很好的融合[10]
    • pg_vector 发了最新的 0.8 版本,并且在大量的项目中被广泛使用[11]
    • Azure 发布自己的向量数据库扩展 DiskANN,并在多个数据库产品中使用[29]
    • MariaDB也在11.6版本开始全面支持向量特性[12]
    • OceanBase 4.3.3 版本发布,支持了向量数据存储与索引功能[31]
    • MySQL 9.0 也开始支持向量存储[13]
    • 此外,几乎所有云厂商的 PostgreSQL 产品都支持了 pg_vector 插件

    分布式数据库:数据库领域的“金色飞贼”

    在整个关系型数据库领域,分布式数据库的市场份额应该是比较有限的。但是,因为其解决的是一个非常困难的问题,而且是大型用户通常需要解决的问题,所以,“分布式数据库”在 RDBMS 领域一直都是一个关键的“组件”。

    在中国,主要的分布式数据库厂商有:OceanBase、TiDB、TDSQL、GoldenDB、PolarDB 等,这些产品在一些垂直场景各有优势。在今年07月,IDC发布了《中国金融行业分布式事务型数据库市场份额》报告[7],则很好的反应这个现状:

    • 腾讯 TDSQL 获得整体市场份额第一[9]
    • OceanBase则获得了金融行业本地部署市场份额第一[8]
    • 阿里云在公共云市场的分布式数据库部署,取得第一:参考
    • GoldenDB 获得银行本地化部署细分市场第一[33]

    从这些数据中,可以看到中国金融行业分布式数据库的情况[7]:整体市场空间约为 2.2 亿美元,同比增长12.1%,其中公共云占比约为30%,专有云占比为70%。

    由于 TiDB 更加坚定的开源、国际化策略,在这次数据中并没有看到 PingCAP 去太多的宣传。TiDB的重点则在Cloud、国际化、Vector Serach等方向。

    国产数据库与信创

    随着全球局势变得更加不确定,对抗思潮的不断推高,更加“自主可控”的基础技术已经变得越来越重要了。在今年的9月,“中国信息安全测评中心”发布了最新一批的安全可靠产品认证名录[36]。相比往期目录,经过认证的数据库数量是增加了,并且额外新增了分布式数据库目录。

    本次目录中的集中式数据库

    集中式数据库主要厂商有华为 GaussDB、金仓、神通、海量、瀚高、华为 TaurusDB。

    本次目录中的分布式数据库

    分布式数据库厂商很多,包括了 PingCAP TiDB、达梦、PolarDB、金仓、GBase、神通、虚谷、TDSQL、GaussDB、GoldenDB、OceanBase等。

    开源与商业

    在今年初,最为广泛使用的缓存数据库 Redis 改变了其原有的开源协议:将从Redis 7.4版本开始转而使用RSALv2+SSPLv1,不再使用BSD协议[25]

    很快,在Linux基金会下很快启动了Valkey项目,该项目同时获得了如Amazon、Google、Oracle等厂商的实际支持[26]。而今年,AWS也正式在自己的云平台上正式支持了Valkey[27],此外,阿里云PolarDB也发布了Redis协议接口支持(Orca)[28]

    此外,今年,CockroachDB 对开源协议做出了重大调整,对于使用开源的用户进一步做出限制。具体的,可以理解为对于小企业(年收入1000万美金,似乎也不是很小…)免费使用,年收入超过1000万美金的企业则需要付费[34]

    PostgreSQL在经历一场缓慢的崛起

    依旧,PostgreSQL在经历一场缓慢的崛起,MySQL则在原地踏步。在2022年的总结中,就曾给出了这个结论[50],而这个趋势似乎越来越明显。

    根据Stack Overflow在2024年的调研数据[51],PostgreSQL已经成为最受开发者欢迎的数据库。在海外,由于云厂商在不断增加对PostgreSQL的投入;在国内,由于国产数据库对于PostgreSQL的青睐。看到,PostgreSQL 崛起的趋势也越来越明显。

    虽然,在DB-Engines的排名中,MySQL依旧优势很大,但,过去的一年,MySQL在引入创新版后,发布8.1/2/3/4、9.0版本,但,MySQL最大的进步本身,大概就是版本迭代的模式变化,而这种变化给MySQL创新带来的效果还没有出现。在9.0版本中MySQL虽然发布了vector但功能还非常不完善,而 PostgreSQL 的 pg_vector 已经被广为使用了。

    在由 JetBrains 发布的 《State of Developer Ecosystem Report 2024[47],也可以看出类似的趋势。该数据显示:

    • 从2019到2024年,MySQL 的采用量从60%下降到52%
    • 从2019到2024年,PostgreSQL 的采用量从30%增长到45%

    数据库领域的融资事件

    受大环境的影响,除了AI或大模型相关技术除外,最近两年融资市场都非常冷清。但在过去的2024年,在数据库领域,依旧有非常多的亮眼的融资事件。

    达梦数据库上市:首日公开交易,发行价为86.96元/股,当日收盘价为240元(对应市值182亿),盘中最高报313元(参考);而到今年年底,达梦的股价一直 350~400 元上下波动,市值则高达250~300亿之间。

    PostgreSQL托管初创公司Tembo获$1400万美元A轮融资[1] ,该公司以开源产品的形式提供完整的PostgreSQL生态产品托管服务,同时提供Tembo Cloud以云产品形式提供托管服务。

    OpenAI 收购 实时分析数据库开发商Rockset[2],其估值约为5~10亿美金,以增强大模型在实时数据搜索与分析的能力。

    ClickHouse 收购 PostgreSQL 数据同步公式 PeerDB [3],具体收购金额并没有透露,但具报道,PeerDB在2023年曾完成了360万美元的种子轮融资[4]

    开源时序数据库 GreptimeDB宣布完成数百万美元的新一轮融资。GreptimeDB是一款Rust 语言编写的时序数据库,具有分布式,开源,云原生,兼容性强等特点,帮助企业实时读写、处理和分析时序数据的同时,降低长期存储的成本[5]

    K1 100%收购 MariaDB。K1是最大的小型企业软件投资公司,总部设在加州曼哈顿海滩。MariaDB 是一个独立的 MySQL 分支,由 MySQL 的创始人 Michael Widenius 发起并创建[15]

    Supabase 完成C轮8000万美元融资,该平台以PostgreSQL为中心,向开发者提供各类服务的平台,包括数据库、认证服务、存储、实时事件同步、向量数据库等 [24]

    ApertureDB 融资$8百万美元,致力于构建AI时代的多模数据流服务,帮助企业更加敏捷的构建上层的智能化的服务[31]

    Gartner 的数据库魔力象限

    在今年的12月,也就是前几天,Gartner 正式对外发布了 2024 数据库魔力象限[48]。今年,依旧由Google、AWS、Azure、Oracle领跑;MongoDB、DataBricks、Snowflake则又向左上角前进了一些。

    阿里云则依旧保持在领导者象限。华为云则在时隔两年后,再次进入该象限。

    分布式数据库厂商 SingleStore 进入,而 Yugabyte 跌出。

    云厂商们的重要发布

    AWS re:Invent 发布新的数据库产品 Aurora DSQL ,提供了跨区域、强一致、多区域读写的能力,同时具备99.999%(多区域部署)的可用性,兼容PostgreSQL;同时发布的还有 DynamoDB 也提供类似的跨区域强一致的能力[6]

    阿里云李飞飞发布由Data+AI驱动的多模数据管理平台DMS[22];RDS 产品则主打“降本增效”发布了自研倚天ARM版、集群版、新增了加速 IO 方案(BPE)等,PolarDB 则发布了 Redis 协议接口

    字节火山云 veDB MySQL 发布透明HTAP支持,当前处于邀测阶段。采用了MySQL plugin 架构方式,在内核侧自动分流AP 和 TP 请求,如需手动分流,可以使用Proxy[19]

    腾讯云开源了 TXSQL [17]; TDSQL 再创 TPC-DS 世界纪录,以7260万QphDS的性能和37.52元/kQphDS的性价比打破榜单纪录,性能提升282%,成本降低37% [32]

    在 Oracle CloudWorld 上,Larry发表主题演讲《Open MultiCloud Era & AI + Cloud Security》,坚定的走多云、私有云战略,发布了Oracle@Google、Oracle@Azure、Oracle@AWS等方案 [16] 

    GCP的主要发力方向为 AlloyDB;同时也在增强其基础产品的能力,例如 Cloud SQL for SQL Server 现提供两种版本 Enterprise Plus 和 Enterprise。

    微软云 Azure 的重点依旧是 Cosmos DB 和 SQL Database。在向量数据库上,Azure多款数据库发布DiskANN向量索引[42]

    华为云数据库持续在垂直行业、学术、高校等生态上继续投入。基于 openGauss 的项目获得中国通信学会科学技术奖(科技进步类一等奖)[45]。在今年的11月份,华为云将原 GaussDB for MySQL 再次更名为 TaurusDB[52]

    OceanBase开发者大会发布 4.3 发版,高调进入实时分析 AP 领域,同时将支持行存 & 列存一体化、新向量化引擎、物化视图等能力,同时宣布了OB Cloud将作为独立的数据库厂商,登陆阿里云精选市场 [23] 

    相比其他数据库,PingCAP 投入了更多资源到 AI (LLM 或者 GenAI,不管叫什么吧)方向上去进行探索,除了支持初步的向量存储之外,TiDB 还可以使用 AutoFlow 和 LlamaIndex 开始的构建一个基于知识库的聊天助手。虽然这个功能与一般意义的“数据库”不那么相关,但是也能看到TiDB的执行力和投入之坚决[35]

    其他

    腾讯云 TDSQL 再创 TPC-DS 世界纪录

    腾讯云 TDSQL 再创 TPC-DS 世界纪录,以7260万QphDS的性能和37.52元/kQphDS的性价比打破世界纪录,性能提升282%,成本降低37%。通过自研MPP和并行执行框架,TDSQL显著提升资源利用率和计算效率,广泛应用于30多家金融机构 [32]

    WeSQL-基于S3的MySQL数据库

    这算是一个非常酷的探索。正如 ApeCloud 创始人曹伟所说,“数据库可以做的方向不多”,ApeCloud 在发布了开源数据库的云原生管控平台之后,与今年的11月又开源了一个有意思的产品:WeSQL,基于S3的MySQL数据库。WeSQL 目前属于探索阶段,如果数据存储量很大的测试环境,可以考虑该方案降低存储成本[37]

    AI与数据库的其他结合

    此外,其他方向诸如,Text2SQL、数据库优化等方向,也有一些厂商在做更多的探索,例如,AWS Redshift 正式支持(GA)自然语言生成SQL功能,该功能由 Amazon Q 实现,可以再Redshift Query Editor中使用该功能 [21] ,Copilot for Azure新增了对Azure SQL、 Azure Database for MySQL的支持等。

    图数据库

    图数据库是大模型生态的一部分,在过去的一年,各个图数据库厂商也借势迅速发展。

    Neo4j 宣布其年度经常性收入(ARR)已超过2亿美元,并在过去三年中实现了ARR翻番。Neo4j 在快速扩张的图技术市场中的领导地位,以及最近几年图技术对于提升生成式AI(GenAI)结果的准确性、透明性和可解释性至关重要作用,是增长的核心因素[38]

    在今年,ISO 颁布了新的 ISO/IEC GQL(图查询语言)标准[40],作为图数据库领域的“SQL”,填补了现有标准在处理图数据时的不足。NebulaGraph 则是首个支持该标准的分布式数据库图数据库[39]

    学术会议与奖项

    今年,在主要的数据库学术会议中,国内的厂商也有很多亮眼的表现。包括:

    • PolarDB 获得 SIGMOD Industry Track Best Paper 《PolarDB-MP: A Multi-Primary Cloud-Native Database via Disaggregated Shared Memory》[43]
    • 阿里云 PolarDB 获2024年度中国计算机学会(CCF)科技进步一等奖 [41] 
    • KaiwuDB 在国际权威数据库性能测试 benchANT 获得时序数据库场景第一名[46]
    • 基于 openGauss 的项目《面向大型企业规模应用的开源数据库》获得中国通信学会科学技术奖(科技进步类一等奖)[45]
    • 腾讯云 TDSQL 获得深圳市科技进步一等奖[44]
    • 此外,在今年,主要的大数据库厂商在 VLDB/ICDE/SIGMOD等学术会议上均由论文发布。

    关于

    关于作者

    关于作者:周振兴,NineData 联合创始人 & 技术副总裁 ;Oracle ACE ;《高性能MySQL 第三、四版》译者;曾任阿里云数据库资深技术专家

    参考链接

  • 本周 Gartner 正式对外发布了 2024 年的数据库魔力象限[1],对今年全球范围内大型数据库厂商做了一个整体的“盘点”,是的,在这个象限中几乎都是“大型”的数据库厂商。

    整体上,依旧有Google、AWS、Azure、Oracle领跑;MongoDB、DataBricks、Snowflake则又向左上角前进了一些;阿里云则依旧保持在领导者象限。华为云则在时隔两年后,再次进入该象限。

    分布式数据库厂商 SingleStore 进入,而 Yugabyte 跌出。

    领跑组:Google 高歌猛进

    Google 是 AI 与云计算领域的领导者,在数据库产品上不断增强与 AI 产品的链接;其他方向上,则加强其 AlloyDB (或其 Omni版本)、BigQuery、Spanner、Cloud SQL等功能。凭借着 AI 与 大数据技术的持续领先,Google 依旧是最领先技术的弄潮儿。

    Amazon 在数据库方向上的核心产品是托管数据库、Aurora 和 DynamoDB 。并且,在今年,Aurora 发布了 DSQL 版本,跨区域强一致的全球数据库,DynamoDB 也发布了类似的能力;托管数据库则不断紧跟社区,并开始以更高性价比的形式支持了最新一代的Graviton 芯片。

    微软在过去的数年,云计算成功的赶上了第一梯度,在 AI 浪潮中,微软凭借快速高效的与OpenAI进行合作并持续创新,再次站在潮头。在数据库方向,在云端微软一方面持续发展SQL Database、Cosmos DB。在本地则发布了SQL Server 2025版本。今年11月,看到 Azure 托管数据库发布支持了 PostgreSQL 17,追赶了这么年,可以认为 Azure 的数据库基础设施最终赶上了其他头部云厂商[3]

    Oracle 则在不断践行多云和 AI 战略,发布了Oracle@Google、Oracle@Azure、Oracle@AWS等系列合作产品。在 MySQL 方向上,依旧的,在不断的增强 HeatWave 能力,包括分析能力和 AI 功能[4]

    中国数据库厂商:阿里云和华为云

    在去年,中国数据库厂商,仅有阿里云数据库在孤军奋战[5] ,今年华为云再次进入该象限(注:2020/2021年曾进入),可见,华为在被美国限制的情况下,依旧在尝试在全球市场寻求更大的突破。阿里云相比于去年的位置,没有发生太大的变化,依旧是处于领导者象限。华为云,则相比于 2020、2021 年的所处的niche players象限进步很大,跃入了挑战者象限。

    而在魔力象限之外,依旧有不少数据库厂商在奋力征战全球市场。分布式数据库 TiDB 从市场宣传、产品投入可以看到,全球市场市场是其重点方向。向量数据库 Zilliz / Milvus,则已经站在了全球向量数据库的领导者的位置。此外,还有 NebularGraph 、Databend、KubeBlocks等。

    独立厂商与平台厂商

    在全球云计算快速侵蚀传统数据中心的大背景下,独立数据库厂商则在尝试寻找独立的、垂直的价值空间。其中一个非常重要的战略是,各个独立厂商都发布了各自的云服务平台,包括TiDB Cloud、Neo4j Aura、Redis Cloud、MongoDB Atlas等。

    关于 Gartner 魔力象限

    曾经在阿里云工作时,多次参加过 Gartner 数据库魔力象限的项目。Gartner 项目团队会从多个角度对数据库厂商进行评估,主要包括营收规模、多维度的产品能力、产品规划等方面,在评价体系中,Gartner 还会邀请厂商的客户对该厂商的产品进行评价。除此,厂商和 Gartner 项目组可以就自己关心的问题进行询问。最终,Gartner 会根据上述信息形成一个综合的评估,并将多个数据库厂商的评估结果汇总成一个整体的报告,也就是通常大家看到的,Magic Quadrant。

    在 Gartner 的 “Cloud Database” 定义是比较广泛的,不仅仅包含RDBMS,也包括各类NoSQL,此外,还包括了各个厂商的分析类产品。在计算营收时,通常云计算厂商会将数据库或大数据库类目的营收数据合并上报,所以规模通常都比较大。而且,云厂商的数据库营收,通常都是硬件(IaaS)营收为主,辅以部分授权收入,这也是云厂商收入规模很大的原因。相比之下,独立的数据库厂商,通常只能计算数据库售卖的授权费用,所以,在营收规模的维度,独立数据库厂商是难以与云厂商抗衡的。所以,第一梯队,甚至第一象限,几乎都是云厂商。

    另一面

    Gartner 更像是一个数据库的“神仙打架”榜单,Gartner的魔力象限有着非常高的准入门槛。入选 Gartner 最为重要的应该就是营收,有了营收,才有后面的所有,才有资源去做产品能力评估、规划汇报或者客户评价等。对于头部厂商来说,所有的资源都是充足了,厂商之间会在其他维度(诸如产品能力、客户评价等)去竞争,从而获得更好的象限位置,以便后续宣传。但,这对小的、创新厂商是不友好的。所有,对于没有进入的厂商,并不是这些厂商不优秀,也不是这些厂商不创新,而只是时候未到。

    过去十年对比参考

    参考链接

  • Mini-batch Gradient Descent的主要想法

    在前面的实践中,使用“Gradient Descent”时,都是一次性把所有的数据集都考虑进去,一切似乎都没有什么问题。

    但是,在现实实践中,如果训练数据量非常大,这种方式就不适用了。试想,在前面的示例中,输入样本数据,即\( X \)(或者 \( A^{[0]}\)),其维度(或者说shape)则可能是\( 300 \times 10,000,000 \)。这会导致每一次的梯度计算量都非常大,一次迭代(epoch)的时间会很长。

    一种非常常见的、也是非常经典的梯度下降改进,就是 mini-batch gradient descent。首先,将样本分层若干小份,并单独对每个“小份”进行“Gradient Descent”,最后逐步完成所有样本的训练。完成一次所有样本的遍历,称之为一次迭代epoch

    在神经网络的训练中,可以用下面步骤理解这个过程:

    for "a-small-batch-of-samples X^{t} " in "all-samples"
        forward  propagation on X^{t}
        backward propagation on X^{t}
        update W/b
            W^{[l]} = W^{[l]} - lr * dW^{[l]}
            b^{[l]} = b^{[l]} - lr * db^{[l]}

    相对于 mini-batch gradient descent ,前面介绍的一次把所有样本都用于训练的方法,也被称为“batch gradient descent”。

    Stochastic Gradient Descent

    在 mini-batch 中,如果每次批量的样本大小是 1 的话,那么,也称为Stochastic Gradient Descent(简称 SGD,随机梯度下降)。事实上,自开始使用 Backpropagation 算法以来,SGD就被用于提升神经网络的训练的效率。并且很快的,mini-batch gradient descent 就作为一种优化被使用。目前,mini-batch gradient descent 依旧是一种常用神经网络训练方法[1][2]

    收敛稳定性预估

    不难想象,在“batch gradient descent”中,一次性把所有数据都用于梯度下降的算法,通常都能够获得更好的收敛速度。而在使用 mini-batch 的时候,由于不同的批次的样本在计算时,“计算梯度”都与“全局梯度”有一定的偏差,并且有时候偏差较大,有时候较小,所以,相比之下,收敛速度要慢一些。而,Stochastic Gradient Descent 则可能会更慢一些。

    可以这么理解, mini-batch 和 Stochastic Gradient Descent 都总是使用一个局部的梯度(部分样本的梯度)来预估整体的梯度方向,自然效果会差一些。

    这里我们改进了原来的神经网络实现 ssnn_bear.py,将其更新为使用 mini-batch 的 ssnn_cat.py。详细代码可以参考GitHub仓库:super simple neural network

    运行 ssnn_cat.py 并观察 mini-batch 的 cost 下降速度如下:

    mini-batch 迭代下cost总是在上下波动

    batch gd算法下cost下降非常稳定

    batch_size 大小的配置

    一些经验数值可能是64、128、256、512等。Mini-batch 需要在大数据量和向量化计算之间取得一个平衡,所以通常需要更具训练的设备选择合适的 batch 大小,使得每次迭代都充分利用硬件的资源。

    代码实现

    在前述的神经网络上(参考),再做了一些修改,实现了 Mini-Batch 或者随机梯度下降。

    新增 batch 大小参数

    首先,新增了 batch_size 参数表示,同时增加对应参数 batch_iteration 表示,在一次样本迭代中,总计需要循环多少次。所以,这两个参数有如下关系:

    batch_iteration = math.ceil(m/batch_size)
    对每批次样本做迭代
    batch_iteration = math.ceil(m/batch_size)
    ...
    for i in range(iteration_count):
        for i_batch in range(batch_iteration):
            ...
            # sample from i_batch*batch_size
            batch_from  = i_batch*batch_size
            batch_to    = min((i_batch+1)*batch_size,m)
            batch_count = batch_to - batch_from
            A0  = X[:,batch_from:batch_to] # column  [batch_from,batch_to)
            Y_L = Y[:,batch_from:batch_to] # Y_label [batch_from,batch_to)
            ...

    代码的其他地方,几乎不需要太大的改动。完整的代码参考:ssnn_cat.py

    参考

    • [1] Stochastic gradient descent
    • [2] https://github.com/orczhou/ssnn/blob/main/ssnn_cat.py
    • [3] https://github.com/orczhou/ssnn/blob/main/ssnn_bear.py
    • [4] https://github.com/orczhou/ssnn

    这是一个系列文章包含了,完整的文章还包括:

  • This content is password protected. To view it please enter your password below:

  • 对话式的大语言模型产品已经在改变我的很多日常习惯。鉴于 ChatGTP 国内访问非常不方便,现在也逐渐的在尝试使用通义千问、文心一言等产品。总体上感觉,通义千问和文心一言也都非常不错了,满足基本的日常使用是完全没有问题的,但相比于 ChatGPT 还是差了那么一点意思。这里记录一些日常使用的对比,看看,所谓的那么“一点意思”到底是什么。

    简要的问题和简要的回答

    这里的问题是:“方括号 英语”。来看看 ChatGPT、通义千问、文心一言的回答:

    ChatGPT

    通义千问

    文心一言

    可以看到,三个引擎都给出准确的答案。其中,ChatGPT 给出的回答最为简洁,也是这里我最为偏好的回答。

    为什么这里给出简单的回答更好呢?

    这里的问题非常简单,这时候,通常也是期望更为简单的回答的。试想这样的场景,你在写一篇英语小短文,但你不确定“方括号”的英语怎么说,恰好你旁边有一个英语很好的同事,你问她:“方括号的英语是?”。如果她像上述通义千问、文心一样,说了一大堆,你可能会打断她,因为当下写材料才是重点,不是想学英语。如果,我真的想学英语的话,我的问题,则可能是这样:“方括号 英语 并给出示例”。

    一般的,简单的问题简单回答就可以了。如果用户期待更多信息或者更详尽的回复,通常也会更详细的描述问题。

    再比如:“Latex表示一个矩阵(方括号): 变量用x表示,共n_x行,m列。其中行号用下标表示,列用带有括号的上标表示”

    ChatGPT

    通义千问

    文心一言

    同样的,ChatGPT 更简洁,通义千问次之,文心一言则略显啰嗦。毕竟,这时候我只是想要答案,不想知道获得这个结果的完整的推理过程。

    类似的,再比如:

    ChatGPT

    通义千问

    文心一言

    “分总/总分总”与“递进式”的结构

    我们来看看如下问题,不同的大模型的回答:使用中文介绍一下“Goldsmiths Research Online”

    ChatGPT

    通义千问

    文心一言

    可以看一下这个三个回答的对比,通义千问和文心一言,都使用了“总分总”或“分总”的结构去回答问题。而,ChatGPT则使用了递进式的结构,显得更加自然。

    同时,因为通义千问和文心一言总是倾向于使用“总分总”或“分总”类似的结构,所以就就会给人比较呆板一些的感受。

    前端展示效果

    因为最近在学习机器学习的一些原理,所以,有时候会让 ChatGPT 帮助编写一些数学公式。这里的问题是:x是一个3×4的矩阵,每个元素分别是1…12,使用latex写出这个矩阵。

    ChatGPT

    通义千问

    文心一言

    可以看到,ChatGPT 在前端应该使用了类似Latex的前端组件,有更好的展示效果。而通义千问、文心一言则没有使用类似组件去展示。根据测试,通义千问、文心一言也都是支持 Latex 的前端展示,只是不会经常使用。

    最后

    总体感觉,在日常使用中,通义千问、文心一言和 ChatGPT 差别并不是很明显,早期通过各种方式去科学访问 ChatGPT 现在看起来必要性并没有那么高了。但,在一些细节点上,还存在一些差距,期待通义千问、文心一言都后续的版本能够变得更强。