Thread: best way to retreive the next record in a multi column index

<div class="Section1"><p class="MsoNormal"><font face="Arial" size="2"><span style="font-size:10.0pt;
font-family:Arial">Can anybody help me with this? (<span class="GramE">sorry</span> for posting on
hackers)</span></font><pclass="MsoNormal"><font face="Arial" size="2"><span style="font-size:10.0pt; 
font-family:Arial"> </span></font><p class="MsoNormal"><font face="Arial" size="2"><span style="font-size:10.0pt;
font-family:Arial">I need to be able determine the next row based on a non unique key (index).<span
style="mso-spacerun:yes"> </span>I have solved this problem, but I would like to know if there is a simpler
solution.<spanstyle="mso-spacerun:yes">  </span>For those of you who have ever dealt with COBOL, this is an on the fly
sqlconstruction of a 'READ NEXT' statement following a START.<span style="mso-spacerun:yes">  </span>Very similar to
cursors,but because of the transactional limitations of cursors they cannot be used in this context.</span></font><p
class="MsoNormal"><fontface="Arial" size="2"><span style="font-size:10.0pt; 
font-family:Arial"> </span></font><p class="MsoNormal"><font face="Arial" size="2"><span style="font-size:10.0pt;
font-family:Arial">Example: </span></font><p class="MsoNormal"><font face="Arial" size="2"><span
style="font-size:10.0pt;
font-family:Arial">I have a table t with columns a, b, c.<span style="mso-spacerun:yes">  </span>I have values a1, b1,
c1for those columns and would like to know the next value in the table when ordered by a, b.<span
style="mso-spacerun:yes"> </span>I have values a1, b1, and oid1 and would like to find the very next record in the
table(essentially looking for the next record in the index).</span></font><p class="MsoNormal"><font face="Arial"
size="2"><spanstyle="font-size:10.0pt; 
font-family:Arial"> </span></font><p class="MsoNormal"><font face="Arial" size="2"><span style="font-size:10.0pt;
font-family:Arial">I have two solutions: one with 'or' logic and one with 'and' logic.<span style="mso-spacerun:yes"> 
</span>Note:if the index we are scanning has the unique constraint, the <span class="SpellE">oid</span> part of the
logic(and the index) can be left out.</span></font><p class="MsoNormal"><font face="Arial" size="2"><span
style="font-size:10.0pt;
font-family:Arial"> </span></font><p class="MsoNormal"><span class="GramE"><font face="Arial" size="2"><span
style="font-size:10.0pt;font-family:Arial">create</span></font></span><fontface="Arial" size="2"><span
style="font-size:10.0pt;font-family:Arial">index <span class="SpellE">t_idx</span> on t(a, b, <span
class="SpellE">oid</span>);</span></font><pclass="MsoNormal"><font face="Arial" size="2"><span style="font-size:10.0pt; 
font-family:Arial"> </span></font><p class="MsoNormal"><font face="Arial" size="2"><span style="font-size:10.0pt;
font-family:Arial">*or* logic:</span></font><p class="MsoNormal"><span class="GramE"><font face="Arial" size="2"><span
style="font-size:10.0pt;font-family:Arial">select</span></font></span><fontface="Arial" size="2"><span
style="font-size:10.0pt;font-family:Arial">* from t </span></font><p class="MsoNormal"><span class="GramE"><font
face="Arial"size="2"><span style="font-size:10.0pt;font-family:Arial">where</span></font></span><font face="Arial"
size="2"><spanstyle="font-size:10.0pt;font-family:Arial"><span style="mso-spacerun:yes">  </span></span></font><p
class="MsoNormal"><fontface="Arial" size="2"><span style="font-size:10.0pt; 
font-family:Arial"><span style="mso-spacerun:yes">    </span>a > a1 OR</span></font><p class="MsoNormal"><font
face="Arial"size="2"><span style="font-size:10.0pt; 
font-family:Arial"><span style="mso-spacerun:yes">    </span>(a = a1 and b > b1) OR</span></font><p
class="MsoNormal"><fontface="Arial" size="2"><span style="font-size:10.0pt; 
font-family:Arial"><span style="mso-spacerun:yes">    </span>(a = a1 and b = b1 and <span class="SpellE">oid</span>
>oid1)</span></font><p class="MsoNormal"><font face="Arial" size="2"><span style="font-size:10.0pt; 
font-family:Arial"><span style="mso-spacerun:yes">    </span><span class="GramE">order</span> by a, b, <span
class="SpellE">oid</span></span></font><pclass="MsoNormal"><font face="Arial" size="2"><span style="font-size:10.0pt; 
font-family:Arial"><span style="mso-spacerun:yes">    </span></span></font><p class="MsoNormal"><font face="Arial"
size="2"><spanstyle="font-size:10.0pt; 
font-family:Arial">*and* logic</span></font><p class="MsoNormal"><span class="GramE"><font face="Arial" size="2"><span
style="font-size:10.0pt;font-family:Arial">select</span></font></span><fontface="Arial" size="2"><span
style="font-size:10.0pt;font-family:Arial">* from t</span></font><p class="MsoNormal"><span class="GramE"><font
face="Arial"size="2"><span style="font-size:10.0pt;font-family:Arial">where</span></font></span><font face="Arial"
size="2"><spanstyle="font-size:10.0pt;font-family:Arial"> </span></font><p class="MsoNormal"><font face="Arial"
size="2"><spanstyle="font-size:10.0pt; 
font-family:Arial"><span style="mso-tab-count:1">            </span>a >= a1 AND</span></font><p
class="MsoNormal"><fontface="Arial" size="2"><span style="font-size:10.0pt; 
font-family:Arial"><span style="mso-tab-count:1">            </span>(a > a1 or b >= b1) AND</span></font><p
class="MsoNormal"><fontface="Arial" size="2"><span style="font-size:10.0pt; 
font-family:Arial"><span style="mso-tab-count:1">            </span>(a > a1 or b > b1 or <span
class="SpellE">oid</span>> oid1)</span></font><p class="MsoNormal"><font face="Arial" size="2"><span
style="font-size:10.0pt;
font-family:Arial"><span style="mso-tab-count:1">            </span><span class="GramE">order</span> by a, b, <span
class="SpellE">oid</span></span></font><pclass="MsoNormal"><font face="Arial" size="2"><span style="font-size:10.0pt; 
font-family:Arial"> </span></font><p class="MsoNormal"><font face="Arial" size="2"><span style="font-size:10.0pt;
font-family:Arial">I think, of the two, <span class="GramE">the or</span> logic is much better.<span
style="mso-spacerun:yes"> </span>The problem with both approaches is that when we have a 4 column based key (common in
COBOL)our index is based on <span class="SpellE">a,b,c,d,o</span> and the number of comparisons (and our select
statement)becomes large, and performance is very important!<span style="mso-spacerun:yes">  </span>If some logical
geniusknows how to reduce the above logic into a more direct approach, feel free to comment.</span></font><p
class="MsoNormal"><fontface="Arial" size="2"><span style="font-size:10.0pt; 
font-family:Arial"> </span></font><p class="MsoNormal"><font face="Arial" size="2"><span style="font-size:10.0pt;
font-family:Arial">Postgres properly optimizes both cases, and uses the key even for a table with 1 million + records
in<span class="GramE">it,</span> the answer comes back right away.</span></font><p class="MsoNormal"><font face="Arial"
size="2"><spanstyle="font-size:10.0pt; 
font-family:Arial"> </span></font><p class="MsoNormal"><font face="Arial" size="2"><span style="font-size:10.0pt;
font-family:Arial">My question is: is there a simpler way to do this? AFIK there is no way in sql to directly find the
'next'or 'previous' record in an ordered index (in other words, I have <span class="SpellE">oid</span> n, what is the
next<span class="SpellE">oid</span> in the index?) without using the above logic.<span style="mso-spacerun:yes"> 
</span>Inother words, I am missing the ability to deal with a multi column index value in a comparison as a single
entity.</span></font><pclass="MsoNormal"><font face="Arial" size="2"><span style="font-size:10.0pt; 
font-family:Arial"> </span></font><p class="MsoNormal"><span class="GramE"><font face="Arial" size="2"><span
style="font-size:10.0pt;font-family:Arial">p.s.</span></font></span><fontface="Arial" size="2"><span
style="font-size:10.0pt;font-family:Arial"></span></font><pclass="MsoNormal"><span class="GramE"><font face="Arial"
size="2"><spanstyle="font-size:10.0pt;font-family:Arial">the</span></font></span><font face="Arial" size="2"><span
style="font-size:10.0pt;font-family:Arial">above queries are 'sliding window' queries similar to cursors.<span
style="mso-spacerun:yes"> </span>If your table traversal can be defined by an (unique) index, you can use the above
templatesto slide over the tables without the use of a cursor.</span></font><p class="MsoNormal"><font face="Arial"
size="2"><spanstyle="font-size:10.0pt; 
font-family:Arial"> </span></font><p class="MsoNormal"><font face="Arial" size="2"><span style="font-size:10.0pt;
font-family:Arial">Merlin</span></font></div>

On Fri, Aug 15, 2003 at 13:42:23 -0400, Merlin Moncure <merlin.moncure@rcsonline.com> wrote:
>  
> Example: 
> I have a table t with columns a, b, c.  I have values a1, b1, c1 for
> those columns and would like to know the next value in the table when
> ordered by a, b.  I have values a1, b1, and oid1 and would like to find
> the very next record in the table (essentially looking for the next
> record in the index).
>  
> I have two solutions: one with 'or' logic and one with 'and' logic.
> Note: if the index we are scanning has the unique constraint, the oid
> part of the logic (and the index) can be left out.
>  
How about something like the following:
select * from t
where  a >= a1 and b >= b1           order by a, b limit 1 offset 1;

Bruno Wolff III wrote:
> How about something like the following:
> select * from t
> where  a >= a1 and b >= b1
>            order by a, b limit 1 offset 1;

Well, this may have recently changed, but the offset clause is not
suitable for arbitrary jumps over large tables.  Essentially, pg does an
index lookup to the first element then sequential scans until the offset
criteria is met.  Even if that was not the case there is another
problem:  Suppose while you are iterating over your table another
backend deletes a row after your initial start position; this will cause
a record to get skipped! (unless inside a transaction, of course, but
that can't be assumed).

I also spent a lot of time thinking about use some type of concatenation
and functional indices to get around the multi column issue (then things
would be really simple!).  This turned out to be a very complicated and
I ended up giving it up: I was stymied in the creation of a 'universal
concatenation' function, plus losing the elegant syntax to do partials
was a loss.

Merlin