SQLite - SELECT query slowing down while fetching from higher offset.

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

SQLite - SELECT query slowing down while fetching from higher offset.

Anthrathodiyil, Sabeel (S.)
Hi,
I am facing issue with SQLite performance when having more records in the table and fetching from higher offsets, though I have proper index in place. Using SQLite version 3.7.10 running on ARM Cortex A5 processor.

Here is my schema (relevant table and index)  and query

CREATE TABLE FileTable(
                FileID                                                     INTEGER PRIMARY KEY,
                FileName                                             TEXT DEFAULT NULL,
                FileType                                                INTEGER DEFAULT 0,
                GenreID                                               INTEGER DEFAULT 0,
                ArtistID                                                 INTEGER DEFAULT 0,
                ComposerID                                       INTEGER DEFAULT 0,
                AlbumID                                              INTEGER DEFAULT 0,
                TrackID                                                INTEGER DEFAULT 0,
                TrackName                                 TEXT DEFAULT NULL,
                TrackDuration                                   INTEGER DEFAULT 0,
                InValidFlag                                         INTEGER DEFAULT 0
)
CREATE INDEX Idx_TrackName_OnFileTable ON FileTable(FileType, TrackName COLLATE NOCASE ASC);

SELECT FileID , TrackName, FileType, InValidFlag FROM  FileTable  WHERE FileType = 1  AND TrackName  <>""  ORDER BY TrackName  COLLATE NOCASE LIMIT 10 OFFSET 19950

database connection opened with flags (SQLITE_OPEN_READWRITE | SQLITE_OPEN_FULLMUTEX)
PRAGMA journal_mode = MEMORY
PRAGMA synchronous = FULL
PRAGMA temp_store = 2
PRAGMA cache_size = 10000LL

When I have 10000  records in the table, it takes 20 ms to fetch 10 items from offset 0, and it increases to 220 ms to fetch 10 items from offset 9900.
While I have 20000 records in the table, it takes 20 ms to fetch 10 items from offset 0, 440 ms for 10 items from offset 9600 and 720 ms for 10 items from offset 19950.

My understanding is, since index table is created in the sorted order, time to fetch from any offset should be the same. Why is the time to fetch increasing when fetching from higher offset? Why is fetching time increasing for the same offset when more records in the table? Is this expected behavior from SQLite or is there something wrong with schema/index/query?

Best regards,
Sabeel
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: SQLite - SELECT query slowing down while fetching from higher offset.

Simon Slavin-3

On 1 Feb 2017, at 2:50pm, Anthrathodiyil, Sabeel (S.) <[hidden email]> wrote:

> When I have 10000  records in the table, it takes 20 ms to fetch 10 items from offset 0, and it increases to 220 ms to fetch 10 items from offset 9900.
> While I have 20000 records in the table, it takes 20 ms to fetch 10 items from offset 0, 440 ms for 10 items from offset 9600 and 720 ms for 10 items from offset 19950.
>
> My understanding is, since index table is created in the sorted order, time to fetch from any offset should be the same.

Thanks for your schema listing, timings, and the thorough description of your problem.  It saved a lot of time.  Your INDEX and SELECT look fine, and the timings you give are plausible.  I don’t think you’re doing anything wrong.

When using an OFFSET clause SQLite has to do the following:

1) Find the first record in the index which fits the WHERE clause
2) Skip to the OFFSET number of rows after it

If the index was arranged as one continuous fixed-width list, it would be easy to skip 19950 entries.  But it’s not, it’s a binary tree.  So SQLite has to iterate through those 19950 entries in tree form, and the time to do that is roughly proportional to the OFFSET number.

Hope this helps.  Does it look reasonable to you ?

Simon.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: SQLite - SELECT query slowing down while fetching from higher offset.

Igor Tandetnik-2
In reply to this post by Anthrathodiyil, Sabeel (S.)
On 2/1/2017 9:50 AM, Anthrathodiyil, Sabeel (S.) wrote:
> I am facing issue with SQLite performance when having more records in the table and fetching from higher offsets

https://www.sqlite.org/cvstrac/wiki?p=ScrollingCursor

Performance of a query with OFFSET N is roughly equivalent to that
without OFFSET clause, where you retrieve and discard first N rows.
SQLite has no means to jump directly to row N.

> My understanding is, since index table is created in the sorted order, time to fetch from any offset should be the same.

Your understanding is incorrect. Imagine that you have a phonebook, with
people's names listed in alphabetic order. This makes it easy to find an
entry for a particular name, but doesn't help at all with finding an
entry number N; for that, you still have to start from the first entry,
and count them one by one.
--
Igor Tandetnik

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: SQLite - SELECT query slowing down while fetching from higher offset.

Richard Hipp-3
On 2/1/17, Igor Tandetnik <[hidden email]> wrote:
> On 2/1/2017 9:50 AM, Anthrathodiyil, Sabeel (S.) wrote:
>> I am facing issue with SQLite performance when having more records in the
>> table and fetching from higher offsets
>
> https://www.sqlite.org/cvstrac/wiki?p=ScrollingCursor

See also https://www.sqlite.org/rowvalue.html#scrolling_window_queries

Note that to use the row-value feature, you'll need to update to a
newer version of SQLite.  But you should do that anyway, since newer
versions will be more than twice the speed of 3.7.10 and will be fully
backwards compatible.

--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: SQLite - SELECT query slowing down while fetching from higher offset.

Jens Alfke-2

> On Feb 1, 2017, at 7:18 AM, Richard Hipp <[hidden email]> wrote:
>
> See also https://www.sqlite.org/rowvalue.html#scrolling_window_queries <https://www.sqlite.org/rowvalue.html#scrolling_window_queries>

This approach comes with a major caveat that’s not mentioned in the text: the data set cannot contain rows that have the same ‘order by’ values. From the example:

        SELECT * FROM contacts
         WHERE (lastname,firstname) > (?1,?2)
         ORDER BY lastname, firstname
         LIMIT 7;
        If the lastname and firstname on the bottom row of the previous screen are bound to ?1 and ?2,
        then the query above computes the next 7 rows.

This makes the assumption that (lastname, firstname) is unique in the table, i.e. the there are no two people with the same last and first names. That’s pretty likely in a personal address book, very unlikely in a phone book!

If there are duplicates, then if one page of results ends in the middle of a run of duplicates, the next page will skip the rest of the duplicates. That’s data loss. Sad!

The best solution is to add criteria to the ordering/comparison to make every row unique. For example, use (lastname, firstname, customerid). If you don’t have a unique value to use, you could always use `rowid`.

If that isn’t feasible (you have a no-rowid table?) you have to fall back to using “>=“ instead of “>” in the test, and then manually skipping the initial row(s) that already appeared in the last page. (And this in turn will fall if there’s a run of duplicate rows that’s larger than your page size … it’s probably better just to add a rowid or some other unique integer and go back to solution 1!)

—Jens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: SQLite - SELECT query slowing down while fetching from higher offset.

Keith Medcalf
In reply to this post by Anthrathodiyil, Sabeel (S.)

> When I have 10000  records in the table, it takes 20 ms to fetch 10 items
> from offset 0, and it increases to 220 ms to fetch 10 items from offset
> 9900.
> While I have 20000 records in the table, it takes 20 ms to fetch 10 items
> from offset 0, 440 ms for 10 items from offset 9600 and 720 ms for 10
> items from offset 19950.
>
> My understanding is, since index table is created in the sorted order,
> time to fetch from any offset should be the same. Why is the time to fetch
> increasing when fetching from higher offset? Why is fetching time
> increasing for the same offset when more records in the table? Is this
> expected behavior from SQLite or is there something wrong with
> schema/index/query?

When you do a "SELECT <something> FROM <somewhere> WHERE <conditions> OFFSET <x>" you are asking SQLite to run the base query and discard <x> result rows.  So the time taken to perform the query is the pretty much the same as if you had just selected all the data and discarded it yourself (by not fetching the rows you did not want).

That is:

row=0
prepare(statement)
while row < x:
   step(statement)
   row++
row=0
while row < y
   step(statement)
   ... retrieve and process row data ...
finalize(statement)

is the same thing as saying <statement> OFFSET x LIMIT y, just the database engine skips the rows for you.





_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users