# \[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:** 1\
**Showing post:** 13

<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 14, 2022, 8:10pm UTC](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190/13 "2022-07-14T20:10:47Z")

</div>

When originally announced, `FlexiJoins` indeed didn’t support interval overlap condition. This is one of the predicates I introduced more recently, see the update post: [[ANN] FlexiJoins.jl: fresh take on joining datasets - #4 by aplavin](https://discourse.julialang.org/t/ann-flexijoins-jl-fresh-take-on-joining-datasets/79655/4).

As for complexity of this query, I think it should be something like M + N\*sqrt(M) + K. For now, the interval overlap joins are performed this way:

- Build a 2d KDTree for (start, end) points in one dataset.
- Loop through the other dataset, and for each item find overlapping intervals using a 2d range query for the tree.

Clearly, this isn’t the most efficient approach, but `NearestNeighbors.jl` was a dependency anyway (for distance joins) – so I used it here as well.

The “overlap-join” is the only interval-related join implemented with a tree. Other conditions ( `∈,∋,⊆,⊊,⊋,⊇`) use sorting and have different complexities.

> [@haberdashPI](#):
>
> In my case it is bound by the smaller of N log N, M log M and K where K is the number of rows in the output.

How is it possible to have the complexity less than K, M, N – whichever is larger? (:

---

_[View the full topic](https://discourse.julialang.org/t/ann-dataframeintervals-jl-joins-on-intervals-of-time/84190)._