0

Consider a table with a single id which has a PRIMARY KEY index:

CREATE TABLE test (id INT PRIMARY KEY)

Now consider queries like

SELECT COUNT(*) FROM test SELECT * FROM test ORDER BY id LIMIT ?, 1

(using MySQL syntax for the LIMIT: ? is the offset)

It seems that despite there being an index on the table (on the id), these queries (counting rows or selecting a row at an offset) all take linear time because they have to do full or partial table scans; there is no index on the "ranks" / positions of the rows in the sorted order which would facilitate counting or getting elements by rank (compare to Redis' sorted set, which allows doing operations by rank efficiently).

The problem is that the (typically B-Tree) index is constrained to just id and is not at all "augmented" to include counts / ranks. I've looked at SQLite, MySQL / MariaDB and PostgreSQL, and none of these DBMS's seem to allow augmenting the index to include counts / ranks.

My questions are:

  • Is it possible to augment the B-Tree indexes SQLite, MySQL / MariaDB or PostgreSQL use to include counting?
  • If not, is there another relational DBMS which uses SQL as its query language which supports such indexes?
Improve this question
1

4 Answers 4

Reset to default
2

Is it possible to augment the B-Tree indexes SQLite, MySQL / MariaDB or PostgreSQL use to include counting?

No.

Is that a clear enough answer for you? :-)

B-tree indexes improve performance when you search by values, not by positions (i.e. using OFFSET).

The tricks used to work around this are generally storing the row positions as values, and then indexing that column. Or else querying a different column by value.

Another common solution is to store "summary tables" which provide quick access to pre-calculated aggregate values. But these are a chore to keep updated if your data is updated frequently.

Also they aren't much help if you have to support arbitrary ranges, like in your ID BETWEEN x AND y example, because trying to keep a summary for O(n2) distinct subranges can be more costly than just doing the aggregate query when needed.

If not, is there another relational DBMS which uses SQL as its query language which supports such indexes?

There's a group of RDBMS implementations that are called column-oriented DBMSes. These optimize for analytical queries. Some of these store data in pages, and internally keep aggregate sub-totals in each page. So if you wanted to get a COUNT(*) for a range of ids, it would only have to visit each page covering that range and then sum up the pre-calculated subtotals from each page, instead of visiting every row.

I don't have any personal experience with column-oriented databases, but I'm aware there are a number of commercial and open source offerings. For example ClickHouse is sometimes used as a complement to MySQL. See https://www.percona.com/blog/using-clickhouse-as-an-analytic-extension-for-mysql/

Being optimized for analytical queries, some column-oriented databases have sacrificed optimization for transactional queries that are more typical. Before you choose a column-oriented database, should test it carefully under your application's workload.

Improve this answer
11
  • Thanks for the clear answer :) I'm surprised that no RDBMS seems to have an option for augmenting B-Tree indexes with counts; it would enable many rank-based operations to run in logarithmic rather than linear time at the cost of requiring a few more (but still only O(log n) total) disk writes for each update (to update the counts of all the nodes in the path). Commented Jun 24, 2023 at 10:35
  • How do you propose counts would be stored in the index, given that many RDBMS implementations support multiple concurrent views against the data? That is, you have many clients, each of which can "see" a different count of rows because of transaction isolation. Commented Jun 24, 2023 at 12:46
  • One solution would be keeping the old pages around and only adding new pages for all modified nodes. This is how persistent tree data structures are usually implemented. For B-Trees, you might want to "compress" the difference between the "new node" and the "old node" since the nodes will usually be very similar. Commented Jun 24, 2023 at 13:16
  • That's roughly how each index value supports multi-versioning. How would you do it for counts? Especially to handle the BETWEEN x AND y scenario you brought up. Commented Jun 24, 2023 at 13:18
  • 1
    In any case, I think I've answered your original question — the feature you are looking for is not implemented in the brands of RDBMS you named, and adding it would be a significant engineering effort. Some support may exist in other architectures, but to do so, they have probably sacrificed other optimizations that you would miss. Commented Jun 24, 2023 at 16:39
3

DBMS don't store rank in either tables or indexes, because rank is a property which is dependent on all the other rows of the table.

Even if we didn't consider multiversioning concurrency (where a single row could have multiple ranks), adding or deleting a new row would require to update all the ranks of the rows after the new/deleted one in the desired order.

This would be a massive performance penalty for a very little benefit.

However, you are of course free to add a ranking system using TRIGGERS.

CREATE TABLE test (id INT PRIMARY KEY, rank INT); CREATE TRIGGER test_insert AFTER INSERT on test FOR EACH ROW BEGIN --set rank of new row by adding 1 to the rank of the previous one UPDATE test SET rank= (SELECT coalesce(r.rank,0)+1 FROM rank r where r.id < NEW.id ORDER BY id DESC LIMIT 1) WHERE id = NEW.id; --update ranks of all rows after the new one, moving them up by 1 UPDATE test SET rank = rank+1 WHERE id > NEW.id; END; CREATE TRIGGER test_delete AFTER DELETE on test FOR EACH ROW BEGIN --update rank of all rows after the deleted one, moving them down by 1 UPDATE test SET rank=rank-1 WHERE id > OLD.id; END;

And this is assuming you never modify an id.

Now, your queries would become:

SELECT rank FROM test ORDER BY id DESC LIMIT 1; --count(*) SELECT * FROM test WHERE rank = ?; --LIMIT ?,1

Unfortunately, to be fast and not require a table scan, the latter would also require an index on rank, but such index would also have to be massively updated every time you insert or delete a row in the table..

Improve this answer
2
  • mysql/mariadb cannot update other rows of a table the trigger is triggered for. (Also, "rank" is not an ideal column name, as it is a keyword in mysql 8+) Commented Jun 24, 2023 at 8:38
  • "adding or deleting a new row would require to update all the ranks of the rows after the new/deleted one in the desired order" - this is not accurate; if you augment B-trees to store counts of subtrees, you only have to update the counts in the path from the root to the leaf where you inserted a new entry; deletions work likewise. It's not O(n) but rather O(log n) at the cost of requiring more disk writes. I'm wondering whether any databases implement it (or an alternative data structure). I effectively want a "sorted list" rather than just a "sorted set / map" data structure. Commented Jun 24, 2023 at 10:30
2

An optimal solution depends on the case, and the database engine you're using.

For InnoDB:
When you do a LIMIT OFFSET query of 100, 100 the database engine will get 200 records and throw away the first 100. If you know the length of your dataset you can avoid this with a few tricks. One of them is using a filter, SELECT Id FROM test WHERE Id > 100 LIMIT 100;.

For counting rows there are a few tricks, and they all depend on the use case. If you want an approximation of the row count you can use a EXPLAIN() and grab the rows column. This will give a good approximation of the row count. You can also introduce a table for caching counting.

Improve this answer
4
  • These are all nice hacks, but overall they are too narrow: I want a proper index which provides efficient rank-based operations. The "counting everything" is just an example; if I were to count rows in a range, manually implementing a "count everything" using triggers wouldn't help at all. Commented Jun 23, 2023 at 11:41
  • 1
    You were asking "Is it possible to augment the B-Tree indexes SQLite, MySQL / MariaDB or PostgreSQL use to include counting?" So you shouldn't complain if you get your question answered. Commented Jun 23, 2023 at 11:52
  • @LaurenzAlbe I don't see my question answered by this post, neither positively nor negatively, and my second question isn't touched upon at all. Commented Jun 23, 2023 at 16:15
  • 1
    Also SHOW TABLE STATUS and the equivalent query into information_schema.TABLES. Commented Jun 24, 2023 at 18:02
1

Is it possible to augment the B-Tree indexes SQLite, MySQL / MariaDB or PostgreSQL use to include counting?

Not with the existing implementation of BTrees. But maybe this...

Whenever a change (insert/delete) occurs in a BTree block, the count of rows in that block and put the count in the parent node. This requires updating that node eventually.

Plan A: Only the next-to-bottom nodes have that count. To get a "rank" you have to add up the counts in that level of the BTree, then dig into the leaf node to finish the count.

Plan B: The counts are percolated up the tree. This leads to Log(n) non-leaf node updates for any insert/delete. To soften this cost, here is a Rule of Thumb: A typical BTree node (in InnoDB) has 100 children. That says that even a trillion-row BTree has only 6 levels ( Log100(1e12) = 6 ).

(Caveat: This design probably has trouble keeping up with ACID/MVCC/etc.)

Approximate way to find a "random" row: Random

OFFSET for pagination is bad, and a typically viable workaround: Pagination; includes a suggestion on more than just "Next" and "Prev" pages.

Plan C: Remember the days when search engines said: "... out of 372369 results"? And then they changed to "... out of over 300K results"? Did we complain about losing the exact number?

Plan C1: Keep track of the "top 10", but be less precise on the rest.

Plan C2: Recompute the stats once a day and make them fuzzy (eg 300K).

Improve this answer
3
  • Plan B is what I was hoping databases would implement (and will try implementing myself). I think it should be possible to make this MVCC compliant (using persistent trees, by creating copies of nodes); I've discussed that with Bill Karwin above. Commented Jun 25, 2023 at 6:39
  • I think I already stumbled on your pages while researching, they definitely do provide nice and probably mostly sufficient workarounds for two common use cases. How would you go about finding the rank of an entry (e.g. counting all smaller entries) though without the augmented B-Tree index? Commented Jun 25, 2023 at 6:48
  • 1
    @Luatic - I added Plan C. Meanwhile, I will stick the "ranking" problem in the back of my head. The COUNT(*) problem can be easily handled by dead-reckoning, as MyISAM does and MariaDB may be doing. But it requires adding a little bit of code in lots of places, plus other ACID issues. Commented Jun 25, 2023 at 15:40

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.