Need a way to navigate very large lists, better than QAbstractItemModel::fetchMore

davidivanmarsh

We're dealing with some very large lists (or database tables) in our Qt app -- hundreds of thousands, or millions of rows. We need to be able to display them quickly without loading all rows, and then navigate around in the lists "nicely".

Qt has a function called fetchMore from the QAbstractItemModel class that loads only a specified number of rows on demand, and then loads more as the user moves the scroll thumb down in the list. I've implemented that functionality in several Qt applications and it works quite well.

But I need a better capability -- I need to be able to jump around better -- if the list is sorted alphabetically, I want to be able to jump to the first name that starts with "M" for example, or let the user type in some characters and then navigate in the list to that location, etc.

I looked at the scrollTo API:

void QAbstractItemView::scrollTo(const QModelIndex &index, ScrollHint hint = EnsureVisible)

but couldn't figure out a way around the problem of the QModelIndex -- when we're dealing with millions of items, we don't create QModelIndex's in advance, since they're only created on an as-needed basis when the next "chunk" of data is loaded on-demand. Then when the user selects (clicks on) one, that QModelIndex is available.

The fetchMore API doesn't require QModelIndexes (although it does allow for a parent QModelIndex to be passed in, although I don't use that):

void QAbstractProxyModel::fetchMore(const QModelIndex &parent)

So I'm stuck on this one. I would really like to use the scrollTo API if I could! Any ideas on this?
-David Marsh

raven-worx

@davidivanmarsh
so you want to know where to scroll before you even know how many items are between? right?

To do such thing quickly you need to ensure that each row has the same height and you need an index (Binary tree, e.g.) to find the position needed for scrolling.

davidivanmarsh

Thanks for your reply, but to respond to your statement "so you want to know where to scroll before you even know how many items are between? right?", no that's not quite right.

We keep an internal list structure (that's very fast) of each item that potentially could be added to the QTreeView, so if the user types in the letter "P" we know what index that would be in our internal list (e.g, index 60,6509 say). But we don't know what the QModelIndex for that item would be in the QTreeView, or how to jump there. That's where I'm getting stuck.

Chris Kawa

I don't think Qt provides a ready-made solution for this case. The problem is that there are lazy loading facilities (the fetchMore() you mentioned) to add items incrementally at the end but there's no way to "unload" items in the front. This effectively means that when a user types "Z" in you example practically the whole list would need to be loaded, because you can't load only the items "around" your point of interest. With fetchMore() you can only load "everything up to".

That said you'll need some manual labor to do what you want. I'd approach this by implementing a view class that would be sort of a "moving window" around your data i.e. always show a constant number of items around a defined (begin,end) area of the data. The model would also need to be customized. I'd extend the interface of fetchMore to something like fetchBefore, fetchAfter, discardBefore and discardAfter. It's gonna be a challenge to provide a meaningful scrollbar for a data set this large, as moving it even 1 pixel up or down would potentially jump hundreds of items. You could for example assume that a constant number (like a 1000) of items is loaded at any given time and scrolling near the top calls fetchBefore/discardAfter and moving it near bottom calls fetchAfter/discardBefore.
Jumping to the middle of the set would require implementing something like fetchAround in the model and the view.

davidivanmarsh

(My partner felt I wasn't being clear enough about our requirements, so he asked me to post this:)

Let me be more clear with a real example:

We have a list of items (e.g. 1 million names) that is already in memory. We can sort them or otherwise order them independent of the interface. We want to be able to display portions of that list within a qt tree view. In addition to starting at the top of the list and letting the user page down (already implemented using fetchMore) we want to be able to 'jump' to any location within the list. For example if the user typed the letter 'S' we want to jump to the first item that starts with that letter (e.g. row 850,223) and then let the user page up or page down from there. We also want the scroll bar to reflect the size of the list so if the user drags the thumb down halfway, it will jump to about row 500,000.

Chris Kawa

@davidivanmarsh I think I got you the first time. Now I'm feeling I wasn't clear enough ;)

Let me relate to that example with 1 million items. Let's say the user types 'S' and the first 'S' item is at position 850 223 like you said. With what Qt provides you can only signal the model somehow that it needs to fetch the items up to that item 850 223 (or possibly a couple dozens after it).

This means a method in a model that does more or less something like this:

void SomeModel::fetchUpTo(int row)
{
    QModelIndex parent; //assuming you want top-level rows
    beginInsertRows(parent, rowCount(), row);
    //if you need any internal handling do it here
    //if you have it already in memory like you said there might be nothing extra to do
    endInsertRows();
}

Calling this in response to the user input will update the view (i.e. the scrollbar) to reflect that there are now 850 223 rows. Now you can call

yourView->scrollTo(yourModel->index(850 223, 0));

to move to it.
Keep in mind that you definitely want to set the uniformRowHeights property in this case or the view will just die calculating the vertical offsets all the time.

Expanding on that example, what I said earlier is that the scrollbar in a model like this will be useless for mouse navigation (PageUp/Down and arrows should be ok though). That's why I suggested that you created your own model and view able to display only a subset in the middle of the data, not the entire thing up to some point.

davidivanmarsh

@Chris-Kawa Chris, your feedback was right-on. This is not going to be a "slam-dunk" design and implementation -- it will require a lot of custom view class work. Your ideas about using a fetchBefore, fetchAfter discardBefore, discardAfter, or fetchUpTo API seem like a good place to start. And I understand your concerns about the scroll bar thumb.

I haven't done work writing custom view classes in Qt before -- is there some tutorial or example code I could use as a model?

But is my scenario unique? Isn't there anyone else out there developing with Qt with the same need? Has anyone already come up with such a custom class?

Cupras

@davidivanmarsh I'm having the same problem right now. Have you found a good solution?

VRonin

I don't think this is achievable without interlacing heavily model and view. Basically you have to break SOLID principles.

the idea would be:

the model rowCount() only ever returns the number of rows you can display
the actual number of rows in the model is used to determine the range of the QAbstactScrollArea in the view.
the model's data method (and setData if you want to make it editable) for index(5,0) should fetch the data of index(5+i,0) where i is the current offset of the scroll area to the first item.
once you scroll to a place you just emit the dataChanged for that index.

You could, in theory, implement this as a proxymodel+view but that would probably still be a drag on performance but if the source model is light enough then it's achievable.

Also, as mentioned above, rows of different sizes are a difficult step further ahead.

P.S.
Given:

we are talking about "if the user drags the thumb down"
my idea basically requires to solder model and view together
QML classes are not currently expandable (unless you recompile them)

The solution I'm suggesting is restricted to QtWidgets