Re: [HACKERS] What about LIMIT in SELECT ?

> I have had more time to think about this.  Basically, for pre-sorted
> data, our psort code is very fast, because it does not need to sort
> anything.  It just moves the rows in and out of the sort memory.  Yes,
> it could be removed in some cases, and probably should be, but it is not
> going to produce great speedups.

    And I got the time to hack around about this.

    I  hacked  in  a little check into the planner, that compares
    the sortClause against the key field list of  an  index  scan
    and  just  suppresses  the sort node if it exactly matchs and
    all sort operators are "<".

    I tested with a 10k row table where key is a text field.  The
    base query is a

        SELECT ... WHERE key > 'val' ORDER BY key;

    The  used 'val' is always a key that is close to the first of
    all keys in the table ('' on the first  query  and  the  last
    selected value on subsequent ones).

    Scenario  1  (S1)  uses exactly the above query but processes
    only the first 20 rows  from  the  result  buffer.  Thus  the
    frontend receives nearly the whole table.

    Scenario  2  (S2)  uses a cursor and FETCH 20. But closes the
    cursor and creates a new one for  the  next  selection  (only
    with another 'val') as it would occur in a web application.

    If  there  is  no index on key, the backend will allways do a
    Sort->SeqScan and due  to  the  'val'  close  to  the  lowest
    existing  key  nearly all tuples get scanned and put into the
    sort. S1 here runs about 10 seconds and S2 about  6  seconds.
    The  speedup  in  S2  results  from  the  reduced overhead of
    sending not wanted tuples into the frontend.

    Now with a btree index  on  key  and  an  unpatched  backend.
    Produced  plan  is  always  a  Sort->IndexScan.   S1 needs 16
    seconds and S2 needs 12 seconds. Again nearly all data is put
    into  the  sort but this time over the index scan and that is
    slower.

    Last with the btree index on key  and  the  patched  backend.
    This  time the plan is a plain IndexScan because the ORDER BY
    clause exactly matches the sort order of the  choosen  index.
    S1  needs  13  seconds  and  S2 less than 0.2!  This dramatic
    speedup comes from the fact, that this time the index scan is
    the  toplevel  executor  node and the executor run is stopped
    after 20 tuples have been selected.

    Analysis of the above timings:

    If there is an ORDER BY clause, using an index  scan  is  the
    clever  way  if  the  indexqual  dramatically reduces the the
    amount of data selected and sorted.   I  think  this  is  the
    normal case (who really selects nearly all rows from a 5M row
    table?). So choosing the index path  is  correct.  This  will
    hurt if someone really selects most of the rows and the index
    scan jumps over the disc.  But here the programmer should use
    an  unqualified  query  to  perform  a  seqscan  and  do  the
    qualification in the frontend application.

    The speedup for the cursor/fetch scenario  is  so  impressive
    that  I'll  create  a  post 6.4 patch. I don't want it in 6.4
    because there is absolutely no query in the whole  regression
    test,  where  it  suppresses  the  sort  node.   So  we  have
    absolutely no check that it doesn't break anything.

    For a web application, that can use a unique  key  to  select
    the next amount of rows, it will be a big win.


Jan

--

#======================================================================#
# It's easier to get forgiveness for being wrong than for being right. #
# Let's break this rule - forgive me.                                  #
#======================================== jwieck@debis.com (Jan Wieck) #