On Thu, Aug 4, 2016 at 7:59 AM, Pavan Deolasee <pavan.deolasee@gmail.com> wrote:
> So marking the index would require us to mark both old and new index tuples
> as requiring re-check. That requires an additional index scan to locate the
> old row and then an additional write to force it to re-check, which is
> algorithmically O(NlogN) on table size.
So, basically, I'm saying this isn't really O(NlogN), it's O(N),
manifested in low-cardinality indexes.