Efficient linq query for changing rank order of entities

Question

I'm trying to figure out the best way to make a table arbitrarily sortable. By that I mean that the user can change the sort order of the table with no relation to the data. To accommodate this I added a new column to the table called Rank which should be used for sorting.

I wrote this function to change the rank of a given entity

public void ChangeRank(int id, int rank)
{
    _dbSet.Find(id).Rank = rank;

    // adjust ranks
    var index = rank + 1;
    foreach (var entity in _dbSet.Where(x => x.Rank >= rank && x.Id != id).OrderBy(x => x.Rank))
        entity.Rank = index++;

    _context.SaveChanges();
}

I believe, correct me if I'm wrong, that the foreach loop isn't translated into a single sql statement which is what I was hoping to do - for performance. I'm pretty sure it's possible to do in raw sql using row_number() but I want to keep it as a LINQ query.

How would I optimize the update of rank?

Are there better ways to implement arbitrary sorting?

I will correct you: `_dbSet.Where(...).OrderBy(...)` should still be only one SQL query. — Corey Adler, Dec 18 '14 at 19:03
So what you're asking for is to go to the database and adjust the ranks in one shot? You'd need a stored proc for that. EF can't do that for you. — Corey Adler, Dec 18 '14 at 19:08

score 0 · Answer 1 · edited May 23 '17 at 12:20

0

I think Find was multiple times slower, than say, First. Secondly, the logic can be simplified, so you don't need to sort:

var row = _dbSet.First(x => x.Id == id);
var oldRank = row.Rank;
if(oldRank == newRank) 
    return;

if(newRank > oldRank)
{
    foreach (var entity in _dbSet.Where(x => x.Rank > oldRank)) 
    {
        if(entity.Rank > newRank) 
            entity.Rank++;
        else 
            entity.Rank--;
    }
} else 
{
    // think the logic yourself.
}

row.Rank = newRank;

If you index the row.Rank, it'll be probably pretty good. You might also want to make sure that Row.Rank has unique constraint, or you should think about transactions.

If you'e working with massive system, you'll probably need to implement some kind of tree structure in SQL, such that updating the rank of an element is O(logn) operation(super fast) - Database Structure for Tree Data Structure

About the entity framework: no, the EF is not good for this type of problem. You should check this threa Batch update/delete EF5 and see if you can find something useful. The fact is that EF does not perform well with bulk records at all.

edited May 23 '17 at 12:20

Community

1
1

answered Dec 18 '14 at 19:13

Erti-Chris Eelmaa

25,338
6
61
78

.Find() is far superior in terms of performance. > Find() is set apart from other element operations in LINQ-To-Entities in that it will first query the in-memory entities that EF is tracking and only hit the database in the event that none is found. Thus it can have superior performance and should always be used where possible – especially in lengthy operations when the entity is likely to already be in memory. [source](http://www.sql-server-performance.com/2013/selecting-data-entity-framework-find-firstordefault-single/) – Snæbjørn Dec 18 '14 at 19:50
1

@Snæbjørn; I was referencing to this http://stackoverflow.com/questions/11686225/dbset-find-method-ridiculously-slow-compared-to-singleordefault-on-id all things considerd - I don't advise one other another. One should run performance tests to see which one is best for the situation. It seems that Find calls internally SaveChanges which would make it pretty slow imo. – Erti-Chris Eelmaa Dec 18 '14 at 20:48
Think you mean `DetectChanges` :) But I wasn't aware of the performance hit, I was sure 'in memory overhead' was neglectable compared to reading from disk (db), thanks for the link – Snæbjørn Dec 19 '14 at 09:08

Aducci · Answer 2 · 2014-12-18T20:03:49.090

0

I would avoid updating multiple entities.

Make Rank a double and whenever you need to ChangeRank, set it to a value between the next two records. So for example if you wanted to move an entity lower:

public void MoveDown(int id)
{
  var entity = _dbSet.Find(id);

  var nextTwo = _dbSet.Where(x => x.Rank > entity.Rank)
                    .OrderBy(x => x.Rank)
                    .Select(x => x.Rank)
                    .Take(2).ToList();

  if (nextTwo.Count == 2)
  {
     entity.Rank = (nextTwo[0] + nextTwo[1]) / 2; 
  }
  // if entity is second last
  else if (nextTwo.Count == 1)
  {
     entity.Rank = nextTwo[0] + 1; 
  }

  _context.SaveChanges();
}

Sample Results of Moving ID 1 down

Before
ID    Rank
1     1
2     2
3     3

After
ID    Rank
1     2.5
2     2
3     3

A similar approach can be used if you want to set an entity to a certain position, but the idea is to only modify one entity

edited Dec 18 '14 at 20:03

answered Dec 18 '14 at 19:51

Aducci

26,101
8
63
67

This is an interesting approach, though the state where it can't be placed in the middle should be handled. You don't have to write that :) Also some consideration need to be put into performance regarding int vs float comparison. [SO](http://stackoverflow.com/questions/7360824/is-there-a-speed-difference-in-ordering-by-int-vs-float) – Snæbjørn Dec 18 '14 at 20:08
By default, Entity Framework will create a transaction and depending on the number of records and relationship this could completely deny access to tables/database and take in inordinate amount of time. (My experience was inserting 300,000 records at once took 18 hours) – Erik Philips Dec 18 '14 at 20:18
@ErikPhilips - I don't understand your comment. The only transaction will be for one update statement. (updating one record) – Aducci Dec 18 '14 at 20:28
@Aducci you are correct, I misread your code. However, now the opposite is true. A transaction per Update isn't very efficient, and depending on tests, doing a batch of updates from 10-500 at a time will heavily create performance. – Erik Philips Dec 18 '14 at 20:38

Efficient linq query for changing rank order of entities

2 Answers2