# \[ANN\] DataFrameIntervals.jl — joins on intervals of time

**URL:** <https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190>\
**Category:** Package Announcements\
**Tags:** dataframes\
**Created:** [July 13, 2022, 6:47pm UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190 "2022-07-13T18:47:42Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![aplavin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aplavin/32/222056_2.png) [@aplavin](https://discourse.julialang.org/u/aplavin)\
**Post date:** [July 16, 2022, 8:09pm UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/21 "2022-07-16T20:09:48Z")

</div>

That’s definitely a different kind of grouping!  
Currently, `FlexiJoins` doesn’t do anything that can be performed separately after the join. The single exception is inner/left/right join - fundamentally, they can be obtained from the outerjoin, but it’s very inconvenient to do each time.

I haven’t thought of the usecase you describe before. Not sure if I fully understand the motivation, can you describe a kinda-realistic example?

Is it grouping of one dataset before the join, while leaving the other as-is? Basically,

```julia
A |>
  group(_.field_group) |>
  map() do gr
    innerjoin((A=gr, B), by...) |>
      map(...) |>
      reduce(...)
  end

```

instead of

```julia
innerjoin((A, B), by...) |>
  group(_.A.field_group) |>
  map() do gr
    gr |>
      map(...) |>
      reduce(...)
  end

```

Or something more complex?

Also, for some common cases, joining by a composite condition is useful: like `by_key(:name) & by_pred(:time, <, :time)`. If both datasets contain `:name` that should also be matched.

---

<div class="post-metadata">

**Author:** ![haberdashPI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/haberdashpi/32/26337_2.png) [@haberdashPI](https://discourse.julialang.org/u/haberdashPI)\
**Post date:** [July 21, 2022, 2:52am UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/22 "2022-07-21T02:52:00Z")

</div>

What I’ve implemented allows you to choose grouping variables from one or both of A and B, (because that would be possible if you did the operations in the opposite order); in your example this would translate to including a second `group` operation within the map before map-reducing.

Example: In my case I have ~8 hours of annotated signal data for each of ~40k recordings. There are 1000-10,000 annotations per recording. It’s much more reasonable to operate on a per-recording basis (so `groupby(df, :recording)`). I want to compute, e.g. the number of occurrences of some annotated event of interest in the each quarter of each recording. So I do something that looks like this, in concept:

```julia
quarters = quantile_windows(4, recordings, :quarter)
groups = groupby_interval_join(recordings, quarters, [:recording, :quarter], 
                               on=:time_span)
combine(groups, :annotation_label => (x -> sum(==(:event_of_interest), x) => :event_count)

```

Doing this join over the entire 40k set of recordings is a lot more memory intensive than doing the join per-recording.

---

<div class="post-metadata">

**Author:** ![aplavin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aplavin/32/222056_2.png) [@aplavin](https://discourse.julialang.org/u/aplavin)\
**Post date:** [July 21, 2022, 10:35am UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/23 "2022-07-21T10:35:24Z")

</div>

Thanks for the example!

I also encounter similar cases in my work: a large dataset that contains sets of measurements for completely separated individual objects. However, I haven’t really felt a need for such a “join-then-group” function. I tend to just group such datasets immediately after loading them, and work with a collection of groups afterwards – instead of a single flat dataset. Often, this approach isn’t even motivated by performance (for smaller datasets), but by convenience: it is conceptually simple to `map` a function over individual objects.

Potentially, such “join-then-group” functionality can be in-scope for FlexiJoins. But for now, I don’t have any plans in this direction.  
Also, care should be taken to avoid confusion. The `groupjoin` term is typically used to mean grouping by one of the join sides, as FlexiJoins currently does. I think this naming originated from C# LINQ.

Further, note that the total FlexiJoins memory allocations in the `Sort` mode should be roughly `2 * sizeof(Int) * (length(input) + length(result))`. When elements of the input dataset contain multiple fields, especially stuff like strings, the `join` memory usage can be less than the input size.

---

<div class="post-metadata">

**Author:** ![Juan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juan/32/7657_2.png) [@Juan](https://discourse.julialang.org/u/Juan)\
**Post date:** [July 21, 2022, 3:15pm UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/24 "2022-07-21T15:15:49Z")

</div>

I think  
can also do it:

> **[GitHub - sl-solution/InMemoryDatasets.jl: Multithreaded package for working...](https://github.com/sl-solution/InMemoryDatasets.jl)**
>
> Multithreaded package for working with tabular data in Julia - GitHub - sl-solution/InMemoryDatasets.jl: Multithreaded package for working with tabular data in Julia

[https://sl-solution.github.io/InMemoryDatasets.jl/stable/man/joins/](https://sl-solution.github.io/InMemoryDatasets.jl/stable/man/joins/)

---

<div class="post-metadata">

**Author:** ![haberdashPI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/haberdashpi/32/26337_2.png) [@haberdashPI](https://discourse.julialang.org/u/haberdashPI)\
**Post date:** [July 22, 2022, 11:23am UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/25 "2022-07-22T11:23:31Z")

</div>

Sorry, I don’t follow. Do what? Lazy joins or interval joins. Can you indicate where that’s documented?

---

<div class="post-metadata">

**Author:** ![Juan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juan/32/7657_2.png) [@Juan](https://discourse.julialang.org/u/Juan)\
**Post date:** [July 22, 2022, 11:27am UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/26 "2022-07-22T11:27:31Z")

</div>

I mean interval joins.

## [Inequality-kind joins](https://sl-solution.github.io/InMemoryDatasets.jl/stable/man/joins/#Inequality-kind-joins)

---

<div class="post-metadata">

**Author:** ![haberdashPI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/haberdashpi/32/26337_2.png) [@haberdashPI](https://discourse.julialang.org/u/haberdashPI)\
**Post date:** [July 22, 2022, 1:50pm UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/27 "2022-07-22T13:50:24Z")

</div>

Thanks @Juan, I’ve added an entry to DataFrameIntervals.jl’s README.

---

<div class="post-metadata">

**Author:** ![aplavin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aplavin/32/222056_2.png) [@aplavin](https://discourse.julialang.org/u/aplavin)\
**Post date:** [July 22, 2022, 2:04pm UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/28 "2022-07-22T14:04:07Z")

</div>

Judging by those docs, it only supports `L.a < R.x < L.b` type of joins — while interval overlap corresponds to a more complex condition.

---

<div class="post-metadata">

**Author:** ![chiraganand](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chiraganand/32/32787_2.png) [@chiraganand](https://discourse.julialang.org/u/chiraganand)\
**Post date:** [July 24, 2022, 7:07pm UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/29 "2022-07-24T19:07:08Z")

</div>

@haberdashPI The PR URL isn’t working?

---

<div class="post-metadata">

**Author:** ![haberdashPI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/haberdashpi/32/26337_2.png) [@haberdashPI](https://discourse.julialang.org/u/haberdashPI)\
**Post date:** [July 24, 2022, 10:03pm UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/30 "2022-07-24T22:03:08Z")

</div>

Oh hey! I’m not sure why it isn’t working for you. That said, I’ve already merged, so if you have any issues with my description of TSx, please feel free to open a PR correcting any mistakes.

---

<div class="post-metadata">

**Author:** ![haberdashPI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/haberdashpi/32/26337_2.png) [@haberdashPI](https://discourse.julialang.org/u/haberdashPI)\
**Post date:** [July 25, 2022, 10:49am UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/31 "2022-07-25T10:49:32Z")

</div>

I actually am not clear now, having read through the documentation for inequality-like joins, whether it does or does not support interval overlap. I find the description ambiguous. @Juan can you clarify your thinking?

---

<div class="post-metadata">

**Author:** ![Juan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juan/32/7657_2.png) [@Juan](https://discourse.julialang.org/u/Juan)\
**Post date:** [July 25, 2022, 11:12am UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/32 "2022-07-25T11:12:20Z")

</div>

I’m not sure either.  
In fact I don’t know how are your “overlapping” intervals. Can not you get the same results with L.a \< R.x \< L.b conditions?

I’ve just pointed out that package because I had seen it and it’s supposed to be very fast.

The creator of InMemoryDatasets is @sl-solution

---

<div class="post-metadata">

**Author:** ![haberdashPI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/haberdashpi/32/26337_2.png) [@haberdashPI](https://discourse.julialang.org/u/haberdashPI)\
**Post date:** [July 25, 2022, 1:16pm UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/33 "2022-07-25T13:16:44Z")

</div>

Ah okay, thanks for the clarification. Overlapping means that the intersection of times between the two intervals is non-empty. So `L.a < R.x < R.b` is just one over several possible cases where this is true.

---

<div class="post-metadata">

**Author:** ![chiraganand](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chiraganand/32/32787_2.png) [@chiraganand](https://discourse.julialang.org/u/chiraganand)\
**Post date:** [July 25, 2022, 5:16pm UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/34 "2022-07-25T17:16:45Z")

</div>

> [@haberdashPI](#):
>
> Oh hey! I’m not sure why it isn’t working for you. That said, I’ve already merged, so if you have any issues with my description of TSx, please feel free to open a PR correcting any mistakes.

@haberdashPI I am unable to open the [repository](https://github.com/beacon-biosignals/DataFrameIntervals.jl) itself, is it private?

---

<div class="post-metadata">

**Author:** ![haberdashPI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/haberdashpi/32/26337_2.png) [@haberdashPI](https://discourse.julialang.org/u/haberdashPI)\
**Post date:** [July 26, 2022, 12:03am UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/35 "2022-07-26T00:03:49Z")

</div>

Oh wow! Surprised no one else mentioned the link wasn’t working for them! I meant to make this public but it looks like something didn’t go through. Should be visible now! I would appreciate it if you could let me know if you have any further trouble accessing the repository.

---

<div class="post-metadata">

**Author:** ![chiraganand](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chiraganand/32/32787_2.png) [@chiraganand](https://discourse.julialang.org/u/chiraganand)\
**Post date:** [July 26, 2022, 7:58am UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/36 "2022-07-26T07:58:34Z")

</div>

Thanks @haberdashPI I can access the repository now.

Just to be clear on the plan for TSx, I would want to support any custom index for the `TS` structure, like BYOIT (Bring Your Own Index Type) as long as there are certain methods provided like `sort`, `==` etc. then all the other TSx methods should be available for free. Though, the actual operation like `join()` would be done by DataFrames.jl code so the type should be supported at that level. Also, it should support `DataFrames.groupby()`.

In fact, `TimeSpan` and `Interval` could be good first use cases for implementing this functionality as they already exist as separate custom types.

---

<div class="post-metadata">

**Author:** ![haberdashPI](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/haberdashpi/32/26337_2.png) [@haberdashPI](https://discourse.julialang.org/u/haberdashPI)\
**Post date:** [July 26, 2022, 5:04pm UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/37 "2022-07-26T17:04:57Z")

</div>

@chiraganand: can you elaborate on this plan a bit? What is needed in the case of an interval is not just a sort. You need to break up the intervals into a sorted list of endpoints (left / right), and then scan for overlap: there is no `==` in this case: multiple intervals in dataset a can overlap with multiple intervals in dataset b (but none of them are equal); I do a join that matches all of these overlapping intervals.

---

<div class="post-metadata">

**Author:** ![sl-solution](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sl-solution/32/34759_2.png) [@sl-solution](https://discourse.julialang.org/u/sl-solution)\
**Post date:** [July 27, 2022, 8:06pm UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/38 "2022-07-27T20:06:19Z")

</div>

`InMemoryDatasets` supports the inequality joins for one column from the left data set, since, this is the case that I could develop an efficient and flexible join algorithm. Adding inequality joins for more than one column needs algorithms with O(n^2) complexity which is very expensive (even for moderate size data sets).

Nevertheless, I welcome PRs that would introduce O(n^2) joins to `InMemoryDatasets`. By “O(n^2) joins” I mean those kind of joins which can find matching rows by using any given function (i.e. in addition to `isequal`), this can be called `cartesianjoin` or `crossjoin`.

---

<div class="post-metadata">

**Author:** ![chiraganand](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chiraganand/32/32787_2.png) [@chiraganand](https://discourse.julialang.org/u/chiraganand)\
**Post date:** [July 31, 2022, 11:52am UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/39 "2022-07-31T11:52:49Z")

</div>

@haberdashPI Okay, now I understand. I don’t think TSx will be able to handle such custom join cases. And, because it relies on the join functionality provided by DataFrames.jl so any data type which can be handled by a DataFrame joins TSx should be able to handle.

---

<div class="post-metadata">

**Author:** ![dyeeee](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dyeeee/32/43774_2.png) [@dyeeee](https://discourse.julialang.org/u/dyeeee)\
**Post date:** [October 22, 2022, 10:19am UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/40 "2022-10-22T10:19:17Z")

</div>

Hi! @sl-solution I completed the development of cartesianjoin() based on IMD, which supports inequality joins with multiple columns or joins with arbitrary user-defined conditions. Besides, all parameters for IMD’s join are supported. Check the link [GitHub - dyeeee/CartesianJoin.jl: A join extension package developed based on InMemoryDatasets.jl](https://github.com/dyeeee/CartesianJoin.jl), and I provide use cases and performance benchmarks. Suggestions are welcome. Thanks.

[Previous page](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190.md?page=1)

[Next page](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190.md?page=3)