Re: AW: question about index cost estimates

Tom Lane writes:

> > Another metric that would be interesing is a number that represents 
> > the divergence of the heap order from the index sort order.

> Got any ideas about how to get that number in a reasonable amount of
> time (not too much more than VACUUM takes now)?

There are a few fairly simple-minded methods to determine the sortedness
of a list. Any more sophisticated methods are probably not much better in
practice and take too much to calculate.

1. The number of items out of place

2. The number of pairs out of order

3. The number of adjacent pairs out of order.

4. Length of list minus length of longest increasing (not necessarily
adjacent) subsequence

For our application I would suggest 3. because it can be calculated in
linear time and it only gives points to situations that you really want,
namely sequential disk access. You could take score/(length-1) to get 1
for a really unsorted list and 0 for a completely sorted one.


-- 
Peter Eisentraut                  Sernanders väg 10:115
peter_e@gmx.net                   75262 Uppsala
http://yi.org/peter-e/            Sweden