4 ms·
The first large scale project I worked on, my team couldn't figure out why operations had slowed down as the data set grew. Indexes have log(n) insertion time
by hinkley 3y ago
The first large scale project I worked on, my team couldn't figure out why operations had slowed down as the data set grew.
Indexes have log(n) insertion time per record. If you had 1000 records in your test database, as you approach 65k your insertion time goes up by 60% (2^10 vs 2^16 records). Success slows everything down, and there are only so many server upgrades available.
Add a couple new indexes for obscure features the business was looking for, and now you're up to double.
- winrid 3y agoDouble a very small number. If that's seriously an issue use a faster disk. So many people trying to run a DB on EBS with less IOPS than my PC from 2015. I manage plenty of DBs with hundreds of millions of records and 40+ indexes per table/collection...
- vjerancrnjak 3y agoInsertion should still be extremely fast for such a small index, right? Doing binary search over a b-tree page is <100 cycles. b-tree traversal over 100M records should still be measured in microseconds and binary search over that should be in microseconds too if not in 100s of nanoseconds.
- lazide 3y ago‘It depends’ - don’t forget about locking overhead, needing to flush multiple pages/leafs as thresholds get hit, disk I/O wait times, etc. At the beginning it’s rarely noticeable, but it does exist and under heavy load or with a lot of index writes needing to happen it can cause very noticeable overhead.
- vjerancrnjak 3y agoYes, but these bits don’t scale with log(n) index tree. They depend on something other than the index data structure.
- lazide 3y agoUsually load.
- hinkley 3y agoThis conversation is about unrepresentative sample data.
- vjerancrnjak 3y agoAre you saying that the index is made on columns which only have few unique values so you need to scan everything all the time? Given that you’ve included the log(b) claim I thought you were referring to a normally functioning btree. A situation where 65k rows end up slowing down things severely should have more to do with other database features (foreign keys and similar).