On 05/08/2014 02:25 AM, Peter Geoghegan wrote:
> findJsonbValueFromSuperHeader()'s lowbound argument
> previously served to establish a low bound for searching when
> searching for multiple keys (so the second and subsequent
> user-supplied key could skip much of the object).
Got that.
> In the case of
> jsonb_exists_any(), say, if you only have a reasonable expectation
> that about 1 key exists, and that happens to be the last key that the
> user passed to the text[] argument (to the existence/? operator), then
> n - 1 calls to what is now findJsonbValueFromContainer() (which now
> does not accept a lowbound) are wasted.
Check.
> That's elem_count - 1
> top-level binary searches of the entire jsonb. Or elem_count such
> calls rather than 1 call (plus 1 sort of the supplied array) in the
> common case where jsonb_exists_any() will return false.
Ok, but I don't see any big difference in that regard. It still called
findJsonbValueFromContainer() elem_count times, before this commit. Each
call was somewhat cheaper, because the lower bound of the binary search
was initialized to where the previous search ended, but you still had to
perform the search.
> Granted, that might not be that bad right now, given that it's only
> ever (say) elem_count or elem_count - 1 wasted binary searches through
> the *top* level, but that might not always be true.
If we are ever to perform a deep search, I think we'll want to do much
more to optimize that than just keep track of the lower bound. Like,
start an iterator of tree and check for all of the keys in one go.
> And even today,
> sorting a presumably much smaller user-passed lookup array once has to
> be cheaper than searching through the entire jsonb perhaps elem_count
> times per call.
Well, the quick testing I did suggested otherwise. It's not a big
difference, but sorting has all kinds of overhead, like pallocing the
array to sort, copying the elements around etc. For a small array, the
startup cost of sorting trumps the savings in the binary searches.
Possibly the way the sorting was done was not optimal, and you could
reduce the copying and allocations involved in that, but it's hardly
worth the trouble.
- Heikki