0

Suppose there is a table T, with column C indexed by a B-tree, and a given constant k. Assume the result of the following query would be n:

select count(*) from T where C > k;

I tried such a query in MySQL(InnoDB) ,with column C indexed by B-tree, and realized the bigger the value of n, the slower the query. On a large table (GBs), I even have to wait for minutes. So, I speculate the time complexity is linear with respect to n. But I know if one stores aggregate information on B-Tree internal nodes that can be done in logarithmic time with respect to the size of table.

Can anybody please suggest any DBMS with the logarithmic solution implemented, or any trick to reduce the query time in MySQL?

Hamid Alaei
  • 406
  • 4
  • 16

2 Answers2

1

You can not tell anything until you see the execution plan. At least in Oracle you should also have histogram on column C to have different exec plans for different values of C.

Also the depth of index is usually 3-5. The base of the logarithm is VERY big. Also keep in mind that many databases cheat when deleting rows from table, usually leaf nodes might point onto rows which were already deleted. It's not worth of the effort to maintain aggregate values in B-tree, it would not scale well.

If you are looking for the database having various fancy indexing option, the look at PostreSQL.

ibre5041
  • 4,903
  • 1
  • 20
  • 35
  • thanks. I know concurrency control makes things difficult. But, In the specific case I am interested in at the moment, I don't have a lot of updates, and I don't care much about locking the entire table while inserting a row. How about that? – Hamid Alaei Sep 26 '14 at 07:39
  • I'm afraid you have to become reconciled to the fact the databases were designed for different purpose. Indexes do not have aggregates in tree nodes because their maintenance would be to expensive in most cases. But first you really should check execution plan of the query. – ibre5041 Sep 26 '14 at 10:29
0

Yes, all DBMS support indexes. Make sure that all K fields are indexed and this is sadly as far as I know the single thing you can basically do.

This link is for SQL Server but it should work (with very little modifications) with MySql.

Not sure, but this question looks related with this question on SO.

Community
  • 1
  • 1
Ciprian Khlud
  • 434
  • 3
  • 6
  • The single way to index in logarithmic way is to use the index. I also recommend you this page (but DBMSes have some slight variations in syntax): [Use the index Luke](http://use-the-index-luke.com/sql/table-of-contents) – Ciprian Khlud Sep 26 '14 at 07:14
  • Please read again my question. I've already used index. with all the respect, you misunderstood my question. – Hamid Alaei Sep 26 '14 at 07:16