They propose a solution for dynamic PGM indexes in the paper (section 3) and benchmark it (section 6). A summary is that, in their benchmark, their index is fas

They propose a solution for dynamic PGM indexes in the paper (section 3) and benchmark it (section 6). A summary is that, in their benchmark, their index is faster by 13%-71% in most cases, but can be slower (1%-15.2%) in a few cases. I agree the example would be more eye-catching without that sort. http://www.vldb.org/pvldb/vol13/p1162-ferragina.pdf http://www.vldb.org/pvldb/vol13/p1162-ferragina.pdf