Slavisa Garic <Slavisa.Garic@infotech.monash.edu.au> writes:
> You didn't understand the question. Inserting ONE ROW when there are already
> 5000 ROWS present takes 0.01 seconds. Inserting ONE ROW when there are
> already 60000 ROWS present takes 0.09 secods.
The numbers you presented didn't really offer any strong grounds for
believing that there's an O(N) growth rate --- as far as I can see your
results are only barely out of the measurement-noise category. Can you
run some tests where the issue is not in the least significant digit
of the available numbers?
But assuming for the moment that you've got hold of a real problem...
The actual insertion of a row should be essentially a constant-time
operation, since we just stick it into the last page of the table
(or any page with sufficient free space). Insertion of index entries
for the row would have cost that depends on the number of existing
table entries, but for btree indexes I'd expect the cost to vary as
O(log2(N)) not O(N). I do not think you've presented enough evidence
to prove that you're seeing linear rather than log-N cost growth.
Most of the serious insertion-cost problems we've seen lately have
to do with the costs of checking foreign key references ... but those
normally vary with the size of the referenced table, not the table into
which you're inserting. Besides which you mentioned nothing about
foreign keys ... or any other schema details as far as I saw ...
regards, tom lane
