Обсуждение: Limit Heap Fetches / Rows Removed by Filter in Index Scans

On Fri, 19 Aug 2016, 1:07 p.m. Victor Blomqvist, <vb@viblo.se> wrote:

Hi,

Is it possible to break/limit a query so that it returns whatever results found after having checked X amount of rows in a index scan?

For example:
create table a(id int primary key);
insert into a select * from generate_series(1,100000);

select * from a
where id%2 = 0
order by id limit 10

In this case the query will "visit" 20 rows and filter out 10 of them. We can see that in the query plan:
"Rows Removed by Filter: 10"
"Heap Fetches: 20"

Is it somehow possible to limit this query so that it only fetches X amount, in my example if we limited it to 10 Heap Fetches the query could return the first 5 rows?

My use case is I have a table with 35 million rows with a geo index, and I want to do a KNN search but also limit the query on some other parameters. In some cases the other parameters restrict the query so much that Heap Fetches becomes several 100k or more, and in those cases I would like to have a limit to my query.

Have you checked the TABLESAMPLE clause in v9.5?

https://wiki.postgresql.org/wiki/TABLESAMPLE_Implementation

Thanks!

/Victor

--

--

Best Regards

Sameer Kumar | DB Solution Architect 

ASHNIK PTE. LTD.

101 Cecil Street, #11-11 Tong Eng Building, Singapore 069 533

T: +65 6438 3504 | M: +65 8110 0350 

Skype: sameer.ashnik | www.ashnik.com

Hi Victor:

On Fri, Aug 19, 2016 at 7:06 AM, Victor Blomqvist <vb@viblo.se> wrote:
> Is it possible to break/limit a query so that it returns whatever results
> found after having checked X amount of rows in a index scan?
>
> For example:
> create table a(id int primary key);
> insert into a select * from generate_series(1,100000);
>
> select * from a
> where id%2 = 0
> order by id limit 10
>
> In this case the query will "visit" 20 rows and filter out 10 of them. We
> can see that in the query plan:
> "Rows Removed by Filter: 10"
> "Heap Fetches: 20"
>
> Is it somehow possible to limit this query so that it only fetches X amount,
> in my example if we limited it to 10 Heap Fetches the query could return the
> first 5 rows?
>
>
> My use case is I have a table with 35 million rows with a geo index, and I
> want to do a KNN search but also limit the query on some other parameters.
> In some cases the other parameters restrict the query so much that Heap
> Fetches becomes several 100k or more, and in those cases I would like to
> have a limit to my query.

Well, if you accept more abstract limits (i.e. you do not depend on
heap fetches, you just want up to 5 even IDs from the first 10 IDs )
you could try:

with base as (select * from a order by id limit 10)
select * from base where id %2 = 0 order by id limit 5;

( Or do it with a subquery instead of a CTE ).

In general

select * from table where common_condition and filter_condition order
by xx limit N

becomes

with base as (select * from table where common_condition order by xx
limit base_fecthes)
select * from base where filter_condition order by XX limit N;

In the example common_condition is non existent, put it as true,
optimize after transforming.

Francisco Olarte.

Hi Victor:


On Fri, Aug 19, 2016 at 7:02 PM, Victor Blomqvist <vb@viblo.se> wrote:
> What I want to avoid is my query visiting the whole 1m rows to get a result,
> because in my real table that can take 100sec. At the same time I want the
> queries that only need to visit 1k rows finish quickly, and the queries that
> visit 100k rows at least get some result back.

You are going to have problems with that. If you just want to limit it
to max 100k rows, max 10 results my solution works, probably better as
nested selects than CTEs, but someone more knowledgeable in the
optimizer will need to say something ( or tests will be needed ). This
is because "the queries that visit 100k rows at least get some result
back." may be false, you may need to visit the whole 1M to get the
first result if you are unlucky. Just set ap=999 where id=1M and ask
for ap>=999 and you've got that degenerate case, which can only be
saved if you have an index on ap ( even with statistics, you would
need a full table scan to find it ).

If you are positive some results are in the first 100k rows, then my
method works fine, how fast will need to be tested with the real data.
You can even try using *10, *100, *1k of the real limit until you have
enough results if you want to time-limit your queries.


Francisco Olarte.