Rails/Sql - order/group search results such that repetition of entities occurs only after appearance of others

Question

In my application, say, animals have many photos. I'm querying photos of animals such that I want all photos of all animals to be displayed. However, I want each animal to appear as a photo before repetition occurs.

Example: 

animal instance 1, 'cat', has four photos, 
animal instance 2, 'dog', has two photos:

photos should appear ordered as so:

#photo         belongs to     #animal

tiddles.jpg ,                  cat 
fido.jpg                       dog 
meow.jpg                       cat 
rover.jpg                      dog 
puss.jpg                       cat 
felix.jpg,                     cat  (no more dogs so two consecutive cats)

• Pagination is required so I can't order on an array.
• Filename structure/convention provides no help, though the animal_id exists on each photo.
• Though there are two types of animal in this example this is an active record model with hundreds of records.
• Animals may be selectively queried.

If this isn't possible with active_record then I'll happily use sql; I'm using postgresql.

My brain is frazzled so if anyone can come up with a better title, please go ahead and edit it or suggest in comments.

Answer 1

Here is a PostgreSQL specific solution:

batch_id_sql = "RANK() OVER (PARTITION BY animal_id ORDER BY id ASC)"

Photo.paginate(
  :select => "DISTINCT photos.*, (#{batch_id_sql}) batch_id",
  :order  => "batch_id ASC, photos.animal_id ASC",
  :page   => 1)

Here is a DB agnostic solution:

batch_id_sql = "
 SELECT COUNT(bm.*) 
 FROM   photos bm 
 WHERE  bm.animal_id = photos.animal_id AND
        bm.id <= photos.id 
"

Photo.paginate(
  :select => "photos.*, (#{batch_id_sql}) batch_id",
  :order  => "batch_id ASC, photos.animal_id ASC",
  :page   => 1)

Both queries work even when you have a where condition. Benchmark the query using expected data set to check if it meets the expected throughput and latency requirements.

Reference

PostgreSQL Window function

Answer 2

New solution

Add an integer column called batch_id to the animals table.

class AddBatchIdToPhotos < ActiveRecord::Migration
  def self.up
    add_column    :photos,   :batch_id, :integer
    set_batch_id
    change_column :photos,   :batch_id, :integer, :nil => false
    add_index     :photos,   :batch_id
  end

  def self.down
    remove_column :photos,   :batch_id
  end

  def self.set_batch_id
    # set the batch id to existing rows
    # implement this
  end
end

Now add a before_create on the Photo model to set the batch id.

class Photo
  belongs_to     :animal
  before_create  :batch_photo_add
  after_update   :batch_photo_update
  after_destroy  :batch_photo_remove

private

  def batch_photo_add
    self.batch_id = next_batch_id_for_animal(animal_id)
    true
  end

  def batch_photo_update
    return true unless animal_id_changed?
    batch_photo_remove(batch_id, animal_id_was)
    batch_photo_add
  end

  def batch_photo_remove(b_id=batch_id, a_id=animal_id)
    Photo.update_all("batch_id = batch_id- 1", 
      ["animal_id = ? AND batch_id > ?", a_id, b_id])
    true
  end

  def next_batch_id_for_animal(a_id)
    (Photo.maximum(:batch_id, :conditions => {:animal_id => a_id}) || 0) + 1
  end
end

Now you can get the desired result by issuing simple paginate command

@animal_photos = Photo.paginate(:page => 1, :per_page => 10, 
                     :order => :batch_id)

How does this work?

Let's consider we have data set as given below:

id  Photo Description    Batch Id
1   Cat_photo_1          1
2   Cat_photo_2          2
3   Dog_photo_1          1
2   Cat_photo_3          3
4   Dog_photo_2          2
5   Lion_photo_1         1
6   Cat_photo_4          4

Now if we were to execute a query ordered by batch_id we get this

# batch 1 (cat, dog, lion)
Cat_photo_1
Dog_photo_1
Lion_photo_1

# batch 2 (cat, dog)
Cat_photo_2
Dog_photo_2

# batch 3,4 (cat)
Cat_photo_3
Cat_photo_4

The batch distribution is not random, the animals are filled from the top. The number of animals displayed in a page is governed by per_page parameter passed to paginate method (not the batch size).

Old solution

Have you tried this?

If you are using the will_paginate gem:

# assuming you want to order by animal name
animal_photos = Photo.paginate(:include => :animal, :page => 1, 
                  :order => "animals.name")

animal_photos.each do |animal_photo|
  puts animal_photo.file_name
  puts animal_photo.animal.name
end

Answer 3

Having no experience in activerecord. Using plain PostgreSQL I would try something like this:

Define a window function over all previous rows which counts how many time the current animal has appeared, then order by this count.

SELECT
   filename,
   animal_id,
   COUNT(*) OVER (PARTITION BY animal_id ORDER BY filename) AS cnt
FROM
   photos
ORDER BY
   cnt,
   animal_id,
   filename

Filtering on certain animal_id's will work. This will always order the same way. I don't know if you want something random in there, but it should be easily added.

Answer 4

I'd recommend something hybrid/corrected based on KandadaBoggu's input.

First off, the correct way to do it on paper is with row_number() over (partition by animal_id order by id). The suggested rank() will generate a global row number, but you want the one within its partition.

Using a window function is also the most flexible solution (in fact, the only solution) if you want to plan to change the sort order here and there.

Take note that this won't necessarily scale well, however, because in order to sort the results you'll need to:

• fetch the whole result set that matches your criteria
• sort the whole result set to create the partitions and obtain a rank_id
• top-n sort/limit over the result set a second time to get them in their final order

The correct way to do this in practice, if your sort order is immutable, is to maintain a pre-calculated rank_id. KandadaBoggu's other suggestion points in the correct direction in this sense.

When it comes to deletes (and possibly updates, if you don't want them sorted by id), you may run into issues because you end up trading faster reads for slower writes. If deleting the cat with an index of 1 leads to updating the next 50k cats, you're going to be in trouble.

If you've very small sets, the overhead might be very acceptable (don't forget to index animal_id).

If not, there's a workaround if you find the order in which specific animals appear is irrelevant. It goes like this:

1. Start a transaction.

2. If the rank_id is going to change (i.e. insert or delete), obtain an advisory lock to ensure that two sessions can't impact the rank_id of the same animal class, e.g.:

   SELECT pg_try_advisory_lock('the_table'::regclass, the_animal_id);
   

   (Sleep for .05s if you don't obtain it.)

3. On insert, find max(rank_id) for that animal_id. Assign it rank_id + 1. Then insert it.

   On delete, select the animal with the same animal_id and the largest rank_id. Delete your animal, and assign its old rank_id to the fetched animal (unless you were deleting the last one, of course).

4. Release the advisory lock.

5. Commit the work.

Note that the above will make good use of an index on (animal_id, rank_id) and can be done using plpgsql triggers:

create trigger "__animals_rank_id__ins"
before insert on animals
for each row execute procedure lock_animal_id_and_assign_rank_id();

create trigger "_00_animals_rank_id__ins"
after insert on animals
for each row execute procedure unlock_animal_id();

create trigger "__animals_rank_id__del"
before delete on animals
for each row execute procedure lock_animal_id();

create trigger "_00_animals_rank_id__del"
after delete on animals
for each row execute procedure reassign_rank_id_and_unlock_animal_id();

You can then create a multi-column index on your sort criteria if you're not joining all over them place, e.g. (rank_id, name). And you'll end up with a snappy site for reads and writes.

Answer 5

You should be able to get the pictures (or filenames, anyway) using ActiveRecord, ordered by name.

Then you can use Enumerable#group_by and Enumerable#zip to zip all the arrays together.

If you give me more information about how your filenames are really arranged (i.e., are they all for sure with an underscore before the number and a constant name before the underscore for each "type"? etc.), then I can give you an example. I'll write one up momentarily showing how you'd do it for your current example.

Answer 6

You could run two sorts and build one array as follows:

result1= The first of each animal type only. use the ruby "find" method for this search.

result2= All animals, sorted by group. Use "find" to again find the first occurrence of each animal and then use "drop" to remove those "first occurrences" from result2.

Then: markCustomResult = result1 + result2

Then: You can use willpaginate on markCustomResult