@@ -365,72 +365,120 @@ gistgetadjusted(Relation r, IndexTuple oldtup, IndexTuple addtup, GISTSTATE *gis
365365}
366366
367367/*
368- * find entry with lowest penalty
368+ * Search an upper index page for the entry with lowest penalty for insertion
369+ * of the new index key contained in "it".
370+ *
371+ * Returns the index of the page entry to insert into.
369372 */
370373OffsetNumber
371374gistchoose (Relation r ,Page p ,IndexTuple it ,/* it has compressed entry */
372375GISTSTATE * giststate )
373376{
377+ OffsetNumber result ;
374378OffsetNumber maxoff ;
375379OffsetNumber i ;
376- OffsetNumber which ;
377- float sum_grow ,
378- which_grow [INDEX_MAX_KEYS ];
380+ float best_penalty [INDEX_MAX_KEYS ];
379381GISTENTRY entry ,
380382identry [INDEX_MAX_KEYS ];
381383bool isnull [INDEX_MAX_KEYS ];
382384
383- maxoff = PageGetMaxOffsetNumber (p );
384- * which_grow = -1.0 ;
385- which = InvalidOffsetNumber ;
386- sum_grow = 1 ;
385+ Assert (!GistPageIsLeaf (p ));
386+
387387gistDeCompressAtt (giststate ,r ,
388388it ,NULL , (OffsetNumber )0 ,
389389identry ,isnull );
390390
391+ /* we'll return FirstOffsetNumber if page is empty (shouldn't happen) */
392+ result = FirstOffsetNumber ;
393+
394+ /*
395+ * The index may have multiple columns, and there's a penalty value for
396+ * each column. The penalty associated with a column that appears earlier
397+ * in the index definition is strictly more important than the penalty of
398+ * a column that appears later in the index definition.
399+ *
400+ * best_penalty[j] is the best penalty we have seen so far for column j,
401+ * or -1 when we haven't yet examined column j. Array entries to the
402+ * right of the first -1 are undefined.
403+ */
404+ best_penalty [0 ]= -1 ;
405+
406+ /*
407+ * Loop over tuples on page.
408+ */
409+ maxoff = PageGetMaxOffsetNumber (p );
391410Assert (maxoff >=FirstOffsetNumber );
392- Assert (!GistPageIsLeaf (p ));
393411
394- for (i = FirstOffsetNumber ;i <=maxoff && sum_grow ;i = OffsetNumberNext (i ))
412+ for (i = FirstOffsetNumber ;i <=maxoff ;i = OffsetNumberNext (i ))
395413{
396- int j ;
397414IndexTuple itup = (IndexTuple )PageGetItem (p ,PageGetItemId (p ,i ));
415+ bool zero_penalty ;
416+ int j ;
398417
399- sum_grow = 0 ;
418+ zero_penalty = true;
419+
420+ /* Loop over index attributes. */
400421for (j = 0 ;j < r -> rd_att -> natts ;j ++ )
401422{
402423Datum datum ;
403424float usize ;
404425bool IsNull ;
405426
427+ /* Compute penalty for this column. */
406428datum = index_getattr (itup ,j + 1 ,giststate -> tupdesc ,& IsNull );
407429gistdentryinit (giststate ,j ,& entry ,datum ,r ,p ,i ,
408430 FALSE,IsNull );
409431usize = gistpenalty (giststate ,j ,& entry ,IsNull ,
410432& identry [j ],isnull [j ]);
433+ if (usize > 0 )
434+ zero_penalty = false;
411435
412- if (which_grow [j ]< 0 || usize < which_grow [j ])
436+ if (best_penalty [j ]< 0 || usize < best_penalty [j ])
437+ {
438+ /*
439+ * New best penalty for column. Tentatively select this tuple
440+ * as the target, and record the best penalty.Then reset the
441+ * next column's penalty to "unknown" (and indirectly, the
442+ * same for all the ones to its right). This will force us to
443+ * adopt this tuple's penalty values as the best for all the
444+ * remaining columns during subsequent loop iterations.
445+ */
446+ result = i ;
447+ best_penalty [j ]= usize ;
448+
449+ if (j < r -> rd_att -> natts - 1 )
450+ best_penalty [j + 1 ]= -1 ;
451+ }
452+ else if (best_penalty [j ]== usize )
413453{
414- which = i ;
415- which_grow [ j ] = usize ;
416- if ( j < r -> rd_att -> natts - 1 && i == FirstOffsetNumber )
417- which_grow [ j + 1 ] = -1 ;
418- sum_grow += which_grow [ j ];
454+ /*
455+ * The current tuple is exactly as good for this column as the
456+ * best tuple seen so far.The next iteration of this loop
457+ * will compare the next column.
458+ */
419459}
420- else if (which_grow [j ]== usize )
421- sum_grow += usize ;
422460else
423461{
424- sum_grow = 1 ;
462+ /*
463+ * The current tuple is worse for this column than the best
464+ * tuple seen so far. Skip the remaining columns and move on
465+ * to the next tuple, if any.
466+ */
467+ zero_penalty = false;/* so outer loop won't exit */
425468break ;
426469}
427470}
428- }
429471
430- if (which == InvalidOffsetNumber )
431- which = FirstOffsetNumber ;
472+ /*
473+ * If we find a tuple with zero penalty for all columns, there's no
474+ * need to examine remaining tuples; just break out of the loop and
475+ * return it.
476+ */
477+ if (zero_penalty )
478+ break ;
479+ }
432480
433- return which ;
481+ return result ;
434482}
435483
436484/*