Checking for date overlaps — the most optimal formula

TL;DR:

Room.Bookings.Filter(
  CurrentValue.End > Search.Start
  AND CurrentValue.Start < Search.End
).IsBlank()


A popular requirement is to test whether a certain date range overlaps with any of the ranges in a dataset. For example: search which of the rooms are available for requested check-in/check-out dates given the database of all bookings.

There’s been a few (1, 2, 3) topics about this already. Actually I even replied to one of these:

My reply got lost because recently I learned that many still use this Excel solution that’s apparently the one that comes up from a Community search first. It goes like this:

First get the number of overlapping days:

Max(Min(End1, End2) - Max(Start1, Start2), 0)

then check whether overlapping days is zero, e.g. whether the list of bookings that would have any overlaps is blank:

Room.Bookings.Filter(
  Max(
    Min(CurrentValue.End, Search.End) - Max(CurrentValue.Start, Search.Start),
    0
  ) > 0
).IsBlank()

The problem with this solution is that while it’s perfectly good for calculating the number of overlap days, to answer the simple “overlapping? — yes/no” question the calculation is too redundant.

Let’s sketch this out:

It becomes apparent that the minimum required condition for dates to not overlap with the search is that each booking’s:

  • End is before (or on-or-before) Search.Start
    OR
  • Start is after (on-or-after) Search.End

This expression in a filter would give us all bookings that are not overlapping. We’re interested in the opposite though: getting the list of bookings that are overlapping so that we could check whether it’s blank. Therefore we need to flip the expression.

We could simply introduce a Not() function call and write:

Not(
  CurrentValue.End <= Search.Start
  OR CurrentValue.Start >= Search.End
)

or put it in a brackets and check against false:

(CurrentValue.End <= Search.Start OR CurrentValue.Start >= Search.End) = false

but there’s a better solution that won’t require any extra operations: flip the logic with De Morgan’s laws:

NOT (A OR B) — is equivalent to — (NOT A) AND (NOT B)

So we flip <= with > and >= with <, the OR with AND, and get:

Room.Bookings.Filter(
  CurrentValue.End > Search.Start
  AND CurrentValue.Start < Search.End
).IsBlank()

:point_up_2: This is the most efficient way to test if the Search range is overlapping with any of the ranges in the Bookings data set. The biggest reason for that in theory is that boolean expressions can short circuit. This means that if the first part of the check CurrentValue.End > Search.Start fails, the second one is not tested at all because Coda already knows the result of the whole expression is false. This saves half the checks on all bookings that are in the past. In the minmax algorithm, the whole expression has to be calculated for every booking.

Also calling functions (Min(), Max()) is more expensive than using operators (>, <, AND). By a very thin margin in systems like Coda but still.

But that’s in theory. To test it in practice I created a simple benchmark doc and confirmed that the algorithm in this post is ~4x times faster than the blindly copied popular solution.

image

Even if you remove the redundant Max(..., 0) check (because we don’t care if the result is negative — only > 0 means overlap) you get 2-3x times the performance of the minmax formula.


So the moral of the story is this.
If you want your Coda docs to perform well and last longer:

  • Don’t just mindlessly copy the solutions you find online. Always try to analyze if the algorithm is not doing anything redundant for your specific case.

  • Learn to come up with solutions yourself. Sketching (like I did above) is your friend and can help you see patterns and deduce optimal algorithms.

  • The performance wins in the screenshot above (16ms vs 71ms on 1000 checks) might seem insignificant but remember this is an isolated calculation. In real world docs you’ll write more sophisticated checks and if you use a suboptimal formula here and a suboptimal formula there, these things add up very quickly, resulting in a painfully slow doc.

  • Despite the fact that Coda and similar tools are aimed at non-developers, it’s the devs who have the experience in finding optimal algorithms (e.g. here’s another one). So the next time you’re building a performance-sensitive Coda doc, seek help of your in-house dev or hire a consultant with development background :slight_smile: (the most shamelessly shameless plug of all, lol)

Take care,
Paul

11 Likes

wonderful contribution @Paul_Danyliuk, I am also fan the one your reference !

Sequence(thisRow.[Start date], thisRow.[End date], 28).ListCombine(thisRow.[End date]).FormulaMap(
  DateTimeTruncate(CurrentValue, "month")
).Unique()
1 Like

An important note: the algorithm works only assumed that for each booking, End is always >= Start. Normally that should be the rule enforced upon booking creation. If that’s not the case though (e.g. you have random sets of {Date1; Date2} in whatever order), you’ll either have to pre-sort these or write a bigger formula and compare all starts and all ends within each other.

This is obvious but we had issues with this because of human errors: a moderator would mistakenly select a date from a previous month as an End date and not see an overlap error. Hence it’s important to have an “End cannot be before Start” alert in place at the moment of booking creation.

1 Like