An improvement to the Django admin queryset count approximation workaround proposed by @adamchainz at http://adamj.eu/tech/2014/07/16/extending-djangos-queryset-to-return-approximate-counts/. Note: This is intended for use with Postgres.

admin.py

class BaseModelAdmin(Admin):
    def queryset(self, request):
        qs = super(BaseModelAdmin, self).queryset(request)
        # Use the approximate queryset to avoid any non-performant
        # 'COUNT(*)' queries

        # Mixin the ApproximateCountQuerySetMixin to add the approximate count
        # to any custom querysets
        class AugmentedApproximateCountQueryset(ApproximateCountQuerySetMixin, qs.__class__):
            pass

        qs = qs._clone(klass=AugmentedApproximateCountQueryset)

        return qs

querysets.py

class ApproximateInt(int):
    '''
    A child of `int` whose string representation will read (for, say, the integer 11)
    '~ 11' instead of '11'.
    '''
    def __str__(self):
        return '~ ' + super(ApproximateInt, self).__str__()


class ApproximateCountQuerySetMixin(object):
    '''
    Avoids performing COUNT(*) on big tables; instead,
    if the table looks big, just extract an approximate count via Postgres's
    `pg_class` table.

    This QuerySet mixin is mainly intended for the Django admin. It's inspired by:
    - http://adamj.eu/tech/2014/07/16/extending-djangos-queryset-to-return-approximate-counts/
    - http://chase-seibert.github.io/blog/2012/06/01/djangopostgres-optimize-count-by-replacing-with-an-estimate.html
    '''
    # The class the approximate row count will be cast as
    approximate_row_count_class = ApproximateInt
    # The minimum row count at which an approximation query will be used
    approximate_row_count_minimum = 1000

    def count(self):
        query = self.query
        # If this is a vanilla "COUNT(*)" query on every row, use
        # an approximate count
        if (
            not query.where and
            query.high_mark is None and
            query.low_mark == 0 and
            not query.select and
            not query.group_by and
            not query.having and
            not query.distinct
        ):
            # Fetch a row count approximation
            cursor = connections[self.db].cursor()
            cursor.execute("select reltuples from pg_class where relname='{table_name}';".format(table_name=self.model._meta.db_table))
            row = cursor.fetchone()
            row_count = int(row[0])

            # If the approximate row_count is greater than the minimum, use it
            if row_count >= self.approximate_row_count_minimum:
                # An ApproximateInt is returned to allow this row
                # count to be represented as
                return self.approximate_row_count_class(row_count)

        # Otherwise, use the standard `count`
        return super(ApproximateCountQuerySetMixin, self).count()

Great idea which I would like to test myself, but unfortunatelly it's not working with Django 1.9
Can I ask for help? I figured that in admin.py there is get_queryset method now, but I can't force def count(self): method to be invoked
Best regards!