SQL Performance Enhancement: Conversion Funnel Analysis
[Abstract]
The essay analyzes the fundamental reason behind slow SQL statements and provides the solution to make improvements through code samples. Click SQL Performance Enhancement: Conversion Funnel Analysis for details.
Problem description
Conversion funnel analysis is an ingroup timeseries operation, which benefits many situations and the conversion analysis of ecommerce purchase is one of them. The user performs actions like page view, search, add to cart, order placing, payment and so on after he logs in the ecommerce website. These events are ordered in time and part of the users will be lost after each of them. Conversion funnel analysis usually counts the user number after each event firstly, then does complex calculations like conversion rate on the basis of the former.
Suppose the fields of table T include id (the event number), gid (the grouping field), etime(the time field), eventtype(the event type), and each of them respectively corresponds to the user event number, user number, action time, event type of the ecommerce purchase analysis. The gross data volume table T involving is usually quite large, which needs to be stored externally, while the data of each group (the user) are not that big, which can be hold in memory.
Here 3 steps of the solution to conversion funnel are illustrated, and other steps can be deduced by analogy. Take Oracle for example, and the SQL is as follows:
with e1 as (
select gid,1 as step1,min(etime) as t1
from T
where etime>= to_date('20210110', 'yyyyMMdd') and etime<to_date('20210125', 'yyyyMMdd')
and eventtype='eventtype1' and …
group by 1
),
with e2 as (
select gid,1 as step2,min(e1.t1) as t1,min(e2.etime) as t2
from T as e2
inner join e1 on e2.gid = e1.gid
where e2.etime>= to_date('20210110', 'yyyyMMdd') and e2.etime<to_date('20210125', 'yyyyMMdd')
and e2.etime > t1
and e2.etime < t1 + 7
and eventtype='eventtype2' and …
group by 1
),
with e3 as (
select gid,1 as step3,min(e2.t1) as t1,min(e3.etime) as t3
from T as e3
inner join e2 on e3.gid = e2.gid
where e3.etime>= to_date('20210110', 'yyyyMMdd') and e3.etime<to_date('20210125', 'yyyyMMdd')
and e3.etime > t2
and e3.etime < t1 + 7
and eventtype='eventtype3' and …
group by 1
)
select
sum(step1) as step1,
sum(step2) as step2,
sum(step3) as step3
from
e1
left join e2 on e1.gid = e2.gid
left join e3 on e2.gid = e3.gid
Subquery e1 firstly filters the data whose event type is eventtype1 in a specified period of time form table T. The starting and ending time of the specified period usually are the given parameters, which change dynamically. “and...” means to have the possibility to satisfy other conditions, and subqueries e2 and e3 also need to satisfy the same condition. Then the data are grouped by gid, and the smallest etime of each group are retrieved as the time t1 of the first step of conversion funnel, and the value of new field step1 are defined as 1.
Subquery e2 uses table T (also known as e2) to inner join with e1, and the join field is gid. It filters the data whose e2.etime is less than 7 days after t1 and event type is eventtype2 in the specified period. The 7day here is called the funnel window period, which can also be the given parameter. Then the data are group by gid, the smallest e2.etime of each group are retrieved as the time t2 of the second step of conversion funnel, and the value of new field step2 are defined as 1.
Subquery e3 uses T table (also known as e3) to inner join with e2, and the join field is gid. It filters the data whose e3.etime is larger than t2 as well as less than 7 days after t1 (funnel window period), and event type is eventtype3 in the specified period. Then the data are grouped by gid, the smallest e3.etime of each group are retrieved as the time t3 of the third step of conversion funnel, and the value of new field step3 are defined as 1.
At last, the database uses e1 to left join with e2 and e3, the join field is gid, and aggregates step1, step2, and step3 to get a sum.
Here are the 3 steps of funnel conversion analysis. If you want to accomplish more steps of funnel conversion analysis, please refer to e3 to write subqueries like e4, e5, and so on, and main query needs to be added with thecorresponding main code of join and aggregation.
Generally speaking, the result set of grouping table T of a specific period by gid tends to be big. To perform big group requires buffering on external storage, which results in bad computation performance.
Solution
1. Presorting and orderbased algorithm
We have to presort the original data orderly according to the grouping field in the process of data preparation. When performing conversion funnel analysis, the algorithm traverses the ordered data which satisfy the conditions like the time period, the event type and so on, reads the data of each group into memory in turn. Specifically, step 1: it sorts the current grouped data in time order; step 2: it finds the first record of the first event type in the current group, records the time as t1, and assigns t1 to the first member of the current grouping result set. If t1 cannot be found, then the current group is skipped; step 3: in the records of the second event type in the current group, it finds the first record whose time is after t1 and before t1+7 (the funnel window period), and assigns its time t2 to the second member of the result set (if t2 cannot be found, then the assignment will be null); step 4: in the records of the third event type in the current group, it finds the first record whose time is after t2 and before t2+7, and assigns its time t3 to the third member of the result set (if t2 is null or t3 cannot be found, then the assignment will be null); step 5: it aggregates the three members of the result set per group to get the final result. This method traverses the data only once and avoids performing grouping with a big result, thus improving the performance greatly.
We can also sort the original data by both grouping field and time field beforehand and spare the resorting of each group, which improves the performance less effectively, but simplifies the code obviously.
In fact, many grouping fields of ingroup timeseries calculation are certain (like the user ID and the account number) rather than randomly chosen. Sorting data by these certain fields can help many situations of ingroup timeseries calculation. Other ingroup timeseries calculations only differ in the specific algorithms, which will be introduced on their own.
Presorting is slow yet oneoff and holds only one kind of storage without redundant data.
SQL, based on the unordered set, cannot ensure the data of each group are orderly stored, therefore, it cannot directly use the orderbased algorithm.
2. Newadded data
Newlyadded data are not always ordered by the grouping field, so they should not be simply appended to the end of the already ordered data. And it will be very timeconsuming to directly do an ordinary full sorting of the existing data and the new data together.
Instead, we can sort the newlyadded data first and then, along with the already ordered data, perform lowcost orderbased MERGE algorithm to generate a new ordered data table. In this way, the overall degree of complexity equals to reading and writing the whole data once, which avoids the frequent temporary external buffering in ordinary full sorting, thus improving the performance greatly.
Furthermore, we can keep a smallscale ordered table additionally (hereinafter referred to as patch data), which will merge with the newlyadded data while keeping the old ordered data unchanged. The patch data will merge with the old ordered data until they accumulate to a suitable size after a while. When performing the timeseries calculation in the group, the algorithm reads from the old ordered data and patch data respectively, merges them and then calculates. In this manner, the performance will be a bit slower compared with handling one table of ordered data, but the data orderliness can still make the computation much faster.
The time when to merge the patch data with the old ordered data is related to the cycles when data should be added. If new data are added every day, we can do the merge once a month. The patch data store data of one month at most and the existing ordered data contain all data one month ago. That is, the patch data may be far smaller than the old ordered data, so the data to be merged every day is relatively small and the data appending is fast. As we do the wholedata orderbased merge only once a month, it is fairly acceptable that it takes a littler longer to complete.
Code example
1. Calculate the conversion funnel when the data is ordered by grouping field and unordered by time field.
A 
B 

1 
=["eventtype1","eventtype2","eventtype3"] 
=file("T.ctx").open() 
2 
=B1.cursor(gid,etime,eventtype;etime>=date("20210110") && etime<date("20210125") && A1.contain(eventtype) && …) 

3 
=A2.group(gid).(~.sort(etime)) 
=A3.new(~.select@1(eventtype==A1(1)):first,~:all).select(first) 
4 
=B3.(A1.(t=if(#==1,t1=first.etime,if(t,all.select@1(eventtype==A1.~ && etime>t && etime<t1+7).etime, null)))) 

5 
=A4.groups(;count(~(1)):STEP1,count(~(2)):STEP2,count(~(3)):STEP3) 
A1: define the three event types, which can also be given parameters.
B1: open the composite table T.ctx.
A2: create a cursor to filter the data satisfying the conditions like time period, event type and so on. These conditions can be given parameters.
A3: define the grouping operation, and sort each group by etime.
B3: create a new cursor, name the first data of the first event type in each group as “first” and the original group as “all”. Then define filtering to skip the data whose “first” field is null.
A4: define the calculation of B3. Loop through each record according to A1. The first loop assigns the time of “first”, which is the earliest time of the first event type, to variable t1, t and the first member of the result set at the same time. The second loop finds the first record whose eventtype is the second event type in “all” and etime is larger than t and smaller than t1+7. Its etime is assigned to t and the second member of the result set (if t cannot be found, the assignment will be null). The third loop finds the first record whose eventtype is the third event type in “all” and etime is larger than t and smaller than t1+7 if t is not null. Its etime is assigned to t and the third member of the result set (if t is null or cannot be found , the assignment will be null). Please note that the 7 days (funnel window period) here can also be given parameter.
A5: execute the previously defined calculation and aggregate the three members of each result set in each group to return a small result set and count the number.
Here are still 3 steps of conversion funnel analysis. To accomplish more steps, you can add the event types of following steps in the event type sequence of A1, for example, ["eventtype1","eventtype2","eventtype3","eventtype4","eventtype5"…]. The code can stay the same if the event type sequence is the given parameter. This method is much simpler compared with adding subqueries and modifying the main query in SQL.
2. Calculate the conversion funnel when the data is ordered by both grouping field and time field.
The above code can be even simpler and (~.sort(etime)) can be omitted in A3 if the data are ordered by both grouping field and time field in advance.
3. The data are presorted and the ordered result set are stored.
A 

1 
=file("Toriginal.ctx") 
2 
=A1.open().cursor().sortx(gid,etime).new(gid,etime,…) 
3 
=file("T.ctx").create(#gid,#etime,…) 
4 
=A3.append@i(A2) 
A1: define the original composite table Toriginal.ctx.
A2: open the composite table Toriginal.ctx, create a cursor based on it, sort the cursor by field gid and field etime where field gid and field etime are in the leading positions. The sortx can be written as sortx(gid) if the cursor is only sorted by gid.
A3: create a new composite table T.ctx with pound sign # preceding the field name, which means this composite table is ordered by field gid and field etime. The create can be written as create(#gid,etime,…) if the table is only sorted by gid.
A4: write the ordered data into the composite table T.ctx.
4. Append the newlyadded data
Suppose the daily newlyadded data for table T are stored in T_new.btx, and have the same field names in the same order as T.ctx have.
A 
B 

1 
=file("T.ctx").open() 

2 
=file("T_new.btx").cursor@b().sortx(gid,etime) 

3 
if (day(now())==1) 
>A1.reset() 
4 
>A1.append@a(A2) 
A1: open the composite table T.ctx.
A2: define a cursor based on T_new.btx and sort it. As the daily volume of new data is small, the sorting is a fast and inmemory operation though sortx function is used. The etime in sortx should be removed if the cursor is only ordered by gid.
A3: identify whether the current date is day 1: if not, execute A4 and use append@a to merge the record with only the patch data; if so, execute B3 and use reset function to merge the existing ordered data with the patch data to generate a new ordered data table.
Chinese version