SQL Query Time Complexity

Question

What is the time complexity of simple SQL statements like the following?

INSERT into table (col1, col2, col3) values ("a", "b", "c")

How does it depend on the following:

1. size of the table
2. datatype of col1, col2
3. number of columns in the table viz. col1, col2, col3, etc

Does this depend on whether I am using MyISAM or InnoDB?

Answer 1

The MySQL 5.0 documentation has a nice page on this topic.

The article provides approximate proportial costs for each of the subtasks involved in an insertion task.

The time required for inserting a row is determined by the following factors, where the numbers indicate approximate proportions:

Connecting: (3)

Sending query to server: (2)

Parsing query: (2)

Inserting row: (1 × size of row)

Inserting indexes: (1 × number of indexes)

Closing: (1)

This does not take into consideration the initial overhead to open tables, which is done once for each concurrently running query.

The size of the table slows down the insertion of indexes by log N, assuming B-tree indexes.

The rest of article provides techniques for speeding up insertions, useful if insert speed becomes a bottleneck in your application.