ReaderMX.
云数据库技术

SQL编程大师-柳胜勋：算法与逻辑解析，如何在 1.201 秒内用 Doris 完成百万车票复杂分配

云柳胜勋约 5 分钟

Image

数据库编程大赛：只用一条 SQL 秒杀 100 万张火车票

2024 第二届数据库编程大赛于 12 月 5 日正式开启初赛！由 NineData 和云数据库技术社区主办，华为云、Doris等协办单位和媒体共同举办。比赛要求选手设计一套SQL算法，只用一条 SQL 秒杀 100 万张火车票，让乘客都都能顺利坐上火车回家过年。查看赛题详情

以下是本次决赛第2名，SQL编程大师柳胜勋的参赛介绍：

Image
参赛选手：柳胜勋
个人简介：PingCAP/TiDB研发工程师
参赛数据库：Doris
性能评测：百万级数据代码性能评测 1.201 秒 
综合得分：88.25
以下是柳胜勋选手的代码说明思路简介：

1. 因为有10%的站票，而且必须买完所有坐票才能买站票，所以我们需要把座位票和无座票分开来卖。即把一列车变成成两列车卖，一列是有座的票，二列是10%的无座票。

2. 先处理有座的车，根据路径分组，车号排序。计算出每列车的起始编号。按照 200个座位一页拆分。比如800座的火车，拆分成4个页，也就是变成4条记录，以此类推。

3. 拆分后，使用窗口函数进行编号座位页号，根据路径分组，车号排序。因为每页的大小都是一样的。所以 路径+页号 是唯一的。

4. 同时，我们使用函数窗口，计算出同一条线路上的乘客编号。

5. 因为有页号，所以可以乘客编号可以对 200 取模，使用JOIN快速映射到记录。

6. 通过这次JOIN后，有座的票就分好了。同时可以根据编号减去列车的起始编号，获得列车上的座位序号，然后除法和取余计算出座位号。

7. 将上一步的结果筛选出未分配列车的乘客，和上面一样的方式，只是按照20一页来取模计算页号。因为无座，所以不需要算车厢号，座位号直接标记无座即可。

8. 将结果和之前有座乘客UNION ALL 一下，然后做最终排序就是结果。
以下是柳胜勋选手的详细算法说明，结尾附完整SQL：

1.首先生成列车的车票信息。借用自增数列t_sequence，通过与train连接，生成车厢号、座位号。另外，生成10%的无座车票。为便于对车票排序，额外生成是否有座说明列。

2.以出发站和到达站点对高铁车次分组，并按照是否有座对可售车票进行顺序编号，有座车票编号在前，无座车票编号在后。

3.乘客按照出发站和到达站点进行顺序编号。

4.车票和乘客顺序编号之后，根据出发站、到达站点、顺序编号对可售座票与乘客进行外连接，即完成车票分配。

性能优化考虑：

  • 由于是全量数据连接操作，表字段个数少，且表连接操作都是在中间结果集之后进行的，创建索引没有多大意义，故无需额外创建索引。
  • 若机器性能较好，可考虑添加并行hint，使用并行查询技术。

  • 可在排序内存和hash连接内存分配上多给一些，消除在磁盘上的排序。

以下是柳胜勋选手的详细算法说明，结尾附完整SQL：
Image
Image
Image
Image

Image

参赛完整SQL：
With T AS (  WITH extension AS (    SELECT      600 AS size    UNION ALL    SELECT      600    UNION ALL    SELECT      600    UNION ALL    SELECT      800    UNION ALL    SELECT      800    UNION ALL    SELECT      800    UNION ALL    SELECT      800    UNION ALL    SELECT      1200    UNION ALL    SELECT      1200    UNION ALL    SELECT      1200    UNION ALL    SELECT      1200    UNION ALL    SELECT      1200    UNION ALL    SELECT      1200    UNION ALL    SELECT      1600    UNION ALL    SELECT      1600    UNION ALL    SELECT      1600    UNION ALL    SELECT      1600    UNION ALL    SELECT      1600    UNION ALL    SELECT      1600    UNION ALL    SELECT      1600    UNION ALL    SELECT      1600  ),  t1 AS(    SELECT      train_id,      departure_station,      arrival_station,      seat_count,      SUM(seat_count) OVER(        PARTITION BY departure_station,        arrival_station        ORDER BY          train_id      ) AS seat_cumsum    FROM      train  )  SELECT    departure_station,    arrival_station,    train_id,    seat_cumsum - seat_count + 1 AS seat_start,    ROW_NUMBER() OVER (      PARTITION BY departure_station,      arrival_station      ORDER BY        t1.train_id    ) AS page_id,    "无座" AS seat_number  FROM    t1    LEFT JOIN extension E ON E.size = t1.seat_count),S AS (  WITH seatNumbers AS (    SELECT      ROW_NUMBER() OVER () AS seat_number    from      passenger    limit      100  )  SELECT    seat_number,    CONCAT(      FLOOR((seat_number -1) / 5) + 1,      SUBSTRING('ABCEF', (seat_number - 1) % 5 + 1, 1)    ) AS seat_label  FROM    seatNumbers),P AS (  SELECT    ROW_NUMBER() OVER (      PARTITION BY departure_station,      arrival_station      ORDER BY        passenger_id    ) AS seat_id,    passenger_id,    departure_station,    arrival_station  FROM    passenger),A1T AS(  SELECT    P.passenger_id,    P.departure_station,    P.arrival_station,    T.train_id AS train_id,    P.seat_id - T.seat_start AS train_seat_id  FROM    P    LEFT JOIN T ON P.departure_station = T.departure_station    AND P.arrival_station = T.arrival_station    AND T.page_id = FLOOR((P.seat_id - 1) / 200) + 1),P2R AS(  SELECT    passenger_id,    departure_station,    arrival_station  FROM    A1T  WHERE    train_id IS NULL),P2M AS(  SELECT    ROW_NUMBER() OVER (      PARTITION BY departure_station,      arrival_station      ORDER BY        passenger_id    ) AS seat_id,    passenger_id,    departure_station,    arrival_station  FROM    P2R),AF AS(  SELECT    passenger_id,    departure_station,    arrival_station,    train_id,    FLOOR(train_seat_id / 100) + 1 AS coach_number,    S.seat_label AS seat_number  FROM    A1T    LEFT JOIN S ON seat_number = train_seat_id % 100 + 1  WHERE    train_id IS NOT NULL  ORDER BY    passenger_id  UNION ALL  SELECT    P2M.passenger_id,    P2M.departure_station,    P2M.arrival_station,    T.train_id AS train_id,    NULL AS coach_number,    seat_number  FROM    P2M    LEFT JOIN T ON P2M.departure_station = T.departure_station    AND P2M.arrival_station = T.arrival_station    AND T.page_id = FLOOR((P2M.seat_id - 1) / 20) + 1)
SELECT  passenger_id,  departure_station,  arrival_station,  train_id,  coach_number,  seat_numberFROM  AFORDER BY  passenger_id;

感谢大家对本次《数据库编程大赛》的关注和支持，欢迎加入技术交流群，更多精彩活动不断，欢迎各路数据库爱好者来挑战！

Image

KEEP THE THREAD GOING

更多来源文章