[dev notes] virtual table approaches - a summary

[tantaman]

Virtualized scrolling turned out to be a surprisingly deep rabbithole.

Observations:

1. Size (in pixels) of the dataset
2. Windowing / Paged data loading
   1. Offset Pagination
   2. Cursor Pagination
   3. Expanding Limit
   4. All Data
3. Reactivity
4. Frame rates

Size (in pixels) of the Dataset

Related:

• https://twitter.com/tantaman/status/1725556143282368960
• https://medium.com/@manju_reddys/rendering-array-of-billion-of-records-at-60-f-s-in-angular-or-vanilla-js-2613e5983a10
• https://stackoverflow.com/questions/51890286/need-to-increase-the-allowable-maximum-height-for-a-div-element
• Million Rows example broken on Chrome adazzle/react-data-grid#786

The first surprise I ran into was dealing with very large datasets or medium sized datasets but with very large rows in terms of pixels. It turns out that browser has a max allowed height for elements. As in, if you try to make a thing too tall the browser will prevent you from doing so.

The max height is a problem since all virtual table libraries create an element the size of the dataset in order to get the browser to paint an accurate scroll bar.

E.g.,

const containerHeightPx = totalRows * rowHeight;

If this height exceeds the browser's max element height then it'll be capped. In other words, that line is really:

const containerHeightPx = Math.min(totalRows * rowHeight, BROWSER_MAX_ALLOWED_HEIGHT);

So any dataset that exceeds those heights will fail to scroll to the bottom.

To ground in examples:
Chrome max height: 33,554,428px

Means:

• For 1 million rows, each row must be < 33px tall
• If we have 100px tall rows, we can only have ~335,000 items
• 100,000 items would imply a max height of ~335px per row

Size (in pixels) - Conclusion

All of the virtual tables added in this repo work around the problem by using the clever solution documented here: https://dev.to/georgii/virtual-scrolling-of-content-with-variable-height-with-angular-3a52

I don't like the idea of maintaining a virtual table implementation, however. So the virtual tables are only available in the demos folder and not part of the materialite package.

Windowing / Paged Data Loading

There are a number of routes to choose here:

1. Offset Pagination
2. Cursor Pagination
3. Expanding Limit
4. Just load all Data

With Materialite, (4) is actually an acceptable path since we can incrementally maintain updates to that data. In other words, keeping 1 or 1 million rows up to date is about the same cost log2(1) vs log2(1_000_000) = 1 operation vs 19 operations.

The only issue with (4), however, is if the user wants to frequently change the filters they use to view the data. Re-materializing a massive view (if the filters return large amounts of data) is expensive in that case so, even with materialite, we do want the ability to do pagination so we only materialize the first page of the view.

1-million.mov

Offset Pagination

Offset pagination is the simplest to implement and the simplest for users of a virtual table to use.

All that is needed is a single onPage callback that accepts an offset. The virtual table calls this with the offset that starts the current window of results. This works for both paging backwards and forwards, simplifying things for the caller. The caller doesn't have to do a backwards fetch, they can always forward-fetch from the provided offest.

Unfortunately it is the least performant for a database to fulfill. An offset into a result set requires scanning all rows prior to the offset.

Cursor Pagination

This is difficult for users of a virtual table use as it requires implementing onNextPage and onPrevPage.

The hard part is onPrevPage. This requires fetching backwards from the current cursor. In other words, the source providing the data needs to understand how to iterate backwards over the collection of data backing the virtual table.

In SQL, this would mean swapping comparisons and orderings.

E.g.,

-- onPrevPage
SELECT * FROM foo WHERE cursored_field < ?cursor OR (cursored_filed = ?cursor_field AND id < ?cursor_id) ORDER BY cursored_field, id DESC

-- onNextPage
SELECT * FROM foo WHERE cursored_fied > ?cursor OR (cursored_field = ?cursor_field AND id > ?cursor_id) ORDER BY cursored_field, id ASC

Expanding Limit

The last option is that the virtual table keeps all old records in memory and ever-expands the limit. This keeps everything based on "forward fetches" or "onNextPage" while still using cursor pagination. We fetch the next page with the cursor of the end of the last page.

Reactivity

Reactivity throws some complicating factors in when it comes to processing deletes. For windowed queries, items may be deleted out of the window meaning we must re-fill the window. This will either require incrementally patching the window which means that the view must call back into the source for more data or re-running the query for the current window on removal of a row from the window.