Time scale on INSERT and UPDATE

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Time scale on INSERT and UPDATE

Hannes Ricklefs
Hello,

does anyone have any experience in the amount of time increase for an UPDATE,
INSERT, SELECT in relation to the size of the actual database?

Is it proportional or exponential for example...

Regards,
Hannes
Reply | Threaded
Open this post in threaded view
|

Re: Time scale on INSERT and UPDATE

Martin Engelschalk
Hello Hannes,

in my experience, the time of inserts does not grow with the size of the
database.
with updates and selects, i would expect that the time of finding the
record(s) (to update or select) (the where-clause) depends on the size
of the table and on whether indexes are used.

Martin

Hannes Ricklefs schrieb:

>Hello,
>
>does anyone have any experience in the amount of time increase for an UPDATE,
>INSERT, SELECT in relation to the size of the actual database?
>
>Is it proportional or exponential for example...
>
>Regards,
>Hannes
>  
>
Reply | Threaded
Open this post in threaded view
|

Re[2]: Time scale on INSERT and UPDATE

Wilfried Mestdagh
Hi,

> with updates and selects, i would expect that the time of finding the
> record(s) (to update or select) (the where-clause) depends on the size
> of the table and on whether indexes are used.

With indexing if the database has eg 65535 records, then maximum 17
comparisations. it is one more for power of 2 every time. eg 128
KRecords maximum 18 comparisations etc.

---
Rgds, Wilfried
http://www.mestdagh.biz

Reply | Threaded
Open this post in threaded view
|

Re: Time scale on INSERT and UPDATE

John Stanton-3
In reply to this post by Hannes Ricklefs
This depends on the number of indices.  Insertions into a B-Tree
essntially follow an Nlog(N) law, so the best you can expect is
O(Nlog(N)).  Similarly for deletions.

A SELECT depends upon the query and indices.  A row search is
essentially linear with size, O(N), whereas a B-Tree index search is
enormously faster, but does follow a basic O(Nlog(N)) law.

The conclusion is that small N is always faster in a tree or list
structure.  A table for each data type may be preferable to all types
being lumped into one table and selected on type.
JS

Hannes Ricklefs wrote:
> Hello,
>
> does anyone have any experience in the amount of time increase for an UPDATE,
> INSERT, SELECT in relation to the size of the actual database?
>
> Is it proportional or exponential for example...
>
> Regards,
> Hannes

Reply | Threaded
Open this post in threaded view
|

Re: Time scale on INSERT and UPDATE

Dennis Cote
In reply to this post by Hannes Ricklefs
Hannes Ricklefs wrote:

>Hello,
>
>does anyone have any experience in the amount of time increase for an UPDATE,
>INSERT, SELECT in relation to the size of the actual database?
>
>Is it proportional or exponential for example...
>
>Regards,
>Hannes
>
>  
>
Hannes,

The execution time for inserts depends upon the number of existing
records and the number of indexes. For each insert the engine must
locate the correct btree block to add a new record to in both the table
and each index. This is an O(log N) operation for both indexes and
tables. The base of the log depends upon the fanout of the btree blocks,
which in turn depends on the size of the records and index keys, but
usually isn't important. So for inserts you have a time T that is
proportional to:

T ~= (number of indexes + 1) O(log number of records)

Note that this depends primarily upon the number of records in the
table, not the size of the database. The size of the database depends
upon the number of records in all the tables. The database size may have
a minor impact on the insert speed by causing the btree blocks to be
spread out further across the disk, therefore requiring additional disk
seeks to read the blocks if they aren't already in the disk cache.

Similar arguments apply to updates. Each update needs to locate the
existing record, and then store the modified values. This may move the
records in the table (if it changes an integer primary key) and in each
of the indexes that were affected by the update. Updates often use
indexes to locate the records to be changed, or are performing a full
table scan if all records are being modified or there is no index. For a
table scan the amortized cost of locating the record is constant, for an
indexed lookup the cost is O(log N), for an unindexed lookup the time is
O(N). After the record is changed it is written back and then all
affected indexes have to be updated. This requires locating and deleting
the existing index record, and inserting a new index record. Both of
these are O(log N) operations on each index. So we have a time
proportional to:

T~= choose_one_of(O(1), O(log N), O(N)) + if_int_pk(O(log N)) + (2 *
number of indexes)O(log N)
   
where N is the number of records in the table.

Selects are generally too complicated to be analyzed in this manner
especially considering joins, grouping and sorting. But the same general
principles apply. A full table scan lookup has a constant amortized
cost, an indexed lookup has a O(log N) cost, and a nunindexed lookup has
an O(N) cost. Joins generally multiply these values together. For
example a full table scan joined to a second table using an index
requires a time proportional to

T ~= O(1) + O(log number of records in the second table) = O(log N2)

for each record returned. For the entire select the time is proportional to

T~= O(N1) * O(log N2)

Sorting a select generally takes O(N log N) where N is the number of
result records, but if an appropriate index is available that can be
used to retrieve the records in the correct order and eliminate the need
for a sort.

As you can see, the short answer is "it depends...".

HTH
Dennis Cote