NineData第2届数据库编程大赛：一条SQL秒杀100万张火车票

Naldonado · 发表于 2024-12-22 21:36

有一种，把train表跟pa表一起unionall的齿轮法

newkid · 发表于 2024-12-23 01:05

Naldonado 发表于 2024-12-22 21:36
有一种，把train表跟pa表一起unionall的齿轮法

那是不是得用分析函数来取代连接？我感觉效率太低了，分析函数里面只能排序，不能HASH

我自己想的新方法是可以把切片变回200,这样HASH表就小了十倍，但是性能上没有任何提升，一半时间都花在解析座位号上面了，所以没啥意义。

Naldonado · 发表于 2024-12-23 09:20

newkid 发表于 2024-12-23 01:05
那是不是得用分析函数来取代连接？我感觉效率太低了，分析函数里面只能排序，不能HASH我自己想的新方法是可 ...

也肯能跟扩展的倍数有关，train表的票数再多一些，车次再多一些，反而又有效果了。不过我觉得如果所有的都是刚刚好，100反而是不是**的分组？直接01A-20F，所有判断都省去了。

〇〇 · 发表于 2024-12-23 13:42

union 改写left join，效率和newkid方法1差不多

with p as (
select
passenger_id,
departure_station,
arrival_station,
row_number() over (
partition by
departure_station,
arrival_station order by passenger_id
) sid
from
passenger
),
t0 as (
select
train_id,
departure_station,
arrival_station,
seat_count,
sum(seat_count) over (
partition by
departure_station,
arrival_station
order by
train_id
) sum_sid,
sum(seat_count) over (
partition by
departure_station,
arrival_station
) sum_d_a
from
train
),
t as(
select
train_id,
departure_station,
arrival_station,
sum_sid,
sum_sid-seat_count+1 start_sid,
sum_d_a+(sum_sid-seat_count) // 10 +1 start_stand_id,
sum_d_a+ sum_sid // 10 end_stand_id,
sum_d_a+sum_d_a//10 sum_seat_number
from
t0
)
select
passenger_id,
p.departure_station,
p.arrival_station,
train_id,
(sid-start_sid) // 100 +1 coach_number ,
concat(cast((sid-1)%100 // 5 +1 as varchar), substr('ABCEF',(sid-1)%5+1,1)) seat_number
from
p
join t on p.departure_station=t.departure_station and p.arrival_station=t.arrival_station and
p.sid between start_sid and sum_sid
union all
select
passenger_id,
p.departure_station,
p.arrival_station,
train_id,
null coach_number ,
'无座' seat_number
from
p
join t on p.departure_station=t.departure_station and p.arrival_station=t.arrival_station and
p.sid between start_stand_id and end_stand_id
union all
select
passenger_id,
p.departure_station,
p.arrival_station,
NULL train_id, NULL coach_number,NULL seat_number
from
p
join (select
departure_station,
arrival_station,
sum_seat_number
from t
group by departure_station,
arrival_station, sum_seat_number)t on p.departure_station=t.departure_station and p.arrival_station=t.arrival_station and
p.sid >sum_seat_number
order by passenger_id;
-- select count(*),substr(seat_number,-1,1) from r group by substr(seat_number,-1,1) order by 2;

复制代码

newkid · 发表于 2024-12-24 01:22

Naldonado 发表于 2024-12-23 09:20
也肯能跟扩展的倍数有关，train表的票数再多一些，车次再多一些，反而又有效果了。不过我觉得如果所有的都 ...

用100个座位（一节车厢）作为分片，无座票先按20个座位切片，然后每5条合并成一个记录：

with p as (
select passenger.*
      ,row_number() over(partition by departure_station,arrival_station order by passenger_id) rn ---- 为每组起终点的乘客编一个序号
   from passenger)
,tr as (
select departure_station,arrival_station,flag
      ,max(train_id) as train_id
      ,listagg(rpad(train_id,10)) within group(order by s2) as str
      ,case when flag=0 then s2 else ceil(s2/100)*100 end AS S2
      ,max(coach_number) as coach_number
   from (select train_id,departure_station,arrival_station,flag
               ,sum(case when flag=0 then 100 else 20 end) over(partition by departure_station,arrival_station order by flag,train_id,coach_number) as s2
               ,seat_count
               ,coach_number
         from train t
               ,(select 0 flag from dual union all select 1 from dual) ---和两条记录的小集合做笛卡尔积，生成额外的车次记录
               ,lateral(select level coach_number from dual connect by level<=case when flag=0 then seat_count/100 else trunc(seat_count*0.1/20) end)
         ) tr1
   group by departure_station,arrival_station,flag,case when flag=0 then s2 else ceil(s2/100)*100 end
)
select p.passenger_id,p.departure_station,p.arrival_station
   ,case when tr.flag=0 then tr.train_id else trim(substr(tr.str, (ceil((p.rn-tr.s2+100)/20)-1)*10+1,10)) end as train_id
   ,case when tr.flag=0 then tr.coach_number end as coach_number
   ,case when tr.flag=0 then
         trim(substr('1A 1B 1C 1E 1F 2A 2B 2C 2E 2F 3A 3B 3C 3E 3F 4A 4B 4C 4E 4F 5A 5B 5C 5E 5F 6A 6B 6C 6E 6F 7A 7B 7C 7E 7F 8A 8B 8C 8E 8F 9A 9B 9C 9E 9F 10A10B10C10E10F11A11B11C11E11F12A12B12C12E12F13A13B13C13E13F14A14B14C14E14F15A15B15C15E15F16A16B16C16E16F17A17B17C17E17F18A18B18C18E18F19A19B19C19E19F20A20B20C20E20F'
                     ,mod(p.rn-1,100)*3+1,3))
         when tr.flag=1 then ' no seat'
   end as seat_number
  from p left join tr on p.departure_station =tr.departure_station and p.arrival_station =tr.arrival_station
   and ceil(p.rn/100) = tr.s2/100
   ;

测试结果：仍然使用了同样的时间，现在车厢号不用算了，座位号也有所简化，如果不算座位号，差不多可以省下一半时间。目前这个座位号需要做取模乘法加法然后SUBSTR的操作。还有什么招？

HASH表只要内存放得下，其大小并不会影响整体执行时间，因为时间主要花在扫描探测表（即乘客表）。

〇〇 · 发表于 2024-12-24 08:19

100个座位的版本在duckdb不错，如果在doris也快，可以领茅台了
不排序 Run Time (s): real 2.324 user 16.016000 sys 0.708000
排序 Run Time (s): real 4.576 user 28.852000 sys 2.036000

〇〇 · 发表于 2024-12-24 18:13

数组版本最高能达到排序后6秒左右

newkid · 发表于 2024-12-31 05:18

用标量子查询来算座位号，因为可以利用缓存，1000万乘客能提高20秒左右：
with p as (
select passenger.*
      ,row_number() over(partition by departure_station,arrival_station order by passenger_id) rn ---- 为每组起终点的乘客编一个序号
      ,mod(row_number() over(partition by departure_station,arrival_station order by passenger_id)-1,100) as m ---- 车厢内序号，这个值是高度重复的所以可以利用标量子查询的缓存
   from passenger)
,tr as (
select departure_station,arrival_station,flag
      -- ,case when flag=0 then s2 else ceil(s2/100)*100 end/100 as chunk_id
      ,max(train_id) as train_id
      ,listagg(rpad(train_id,10)) within group(order by s2) as str
      ,case when flag=0 then s2 else ceil(s2/100)*100 end AS S2
      ,case when flag=0 then s2 else ceil(s2/100)*100 end-100 AS S1
      ,max(coach_number) as coach_number
   from (select train_id,departure_station,arrival_station,flag
               ,sum(case when flag=0 then 100 else 20 end) over(partition by departure_station,arrival_station order by flag,train_id,coach_number) as s2
               ,seat_count
               ,coach_number
         from train t
               ,(select 0 flag from dual union all select 1 from dual) ---和两条记录的小集合做笛卡尔积，生成额外的车次记录
               ,lateral(select level coach_number from dual connect by level<=case when flag=0 then seat_count/100 else trunc(seat_count*0.1/20) end)
         ) tr1
   group by departure_station,arrival_station,flag,case when flag=0 then s2 else ceil(s2/100)*100 end
)
select p.passenger_id,p.departure_station,p.arrival_station
   ,case when tr.flag=0 then tr.train_id else trim(substr(tr.str, (ceil((p.rn-tr.s1)/20)-1)*10+1,10)) end as train_id
   ,case when tr.flag=0 then tr.coach_number end as coach_number
   ,case when tr.flag=0 then ---------- 利用标量子查询计算座位号
               (select trim(substr('1A 1B 1C 1E 1F 2A 2B 2C 2E 2F 3A 3B 3C 3E 3F 4A 4B 4C 4E 4F 5A 5B 5C 5E 5F 6A 6B 6C 6E 6F 7A 7B 7C 7E 7F 8A 8B 8C 8E 8F 9A 9B 9C 9E 9F 10A10B10C10E10F11A11B11C11E11F12A12B12C12E12F13A13B13C13E13F14A14B14C14E14F15A15B15C15E15F16A16B16C16E16F17A17B17C17E17F18A18B18C18E18F19A19B19C19E19F20A20B20C20E20F'
                     ,p.m*3+1,3)) from dual
               )
         when tr.flag=1 then ' no seat'
   end as seat_number
  from p left join tr on p.departure_station =tr.departure_station and p.arrival_station =tr.arrival_station
   and ceil(p.rn/100) = tr.s2/100
   ;

〇〇 · 发表于 2025-1-1 07:14

标量子查询优化对duckdb**
用7.863
不用5.374

newkid · 发表于 2025-1-1 09:51

鸭子是不是没有 row cache? Oracle 的执行计划可以查看子查询的启动次数，鸭子库不知道有没有

NineData第2届数据库编程大赛：一条SQL秒 杀100万张火车票

NineData第2届数据库编程大赛：一条SQL秒杀100万张火车票