Handling overlapping values
- Comments:
- here.
One of the things that I enjoy most about Postgres are the rich types. Using these types can help reduce the amount of validation that the application needs to do.
Take for instance anything which contains a start date and a finish date. If you model this using two fields, then you also need to include validation about start <= finish (or perhaps start < finish, depending upon your requirements).
If you use a date range instead, then the database will do this validation for you. It is not possible to create a range value that is “backwards”. Sure, you’ll also need to do application-level (and probably client-side) validation, but there is something nice about having a reliable database that ensures you cannot possibly have invalid data.
Django is able to make good use of range types, and most of my new code seemingly has at least one range type: often a valid_period. So much so that I have a Mixin and a QuerySet that make dealing with these easier:
class ValidPeriodMixin(models.Model):
valid_period = DateRangeField()
class Meta:
abstract = True
@property
def start(self):
if self.valid_period.lower_inc:
return self.valid_period.lower
elif self.valid_period.lower is not None:
return self.valid_period.lower + datetime.timedelta(1)
@property
def finish(self):
if self.valid_period.upper_inc:
return self.valid_period.upper
elif self.valid_period.upper is not None:
return self.valid_period.upper - datetime.timedelta(1)
@property
def forever(self):
return self.valid_period.lower is None and self.valid_period.upper is None
def get_valid_period_display(self):
if self.forever:
message = _('Always applies')
elif self.start is None:
message = _('{start} \u2092 no end date')
elif self.finish is None:
message = _('no start date \u2092 {finish}')
else:
message = _('{start} \u2092 {finish}')
return message.format(
start=self.start,
finish=self.finish,
)
def ensure_date_range(period):
"""
If we have a 2-tuple of dates (or strings that are valid dates),
ensure we turn that into a DateRange instance. This is because
otherwise Django may mis-interpret this.
"""
if not isinstance(period, DateRange):
return DateRange(period[0] or None, period[1] or None, '[]')
return period
class OverlappingQuerySet(models.query.QuerySet):
def overlapping(self, period):
return self.filter(valid_period__overlap=ensure_date_range(period))
def on_date(self, date):
return self.filter(valid_period__contains=date)
def today(self):
return self.on_date(datetime.date.today())
As you may notice from this, it is possible to do some filtering based on range types: specifically, you can use the && Postgres operator using .filter(field__overlap=value), and the containment operators (<@ and @>) using .filter(field__contains=value) and .filter(field__contained_by=value). There are also other operators we will see a bit later using other lookups.
If you have a legacy table that stores a start and a finish, you would need to have a validator on the model (or forms that write to the model) that ensures start < finish, as mentioned above. Also, there is no way (without extra columns) to tell if the upper and lower values should be inclusive or exclusive of the bounds. In Postgres, we write range values using a notation like a mathematical range: using ‘[’, ‘]’ and ‘(’, ‘)’ to indicate inclusive and exclusive bounds.
SELECT '[2019-01-01,2020-01-01)'::DATERANGE AS period;
One caveat when dealing with discrete range types (like dates and integers) is that Postgres will, if it is able to, convert the range to a normalised value: it will store (2019-01-01,2019-12-31] as [2019-01-02,2020-01-01). This can become a problem when showing the value back to the user, because depending upon context, it’s likely that you will want to use inclusive bounds when showing and editing the values.
You can manage this by using a form field subclass that detects an exclusive upper bound and subtracts one “unit” accordingly:
import datetime
from django.contrib.postgres.forms.ranges import (
DateRangeField, IntegerRangeField
)
class InclusiveRangeMixin(object):
_unit_value = None
def compress(self, values):
range_value = super().compress(values)
if range_value:
return self.range_type(
range_value.lower,
range_value.upper,
bounds='[]'
)
def prepare_value(self, value):
value = super().prepare_value(value)
value = [
field.clean(val)
for field, val in zip(self.fields, value)
]
if value[1] is not None:
value[1] = value[1] - self._unit_value
return value
class InclusiveDateRangeField(
InclusiveRangeMixin, DateRangeField
):
_unit_value = datetime.timedelta(1)
class InclusiveIntegerRangeField(
InclusiveRangeMixin, IntegerRangeField
):
_unit_value = 1
Back on to the topic of storing two values instead of a range: it’s possible to add an expression index on the table that uses DATERANGE:
CREATE INDEX thing_period_idx
ON thing_thing (DATERANGE(start, finish));
You would be able to annotate on this value, do some querying, and it should use the index, allowing you to build querysets like:
Thing.objects.annotate(
period=Func(
F('start'),
F('finish'),
function='DATERANGE',
output_field=DateRangeField())
).filter(period__overlap=other_period)
Range types show their full power when used with exclusion constraints. These allow you to prevent writing rows that violate the constraint. For instance, consider this model (and some largely irrelevant other models, Team and Player):
class TeamMembership(ValidPeriodMixin):
ployer = models.ForeignKey(
Player,
related_name='team_memberships',
on_delete=models.CASCADE,
)
team = models.ForeignKey(
Team,
related_name='player_memberships',
on_delete=models.CASCADE,
)
A player may only belong to one team at a time: that is, we may not have any overlapping valid_periods for a player.
You can do this using an exclusion constraint, but it does need the btree_gist extension installed:
CREATE EXTENSION IF NOT EXISTS btree_gist;
ALTER TABLE team_teammembership
ADD CONSTRAINT prevent_overlapping_team_memberships
EXCLUDE USING gist(person_id WITH =, valid_period WITH &&)
DEFERRABLE INITIALLY DEFERRED;
Since this type of constraint is not yet supported in Django, you’ll have to do it in a RunSQL migration.
From here, we can attempt to write conflicting data, but the database will forbid it. You will still need to write code that checks before writing - this enables you to return a ValidationError to the user when you detect this conflict in a form, but having the exclusion constraint means that we can avoid the race condition where:
- Check for overlapping ranges
- Other process creates a range that will overlap
- Save our data
You could possibly also use select_for_update in this context, but I prefer adding database constraints.
Note that the DEFERRABLE INITIALLY DEFERRED clause is important: it allows you, within a transaction, to write conflicting data, and it’s only when the transaction commits that the constraint is checked. This makes rewriting a bunch of values in one transaction much simpler: if you do not have this flag enabled then you will need to ensure you update them in an order that maintained no overlaps at each stage. I’m pretty confident this is always possible, but it’s a bunch of work (and it is possible that you might need to write some rows multiple times to maintain that).
So, now we can store range values (with database validation), and prevent overlapping data (with database validation).
What about a process that enables us to say “this row should replace, trim or split any that overlap with it”? I’m glad you asked.
It turns out given two rows, where one should “supersede” the other, there are five different conditions we need to take into account:
- The rows do not overlap: no action required
- The new row completely covers the old row: remove the old row
- The old row has bounds that exceed the new row in both directions: split the old row into two rows
- The old row has a lower bound that is smaller than the new row: trim the old row at the upper end
- The old row has an upper bound that is larger than the new row: trim the old row at the lower end
It turns out we can perform this query with the Django range field lookups:
class OverlappingQuerySet(models.query.QuerySet):
def with_overlap_type(self, period):
period = ensure_date_range(period)
return self.annotate(
overlap_type=Case(
# The objects do not overlap.
When(~Q(valid_period__overlap=period,
then=Value(None))),
# The existing value is covered by the new value
When(valid_period__contained_by=period,
then=Value('replace')),
# The existing value has no values
# less than the new value
When(valid_period__not_lt=period,
then=Value('trim:lower')),
# The existing value has no values
# greater than the new value
When(valid_period__not_gt=period,
then=Value('trim:upper')),
# The existing value contains the new value
When(valid_period__contains=period,
then=Value('split')),
output_field=models.TextField()
)
)
This works because a CASE WHEN stops evaluating when it finds a match: technically a trim:lower value could also match on containment (split), so we need to test that one earlier.
We are going to have to (possibly) perform multiple queries when writing back the data. If there are any than need to be “removed”, they will need a DELETE. Any that have a “trim” operation will require an UPDATE.
new_instance = Thing(valid_period=('2019-01-01', '2019-02-09'))
overlapping = Thing.objects.overlapping(
new_instance.valid_period
).with_overlap_type(new_instance.valid_period)
overlapping.filter(overlap_type='replace').delete()
overlapping.filter(
overlap_type__in=('trim:upper', 'trim:lower')
).update(
valid_period=valid_period - new_instance.valid_period
)
But the tricky part is that any that are “split” will require at least two: either a DELETE followed by an INSERT (that inserts two rows), or a single UPDATE and a single INSERT. The tricky part here is that we also need to read the values first, if we are going to manipulate them in python. Instead, we can look at how to do it in raw SQL, with the benefit that we can perform this in a single operation.
WITH new_period AS (
SELECT %s AS new_period
),
split AS (
SELECT thing_id,
valid_period,
other_field,
new.new_period
FROM thing_thing old
INNER JOIN new_period new ON (
LOWER(old.valid_period) < LOWER(new.new_period)
AND UPEER(old.valid_period) > UPEER(new.new_period)
)
), new_rows AS (
SELECT other_field,
DATERANGE(LOWER(valid_period),
LOWER(new_period)) AS valid_period
FROM split
UNION ALL
SELECT other_field,
DATERANGE(UPPER(new_period),
UPPER(valid_period)) AS valid_period
),
removed AS (
DELETE FROM thing_thing
WHERE thing_id IN (SELECT thing_id FROM split)
)
INSERT INTO thing_thing (other_field, valid_period)
SELECT other_field, valid_period FROM new_rows;
This is less than ideal, because we need to enumerate all of the fields (instead of just other_field), so this code is not especially reusable as-is.
Let’s look at alternatives:
# Fetch the existing items.
splits = list(overlapping.filter(overlap_type='split').values())
to_create = []
to_delete = []
for overlap in splits:
to_delete.append(overlap.pop('thing_id'))
valid_period = overlap.pop('valid_period')
to_create.append(Thing(
valid_period=(valid_period.lower, new_instance.valid_period.lower),
**overlap
))
to_create.append(Thing(
valid_period=(new_instance.valid_period.upper, valid_period.upper),
**overlap
))
overlapping.filter(pk__in=to_delete).delete()
Thing.objects.bulk_create(to_create)
We can stick all of that into a queryset method, to make it easier to manage.
import copy
class OverlappingQuerySet(models.query.QuerySet):
def trim_overlapping(self, period):
"""
Trim/split/remove all overlapping objects.
* Remove objects in the queryset that are
"covered" by the period.
* Split objects that completely cover the
new period with overlap at both sides
* Trim objects that intersect with the new
period and extend in one direction or the
other, but not both.
This will do a single query to trim object that need
trimming, another query that fetches those that need
splitting, a single delete query to remove all
split/replaced objects, and finally an optional query
to create replacement objects for those split.
That means this method _may_ perform 3 or 4 queries.
This particular algorithm should work without a
transaction needing to be present, but in practice
this action and the create of a new one should be
in the same transaction, so they can all roll-back
if anything goes wrong.
"""
period = ensure_date_range(period)
overlapping = self.overlapping(period)\
.with_overlap_type(period)
# Easy first: update those that we can just update.
overlapping.filter(
overlap_type__startswith=('trim')
).update(
valid_period=models.F('valid_period') - period
)
# Create the new objects for each of the ones that
# extend either side of the new value.
# There will alwasy be two of them: one for the lower
# section, and one for the upper section.
to_create = []
for instance in overlapping.filter(overlap_type='split'):
# Setting the primary key to None will trigger a new
# instance.
instance.pk = None
# We need to create two instances, each with a different
# valid_period.
valid_period = instance.valid_period
# The one _before_ the new value.
instance.valid_period = DateRange(
valid_period.lower, period.lower, bounds='[)'
)
to_create.append(instance)
# And a new copy to go _after_ the new value.
instance = copy.deepcopy(instance)
instance.valid_period = DateRange(
period.upper, valid_period.upper, bounds='(]'
)
to_create.append(instance)
# Now clean up any that we need to get rid of.
overlapping.filter(
overlap_type__in=('replace', 'split')
).delete()
# And finally add back in any replacement objects
# that extended either side of the new value.
if to_create:
self.model._default_manager.bulk_create(to_create)
Yeah, I think that will do for now.