Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

From: sqlite-users-boun...@sqlite.org [sqlite-users-boun...@sqlite.org] on behalf of Clemens Ladisch [clem...@ladisch.de] Sent: Wednesday, September 11, 2013 18:57 To: sqlite-users@sqlite.org Subject: Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 12 sep. 2013, at 07:20, "James K. Lowden" > wrote: On Tue, 10 Sep 2013 12:58:21 + Harmen de Jong - CoachR Group B.V. > wrote: I think the way I wrote our timings were not that clear,

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On Tue, 10 Sep 2013 12:58:21 + Harmen de Jong - CoachR Group B.V. wrote: > I think the way I wrote our timings were not that clear, since they > are definately exponentially. The numbers from my previous post refer > to the multiplier between the test cases. Just to make

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

Harmen de Jong - CoachR Group B.V. wrote: > http://www.coachrdevelopment.com/share/callstack_tree.html > > This shows most time is spend on sqlite3CodeRowTriggerDirect. I'd guess the actual culprit is the loop in getRowTrigger (which does not show up because it is inlined): /* It may be that

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

To get rid of the question of WHERE exactly the time is consumed, we did some profiling on the application that run the query (using the 1 tables test DB). As a result you will find an overview of time consumed per function (shown as percentage of the total time) at this link:

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 10 sep. 2013, at 21:24, "E.Pasma" > wrote: My suppositions that the time was spent in the execute step and that this has been fixed in the new release appeared both wrong. Thus I may be wrong again but I think to have an explanation now. It is

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 10 sep. 2013, at 21:24, "E.Pasma" wrote: > My suppositions that the time was spent in the execute step and that this has > been fixed in the new release appeared both wrong. Thus I may be wrong again > but I think to have an explanation now. > It is as Simon guesses

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 10 sep. 2013, at 21:24, "E.Pasma" wrote: > Op 10 sep 2013, om 19:48 heeft Simon Slavin het volgende geschreven: > >> >> On 10 Sep 2013, at 4:15pm, Harmen de Jong - CoachR Group B.V. >> wrote: >> >>> That is something we suspected too. We already

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

Op 10 sep 2013, om 19:48 heeft Simon Slavin het volgende geschreven: On 10 Sep 2013, at 4:15pm, Harmen de Jong - CoachR Group B.V. wrote: That is something we suspected too. We already made some tests where we timed the time needed for all memory allocations executed

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 10 Sep 2013, at 4:15pm, Harmen de Jong - CoachR Group B.V. wrote: > That is something we suspected too. We already made some tests where we timed > the time needed for all memory allocations executed in the entire operation. > In total for the 1 tables test this was

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 10 sep. 2013, at 16:44, "E.Pasma" wrote: > Op 10 sep 2013, om 16:36 heeft Harmen de Jong - CoachR Group B.V. het > volgende geschreven: > >> On 10 sep. 2013, at 16:16, "E.Pasma" wrote: >> >>> Op 10 sep 2013, om 11:37 heeft Harmen de Jong - CoachR

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

Op 10 sep 2013, om 16:36 heeft Harmen de Jong - CoachR Group B.V. het volgende geschreven: On 10 sep. 2013, at 16:16, "E.Pasma" wrote: Op 10 sep 2013, om 11:37 heeft Harmen de Jong - CoachR Group B.V. het volgende geschreven: I included 5 databases that we used for

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

> >> het volgende geschreven: > >>> I included 5 databases that we used for testing in this link: > http://wikisend.com/download/570088/test_databases.zip > >>> > >>> The query performed on these databases is: > >>> delete from A where id=1; > >> > >> I could not resist trying this but the tables

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

Sent from my iPad On 10 sep. 2013, at 17:04, "Keith Medcalf" wrote: >>> No, it is all about preparing, so there is no need to insert data. >>> When we perform the query "delete from A where id=1;" on the >>> databases from the zip file, we get the following timings: >>>

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 10 sep. 2013, at 16:16, "E.Pasma" wrote: > Op 10 sep 2013, om 11:37 heeft Harmen de Jong - CoachR Group B.V. het > volgende geschreven: >> I included 5 databases that we used for testing in this link: >> http://wikisend.com/download/570088/test_databases.zip >> >> The

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

Op 10 sep 2013, om 11:37 heeft Harmen de Jong - CoachR Group B.V. het volgende geschreven: I included 5 databases that we used for testing in this link: http://wikisend.com/download/570088/test_databases.zip The query performed on these databases is: delete from A where id=1; I could not

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 10 sep. 2013, at 15:41, "Igor Tandetnik" wrote: > Not exponential - polynomial. Between 500 and 1 the size of input > increases x20, so the time increase of x400 would be consistent with a > quadratic algorithm. Your observed measurements are even better than that.

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 9/10/2013 5:37 AM, Harmen de Jong - CoachR Group B.V. wrote: The time factors it takes on each database are as follows (where the time needed for the 500 tables was taken as starting point to calculate the other factors): 500 tables - 1x 1000 tables - 2.5x 5000 tables - 29x 1 tables -

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 10 sep. 2013, at 14:43, "E.Pasma" wrote: > The timings do not look truly exponential to me. It looks more as if there is > a graduated charge (NL: staffeltoeslag) on the time per table. For instance: > table 1 - 500 - 2 msec/table > table 501 - 1.000 - 3 msec/table >

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

Op 10 sep 2013, om 11:37 heeft Harmen de Jong - CoachR Group B.V. het volgende geschreven: On 9 sep. 2013, at 22:11, "E.Pasma" wrote: Ha, I did not mean the length of the names but the length of the hash table (NL: klutstabel), That is the number of buckets over

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 10 sep. 2013, at 11:37, "Harmen de Jong - CoachR Group B.V." wrote: > As you can see this is an exponential growth in time it takes to execte the > query. So far we're missing the point of why this growth should be > exponential. We tried some further debugging and it

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 9 sep. 2013, at 22:11, "E.Pasma" wrote: > Ha, I did not mean the length of the names but the length of the hash table > (NL: klutstabel), That is the number of buckets over which the hash values > are distributed. I looked some further in the code and now believe that

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

Op 9 sep 2013, om 10:06 heeft Harmen de Jong - CoachR Group B.V. het volgende geschreven: Our table and column names are not too long either as E.Pasma suggests. Ha, I did not mean the length of the names but the length of the hash table (NL: klutstabel), That is the number of buckets

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 7 sep. 2013, at 04:45, "David de Regt" wrote: > Mayhaps the CROSS JOIN trick is your friend in this case, if you can be > pretty sure of the correct direction of the join order. :) In the examples I gave it was actually about a simple delete query from one table without

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

The developers choose the C type 'int' to represent the hash value. Possibly this is too small for your case? Op 6 sep 2013, om 22:00 heeft Harmen de Jong - CoachR Group B.V. het volgende geschreven: On 6 sep. 2013, at 20:09, "Kevin Benson" wrote: Dr. Hipp does

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

Mayhaps the CROSS JOIN trick is your friend in this case, if you can be pretty sure of the correct direction of the join order. :) -David -Original Message- From: sqlite-users-boun...@sqlite.org [mailto:sqlite-users-boun...@sqlite.org] On Behalf Of James K. Lowden Sent: Friday,

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

Two things: 1. The longer the table names, the longer it will take to compute the hash of each table name. 2. Because the entire schema must be reprocessed after each change, all the table names will be rehashed after each table has been created. Creating 10,000 tables will result in re-reading

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 6 Sep 2013, at 9:00pm, Harmen de Jong - CoachR Group B.V. wrote: > as dr. Hipp states in this thread, the tables are stored in a hash. Therefore > I would not expect a large performance decrease on large number of tables at > all, or am I missing something? The /names/

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 6 sep. 2013, at 20:09, "Kevin Benson" wrote: > Dr. Hipp does a little bit of explaining on this topic, generally, in his > replies on this thread: > > http://www.mail-archive.com/sqlite-users@sqlite.org/msg78602.html Thanks for pointing me to that thread, but as dr.

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On Fri, Sep 6, 2013 at 1:29 PM, Harmen de Jong - CoachR Group B.V. < har...@coachr.com> wrote: > On 6 sep. 2013, at 18:42, "Igor Tandetnik" wrote: > > If I recall correctly, query planner's behavior is worst-case quadratic > in the number of tables participating in the query.

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 6 sep. 2013, at 18:42, "Igor Tandetnik" wrote: > If I recall correctly, query planner's behavior is worst-case quadratic in > the number of tables participating in the query. This includes tables > mentioned directly, and also those pulled in indirectly via views,

Re: [sqlite] Query preperation time does not scale linearly with growth of no. of tables

On 9/6/2013 10:35 AM, Harmen de Jong - CoachR Group B.V. wrote: We ran into an issue where specific queries are geting non linearly slower when the total number of tables grows. If I recall correctly, query planner's behavior is worst-case quadratic in the number of tables participating in

[sqlite] Query preperation time does not scale linearly with growth of no. of tables

We ran into an issue where specific queries are geting non linearly slower when the total number of tables grows. Example 1 (not slow): Database has table A Database has 1,000 other tables with foreign key to table A Row is deleted from table A (no deletion of actual data in other