Optimization techniques for fast query
When we work on a specific problem, We first think of the solution for the worst-case scenario which leads to a brute force approach to solving the problem. This is OK most of the time, as we don’t get much time to think about an optimal solution due to tight deadlines. In this blog post, We’re talking about storing weekdays data model problems. First, we go through the problematic approach – brute force, then optimize our data model so that we can optimize our database tables for the fast queries.
Let’s give a perspective to our problem first, suppose we are developing an application and in our application, we need to manage branches (e.g branches of a restaurant or supermarket) and each branch has its own weekdays.
So we can design that in an RDBMS database like this, we make a table branches where we store branch-related information and for the weekdays of a specific branch we can store that in a pivot table like branch_weekdays which represents one to many relationships.
In this design, the pivot table can store the days’ info of a branch which represents one to many relationships. For small data, it’s completely fine as it’s not going to be a problem.
But just think like this, in the worst case if every branch has 7 days as it’s a weekday in the table then the table becomes one of the major problems when there are a million rows in the branches table which makes the branch_weekdays table 7 times larger than the branches table. If we have several tables like that in our application and we need to join tables to serve some data, this will be a major problem as it will make our query slow when we need to join these tables.
Solutions:
To solve this problem, we use the binary operation to store the days as a mask in the branches table without managing a separate pivot table like below
Let me explain how we can generate the mask in the branches table. So we all know 7 days makes a whole week and if we flag 0 as Sunday to 6 as Saturday respectively, then we get 0-6 values for each day in a week. While working with binary may initially seem confusing, understanding that each binary place value represents 2n, just as each decimal place represents 10n, should help clarify. Take the number 8 for example:
8 × 100 = 8 × 1 = 8
In binary, 8 is represented as 1000. Reading from right to left, the first 0 represents 20, the second 21, the third 22, and the fourth 23; just like the decimal system, except with a base of 2 rather than 10.
20 + 21 + 22 + 23 + 24 + 25 + 26 = 127
If we sum the values, we get 127 as the mask value which means the branch is available in seven days. As we’ll use the bitwise operation to check whether the current day is available or not in the mask value which makes the operation much faster and we’re able to save a lot of space too. Also, most importantly, we don’t face a million rows joining problem.
For this part, I’ll write the code in Golang, Let me define some utils functions so that we can re-use the code in our application
// Contains check if a `needle` can be found in the `haystack`
// e.g.
// haystack -> []slice
// needle -> int
// result -> bool
func Contains(haystack interface{}, needle interface{}) bool {
switch reflect.TypeOf(haystack).Kind() {
case reflect.Slice:
s := reflect.ValueOf(haystack)
for i := 0; i < s.Len(); i++ {
if reflect.DeepEqual(needle, s.Index(i).Interface()) {
return true
}
}
}
return false
}
// GenerateAvailabilityMask covert days slice into binary mask value
func GenerateAvailabilityMask(days []int) *int {
mask := 0
for i = 0; i < 7; i++ {
if Contains(days, i) {
mask += int(math.Pow(2, float64(i)))
}
}
return &mask
}
// input
// [0,1,2,3,4,5,6]
// output
// 127
We need a function to generate weekdays from the mask as we’ll return days as a comma-separated string
// GenerateWeekdays convert mask value into weekdays comma separated string
func GenerateWeekdays(mask int) string {
var sb strings.Builder
nbits := 7
for i := 0; i < nbits; i++ {
if IsCurrentDayAvailable(mask, i) {
sb.WriteString(strconv.Itoa(i))
sb.WriteString(",")
}
}
return TrimSuffix(sb.String(), ",")
}
// input
// 127
// output
// "0,1,2,3,4,5,6"
// TrimSuffix remove suffix from the string if string ends with the suffix
func TrimSuffix(s, suffix string) string {
if ok := strings.HasSuffix(s, suffix); ok {
s = s[:len(s)-len(suffix)]
}
return s
}
// IsCurrentDayAvailable check if current weekday is available in availability mask
func IsCurrentDayAvailable(mask int, currentDay int) bool {
x := 1
return (mask & (x << currentDay)) > 0
}
IsCurrentDayAvailable function is where we apply the bitwise AND (&) operation to find if the current day is available in the mask or not.
To get the current day we can use the below function
// CurrentLocalTimeAndWeekday use timezone to get current zone time and weekday and return current weekday & current time in military format
func CurrentLocalTimeAndWeekday(tz string) (int, int) {
militaryLayout := "1504"
loc, err := time.LoadLocation(tz)
if err != nil {
logrus.Error("error occurred when trying to find timezone location.", err)
return 0, -1
}
t := time.Now().In(loc)
currentWeekday := int(time.Now().In(loc).Weekday())
militaryTime, err := strconv.Atoi(t.Format(militaryLayout))
if err != nil {
logrus.Error("error occurred when converting time to military integer format.")
return 0, -1
}
return militaryTime, currentWeekday
}
So after fetching the mask from the branches table, we can use the CurrentLocalTimeAndWeekday utils function to get the current time and weekday and use the IsCurrentDayAvailable function to determine if the current weekday is available or not in the mask. Also if we need to send Mask as weekdays in the response we can use the GenerateWeekdays function to make the mask as an array of weekdays.
In Conclusion, We may not often get enough time to think or come up with an optimized solution in the first go but if we put some thought into the problem, we may come up with solutions that make the database query faster as we reach to million rows.
