Fetching next and/or prior objects given an arbitrary ordering

120 views
Skip to first unread message

Bernd Wechner

unread,
Feb 28, 2018, 6:57:32 AM2/28/18
to django...@googlegroups.com

I'm a bit stumped on this. Given an arbitrary ordering as specified by the ordering meta option:

    https://docs.djangoproject.com/en/2.0/ref/models/options/#ordering

for example:

class Thing(models.Model):
    field1 = ...
    field2 = ...
    field2 = ...
    class Meta:
        ordering = ['field1', '-field2', 'field3']

given an instant of Thing:

thing = Thing.objects.get(pk=...)

how can I get the next Thing after that one, and/or the prior Thing before that one as they appear on the sorted list of Things.

It's got me stumped as I can't think of an easy way to build a filter even with Q object for an arbitrary ordering given there can be multiple fields in ordering and multiple Things can have the same ordering list (i.e. there can be ties - that Django must resolve either arbitrarily or with an implicit pk tie breaker on ordering).

It's got me stumped. I can solve any number of simpler problems just not his generic one (yet).

Ideally I'd not build a list of all objects (waste of memory with large collections), and look for my thing in the list and then pick out the next or prior.

I'd ideally like to fetch it in one query returning the one Thing, or if not possible no worse than returning all Things on side of it and picking off the first or last respectively (even that's kludgy IMHO).

I'm using postgresql and I found a related question here:

    https://dba.stackexchange.com/questions/53862/select-next-and-previous-rows

but would rather stick with the ORM and not even explore SQL (just took a peak to see SQL can be constructed to do it I guess, as if not, the ORM sure won't have a good way of doing it methinks).

I'd have thought this a sufficiently common use case but am perhaps wrong there, with most sites exploiting simple orderings (like date_time or creation say). But I want to build a generic solution that works on any model I write, so I can walk through the objects in the order specified by ordering, without building a list of all of them. In short I want to solve this problem, not reframe the problem or work around it ;-).

Regards,

Bernd.

Julio Biason

unread,
Feb 28, 2018, 8:58:58 AM2/28/18
to django...@googlegroups.com
Hi Bernd,

Well, the thing with `get()` is that it will return only one object. What you're looking for is `filter()`.

Say, you want all the things that have an ID after a certain value. So you get `list_of_things = Things.objects.filter(pk__gte=...)`. Now it'll return the list, with all elements after the one you asked.

If you want the previous and next, you can do `list_of_previous = Things.objects.filter(pk__lt=...).limit(1)` and `list_of_next = Things.objects.filter(pk__gt).limit(1)`.

Or something like that ;P

--
You received this message because you are subscribed to the Google Groups "Django users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to django-users+unsubscribe@googlegroups.com.
To post to this group, send email to django...@googlegroups.com.
Visit this group at https://groups.google.com/group/django-users.
To view this discussion on the web visit https://groups.google.com/d/msgid/django-users/751c367c-d5e9-e06b-8f5c-82054f11a9ab%40gmail.com.
For more options, visit https://groups.google.com/d/optout.



--
Julio Biason, Sofware Engineer
AZION  |  Deliver. Accelerate. Protect.
Office: +55 51 3083 8101  |  Mobile: +55 51 99907 0554

Bernd Wechner

unread,
Feb 28, 2018, 6:50:56 PM2/28/18
to Django users
Julio,

Thanks for giving it some though. But I think you misread me a little. I am using the get() only to illustrate that the precondition is, I have a single object. The goal then is find a neighboring object (as defined by the ordering in the model).

Yes indeed, a filter is the first and primary candidate for achieving that, but can you write one that respects an abritrary ordering involving multiple fields, as I exemplified with:


class Thing(models.Model):
     field1
= ...
     field2
= ...
     field2
= ...
     
class Meta:
         ordering
= ['field1', '-field2', 'field3']

Also consider that the ordering thus specified does not stipulate uniqueness in any way, that is many neighboring things in an ordered list may have identical values of field1, field2 and field3.

I'm not sure how Django sorts those ties, but imagine it either defers to the underlying database engine (i.e. uses the sort simply to generate an ORDER BY clause in the SQL for example in the above case:

ORDER BY field1 ASC, field2 DESC, field3 ASC

and lets the underlying database engine define how ties are ordered. Or it could add a pk tie breaker to the end. Matters little, the problem remains: how to find neighbors given an arbitrary ordering and ties.

Can you write a filter clause to do that? I'm curious on that front.

It's easy of course with one sort field with unique values collapsing to an __gt or __lt filter folllowed by first() or last() respectively (not sure that injects a LIMIT clause into the SQL or collects a list and then creams one element from it - I'll test a little I think).

In the mean time, I still feel this has to be a fairly standard use case. It's about browsing objects in a table one by one, with a next and previous button given an ordering specified in the model and no guarantee of uniqueness on the (sort keys).

Regards,

Bernd.
To unsubscribe from this group and stop receiving emails from it, send an email to django-users...@googlegroups.com.

Bernd Wechner

unread,
Feb 28, 2018, 7:04:01 PM2/28/18
to Django users
I should add that one solution which I find functional but unattractive is to build a and ordered list of PKs:

things = list(Thing.objects.all().values_list('pk', flat=True))

then find the PK of the current object in that list and look one ahead or behind to get the PK of the neighbor and then fetch it with get(). The problem with this is that it loads an arbitrarily large list of PKs into memory for a job that should have a solution in the form of a database query that the ORM can execute lazily and receiving just one object.

Note that the list of Things above is ordered by Django in respect of the ordering defined in the model meta class, that is, this is an ordered list.


Regards,

Bernd.

On Thursday, 1 March 2018 00:58:58 UTC+11, Julio Biason wrote:
To unsubscribe from this group and stop receiving emails from it, send an email to django-users...@googlegroups.com.

Mike Dewhirst

unread,
Mar 1, 2018, 12:57:44 AM3/1/18
to Django users
On 1/03/2018 10:50 AM, Bernd Wechner wrote:
> Julio,
>
> Thanks for giving it some though. But I think you misread me a little.
> I am using the get() only to illustrate that the precondition is, I
> have a single object. The goal then is find a neighboring object (as
> defined by the ordering in the model).
>
> Yes indeed, a filter is the first and primary candidate for achieving
> that, but can you write one that respects an abritrary ordering
> involving multiple fields, as I exemplified with:
>
> |
> classThing(models.Model):
>      field1 =...
>      field2 =...
>      field2 =...
> classMeta:
>          ordering =['field1','-field2','field3']
> |
>
> Also consider that the ordering thus specified does not stipulate
> uniqueness in any way, that is many neighboring things in an ordered
> list may have identical values of field1, field2 and field3.

Nothing to stop you adding 'pk' or '-pk' to the ordering list.

I have done something similar recently where an online training course
leads the user with next and previous links to the next or previous
questions. At the first and last question for each set of instruction,
the links morph into previous and next instruction.

My approach relies on there being only a few questions per instruction.
It isn't very elegant because it tramples over the 'last' values until
the last man standing is correct and it bails out as soon as it finds a
greater 'next' value.

I did need/want a separate numeric ordering field because a trainer
writing up a course needs a sequence to force instruction items and
questions into adjustable arbitrary orders. Hence, the model save()
method updates a num_sequence float field from the user entered sequence
char field.

I haven't thought about < or > in the context of your ['field1',
'-field2', 'field3'] ordering but I went for a num_sequence float field
because '11' < '2' but 2.0 < 11.0 and so on.

The view code goes like this ...

def get_last_next_question_links(question, instruction, course, user):
lastlink = 'No previous question'
nextlink = 'No more questions'
questions = Question.objects.filter(instruction_id=question.instruction.pk)
for obj in questions:
if obj.num_sequence < question.num_sequence:
lasturl = '/question/%s/' % obj.pk
lastname = 'Previous Question %s' % obj.sequence
lastlink = '<a href="%s">%s</a>' % (lasturl, lastname)
elif obj.num_sequence > question.num_sequence:
nexturl = '/question/%s/' % obj.pk
nextname = 'Next Question %s' % obj.sequence
nextlink = '<a href="%s">%s</a>' % (nexturl, nextname)
break
if lastlink.startswith('No'):
lastlink = get_instruction_link(
course, instruction, user, next=False
)
if nextlink.startswith('No'):
nextlink = get_instruction_link(
course, instruction, user, next=True
)
return lastlink, nextlink


hth

>
> I'm not sure how Django sorts those ties, but imagine it either defers
> to the underlying database engine (i.e. uses the sort simply to
> generate an ORDER BY clause in the SQL for example in the above case:
>
> |
> ORDER BY field1 ASC,field2 DESC,field3 ASC
> <javascript:>.
> To post to this group, send email to
> django...@googlegroups.com <javascript:>.
> <https://groups.google.com/group/django-users>.
> <https://groups.google.com/d/msgid/django-users/751c367c-d5e9-e06b-8f5c-82054f11a9ab%40gmail.com?utm_medium=email&utm_source=footer>.
> For more options, visit https://groups.google.com/d/optout
> <https://groups.google.com/d/optout>.
>
>
>
>
> --
> *Julio Biason*,Sofware Engineer
> *AZION*  | Deliver. Accelerate. Protect.
> Office: +55 51 3083 8101 |  Mobile: +55 51 _99907 0554_
>
> --
> You received this message because you are subscribed to the Google
> Groups "Django users" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to django-users...@googlegroups.com
> <mailto:django-users...@googlegroups.com>.
> To post to this group, send email to django...@googlegroups.com
> <mailto:django...@googlegroups.com>.
> Visit this group at https://groups.google.com/group/django-users.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/django-users/bf6698d0-9aa5-4251-be69-62fe53afb603%40googlegroups.com
> <https://groups.google.com/d/msgid/django-users/bf6698d0-9aa5-4251-be69-62fe53afb603%40googlegroups.com?utm_medium=email&utm_source=footer>.

Bernd Wechner

unread,
Mar 1, 2018, 1:45:12 AM3/1/18
to django...@googlegroups.com, Mike Dewhirst
Mike,

Yep, adding pk as a final tie breaker is trivial, but not the issue ;-). Alas adding a sequencing field is not an option because I am looking for a generic solution, akin to what the admin site on Django offers, I have a model browser that I want to browse any of my models with.  And I was in fact using a date_time sequencer, only found that it broke in the generic sense for any ordering and with ties.

Moreover, without understanding the full context in your example you seem be fetching a pile of questions and then walking them to find the prior (I prefer the term "prior" as "last" has unfortunate ambiguity) and next questions, your set defined by "instruction_id=question.instruction.pk". My guess is that in your scenario that list is likely to be small (<1000 objects ;-) and this strategy becomes unappealing again if that list could be arbitrarily large (millions, or more) which is true for a generic scenario which makes no assumptions about the model other than what is provided by its ordering and known about the current object.

Regards,

Bernd.

Mike Dewhirst wrote:

Mike Dewhirst

unread,
Mar 1, 2018, 3:19:24 AM3/1/18
to Django users
On 1/03/2018 5:44 PM, Bernd Wechner wrote:
> Mike,
>
> Yep, adding pk as a final tie breaker is trivial, but not the issue
> ;-). Alas adding a sequencing field is not an option because I am
> looking for a generic solution, akin to what the admin site on Django
> offers, I have a model browser that I want to browse any of my models
> with.  And I was in fact using a date_time sequencer, only found that
> it broke in the generic sense for any ordering and with ties.
>
> Moreover, without understanding the full context in your example you
> seem be fetching a pile of questions and then walking them to find the
> prior (I prefer the term "prior" as "last" has unfortunate ambiguity)
> and next questions, your set defined by
> "instruction_id=question.instruction.pk". My guess is that in your
> scenario that list is likely to be small (<1000 objects ;-)

actually < 20 but usually < 5 ie., human scale

> and this strategy becomes unappealing again if that list could be
> arbitrarily large (millions, or more) which is true for a generic
> scenario which makes no assumptions about the model other than what is
> provided by its ordering and known about the current object.

Well something in the mix has to keep track of things. Maybe you need a
query which fetches a handy bucket of objects guaranteed to contain the
one you are interested in, single it out then 'next' or 'prior' until no
more before fetching another bucket.

If it wasn't for people like you there'd be no progress ;)

Cheers

Mike

C. Kirby

unread,
Mar 1, 2018, 11:48:53 AM3/1/18
to Django users
I'm having a hard time envisioning the SQL statement that could do what you are asking, without a sub select or something like that. If you can write the expression in sql you _might_ be able to get back to the ORM that would create that. Can you provide an sql  statement that does what you want for us to help you think about it?

Bernd Wechner

unread,
Mar 1, 2018, 7:43:58 PM3/1/18
to django...@googlegroups.com

I too have a hard time envisioning the SQL, so yes, I tried that. Haven't got past the one I cited in first post yet:

https://dba.stackexchange.com/questions/53862/select-next-and-previous-rows

but it contains some very specific function LAG and LEAD which I can see Postgresql, MySQL, MS-SQL supports these by SQLlite does not (perhaps not a crisis as I expect we could ignore SQLlite in what I implement).

LAG and LEAD are analytic functions that provide access to precisely what I want, the prior and next tuple(s).

But you can using them write something like this (in pro forma):

SELECT  *,  LAG(id) over (order by ...) as prior, LEAD(id) over (order by ...) as next
FROM table
WHERE id = myid

This will produce one tuple which has two new columns, prior and next, which contain the id of the prior and next tuples to that with myid following the specified order by.

Alas it uses two analytic functions I'm not sure the ORM supports. I think if not there's a fair case to put to Django to implement this as it's a fairly ordinary use case (finding neighboring objects in the models ordering).

There may be a way to replicate LAG and LEAD using self joins, with even better performance:

https://dba.stackexchange.com/questions/158374/performance-comparison-between-using-join-and-window-function-to-get-lead-and-la/158429

http://sqlblog.com/blogs/michael_zilberstein/archive/2012/03/14/42332.aspx

Regards,

Bernd.

You received this message because you are subscribed to a topic in the Google Groups "Django users" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/django-users/pVJH7MYOzuA/unsubscribe.
To unsubscribe from this group and all its topics, send an email to django-users...@googlegroups.com.

To post to this group, send email to django...@googlegroups.com.
Visit this group at https://groups.google.com/group/django-users.

Bernd Wechner

unread,
Mar 1, 2018, 8:02:51 PM3/1/18
to django...@googlegroups.com

Good news is that Django 2.0 is out and does support the Window functions:

    https://docs.djangoproject.com/en/2.0/ref/models/database-functions/#lag

Though it will mean a) upgrading on my dev box, c) working out how to use it and if happy, c) upgrading on my production box and rolling it out.

Great to see Django evolving though and the hope this SQL solution I just shared may be implementable in the ORM.

There's also a fine tutorial here:

    https://agiliq.com/blog/2017/12/django-20-window-expressions-tutorial/

and it looks like a filter can be annotated with such window functions and all migth work neatly in Django 2.0 ORM.


Regards,

Bernd.

On 2/03/2018 3:48 AM, C. Kirby wrote:
You received this message because you are subscribed to a topic in the Google Groups "Django users" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/django-users/pVJH7MYOzuA/unsubscribe.
To unsubscribe from this group and all its topics, send an email to django-users...@googlegroups.com.

To post to this group, send email to django...@googlegroups.com.
Visit this group at https://groups.google.com/group/django-users.

Bernd Wechner

unread,
Mar 12, 2018, 8:43:33 AM3/12/18
to Django users
OK Trying to implement this now and has SQL that works but can't work how to use the Django ORM to produce it. Here is the proforma SQL:

SELECT *
FROM
(
        SELECT id
, LAG(id, 1) OVER (ORDER BY <an order_by expression>) AS prior, LEAD(id 1) OVER (ORDER BY <an order_by expression>) AS next
        FROM
<mytable>
     
) result
WHERE id
=<myid>;

There's a sub query involved (as LAG and LEAD don't work if you constrain the inner query alas. And I've used SubQuery in Django before but not like this, (in the FROM clause), and am a tad stuck. Can anyone code this sort of query up in the Django ORM with QuerySets.

I can create the inner set.

result = model.objects.annotate(prior=Window(expression=Lag("pk"), order_by=order_by)).annotate(next=Window(expression=Lead("pk"), order_by=order_by))

Now the question is how to filter() the result of that, rather than that itself ;-). If that makes sense. Namely the aforementioned SQL. Any filter() I add to the end of this ORM QyerySet produces SQL more like

SELECT id, LAG(id, 1) OVER (ORDER BY <an order_by expression>) AS prior, LEAD(id 1) OVER (ORDER BY <an order_by expression>) AS next
FROM
<mytable>
WHERE id
=<myid>;

In with prior and next are empty, because that's just how such SQL works it seems. do the WHERE on the table produced by the SELECT/FROM as per SQL above to make this work.

Regards,

Bernd.

Bernd Wechner

unread,
Mar 13, 2018, 3:28:55 PM3/13/18
to Django users
Hmmm, really stuck on this. Can find no way of selecting from a select in the ORM. The whole premise seems be to start from model.objects and add SQL clauses with filter, annotate and other methods. But a QuerySet is not a model and queryset.objects doesn't exist, and queryset.filter just adds a where clause to the select on the original model not on the result of the queryset. It's almost as if we need a way to cast a queryset as a virtual model in the style of:

def get_prior(model, pk):
   
# Get the ordering list for the model (a list of fields
   
# See: https://docs.djangoproject.com/en/2.0/ref/models/options/#ordering
    ordering
= model._meta.ordering
   
    order_by
= []
   
for f in ordering:
       
if f.startswith("-"):
            order_by
.append(F(f[1:]).desc())
       
else:
            order_by
.append(F(f).asc())
   
    my_queryset
= model.objects.annotate(prior=Window(expression=Lag("pk"), order_by=order_by))

    my_result
= Model(my_queryset).objects.filter(pk=pk)

That last line is the crux of the issue.I see no way of writing this. When doing this:

    my_result = my_queryset.filter(pk=pk)

The WHERE clause ends up on the select in in my_querset. we want to wrap the whole of my_queryset with

select * from my_queryset where pk=pk

But how? Can anyone think of a way to do that?

Regards,

Bernd.

Bernd Wechner

unread,
Mar 15, 2018, 2:56:47 AM3/15/18
to Django users
Well the silence was stunning, so I pottered along and have a working solution. Alas I lean on a raw() call which I'd rather not. If there is any way to do this in the ORM I'd love to know. Otherwise I'm probably off to submit it as a feature request. The Window functions will all suffer this utility problem, that to use them meaningfully it may often be necessary to nest SELECTs. Here's a working neighbour fetcher:

def get_neighbor_pks(model, pk, filterset=None, ordering=None):
   
'''
    Given a model and pk that identify an object (model instance) will, given an ordering
    (defaulting to the models ordering) and optionally a filterset (from url_filter), will
    return a tuple that contains two PKs that of the prior and next neighbour in the list
    either of all objects by that ordering or the filtered list (if a filterset is provided)
    :param model:        The model the object is an instance of
    :param pk:           The primary key of the model instance being considered
    :param filterset:    An optional filterset (see https://github.com/miki725/django-url-filter)
    :param ordering:     An optional ordering (otherwise default model ordering is used). See: https://docs.djangoproject.com/en/2.0/ref/models/options/#ordering  
    '''

   
# If a filterset is provided ensure it's of the same model as specified (consistency).
   
if filterset and not filterset.Meta.model == model:
       
return None    
   
   
# Get the ordering list for the model (a list of fields
   
# See: https://docs.djangoproject.com/en/2.0/ref/models/options/#ordering
   
if ordering is None:

        ordering
= model._meta.ordering
   
    order_by
= []
   
for f in ordering:
       
if f.startswith("-"):
            order_by
.append(F(f[1:]).desc())
       
else:
            order_by
.append(F(f).asc())


   
# Define the window functions for each neighbour    
    window_lag
= Window(expression=Lag("pk"), order_by=order_by)
    window_lead
= Window(expression=Lead("pk"), order_by=order_by)

   
# Get a queryset annotated with neighbours. If annotated attrs clash with existing attrs an exception
   
# will be raised: https://code.djangoproject.com/ticket/11256    
   
try:
       
# If a non-empty filterset is supplied, respect that
       
if filterset and filterset.filter:
            qs
= filterset.filter() | model.objects.filter(pk=pk).distinct()
       
# Else we just use all objects
       
else:
            qs
= model.objects
           
       
# Now annotate the querset with the prior and next PKs
        qs
= qs.annotate(neighbour_prior=window_lag, neighbour_next=window_lead)
   
except:
       
return None
   
   
# Finally we need some trickery alas to do a query on the queryset! We can't add this WHERE
   
# as a filter because the LAG and LEAD Window functions fail then, they are emoty because
   
# there is no lagger or leader on the one line result! So we have to run that query on the
   
# whole table.then extract form the result the one line we want! Wish I could find a way to
   
# do this in the Django ORM not with a raw() call.    
    ao
= model.objects.raw("SELECT * FROM ({}) ao WHERE {}=%s".format(str(qs.query), model._meta.pk.name),[pk])
   
   
if ao:
       
return (ao[0].neighbour_prior,ao[0].neighbour_next)
   
else:
       
raise None  

Matthew Pava

unread,
Mar 15, 2018, 9:55:09 AM3/15/18
to django...@googlegroups.com

--

You received this message because you are subscribed to the Google Groups "Django users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to django-users...@googlegroups.com.
To post to this group, send email to django...@googlegroups.com.
Visit this group at https://groups.google.com/group/django-users.

Bernd Wechner

unread,
Mar 15, 2018, 5:47:52 PM3/15/18
to Django users
Mathtew,

Yes I most certainly have. I use them elsewhere. i love SubQuery. But I can only find examples and documentation about using them in the WHERE clause (or a filer() arguments). If you can write me an example of how one might be used in the FROM clause as in my example below I'd be indebted. It's a challenge indeed, as the FROM clause in the ORM is dictated by the model in the syntax model.objects.filter(), where filter() defines the WHERE clause and model the FROM clause. How can a SubQuiery be put into place there, in the FROM clause?

I would dearly love to learn that was possible and I've overlooked it somehow.

Regards,

Bernd.

To post to this group, send email to djang...@googlegroups.com.

Matthew Pava

unread,
Mar 16, 2018, 5:01:41 PM3/16/18
to django...@googlegroups.com

Hi Bernd,

Indeed, I did not look closely at what was happening.  Definitely add a feature request.  I sincerely believe that if we would implement the Subquery object as a CTE, it would resolve these situations without much changing anything else.  https://code.djangoproject.com/ticket/28919

Thanks,

Matthew

 

I would like to see something like this:

cte = Subquery(model.objects.annotate(prior=Window(expression=Lag("pk"), order_by=order_by)).annotate(next=Window(expression=Lead("pk"), order_by=order_by)))

result = model.objects.annotate(id=cte["id"], prior=cte["prior"], next=cte["next"]).filter(pk=some_id)

 

would produce something like this

 

WITH cte(id, prior, next) AS (

SELECT id, LAG(id, 1) OVER (ORDER BY <an order_by expression>) AS prior, LEAD(id 1) OVER (ORDER BY <an order_by expression>) AS next


FROM
<model>

)

SELECT cte.id, cte.prior, cte.next

FROM <model> JOIN cte ON cte.id=<model>.id

WHERE id=<some_id>

To post to this group, send email to django...@googlegroups.com.

Reply all
Reply to author
Forward
0 new messages