perf: lazy operations on sorter by H4ad · Pull Request #434 · oramasearch/orama

H4ad · 2023-07-03T15:42:49Z

Well, instead of sorting every time you insert an item, now it only sort when you need to search, this speedup up the insert by A LOT.

To compare, the following code went from 1m 7s to 1s with this change:

import { create, insert, remove, search } from "./dist/index.js";

(async () => {
  const db = await create({
    schema: {
      name: "string"
    }
  });

  let now = performance.now();
  for (let i = 0; i < 3e4; i++) {
    await insert(db, {
      id: i.toString(),
      name: Math.random().toString(16).substring(8)
    });
  }
  console.log(`insert: ${performance.now() - now}ms`);
  console.log(`memory: ${process.memoryUsage().heapUsed / 1024 / 1024}MB`);
  now = performance.now();

  await search(db, {
    term: 'lll'
  });
  console.log(`search: ${performance.now() - now}ms`);
  now = performance.now();

  for (let i = 0; i < 1e4; i++) {
    await remove(db, i.toString());
  }
  console.log(`remove: ${performance.now() - now}ms`);
  console.log(`memory: ${process.memoryUsage().heapUsed / 1024 / 1024}MB`);
  now = performance.now();

  await search(db, {
    term: 'lll'
  });
  console.log(`search: ${performance.now() - now}ms`);
})();

Before this change:

insert: 49947.061446000356ms
memory: 44.56006622314453MB
search: 1.312158000189811ms
remove: 5246.693398999982ms
memory: 45.88232421875MB
search: 0.10874100029468536ms

Now:

insert: 694.5329680000432ms
memory: 54.184051513671875MB
search: 1.2686470001935959ms
remove: 92.8359210002236ms
memory: 58.10900115966797MB
search: 0.10343399969860911ms

Also, this new change also fix the #348, instead of hours, it took just a minute to run.

/claim #434

vercel · 2023-07-03T15:42:53Z

The latest updates on your projects. Learn more about Vercel for Git ↗︎

Name	Status	Preview	Comments	Updated (UTC)
orama-docs	✅ Ready (Inspect)	Visit Preview	💬 Add feedback	Jul 10, 2023 11:31am

micheleriva · 2023-07-03T15:44:18Z

@H4ad how does this affect search time?

H4ad · 2023-07-03T15:47:51Z

Just add 50~60ms on the first search.

You can also call ensureIsSorted after insert to not affect the search.

Now it probably consumes 99% less time.

micheleriva · 2023-07-03T16:10:47Z

You can also call ensureIsSorted after insert to not affect the search.

Could you please add this as a last function call in insertMultiple?

@allevo maybe we should expose a simple sort function to ensure sorting? Something like:

import { create, insertMultiple, ensureSort } from '@orama/orama'

const db = await create({ ... })

await insertMultiple(db, [...])

await ensureSort(db)

^ super bad DX, written it down not to forget about it

H4ad · 2023-07-03T16:57:05Z

@micheleriva Only worth adding if you know the users never call insertMultiple twice, do you still want to add it?

About the ensureSort, you can add a option during the insert: lazySort, and let it default to true.

ShogunPanda · 2023-07-04T07:41:45Z

The PR looks fine to me in general, even though I don't really like the lazy approach to solve the performance problem.
I'm conflicted on where to put ensureSort.

As @H4ad pointed out, doing it within insertMultiple might make not a lot of sense if is not called iteratively.

If we move the .sorted check from ensurePropertyIsSorted to ensureIsSorted it should probably be fine to call within search.

micheleriva · 2023-07-04T09:00:04Z

What about this:

Add a isSorted boolean property to the Orama instance
Running a function such as ensureSort will set it to true
If isSorted is set to false, the first search operation will call ensureSort
After every new insertion/update, isSorted should route back to false

what do you think?

ShogunPanda · 2023-07-04T09:01:34Z

So we handle this outside of the sorter? Ok, it makes sense to me.

@H4ad Can you please implement the aforementioned changes?

micheleriva · 2023-07-04T09:07:39Z

@H4ad we didn't plan this activity, but we'll reward a small bounty anyway as soon as it lands. Your work is immensely appreciated

micheleriva · 2023-07-04T09:24:18Z

/tip $70

algora-pbc · 2023-07-04T09:24:21Z

👉 @micheleriva: Click here to proceed

H4ad · 2023-07-04T11:33:16Z

As soon as I have time I will implement these changes, probably today.

algora-pbc · 2023-07-04T17:24:25Z

💡 @H4ad submitted a pull request that claims the bounty. You can visit your org dashboard to reward.
👉 @H4ad: To receive payouts, sign up on Algora, link your Github account and connect with Stripe on your dashboard.

H4ad · 2023-07-04T21:22:13Z

@micheleriva I read the suggestions but it doesn't make sense to have the isSorted inside the orama instance.

If I define the isSorted on orama instance, I don't know which property is not sorted since we keep the orderedDocs inside an Record of properties.

Or, I keep the current changes and I also add a property called isSorted, so when I call insert I mark the PropertySort and also the orama instance as isSorted=false, what do you think?

ShogunPanda · 2023-07-05T07:37:06Z

@H4ad The idea is that you don't really remember which properties are sorted and which are not.

It's easier to just assume that when a document is inserted/updated/removed all properties are unsorted. The rationale behind this is that unliked other system Orama is optimized to be used in a two phases: "insert all documents" and then "search" (and the DB in this phase should not be modified anymore).
All heavy duties are done in the inserting phase while the searching phase must be the most lightweight possible.

H4ad · 2023-07-05T11:29:21Z

@ShogunPanda I agree with your design of Orama and this change will not affect that.

Calling ensureSort was just used by the tests, it will not be used by the users because they don't need it.

Doing this approach will just make the search slower since we need to traverse NItems*NProperties, instead of traversing the properties that were modified.

On the optimization side, adding it to orama does not make sense, but if you still want to do that, I will push a commit later this day.

ShogunPanda · 2023-07-05T12:56:58Z

If you don't want to add to Orama, you can add it to the sorter, eventually.

H4ad · 2023-07-05T22:56:46Z

@ShogunPanda Added isSorter to sorter and also I added the properties to be serialized, so we can restore the sorter without needing to sort again.

I also removed the export of ensureSort method, that method is a implementation detail and it should not be required.

H4ad · 2023-07-05T23:36:01Z

I also transform the remove operation into lazy one, before:

insert: 49947.061446000356ms
memory: 44.56006622314453MB
search: 1.312158000189811ms
remove: 5246.693398999982ms
memory: 45.88232421875MB
search: 0.10874100029468536ms

Now:

insert: 694.5329680000432ms
memory: 54.184051513671875MB
search: 1.2686470001935959ms
remove: 92.8359210002236ms
memory: 58.10900115966797MB
search: 0.10343399969860911ms

micheleriva · 2023-07-06T07:16:53Z

packages/orama/src/components/sorter.ts

        sorter.sortablePropertiesWithTypes[path] = type
        sorter.sorts[path] = {
-          docs: {},
+          docs: new Map(),


I fear we can't use maps here as they're not directly serializable to JSON. @allevo, @ShogunPanda please correct me if I'm wrong

yes correct

% node Welcome to Node.js v20.2.0. Type ".help" for more information. > JSON.stringify({ a: new Map() }) '{"a":{}}' > a = new Map() Map(0) {} > a.set('a', 0) Map(1) { 'a' => 0 } > JSON.stringify({ a }) '{"a":{}}' > a Map(1) { 'a' => 0 } >

A custom toJSON function is required here.

It's quite strange that our tests couldn't identify this. We need to fix that sooner or later

I already cover the serialization here: https://github.com/oramasearch/orama/pull/434/files/698be5fbff8958e80fa30b29465c45deca238cf9#diff-7bf96b26edf177621478ee69fd6da1265f94d1ad031a8468084ec5853ed7e35dR265-R277

packages/orama/src/components/sorter.ts

ShogunPanda · 2023-07-07T14:16:13Z

Other than things that @micheleriva outlined, looks good to me.

micheleriva · 2023-07-07T15:07:14Z

Looks good to me. @allevo / @ShogunPanda would you be so kind to test this locally with serialization/deserialization before merging?

ShogunPanda · 2023-07-10T07:41:46Z

@micheleriva I'm currently full on my list. @allevo can probably test this quicker.

allevo

HI! Thanks for your contribution.
I'm checking the code.
Does this change also affect the documentation?

allevo · 2023-07-10T08:47:40Z

packages/orama/src/components/sorter.ts

    return
  }
+
+  sorter.language = language


I don't think we want to support a language change during the insertion: the language remains the same as the DB creation.

This is what Orama does already: https://github.com/oramasearch/orama/blob/main/packages/orama/src/components/sorter.ts#L111

But I change the default to get from tokenizer.

allevo · 2023-07-10T08:59:42Z

Another tip: could you ensure after the insertMany / removeManythe sorting?

H4ad · 2023-07-10T11:31:31Z

@allevo We can do that, but doesn't make sense on the optimization side: #434 (comment)

And this change doesn't change the documentation.

allevo · 2023-07-11T14:53:58Z

LGTM !
And thanks a lot!

allevo

LGTM

micheleriva

LGTM. Amazing job @H4ad

algora-pbc · 2023-07-11T14:55:58Z

@H4ad: You just got a $70 tip! 👉 Complete your Algora onboarding to collect your payment.

algora-pbc · 2023-07-11T16:30:38Z

🎉🎈 @H4ad has been awarded $70! 🎈🎊

H4ad mentioned this pull request Jul 3, 2023

perf: use binary search instead of linear search #431

Closed

vercel bot deployed to Preview July 3, 2023 15:43 View deployment

This was referenced Jul 3, 2023

Disable sort by default #427

Closed

Abnormal memory use #348

Closed

micheleriva added the 💎 Bounty label Jul 4, 2023

H4ad mentioned this pull request Jul 5, 2023

fix: issue with max call stack when search #437

Merged

vercel bot deployed to Preview July 5, 2023 22:50 View deployment

vercel bot deployed to Preview July 5, 2023 22:57 View deployment

H4ad changed the title ~~perf: lazy sort on insert~~ perf: lazy operations on sorter Jul 5, 2023

vercel bot deployed to Preview July 5, 2023 23:34 View deployment

H4ad force-pushed the perf/faster-insert branch from 63c011b to 698be5f Compare July 5, 2023 23:38

vercel bot deployed to Preview July 5, 2023 23:39 View deployment

micheleriva reviewed Jul 6, 2023

View reviewed changes

packages/orama/src/components/sorter.ts Show resolved Hide resolved

micheleriva reviewed Jul 6, 2023

View reviewed changes

packages/orama/src/components/sorter.ts Outdated Show resolved Hide resolved

packages/orama/src/components/sorter.ts Outdated Show resolved Hide resolved

vercel bot deployed to Preview July 6, 2023 11:30 View deployment

H4ad mentioned this pull request Jul 9, 2023

feat: id as number #441

Merged

5 tasks

allevo reviewed Jul 10, 2023

View reviewed changes

H4ad added 6 commits July 10, 2023 08:15

perf: lazy sort on insert

092b768

fixup! perf: lazy sort on insert

9765303

fixup! fixup! perf: lazy sort on insert

ef503e7

perf: lazy remove items on sorter

af4ff22

fixup! perf: lazy remove items on sorter

ece2a31

fixup! perf: lazy remove items on sorter

8bed2bb

H4ad force-pushed the perf/faster-insert branch from 6d4611c to 8bed2bb Compare July 10, 2023 11:31

vercel bot deployed to Preview July 10, 2023 11:31 View deployment

allevo approved these changes Jul 11, 2023

View reviewed changes

micheleriva approved these changes Jul 11, 2023

View reviewed changes

micheleriva merged commit a4b4694 into oramasearch:main Jul 11, 2023

H4ad deleted the perf/faster-insert branch July 11, 2023 15:18

algora-pbc bot added the 💰 Rewarded label Jul 11, 2023

allevo mentioned this pull request Jul 18, 2023

Align documentation after PRs #448

Closed

Uh oh!

Conversation

H4ad commented Jul 3, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

vercel bot commented Jul 3, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

micheleriva commented Jul 3, 2023

Uh oh!

H4ad commented Jul 3, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

micheleriva commented Jul 3, 2023

Uh oh!

H4ad commented Jul 3, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ShogunPanda commented Jul 4, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

micheleriva commented Jul 4, 2023

Uh oh!

ShogunPanda commented Jul 4, 2023

Uh oh!

micheleriva commented Jul 4, 2023

Uh oh!

micheleriva commented Jul 4, 2023

Uh oh!

algora-pbc bot commented Jul 4, 2023

Uh oh!

H4ad commented Jul 4, 2023

Uh oh!

algora-pbc bot commented Jul 4, 2023

Uh oh!

H4ad commented Jul 4, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ShogunPanda commented Jul 5, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

H4ad commented Jul 5, 2023

Uh oh!

ShogunPanda commented Jul 5, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

H4ad commented Jul 5, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

H4ad commented Jul 5, 2023

Uh oh!

micheleriva Jul 6, 2023

Choose a reason for hiding this comment

Uh oh!

allevo Jul 6, 2023

Choose a reason for hiding this comment

Uh oh!

micheleriva Jul 6, 2023

Choose a reason for hiding this comment

Uh oh!

H4ad Jul 6, 2023

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

ShogunPanda commented Jul 7, 2023

Uh oh!

micheleriva commented Jul 7, 2023

Uh oh!

ShogunPanda commented Jul 10, 2023

Uh oh!

allevo left a comment

Choose a reason for hiding this comment

Uh oh!

allevo Jul 10, 2023

Choose a reason for hiding this comment

Uh oh!

H4ad Jul 10, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

H4ad commented Jul 3, 2023 •

edited

Loading

vercel bot commented Jul 3, 2023 •

edited

Loading

H4ad commented Jul 3, 2023 •

edited

Loading

H4ad commented Jul 3, 2023 •

edited

Loading

ShogunPanda commented Jul 4, 2023 •

edited

Loading

H4ad commented Jul 4, 2023 •

edited

Loading

ShogunPanda commented Jul 5, 2023 •

edited

Loading

ShogunPanda commented Jul 5, 2023 •

edited

Loading

H4ad commented Jul 5, 2023 •

edited

Loading

H4ad Jul 10, 2023 •

edited

Loading