Mailing-List: contact dev-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@lucene.apache.org
Date: Tue, 22 Nov 2016 17:43:58 +0000 (UTC)
From: "Michael McCandless (JIRA)" <jira@apache.org>
To: dev@lucene.apache.org
Message-ID: <JIRA.13020853.1479229616000.340933.1479836638432@Atlassian.JIRA>
In-Reply-To: <JIRA.13020853.1479229616000@Atlassian.JIRA>
References: <JIRA.13020853.1479229616000@Atlassian.JIRA> <JIRA.13020853.1479229616736@arcas>
Subject: [jira] [Updated] (LUCENE-7563) BKD index should compress unused
 leading bytes
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
archived-at: Tue, 22 Nov 2016 17:44:09 -0000


     [ https://issues.apache.org/jira/browse/LUCENE-7563?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Michael McCandless updated LUCENE-7563:
---------------------------------------
    Attachment: LUCENE-7563.patch

Initial patch, compacting (at indexing time) the long[] leafBlockFPs
and byte[] splitPackedValues in the current BKD index, into a smaller
packed byte[] structure.

I still have a number of nocommits but the core idea seems to be
working ... Lucene's tests pass at least once.

At first I prototyped using an FST to compact the binary tree index,
and it reduced quite a bit, but then I realized even FST has some
annoying inefficiency for this usage, so I made this dedicated packed
byte[] structure instead which compressed even better.

On our nightly 20M NYC taxis benchmark
(https://home.apache.org/~mikemccand/lucenebench/sparseResults.html)
this reduces heap usage by ~60%.

It compresses N>1 dimension too but I haven't tested by how much...

The structure should work very well for apps that e.g. index a short
as if it were a long, prefix-coding away all those leading 0s.  It
takes advantage of how the BKD tree is traversed at search time,
always starting at root and pushing down to children.

Separately, I think we could consider increasing the max leaf block size
from 1024 points to maybe 2048 or 4096 points ... I'll open a new
issue for that.


> BKD index should compress unused leading bytes
> ----------------------------------------------
>
>                 Key: LUCENE-7563
>                 URL: https://issues.apache.org/jira/browse/LUCENE-7563
>             Project: Lucene - Core
>          Issue Type: Improvement
>            Reporter: Michael McCandless
>             Fix For: master (7.0), 6.4
>
>         Attachments: LUCENE-7563.patch
>
>
> Today the BKD (points) in-heap index always uses {{dimensionNumBytes}} per dimension, but if e.g. you are indexing {{LongPoint}} yet only use the bottom two bytes in a given segment, we shouldn't store all those leading 0s in the index.


--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org