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

[Keith Medcalf]

> When I have 1  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 2 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  FROM  WHERE  OFFSET 
" you are asking SQLite to run the base query and discard  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  OFFSET x LIMIT y, just the database 
engine skips the rows for you.





___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

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

[Jens Alfke]

> On Feb 1, 2017, at 7:18 AM, Richard Hipp  wrote:
> 
> See also 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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

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

[Richard Hipp]

On 2/1/17, Igor Tandetnik  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
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

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

[Igor Tandetnik]

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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

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

[Simon Slavin]

On 1 Feb 2017, at 2:50pm, Anthrathodiyil, Sabeel (S.)  
wrote:

> When I have 1  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 2 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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

[sqlite] 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,
FileTypeINTEGER 
DEFAULT 0,
GenreID   INTEGER 
DEFAULT 0,
ArtistID 
INTEGER DEFAULT 0,
ComposerID   INTEGER 
DEFAULT 0,
AlbumID  INTEGER 
DEFAULT 0,
TrackIDINTEGER 
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 = 1LL

When I have 1  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 2 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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users