current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.
up vote 1 down vote favorite
1

I am studying big-O time-space complexities of different algorithms with the partial index of PostgreSQL 9.4:

  • introsort (O(n log n)-time, O(log n)-space) and
  • heapsort (O(n log(n))-time O(1)-space),

motivated by this thread. The introsort is using randomized quicksort to mostly sort the array, switching to heapsort if quicksort is to degenerate. I think the partial index implementation is not using any sorting algorithms with accesses. To access the data of the partial index is fast when the range is sufficiently small and the number of objects is less than one billion with 32-bit system. I am interested in how O(n log n)-time, O(log n)-space algorithms can work with the partial index with enough big ranges from the partial index.

How can you estimate suitable sorting/access algorithms in the partial index?

share|improve this question
1  
Interesting question! Regarding the internals of PostgreSQL like that, you might get a much more thorough and in-depth answer if you post it to [email protected] –  Kassandry Aug 12 at 19:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.