Re: [sqlite] programmatic way of determining fragmentation?

[Max Vlasov]

On Sat, Oct 23, 2010 at 2:28 AM, Dustin Sallings  wrote:

>
> On Oct 22, 2010, at 15:12, Max Vlasov wrote:
>
> > As for your initial question, I think fragmentation evaluation is
> possible
> > with the help of VFS. I'd keep a total sum of of absolute difference
> between
> > consequent read offsets for xRead operation. In this case if some xRead
> > request reads 1024 bytes at the 4096 offset and the next xRead reads
> > something at 5120 (4096 +1024) this will add 0 to the sum, but if the
> next
> > read something at 8192, this will add 3072 = (8192 - (4096 +1024)). If
> this
> > implemented, you will be able to see how this value changes for some of
> your
> > SELECT and maybe evaluate it on per record basis. If it's more like some
> > threshold value, ok, peform VACUUM
>
>
> This sounds like a *really* awesome idea.  I know exactly what
> operations I'm doing that *shouldn't* generally seek and I can keep some
> stats on that.
>
>

Just thought that we should take also sqlite internal cache into account
since if the page is cached there won't be reading for the records from that
page and it can affect the logic of the evaluator, so the algorithm should
track also the total size of the reading.

I don't know whether it worth or not but maybe some future version of sqlite
would provide us with vfs counters (statistics) in some form
(sqlite4_vfscounters?). At least read/write * seek/size counters would be
useful.

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

Re: [sqlite] programmatic way of determining fragmentation?

[Nicolas Williams]

On Sat, Oct 23, 2010 at 02:12:19AM +0400, Max Vlasov wrote:
> As for your initial question, I think fragmentation evaluation is possible
> with the help of VFS. I'd keep a total sum of of absolute difference between
> consequent read offsets for xRead operation. In this case if some xRead
> request reads 1024 bytes at the 4096 offset and the next xRead reads
> something at 5120 (4096 +1024) this will add 0 to the sum, but if the next
> read something at 8192, this will add 3072 = (8192 - (4096 +1024)). If this
> implemented, you will be able to see how this value changes for some of your
> SELECT and maybe evaluate it on per record basis. If it's more like some
> threshold value, ok, peform VACUUM

SQLite knows when it's generating full table scans, so it could arrange
to detect non-sequential I/O for just that table's B-Tree (random I/O
might result anyways if the query is a join, say), gather rudimentary
statistics (say, the number of non-sequential page reads for the table
scan) and report fragmentation via a pragma.

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

Re: [sqlite] programmatic way of determining fragmentation?

[Dustin Sallings]

On Oct 22, 2010, at 15:12, Max Vlasov wrote:

> As for your initial question, I think fragmentation evaluation is possible
> with the help of VFS. I'd keep a total sum of of absolute difference between
> consequent read offsets for xRead operation. In this case if some xRead
> request reads 1024 bytes at the 4096 offset and the next xRead reads
> something at 5120 (4096 +1024) this will add 0 to the sum, but if the next
> read something at 8192, this will add 3072 = (8192 - (4096 +1024)). If this
> implemented, you will be able to see how this value changes for some of your
> SELECT and maybe evaluate it on per record basis. If it's more like some
> threshold value, ok, peform VACUUM


This sounds like a *really* awesome idea.  I know exactly what 
operations I'm doing that *shouldn't* generally seek and I can keep some stats 
on that.

Thanks a lot.

-- 
Dustin Sallings

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

Re: [sqlite] programmatic way of determining fragmentation?

[Max Vlasov]

On Thu, Oct 21, 2010 at 11:32 AM, Dustin Sallings  wrote:

>
>Mostly, I want to have an idea how fragmented I am.  My app can
> tremendously wreck a sqlite table right now to the point where a
> reconstruction (vacuum, etc...) is the difference between three hours and
> one minute.  I'd like to know when things are getting bad.
>
>If no such thing exists, I can build it, but I would imagine it's
> been done before.
>
>
Dustin, thanks for your interesting post, always wondered how the internal
sqlite fragmentation can affect the performance overall. I did some tests
today and the numbers are interesting

Windows 7, 64 bit, sqlite 3.6.10, 3.7.2

The table

CREATE TABLE [TestTable] (
[Id] INTEGER PRIMARY KEY AUTOINCREMENT,
[Text] TEXT)

is filled with a repeated query about 1M times

INSERT INTO TestTable (id, text) VALUEs (abs(random() % (1 << 48)),
'12345678901234567...') {508 symbols total in the string to make it more
like 2G/5m records ratio Dustin posted}

The db now is about 1G in size.

This test will probably produce very fragmented main B-tree since every next
record has a "random" rowid while at the same time records as they added are
placed in consequent pages. The insert took about an hour (for obvious
reasons)

So, after that tests, querying SELECT * FROM TestTable LIMIT ... produces an
interesting results (I made sure every next open clears the windows system
cache with this trick:
http://www.mail-archive.com/sqlite-users@sqlite.org/msg54234.html)

SELECT * FROM TestTable LIMIT 1
reads about 10M from the db, takes about 2 minutes to run

SELECT * FROM TestTable LIMIT 5
reads about 50M from the db, takes about 10 minutes to run

SELECT * FROM TestTable LIMIT 10
this was was too long to wait so probably SELECT * FROM TestTable would
indeed take hours.

Actually these are expected results. Windows system cache predictions fails
since sqlite really does almost completely random read at different file
offsets.

As for your initial question, I think fragmentation evaluation is possible
with the help of VFS. I'd keep a total sum of of absolute difference between
consequent read offsets for xRead operation. In this case if some xRead
request reads 1024 bytes at the 4096 offset and the next xRead reads
something at 5120 (4096 +1024) this will add 0 to the sum, but if the next
read something at 8192, this will add 3072 = (8192 - (4096 +1024)). If this
implemented, you will be able to see how this value changes for some of your
SELECT and maybe evaluate it on per record basis. If it's more like some
threshold value, ok, peform VACUUM

back to the tests, can someone perfom similar tests on linux? I heard it
have a different cache system, i wonder whether it can show better
performance in this artificial tests. Thanks in advance

Max Vlasov
maxerist.net
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] programmatic way of determining fragmentation?

[Jim Wilcoxson]

On Thu, Oct 21, 2010 at 1:27 PM, Dustin Sallings  wrote:

>
> On Oct 21, 2010, at 10:05, Pavel Ivanov wrote:
>
> > I think it's not related to fragmentation, but to fill percentage of
> > b-tree pages. I guess your reconstructed table is much less in total
> > size than your initial one. Also does changing cache_size changes
> > above numbers?
>
> Interesting.  We have been using sqlite3_analyze on some tests and
> finding that we can get our dbs very fragmented.  It doesn't report fill
> size as far as I can tell.
>
>
It does report fill percentage, as "Bytes of user payload stored"


>We'll play around with cache_size to see if that does anything
> useful for us in the meantime.
>
> > What size do these tables have?
>
> About 2.2GB with about 4 million rows.
>
> > What bottleneck appears to be in 3-hour query execution? Is it disk
> thrashing?
>
> Yes.
>
>I've tried different strategies in the past.  Vacuum and the rebuild
> both seem to help quite a bit.  I don't understand the file layout all that
> well right now, so I don't completely understand how the index is traversed.
>

How much memory do you have in the test system?  Because if you rebuild, you
are loading the whole db into the filesystem cache, if it'll fit.  Then you
are no longer accessing the file randomly.  You might get the same
performance increase by just catting the db (sequentially reading it into
the FS cache) and then running your test.

It's a good idea to make sure you purge your filesystem cache before running
any performance tests related to fragmentation.  On OSX, it's purge.  On
Linux, its echo 3>/proc/sys/vm/drop_caches.  Otherwise, it's easy to fool
yourself.

But I agree with you that fragmentation can be a big issue, depending on how
the data is loaded and how it is subsequently accessed.

Jim
--
HashBackup, LLC
http://sites.google.com/site/hashbackup
**
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] programmatic way of determining fragmentation?

[Dustin Sallings]

On Oct 21, 2010, at 10:05, Pavel Ivanov wrote:

> I think it's not related to fragmentation, but to fill percentage of
> b-tree pages. I guess your reconstructed table is much less in total
> size than your initial one. Also does changing cache_size changes
> above numbers?

Interesting.  We have been using sqlite3_analyze on some tests and 
finding that we can get our dbs very fragmented.  It doesn't report fill size 
as far as I can tell.

We'll play around with cache_size to see if that does anything useful 
for us in the meantime.

> What size do these tables have?

About 2.2GB with about 4 million rows.

> What bottleneck appears to be in 3-hour query execution? Is it disk thrashing?

Yes.

I've tried different strategies in the past.  Vacuum and the rebuild 
both seem to help quite a bit.  I don't understand the file layout all that 
well right now, so I don't completely understand how the index is traversed.

-- 
Dustin Sallings

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

Re: [sqlite] programmatic way of determining fragmentation?

[Pavel Ivanov]

>        Select * from a table took just slightly under three hours.
>        Select * from a reconstructed table (insert into select from) in a new 
> database took 57 seconds.

I think it's not related to fragmentation, but to fill percentage of
b-tree pages. I guess your reconstructed table is much less in total
size than your initial one. Also does changing cache_size changes
above numbers? What size do these tables have? What bottleneck appears
to be in 3-hour query execution? Is it disk thrashing?


Pavel

On Thu, Oct 21, 2010 at 12:38 PM, Dustin Sallings  wrote:
>
> On Oct 21, 2010, at 9:27, Simon Slavin wrote:
>
>> Have you actually demonstrated this ?  In other words do you have an 
>> operation that's really 'too slow', but after a VACUUM it's fast enough ?
>
>
>        Yes.
>
>        Select * from a table took just slightly under three hours.
>
>        Select * from a reconstructed table (insert into select from) in a new 
> database took 57 seconds.
>
> --
> Dustin Sallings
>
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] programmatic way of determining fragmentation?

[Simon Slavin]

On 21 Oct 2010, at 5:38pm, Dustin Sallings wrote:

> On Oct 21, 2010, at 9:27, Simon Slavin wrote:
> 
>> Have you actually demonstrated this ?  In other words do you have an 
>> operation that's really 'too slow', but after a VACUUM it's fast enough ?
> 
>   Yes.
> 
>   Select * from a table took just slightly under three hours.
> 
>   Select * from a reconstructed table (insert into select from) in a new 
> database took 57 seconds.

Okay.

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

Re: [sqlite] programmatic way of determining fragmentation?

[Dustin Sallings]

On Oct 21, 2010, at 9:27, Simon Slavin wrote:

> Have you actually demonstrated this ?  In other words do you have an 
> operation that's really 'too slow', but after a VACUUM it's fast enough ?


Yes.

Select * from a table took just slightly under three hours.

Select * from a reconstructed table (insert into select from) in a new 
database took 57 seconds.

-- 
Dustin Sallings

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

Re: [sqlite] programmatic way of determining fragmentation?

[Simon Slavin]

On 21 Oct 2010, at 5:21pm, Dustin Sallings wrote:

>   Those provide some info, but not the specific info I'm having problems 
> with right now.  I have too many non-sequential pages and it's making my 
> application run a couple of orders of magnitude slower than a fresh DB.

Have you actually demonstrated this ?  In other words do you have an operation 
that's really 'too slow', but after a VACUUM it's fast enough ?

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

Re: [sqlite] programmatic way of determining fragmentation?

[Dustin Sallings]

On Oct 21, 2010, at 7:52, Roger Binns wrote:

> You'll need to read the docs on the file format:
> 
>  http://www.sqlite.org/fileformat.html
>  http://www.sqlite.org/fileformat2.html
> 
> - From that you can determine a measure of how bad the fragmentation is, and
> your code can be quick and crude.


I've seen this, and that's my last resort.  I figured I'd ask because 
it feels like something someone would have done other than sqlite3_analyzer.

Thanks.

-- 
Dustin Sallings

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

Re: [sqlite] programmatic way of determining fragmentation?

[Dustin Sallings]

On Oct 21, 2010, at 1:00, Kees Nuyt wrote:

> PRAGMA page_count; and PRAGMA freelist_count; will give you
> some info, but not as much as sqlite3_analyzer.
> It might be enough in your case.

Those provide some info, but not the specific info I'm having problems 
with right now.  I have too many non-sequential pages and it's making my 
application run a couple of orders of magnitude slower than a fresh DB.

> Running a full analysis takes quite some time, you might as
> well start a VACUUM periodically. I would suggest to run it
> with half the frequency you intend to run the analysis. That
> way the time spent to this kind of housekeeping will be
> about the same.

We're not measuring it taking too long at this point.  We have a lot of 
application-specific optimizations we could perform if we had a bit more 
information.

> And you could consider
> PRAGMA auto_vacuum =  0 | NONE | 1 | FULL | 2 | INCREMENTAL;


The problem with auto_vacuum is that it's documented to make the 
problem worse.

-- 
Dustin Sallings

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

Re: [sqlite] programmatic way of determining fragmentation?

[Roger Binns]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

On 10/21/2010 12:32 AM, Dustin Sallings wrote:
>   Mostly, I want to have an idea how fragmented I am.

You'll need to read the docs on the file format:

  http://www.sqlite.org/fileformat.html
  http://www.sqlite.org/fileformat2.html

- From that you can determine a measure of how bad the fragmentation is, and
your code can be quick and crude.

Roger
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkzAU7UACgkQmOOfHg372QQRkwCfUFLhRUwAVzLb1dOUOkADKl+s
XHQAoI3NtKQJ/n+vk6CdcBc45/RPNTs5
=T4ik
-END PGP SIGNATURE-
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] programmatic way of determining fragmentation?

[Kees Nuyt]

On Thu, 21 Oct 2010 00:32:28 -0700, Dustin Sallings
 wrote:

>
> I realize sqlite3_analyzer will give me some good
> data for general use, but I'd like to be able to
> do this from within my app.  Does anyone have a
> lib-like thing I can use, or an internal sqlite API
> that can help me out here?
>
> Mostly, I want to have an idea how fragmented I am.
> My app can tremendously wreck a sqlite table right
> now to the point where a reconstruction (vacuum, etc...)
> is the difference between three hours and one minute.
> I'd like to know when things are getting bad.

PRAGMA page_count; and PRAGMA freelist_count; will give you
some info, but not as much as sqlite3_analyzer.
It might be enough in your case.

Running a full analysis takes quite some time, you might as
well start a VACUUM periodically. I would suggest to run it
with half the frequency you intend to run the analysis. That
way the time spent to this kind of housekeeping will be
about the same.

And you could consider
PRAGMA auto_vacuum =  0 | NONE | 1 | FULL | 2 | INCREMENTAL;

> If no such thing exists, I can build it, but I would
> imagine it's been done before.
-- 
  (  Kees Nuyt
  )
c[_]
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

[sqlite] programmatic way of determining fragmentation?

[Dustin Sallings]

I realize sqlite3_analyzer will give me some good data for general use, 
but I'd like to be able to do this from within my app.  Does anyone have a 
lib-like thing I can use, or an internal sqlite API that can help me out here?

Mostly, I want to have an idea how fragmented I am.  My app can 
tremendously wreck a sqlite table right now to the point where a reconstruction 
(vacuum, etc...) is the difference between three hours and one minute.  I'd 
like to know when things are getting bad.

If no such thing exists, I can build it, but I would imagine it's been 
done before.

-- 
Dustin Sallings

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