Lucene's PulsingCodec on "Primary Key" Fields

Update Aug, 2014: the pulsing approach described here works well and has now been incorporated into Lucene's default postings format, so there's really no need to use PulsingPostingsFormat yourself unless you are using a custom postings format that doesn't do its own pulsing.

Flexible indexing in Lucene (now available on trunk, which will eventually be the next major release, 4.0) enables apps to use custom codecs to write/read the postings (fields, terms, docs, positions, payloads).

By default, Lucene uses the StandardCodec, which writes and reads in nearly the same format as the current stable branch (3.x). Details for a given term are stored in terms dictionary files, while the docs and positions where that term occurs are stored in separate files.

But there is an experimental codec, PulsingCodec, which implements the pulsing optimization described in a paper by Doug Cutting and Jan Pedersen. The idea is to inline the docs/positions/payloads data into the terms dictionary for low frequency terms, so that you save 1 disk seek when retrieving document(s) for that term.

The PulsingCodec wraps another fallback Codec that you provide; this allows the pulsing to be dynamic, per term. For each term, if its frequency (the number of documents that it appears in) is below a threshold (default 1) that you provide, then that term's postings are inlined into the terms dictionary; otherwise, the term is forwarded (pulsed) to the wrapped codec. This means PulsingCodec should be helpful for ordinary text fields which obey Zipf's Law, as many terms will be rare-ish.

PulsingCodec should really shine on "primary key" fields, where each term occurs in exactly one document, and batch lookups (for example because the app performs deletes, updates and/or lookups) are common.

I created a simple performance test to confirm this.

The test first creates an optimized index with 10M docs, where each doc has a single field with a randomly generated unique term, and then performs term -> doc lookup for N (parameter) random terms. It's a self-contained test (source code is here).

It's important to flush your OS's IO cache before running the test; otherwise you can't measure the reduced number of seeks. On recent Linux kernels, just run echo 1 > /proc/sys/vm/drop_caches. That said, in a real production usage, the IO cache will typically (legitimately) help you, and pulsing should make more efficient use of the IO cache since the postings data is contiguously stored.

To measure the speedup from using PulsingCodec on a primary key field, as well as the impact of the OS's IO cache, I ran the above test on an increasing number of random term lookups (always flushing the the OS's IO cache first):



The results are compelling! When performing a small number of term lookups relative to the total number of terms on a cold OS IO cache, which is likely the more common case in a real application, pulsing shows a ~45-50% speedup, as expected, since it requires 1/2 the seeks.

As the number of random term lookups increases, PulsingCodec's gains decrease, because more and more of the lookups are hitting the OS's IO cache and thus avoiding the seek (the machine I ran the test on had plenty of RAM to cache the entire index). It's interesting that PulsingCodec still shows ~15% gain once the lookups are mostly cached; likely this is because PulsingCodec saves the deref cost of finding the postings in the frq file.

Pulsing also makes the index a bit smaller (211 MB vs 231 MB), because it saves one vLong pointer per term. For the test, the index with pulsing had a 0 byte frq file since all postings were inlined into the terms dict. There is no prx file because I index the field with setOmitTermFreqAndPositions(true).

Note that the test case simply uses PulsingCodec for all fields; if you'd like per-field control you should use the PerFieldCodecWrapper. However, because PulsingCodec is dynamic (per term), it is likely a good default for all fields.

Another way to speed up primary key lookups through Lucene is to store your index on a solid-state disk, where seeks are much less costly than they are on spinning magnets (though, still several orders of magnitude more costly than RAM). Or better yet, do both!

Cancer and chemicals

The President's Cancer panel yesterday released their 2008-2009 annual report. It's a long (240 page) report, and what's amazing is that these are mainstream scientists who are now calling for precautionary reduction of our exposure to all sorts of chemicals we are now routinely exposed to.

It has some sobering facts about cancer, such as:

Approximately 41% of Americans will be diagnosed with cancer at some point in their lives, and 21% will die from it.

And:

The incidence of some cancers, including some most common among children, is increasing for unexplained reasons.

This this op-ed pulls out some great highlights from the report. For example, here's a depressing one:

Noting that 300 contaminants have been detected in umbilical cord blood of newborn babies, the study warns that: "to a disturbing extent, babies are born 'pre-polluted.' "

And then there's this quote:

The report blames weak laws, lax enforcement and fragmented authority, as well as the existing regulatory presumption that chemicals are safe unless strong evidence emerges to the contrary.

Congress is now attempting to address this, with the Safe Chemicals Act.

Here is a quote specifically about Bisphenol A:

Studies of BPA have raised alarm bells for decades, and the evidence is still complex and open to debate. That's life: In the real world, regulatory decisions usually must be made with ambiguous and conflicting data. The panel's point is that we should be prudent in such situations, rather than recklessly approving chemicals of uncertain effect.

This is an important point: during the time of uncertainty, when we don't know that a given chemical is dangerous nor do we know that it is safe, we should err on the side of caution, treating the chemical as guilty until proven innocent. I discovered that there is a name for this approach: the precautionary principle, and this is of course the core change to the Safe Chemicals Act.

Here's yet another quote, this time from a brief article about one of the scientists who discovered lead exposure, even in tiny amounts, is very dangerous for kids:

We've been very careless in simply presuming that chemicals are innocent until proven guilty," says Dr. Phillip Landrigan.

Plants and animals use quantum mechanics?

Quantum mechanics, which Einstein once referred to as "spooky action at a distance", is a set of laws that govern how tiny (atomic & sub-atomic) things interact with one another. The laws are very different from classical physics, and really quite surprising, but nevertheless appear to be true (there's been much experimental validation).

Using quantum mechanics, it's possible to build a quantum computer, and indeed many research labs and at least one startup, have built simple ones. Quantum computers can do some amazing things, such as factoring integers very quickly, something classical computers can only do very slowly as the number gets bigger (as best we know, so far).

Most recently, a simplistic quantum computer was used to compute a discrete fourier transform using a single iodine molecule. Someday quantum computers will be all over the place...

But, isn't it possible that plants and animals have evolved to take advantage of quantum mechanics? Indeed there is evidence that we have!

The process of photosynthesis looks to be based on quantum entanglement.

And, one leading theory about how animals can smell so well is based on quantum vibrations. Luca Turin, who created this theory, has a good quote in that article:

Most people would probably feel that if it can be done at all, evolution has managed to make use of it.

And this makes sense - evolution is relentless at trying to find good ways to create plants and animals. Since quantum mechanics is real, evolution should have tapped into it.

This is also the reason I would expect Lamarckian inheritance to in fact be true. Any animal that can alter the traits of its offspring based on experiences in its own lifetime would clearly have a big advantage, so, evolution really should have found a way.

In fact, it sort of did, in a non-biological manner: language. We can pass on all sorts of life lessons to our kids, through language, and we get to stand on the shoulders of past giants, as we take for granted the knowledge created by the generations before us, passed on through language.

Lots of problems these days...

I try to keep my kids roughly informed about what's going on in the world; I think it's important they grow up with at least a basic world view.

Last night, my 7 year old son observed "you know there are alot of problems right now", and he's right! He then rattled off the Iceland volcano eruption, the ruptured water main in our state, forcing us to boil water before drinking it, and the disastrous oil rig explosion and subsequent and ongoing oil geyser.

Concord bans sale of bottled water

Fabulous! The town of Concord, MA has banned the sale of bottled water because of the wretched environmental impact these bottles have.

The environmental cost of such trash is stunning. We know this fills up our landfills, but have you heard of the Great Pacific Garbage Patch? This is one of 5 spots in the oceans where garbage collects and kills marine life.

Of course you really shouldn't drink bottled water in the first place.

Your ideas and your name

I love this quote:

Your ideas will go further if you don't insist on going with them.

It's very true (note that I didn't tell you who said it)!

I find it especially applies to healthy open source projects. In Apache, the individuals (contributors, committers) who work on a given project are fleeting, transient. We will come and go. Our names are not attached to the code we commit.

Sinister search engine de-optimization

There's a large recall going on right now for many popular over-the-counter infant's and children's medicines, such as Motrin, Tylenol, and Zyrtec.

But if you look at the recall details page, posted by the company that manufactures these medicines (McNeil), you'll see that the table is actually a single JPEG image instead of an HTML table. If you don't believe me, try searching in your browser for the words you see in that table!

At first I thought "how strange -- why would they use an image instead of a normal HTML table?". But then a more sinister plot came to mind: perhaps they want to make it as hard as possible for future web searches to find this page. After all, they must now be in major damage control mode. It's the exact opposite problem of the more common search engine optimization.

Hiding text into a JPEG image to avoid searches finding you is a rather nasty practice, in my opinion (hmm, I see there's even this service to help you do it!). Google could prevent such sneakiness by running OCR on the image (perhaps they do this already -- anyone know?), but then I suppose the war would escalate and we'd start seeing barely readable tables like this that look like the dreaded Captcha tests. To workaround such companies, if we all link to this page with some real text (as I've done above) then Google will still find it!

It's also possible there's a more reasonable explanation for this maybe the good old saying "never attribute to malice that which can be adequately explained by something else" somehow applies?

Safe Chemicals Act

Finally, there's been a bill introduced to congress, called the Safe Chemicals Act, to better regulate the chemicals we all are exposed to in day to day products.

The current law (from 1976) is ancient, and assumes any chemical is safe until proven otherwise -- innocent until proven guilty -- a dangerously lax approach which has resulted in the potentially dangerous chemicals we all have heard about, such as bisphenol A in certain plastics, brominated flame retardents, numerous phthalates released by vinyl (this causes that awful new shower curtain smell), etc.

There are 80,000 chemicals in use today and the EPA has only required testing for 200 of them. There are surely additional dangerous chemicals lurking, undetected.

Refreshingly, the new bill takes the opposite approach, the same I approach I take with my family: a chemical is guilty until proven innocent! This is why I use no pesticides on my life support grass.

If this bill becomes law, manufacturers must prove a chemical is safe before they can use it in their products. The burden of proof moves to the manufacturers. Here's a good writeup of the bill.

Lobbyists will undoubtedly fight this bill tooth and nail... so we need to push our congressional representatives!! You can use this site to do so.

Disagreements are healthy!

Another great quote, this time from Henry Ford:

If two people always agree, one if them is unnecessary.

The quote applies very well to open source development -- what makes open source so strong is that such wildly diverse people, with different backgrounds, ideas, approaches, languages, IDEs, interests, itches, sleeping habits, coffee addictions, etc., come together and work on the same problems.

And lots of disagreement ensues.

As long as the resulting discussions are driven by technical merit and not personal attacks (ie, The Apache Way), and consensus is eventually reached, then the disagreements are very powerful.

Serenity, courage and wisdom

I love this quote:

Strive for the serenity to accept the things you cannot change;

courage to change the things you can; and wisdom to know the

difference.

It's the opening to the Serenity Prayer (from the Bible), but I've taken the liberty of replacing God grant with strive for.

The idiom "pick your battles" means the same thing as the 3rd goal.

This great quote from George Bernard Shaw relates closely to the 2nd goal:

The reasonable man adapts himself to the conditions that surround him...

The unreasonable man adapts surrounding conditions to himself...

Therefore, all progress depends on the unreasonable man

Think about these goals. You'll likely find that each goal is distinct, very important, and somewhat surprisingly often applies in your day to day life.

Why do people vote against their own interests?

I found this article very interesting.

The first thing that struck me is its detached tone -- sort of like the curious look a child gives when looking inside a cage at an exotic animal. Probably this was written by someone who lives in Great Brittain, looking over the Atlantic ocean with mild curiosity at how crazy the US health care situation is.

The second thing that struck me is that the observation is very true. A huge majority of the population in this country would benefit from health care reform, including the public option. Those who cannot afford health insurance now, those with pre-existing conditions, etc.

Yet, many people who stand to benefit angrily fight reform. It's just plain weird. Here are two quotes from the article:

• Why are so many American voters enraged by attempts to change a horribly inefficient system that leaves them with premiums they often cannot afford?
  
  
• In Texas, where barely two-thirds of the population have full health insurance and over a fifth of all children have no cover at all, opposition to the legislation is currently running at 87%.

Finally, the two books referenced by the article certainly look relevant, roughly concluding that the average American doesn't really make decisions based on facts. (This also means "trial by a jury of your peers" is not a very comforting approach.) While I haven't read these books, I have come to the same depressing conclusion.

A democracy is only as effective as its population is at making rational decisions.

Why not create a public bank?

Why don't we have a public bank already? I mean a bank run by the federal government that competes with private banks, keeping them honest.

Let's recap what's happened in the past few years. First, the financial world collapsed (the risky sub-prime loans, CDOs, etc.). So, the federal gov't was forced to loan insane amounts of taxpayer's (and our children's future) money to the banks, just to barely keep them afloat. By and large, that worked: the banks have survived and recovered.

Yet, today they still pay out insane bonuses to their top employees, still fly around in private jets, throw lavish parties, travel to exotic places, etc. They are not extending the loans to small businesses that are required for our economy to really recover. And they are now spending lots of money, fighting the legislation that would regulate things to prevent a future collapse from happening again. In short, they have not changed.

Something has gone terribly wrong!

See, these banks don't contribute directly to economic progress. They don't build houses, invent new products, grow food, create more fuel efficient cars, etc. Really they are just the "lubrication" to enable all the real progress in our economy. They are not suposed to make tons of money, yet they do. And they most certainly shouldn't be given the power to hold our economy hostage, as they are today.

So why not create a public bank, run by the federal government, that would extend legitimate loans with reasonable terms, today? This would put a strong competitive pressure on the existing banks to lend, as the public bank would otherwise take customers away. It would be a much more direct way to stimulate the economy, than the "give lots of money to the banks and hope they loan it out instead of paying themselves fat bonuses" approach that is clearly not working very well today.

It could be a temporary creation, only around until the private banks start behaving well again. Or it could remain indefinitely, keeping the banks honest over time.