Expected number of requests for ORDER BY queries on indexed columns

[johtso]

So I seem to be ending up with quite a lot of requests to query my indexed column, more than I would have expected. Would love to know whether it looks like I might be doing something wrong or whether that's just the expected behaviour!

This is how I'm making the database:

CREATE TABLE images(
  id TEXT NOT NULL,
  server TEXT NOT NULL,
  secret TEXT NOT NULL,
  original_secret TEXT NOT NULL,
  width INTEGER NOT NULL,
  height INTEGER NOT NULL,
  faves INTEGER NOT NULL,
  comments INTEGER NOT NULL,
  views INTEGER NOT NULL
);

.separator ' '
.import shuffled_api_dump.txt images

create index idx_views
    on images(views);

create index idx_faves
    on images(faves, views);

pragma journal_mode = delete; -- to be able to actually set page size
pragma page_size = 1024; -- trade off of number of requests that need to be made vs overhead.
vacuum; -- reorganize database and apply changed page size

and then I'm splitting it with create_db.sh.

A query like select * from images order by views desc limit 20 results in 47 queries.

Database has about 5 million rows.

Does that sound right?

[johtso]

Aha, I think I've just learnt about the concept of "covering indexes".

[phiresky]

Even without a covering index it sounds more than expected -

It should be maybe 3 requests for initialization, then one request per b-tree depth (you can use sqlite3_analyzer to see info on b-tree depth). The depth should be maybe 3 to 6. Without a covering index it traverses two b-trees. so that should be max 3 + 2*6 requests.

try increasing the page size to 32kB and also try using explain query plan to see it uses the correct index

[phiresky]

sadly there's no integrated to analyze exactly which pages sqlite reads and why

[phiresky]

so that should be max 3 + 2*6 requests.

Actually I guess you have to add one b-tree search and one request per actual row returned (without covering index) since the content is not ordered by the index. so then it is closer to your number of queries.

[johtso]

Thanks for the thoughts @phiresky !

Just to explain the use case..

I'm basically going to be paging through ranges of rows, sorted either randomly (the inherent ordering as I loaded the rows randomly), by views ascending, by views descending or by faves descending.

I just tried making the indexes cover all the fields and things got even worse!

create index idx_views
    on images(views, faves, comments, id, server, secret, original_secret, width, height);

create index idx_faves
    on images(faves, views, comments, id, server, secret, original_secret, width, height);

pragma journal_mode = delete;
pragma page_size = 8192;
vacuum;

select * from images order by faves desc limit 20 offset 300000 took over 2000 requests.
query plan: [{"id":7,"parent":0,"notused":0,"detail":"SCAN TABLE images USING COVERING INDEX idx_faves"}]

Strangely, even if I change the index to be descending like so (assuming there's a reason why we can't efficiently navigate the index in a reverse direction):

create index idx_faves
    on images(faves desc, views desc, comments desc, id, server, secret, original_secret, width, height);

The request count is still higher when querying descending than ascending..
select * from images order by faves asc limit 20 offset 300000: ~35 req
select * from images order by faves desc limit 20 offset 300000: 2000+ req

[johtso]

Also when I upped the offset to 3,000,000 it completely died with a Error: SQLite: database disk image is malformed.. and now fails with that error even when I bring the offset down again.

If I open it in an incognito window the lower offset query works fine again. I'm guessing there's something corrupted in the worker's cache or something? Very strange..

[phiresky]

Using offset+limit for pagination is in general a bad idea (with most SQL engines afaik), since in many cases has to iterate through the whole table / index to find where it has to start (limit X offset Y is basically equivalent to limit X+Y offset 0). There's some articles about this e.g. https://use-the-index-luke.com/no-offset / https://use-the-index-luke.com/sql/partial-results/fetch-next-page . Looks like SQLite has specific optimization for the ascending order that doesn't apply to the descending one - not sure why.

Better solution for pagination is to use the sorting key in a WHERE clause (e.g. for the second page `select * from images order by faves desc where faves <= last_seen_min_faves limit 20). It's kinda annoying because you'll add more logic to handle duplicates.

[phiresky]

The caching should only be in RAM as far as I remember.. does it still happen when you "disable cache" in browser dev tools?

[johtso]

Those are some really useful pointers, thank you! Will do some reading up on better ways to handle pagination. I guess with the approach of "filtering based on the highest seen value that you're sorting on", you could still get into a pickle if you have a lot of rows with the same value. You'd still have the same problem of paging through those rows just on a smaller scale.

I guess I really want to be able to use a cursor based approach.

The caching should only be in RAM as far as I remember.. does it still happen when you "disable cache" in browser dev tools?

Disabling the cache seemed to fix it..

I'm thinking my use case might not be a great fit for this as I'm not really querying the data, I'm just paging through it with various sorting applied.

It might make more sense just to take a lower level approach and store the data as rows in a file padded to all have the same length. Then I can just use range queries to directly access ranges of rows.
I'd just have to duplicate the data for each sorting I want to be able to consume it in, which I guess is pretty much what you end up doing if you make a fully covering index in sqlite..

[phiresky]

you could still get into a pickle if you have a lot of rows with the same value

You could still use offset to offset within the previous value of faves as a compromise (as you already thought of i guess). For example with select *, row_number() over (partition by faves) as next_offset from images where faves <= last_faves order by faves desc limit 20 offset $offset; then in the pagination token would be something like (last_faves=last_results[-1].faves, $offset=last_results[-1].next_offset)

I'm just paging through it with various sorting applied.

That (in general) sounds like a fairly good use case for SQLite. Yeah the results are probably going to be similar like manually creating your own "database" format. Probably you should go whatever is less work.

[phiresky]

as another alternative, since you know beforehand which keys you want to sort and paginate by you could also create fully duplicated tables that have a primary key that directly corresponds to the rank that image has in the corresponding order e.g. insert into images_by_faves select row_number(), * from images order by faves desc then you can directly query by the primary key in that table, and the pagination token is simply the int primary key

[johtso]

I decided to persevere, and I think I've managed to get some efficient queries!

Index now looks like this:

create index idx_faves
    on images(faves desc, views desc, comments desc, id desc, server, secret, original_secret, width, height);

async function cursorQuery(worker: WorkerHttpvfs, limit: number, cursor?: Cursor | null, initial?: boolean): Promise<{ images: Image[], cursor: Cursor }> {
  let images;
  if (limit < 1) {
    throw "limit must be a positive number";
  }

  if (cursor) {
    let [faves, views, comments, id] = cursor;
    // if this is the initial data load we want to include the current image
    let comparator = initial ? "<=" : "<";
    images = await worker.db.query(`
      select
        * from images
      where
        (faves, views, comments, id) ${comparator} (${faves}, ${views}, ${comments}, '${id}')
      order by
        faves desc, views desc, comments desc, id desc
      limit ${limit};`) as Image[];
  } else {
    images = await worker.db.query(`
      select
        * from images
      order by
        faves desc, views desc, comments desc, id desc
      limit ${limit};`) as Image[];
  }

  let lastImage = images[images.length - 1];
  let newCursor: Cursor = [lastImage.faves, lastImage.views, lastImage.comments, lastImage.id];
  return {
    'images': images,
    'cursor': newCursor
  }
}

The key being a fully covering index including the unique ID, and then using all those columns as a cursor.

Skipping millions of results still uses minimal requests!

What I'm currently still stuck on is efficiently doing the same using rowid.

Doing something like this results in A LOT of requests:

    images = await worker.db.query(`
      select
        * from images
      where rowid > 2000000
      limit ${limit};`) as Image[];

I was trying to avoid the overhead of duplicating all the data again in another covering index.. thinking I could just use the rowid to achieve a random ordering..

[johtso]

I have about 350MB of data in CSV.

With these indexes that ends up being about 1.2GB of sqlite..

create index idx_views
    on images(views desc, faves desc, comments desc, id desc, server, secret, original_secret, width, height, random_id);

create index idx_faves
    on images(faves desc, views desc, comments desc, id desc, server, secret, original_secret, width, height, random_id);

create index idx_random
    on images(random_id, views, faves, comments, id, server, secret, original_secret, width, height, bookid);

This is pushing it above github pages limits.

Now I'm wondering if maybe, rather than all these fully covering indexes I could instead just index the id.. and then make a second request to get the full rows based on the id.

Edit:

So gave that a go, and it requires about 2 requests for every row returned. Not the worst, but not ideal. I'm guessing you're not going to get better than that?

      select
        views, faves, comments, id, server, secret, original_secret, width, height, random_id from images
      where random_id in (
        select
          random_id from images
        where
          (faves, views, comments, id) > (${faves}, ${views}, ${comments}, '${id}')
        order by
          faves desc, views desc, comments desc, id desc
        limit ${limit}
      )
      order by faves desc, views desc, comments desc, id desc;

[phiresky]

Nice, good idea to use the other columns as differentiating factors for the pagination. Though probably just using the (views, id) is enough since ID is unique in any case?

Doing something like this results in A LOT of requests:

Did you try adding a order by rowid asc to that? There's no guarantee about order if you don't explicitly state it, and thus it might not optimize the index search without it. I also don't exactly understand what you want to accomplish with your random_id.

Now I'm wondering if maybe, rather than all these fully covering indexes I could instead just index the id..

I don't fully understand what you mean but wouldn't that be the same thing as just having the index be non-covering with the columns (views desc, id) but still querying all columns?

I also don't exactly understand what your random_id does

[johtso]

explicitly ordering by rowid was key, thank you!

All my queries are performing really nicely now, with random start points, cursor based pagination, and various filters and sorting. Awesome!